1
$\begingroup$

It is very surprising to me that some combinatorial games such as generalized chess are EXPTIME complete. I have no idea why having a solver for a combinatorial game allows you to solve arbitrary exponential problems. The reason is that while I understand that such games can be solved in exponential time, they seem to me to be a quite specific exptime problem, and I cannot see how exptime problems that are unrelated to games would be reducible to them (whereas the fact that CSAT, SAT, 3SAT etc are NP-complete is much more clear to me).

In particular I would like to see a "direct" proof, where arbitrary exptime problems are encoded as instances of some combinatorial game. Hence I tried to read the original paper "Provably Difficult Combinatorial Games" by Stockmeyer and Chandra. However it is quite dense. It would be helpful if there is an intuitive simple (possibly a bit handwavy) description of a reduction of arbitrary EXPTIME problems to a combinatorial games.

EDIT: It would suffice to give a simple description of the reduction of "does DTM M halt in k steps?" to such a combinatorial game, as pointed out in the comments. That this is possible is equally surprising to me as the original problem

EDIT 2: Just to give a sense of what I find surprising about this: I would have guessed that such games are at best PH-Complete, since a game essentially checks a question of the form $\forall x_1,\exists y_1, \forall x_2 ....Win(x_1,y_1,...y_k)$. This is the whole point of game semantics.

$\endgroup$
5
  • $\begingroup$ Note that the problem "Does DTM $M$ halt in $k$ steps?" is EXPTIME-complete. Try reducing this to one of your games and you are done, because encoding another EXPTIME problem as the first problem is usually pretty simple. $\endgroup$
    – plshelp
    Jul 12, 2022 at 0:35
  • $\begingroup$ @plshelp, yes this does actually make it easier, but it seems like the main difficulty of the problem is still there. $\endgroup$
    – user56834
    Jul 12, 2022 at 5:25
  • $\begingroup$ The original paper by Fraenkel and Lichtenstein seems pretty readable. What would you like to see that isn't provided there? $\endgroup$ Jul 15, 2022 at 14:48
  • $\begingroup$ @reinierpost, a shorter intuitive explanation of how the reduction works that isnt spread out over multiple lemmas and definitions (and maybe as a result isnt as rigorous, if necessary). $\endgroup$
    – user56834
    Jul 17, 2022 at 5:26
  • $\begingroup$ (Note I didn't find it readable enough possibly due to the complexity needed to prove everthing precisely) $\endgroup$
    – user56834
    Jul 17, 2022 at 6:47

2 Answers 2

4
+250
$\begingroup$

As you already see, the essence of the two-player games is alternation. The class of languages recognized by an alternating Turing machine in polynomial time $\mathrm{APTIME}$ is equivalent to the $\mathrm{PSPACE}$, the class of languages recognized by a polynomial-space Turing machine.

The $\mathrm{APTIME}$ class corresponds to games that can only last for a polynomial number of turns. This restriction is valid for permanent token-placing games such as Hex or M,n,k-game (a generalization of tic-tac-toe).

However, other games such as Checkers or generalized chess can last for an exponential number of non-repeating turns. Therefore, it is more appropriate to use $\mathrm{APSPACE}$, the class of languages recognized by an alternating Turing machine using polynomial space.

Now, the question is how to prove $\mathrm{APSPACE}$ is equivalent to $\mathrm{EXPTIME}$, the class of languages recognized by a deterministic Turing machine in exponential time. The direction $\mathrm{APSPACE} \subseteq \mathrm{EXPTIME}$ can be shown by a brute-force search algorithm. For the other direction, given a deterministic Turing machine $M$ and an input $I$, define propositions:

  • $P^1_t(i,q)$: "at step $t$, the head of the Turing machine is position $i$ and the internal state is $q$".
  • $P^2_t(i,a)$: "at step $t$, the content of the tape cell $i$ is alphabet $a$".

Then, it is $\mathrm{EXPTIME}$-hard to determine $P^1_t(0,q_f)$ given the terminating state $q_f$ and time $t$ encoded in binary.

Now, we can show that the propositions $P^1_t$s and $P^2_t$s can be represented by a Boolean formula, where leaves of the formula are $P^1_{t-1}$s and $P^2_{t-1}$s. Namely, for $t > 0$, $$ \begin{align} P^2_t(i,a) \iff & P^2_{t-1}(i,a) \land \not \exists q, P^1_{t-1}(i,q) \\ \lor & \exists b, P^2_{t-1}(i,b) \land \exists q, P^1_{t-1}(i,q) \land \delta(q,b) = a \end{align} $$

where $\delta(q, a)$ is the symbol written to the cell after the transition of the Turing machine with the internal state $q$ and the cell alphabet $a$. The formula for $P^1_t$ is left to readers.

Furthermore, this Boolean formula can be constructed in $O(\mathrm{poly}(|M| + |I| + \log i))$ time. Therefore, the proposition $P^1_t(0,q_f)$ can be determined by an alternative Turing machine using $O(\mathrm{poly}(|M| + |I| + \log t))$ space by using the formulae recursively, concluding $\mathrm{APSPACE} = \mathrm{EXPTIME} \; \Box$.

$\endgroup$
3
  • $\begingroup$ "Therefore, it is more appropriate to use APSPACE". If you can argue (even informally, but conveying the key idea) that generalized chess or some other game is APSPACE-complete, then I will award the bounty. $\endgroup$
    – user56834
    Jul 18, 2022 at 16:55
  • $\begingroup$ Btw, side-question, does the original paper use this equivalence between APSPACE and EXPTIME? $\endgroup$
    – user56834
    Jul 18, 2022 at 16:55
  • $\begingroup$ The current answer is a proof of (weaker) Theorem 3.4 in Chandra, A. K., & Stockmeyer, L. J. "Alternation". "Provably Difficult Combinatorial Games" paper is based on this result and provides a more "easy-to-reduce" EXPTIME-complete game. $\endgroup$
    – pcpthm
    Jul 19, 2022 at 2:36
0
$\begingroup$

Let me put a few ideas about the chess, to start from:

  • The main course of any game is to win. So assuming that both players will do best to prevent win or loose is against the logic of game and asks different question. What will be the complexity of not getting winner? instead of Complexity of winning?
  • Since chess players have a goal to win, the next thinking step is define what does this means. Specifically in chess this means winning material (take figures). And material is a target for your algorithm.
  • So eventually chess algorithm will be focused on winning material (not the game itself, taking figures one by one based on priority) - winning the game is consequence of winning material
  • As a result of that the move of a figure is decision tree, where you can through many leaf's without analysing since they have same outcomes (useless moves no hits, or same positions after a course of 5-6 moves) do the best choice. You still get a lot, and as more steps you analyse as more combinations you have, and each next will include previous. Let's have a look practically: 1 move will be for ex 20 combinations, respond similarity 20, and the next one ~30. We should be able to see that number of moves have direct dependency on number of empty spaces on the board and figure capabilities (task have limits and those are clear).

So the task is polynomial-time many-one reduction, because estimation of complexity of each next move will include estimation of complexity of previous move. Since instead of re-evaluation, you can reuse (i.e transform).

Now let's analyse reverse question, making sure that nobody wins - in the same way we can consider that both players will make sure that targets/materials are not hit, with all consequences.

Hope that helps :)

PS: I skipped chess tactic for simplicity.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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