# Why is this proof that CHESS is in EXPTIME correct?

I've been reading the following paper (open) by Fraenkel and Lichtenstein that shows that the Generalized $$n \times n$$ Chess problem ($$\texttt{CHESS}$$) is $$\texttt{EXPTIME-complete}$$. They start by proving that $$\texttt{CHESS}$$ is in $$\texttt{EXPTIME}$$, but I don't understand at all the fragment highlighted in pink (the final implication).

I understand how they derived that the maximum possible number of configurations is bounded by an exponential, however I don't immediately see why that would imply that there exists an algorithm with time complexity $$O(2^{p(n)})$$ where $$p(n)$$ is a polynomial.

The algorithm I assume would be similar to a MiniMax algorithm, traversing the entire game-tree of $$\texttt{CHESS}$$. We can also say that if in a branch black can force the same configuration (and turn of play) to reappear, then it's an immediate draw (because white must do better than an infinite loop).

However, since in different branches the same configuration can reappear, wouldn't this be a time complexity $$n^n$$, worse than exponential?

Whats exactly the algorithm or catch that I'm missing?

IMAGE TRANSCRIPT:

Let $$Q$$ be the following question: Given an arbitrary position of a generalized chess game on an $$n \times n$$ cheessboard from our class of chess games, can White (Blacn) win from that position? We define Exptime to be the set of all decision problems with time complexity bounded above by $$2^{p(n)}$$ for some polynomial $$p$$ of the input size $$n$$. Since in chess there are six distinct pieces of each color, the number of configurations in $$n\times n$$ chess is bounded above by $$13^{n^2}$$, hence $$Q \in$$ Exptime.

If you keep track of previous computation, then the same configuration appearing multiple times would not require multiple computations.

That means that a Min-Max algorithm would require a time complexity linear in the number of configurations times the number of possible moves for a given configuration. This is indeed exponential in $$n$$.

• I get it. So basically we should use the Min-Max algorithm with a dynamic programming approach, correct? Commented Mar 9, 2023 at 18:39
• Yes that's it: this is all about smart recursion. Commented Mar 9, 2023 at 18:42
• @alexland7219 It doesn't say what algorithm you should use, it just says there is one that takes exponential time or less, which is obvious from the fact there are an exponential number of configurations. Note that being in EXPTIME doesn't mean it isn't also in a smaller, faster group as well. For example, all problems in P or NP are also in EXPTIME. Commented Mar 10, 2023 at 14:13