An intuitive explanation of "provably complex combinatorial games"

Question

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.

Answer 1

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$.

Answer 2

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.