Two-person Pebble Game Fixed Rank (PEBBLE)

Input

A fixed rank pebble game $G = (X, R, S, t)$.

Problem

Does player $P_1$ have a winning strategy?

Definitions

A pebble game $G = (X, R, S, t)$ has the following properties:

1. $X$ is a finite set of vertices.
2. $R \subseteq \{(x, y, z) \mid x, y, z \in X, x \neq y, y \neq z, z \neq x\}$ is called the set of rules. For $A, B \subseteq X$, we write $A \vdash B$ if $(x, y, z) \in R$, $x, y \in A$, $z \notin A$, and $B = (A \setminus \{x\}) \cup \{z\}$. The move $A \vdash B$ is made by the rule $(x, y, z)$. The symbol $\vdash^\ast$ denotes the reflexive and transitive closure of $\vdash$.
3. $S$ is a subset of $X$.
4. $t \in X$ is the terminal vertex.

A pebble game has fixed rank if the number of vertices in $S$ is fixed. In a two-person pebble game two players $P_1$ and $P_2$ alternate moving pebbles with $P_1$ moving first. The winner is the first player who can pebble $t$ or who can force the other player into a no move situation.

Status

$\P$-complete (Kasai, Adachi, and Iwata [1]).

Remarks

The reduction to show hardness is from a logarithmic space bounded alternating Turing machine.

A pebble game is solvable if there exists $A \subseteq X$ such that $S \vdash^\ast A$ and $t \in A$. The one-person pebble game, which is to determine if the game is solvable, of fixed ranked is $\mathsf{NLOG}$-complete [1]. For questions with a similar flavor see GAME and CM. For additional remarks about pebbling see [2, Section 5.4].