Wolfgang Slany

We consider combinatorial avoidance and achievement games

based on graph Ramsey theory: The players take turns in coloring

still uncolored edges of a graph G, each player being assigned a

distinct color, choosing one edge per move. In avoidance games,

completing a monochromatic subgraph isomorphic to ...
more >>>

Rahul Mehta

We prove that a variant of 2048, a popular online puzzle game, is PSPACE-Complete. Our hardness result

holds for a version of the problem where the player has oracle access to the computer player's moves.

Specifically, we show that for an $n \times n$ game board $G$, computing a

more >>>

Greg Bodwin, Ofer Grossman

In many combinatorial games, one can prove that the first player wins under best play using a simple but non-constructive argument called strategy-stealing.

This work is about the complexity behind these proofs: how hard is it to actually find a winning move in a game, when you know by strategy-stealing ...
more >>>

Dmitry Itsykson, Alexander Okhotin, Vsevolod Oparin

The partial string avoidability problem is stated as follows: given a finite set of strings with possible ``holes'' (wildcard symbols), determine whether there exists a two-sided infinite string containing no substrings from this set, assuming that a hole matches every symbol. The problem is known to be NP-hard and in ... more >>>