'Stones' game complexity

Question

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.

Answer 1

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.