5
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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". $\endgroup$ – Hendrik Jan Jun 1 '13 at 9:01
  • $\begingroup$ 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$)? $\endgroup$ – Vor Jun 1 '13 at 22:51
  • $\begingroup$ @Vor: stone from y is not removed. Reversible moves can be allowed (but don't have to). $\endgroup$ – warran Jun 1 '13 at 23:18
  • 1
    $\begingroup$ @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 :-) $\endgroup$ – Vor Jun 1 '13 at 23:41
  • 1
    $\begingroup$ 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) ;) $\endgroup$ – warran Jul 3 '14 at 22:47
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.