<p>It is known that evaluating who wins in <span class="math-container">$n \times n$</span> chess positions is EXP-complete (and thus unconditionally not in P), and this effect is due to the game having rich possibilities for exponentially long mate lines (the proof shows how to emulate TM in chess). But in practice, when people see theoretical &quot;mate in 237&quot;, they usually don't care about the exact number, only that the position has &quot;a very long forced mate&quot;.</p>
<p>Hence my question: what is the complexity of evaluating distance to mate (DTM) <strong>with the 50-move rule</strong>? (constant 50 is arbitrary, I guess it doesn't matter)</p>
<p>Trivial observation 1: no win can take more than polynomial length, so the problem is trivially in PSPACE.</p>
<p>Trivial observation 2: if nobody is allowed to eat more than a constant number of pieces, the problem is trivially in P.</p>
<p>Observation 3 (informal): usually a long forced win is hard only on the first stage of it or two, when no pieces are eaten for very long time, and all subsequent phases are much shorter (due to the already secured increase in advantage), and observation 2 shows that this first stage is easy.</p>

CC BY-SA 4.0
2024-03-16T16:44:44.783Z
The right generalization of the 50-move rule to $n\times n$ boards is likely not any constant number of moves, but something growing with $n$. (I'm not sure of the right order; perhaps $n^2$?)
Emil Jeřábek
CC BY-SA 4.0
2024-03-17T14:22:59.813Z
Yes, I agree, this is probably better (though, for a constant number there is more hope that the problem is easy).
By the way, are there any known endgames which require >n moves? Even KNBvK seems to require only linear number of moves
Alexey Slizkov
CC BY-SA 4.0
2024-03-23T19:28:07.970Z
My guess is this is in $\Pi_{50}^p \cup \Sigma_{50}^p$ Where these are the fiftieth level of the polynomial hierarchy. I think what you are looking for is a definition of the polynomial hierarchy. It is known that PH is contained in PSPACE and thought to be so strictly. See ch3 and exercise 3.6 here: https://www.cs.mcgill.ca/~hatami/comp531-F2022/files/Lectures.pdf
abrahimladha
<turing-machines><complexity><pspace><board-games>
Complexity of chess with 50-move rule
Alexey Slizkov
# Complexity of chess with 50-move rule

(Asked by: username_0 on 2024-03-16)

It is known that evaluating who wins in $n \times n$ chess positions is EXP-complete (and thus unconditionally not in P), and this effect is due to the game having rich possibilities for exponentially long mate lines (the proof shows how to emulate TM in chess). But in practice, when people see theoretical "mate in 237", they usually don't care about the exact number, only that the position has "a very long forced mate".

Hence my question: what is the complexity of evaluating distance to mate (DTM) **with the 50-move rule**? (constant 50 is arbitrary, I guess it doesn't matter)

Trivial observation 1: no win can take more than polynomial length, so the problem is trivially in PSPACE.

Trivial observation 2: if nobody is allowed to eat more than a constant number of pieces, the problem is trivially in P.

Observation 3 (informal): usually a long forced win is hard only on the first stage of it or two, when no pieces are eaten for very long time, and all subsequent phases are much shorter (due to the already secured increase in advantage), and observation 2 shows that this first stage is easy.

**Tags:** turing-machines, complexity, pspace, board-games

> **Comments:**
> **username_1**: The right generalization of the 50-move rule to $n\times n$ boards is likely not any constant number of moves, but something growing with $n$. (I'm not sure of the right order; perhaps $n^2$?)  
> **username_0**: Yes, I agree, this is probably better (though, for a constant number there is more hope that the problem is easy). By the way, are there any known endgames which require >n moves? Even KNBvK seems to require only linear number of moves  
> **username_2**: My guess is this is in $\Pi_{50}^p \cup \Sigma_{50}^p$ Where these are the fiftieth level of the polynomial hierarchy. I think what you are looking for is a definition of the polynomial hierarchy. It is known that PH is contained in PSPACE and thought to be so strictly. See ch3 and exercise 3.6 here: https://www.cs.mcgill.ca/~hatami/comp531-F2022/files/Lectures.pdf  

---

## 0 answers

