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

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