# 'Stones' game complexity

I'm trying to find complexity class of finding winning strategy for first player in following game:

Intance of 'Stones' game is:

• finite set $X$
• relation $R \subseteq X^3$
• set $Y \subseteq X$ and node $f \in X$

At the beggining we place stone in every element of $Y$. Every player in his turn can move stone from $x$ to $z$ iff. $\exists y.R(x, y, z) \wedge y\ has\ stone\ placed\ in\ it$. Player who places stone in $f$ wins.

I think it's $PSPACE-complete$, but I was trying to proove this for some time, and I run out of ideas.

I won't lie, it's homework assignment for my complexity class. Any help will be highly appreciated.

• It looks like a Pebble Game, in particular it is very similar to the last one mentioned in the wikipedia page: "pebble may be moved along an edge-arrow to an unoccupied vertex only if a second pebble is located at a third, control vertex". – Hendrik Jan Jun 1 '13 at 9:01
• Once the stone has moved from x to z, is y removed? If not, are reversible moves allowed (i.e. $(x,y,z), (z,y,x)$ both contained in $R$)? – Vor Jun 1 '13 at 22:51
• @Vor: stone from y is not removed. Reversible moves can be allowed (but don't have to). – warran Jun 1 '13 at 23:18
• @warran: ok, you can easily prove that it is PSPACE-hard building a reduction from generalized geography which is PSPACE-complete ... obviously you must think of a way to "convert" the ending condition of GG (no more moves) to the ending condition of your game (a stone in f) ... but you can use a (separate) gadget containing f in which the first player forced to move on it loses ... try if you can figure out the whole reduction, otherwise I'll give you more hints :-) – Vor Jun 1 '13 at 23:41
• Following @HendrikJan hint, I've found that this problem was studied by Kasai, Adachi and Iwata and was proven to be EXP-complete. Look for the proof in SICOMP 8 (4) ;) – warran Jul 3 '14 at 22:47

The game is actually an instance of two-persons Pebble game, as @HendrikJan pointed out, and as such is proven to be $EXPTIME-complete$. The following is a summary based on a proof by Kasai, Adachi and Iwata in SICOMP 8 (4).

For starters, it's pretty obvious that the game is in $EXPTIME$ - we can simply check all the possible games and see if there is winning strategy. To proove it's $EXPTIME-hard$ is a little bit more challenging.

First we need to know the notion of Alternating Turing machines (or ATMs for short). We will further tighten the definition to get so-called standard ATM:

We say an ATM $M$ is standard if

1. $M$ has only one work tape with the head initialized to the first cell of the tape,
2. if a configuration $C$ of $M$ is existential (universal), then every configuration $C’ \in Next_M(C)$ is universal (existential),
3. the initial state is existential and the accepting state is universal, and
4. $Next_M(C) = \emptyset$ if and only if $C$ is an accepting configuration.

Where $Next_M(C)$ deontes set of possible configurations after one move starting from configuration $C$

Now there come two important lemmas proven by Chandra, Kozen and Stockmayer in Journal of the ACM 28(1):

Lemma 1

For every $S(n) \geq log (n)$, if $L \in ASPACE(S(n))$, then $L$ is accepted by a standard ATM within space $S(n)$.

Lemma 2

$EXPTIME = APSPACE$

Having those two in mind, we now see that, given a standard ATM $M = (Q, \Sigma, \Gamma, \delta, b, q_1, q_a, U)$ such that only $p(n)$ cells are available on the work tape for some polynomial $p$ in $n$, and a word $w = w_1 w_2 ... w_n$, we need to construct, in logarythmic space, an instance of pebbles game $G$ such, that $w$ is accepted by $M$ iff. first player has winning strategy in $G$.

In order to do that we will need

1. set of fields $X$ consisting of

• fields representing the state of working tape ($\{1..p(n)\} \times \Gamma$)
• fields representing current state of machine and it's heads ($Q \times \{1..n\} \times \{1..p(n)\}$)
• fields representing work tape transitions ($Q \times \{1..n\} \times \{1..p(n)\} \times \Gamma^2)$
• three additional fields $s_1, s_2, t$ to ensure that correct player wins the game
2. Set $R$ of rules that translates $\delta$ into our game:

• For each element of $Q \times \{1..n\} \times \{1..p(n)\}$ if $\delta (q, w_i, a)$ contains $(q', a', (d', d'')), a \neq a'$ then this transition can be encoded with the following rules:
• $([q, i, l], [l, a], [q, i, l, a, a'])$
• $([l, a], [q, i, l, a, a'], [l, a'])$
• $([q, i, l, a, a'], [l, a'], [q, i+d', l+d''])$
• For each element of $Q \times \{1..n\} \times \{1..p(n)\}$ if $\delta (q, w_i, a)$ contains $(q', a, (d', d''))$ we need just one rule:
• $([q, i, l], [l, a], [q, i+d', l+d''])$
• Finally we need to have "game finishers" rules:
• for each $i$ and $l$ there should be rule $([q_a, i, l], s_1, s_2)$
• we also add rule $(s_2, s_1, t)$
3. And to start the game properly we need the set $S = \{[q_1,1,1],s_1\} \cup \{[l,b] | 1 \leq l \leq p(n)\}$, which denotes that we're in initiall state, both heads are at the beggining of the tapes, and the working tape is empty.

From this, the proof of the fact that $w$ is accepted by $M$ iff. first player has a winning strategy in $G$ should be pretty straightforward.