2
$\begingroup$

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.

enter image description here

$\endgroup$

1 Answer 1

0
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ I get it. So basically we should use the Min-Max algorithm with a dynamic programming approach, correct? $\endgroup$ Mar 9, 2023 at 18:39
  • $\begingroup$ Yes that's it: this is all about smart recursion. $\endgroup$
    – Nathaniel
    Mar 9, 2023 at 18:42
  • $\begingroup$ @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. $\endgroup$
    – user253751
    Mar 10, 2023 at 14:13

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.