Do there exist chess positions that require exponentially many moves to reach? - MathOverflow

Do there exist chess positions that require exponentially many moves to reach?

2010-06-12T16:39:43Z

By "chess" here I mean chess played on an $n\times n$ board with an unbounded number of (non-king) pieces. Some care is needed if you want to generalize some of the subtler rules of chess to an $n\times n$ board, but I will not dwell on this point because the answer to the question I'm interested in should be the same under any reasonable generalization. Namely, does there exist an infinite sequence $(A_n, B_n)$ of pairs of chess positions on an $n\times n$ board such that the minimum number of legal moves required to get from $A_n$ to $B_n$ is exponential in $n$? Here I allow any legal moves and not only strategically intelligent moves.

Technically this question might be classified as an "open problem" (which is illegal on MO) because it was implicitly asked by A. Fraenkel and D. Lichtenstein in "Computing a perfect strategy for $n\times n$ chess requires time exponential in $n$," J. Comb. Th. A 31 (1981), 199–214. However, I think it is fair game for MO because I'm pretty confident that this has not been looked at much. Fraenkel and Liechtenstein showed that determining whether a given chess position is won for White (with best play) is EXPTIME-complete and asked for the computational complexity of the chess reachability problem ("is $B_n$ reachable from $A_n$?"). Clearly chess reachability is in NPSPACE = PSPACE, and Hans Bodlaender has shown that it is NP-hard. If the answer to the question I've posed above is "No, it can always be done with polynomially many moves" then it would solve this problem by showing that chess reachability is NP-complete, because exhibiting the sequence of moves yields a short certificate.

If you have some experience with retrograde chess problems and if you've read Hearn and Demaine's lovely book Games, Puzzles, and Computation then you may get the intuition that shuffling chess pieces around is reminiscent of other rearrangement puzzles that have been shown to be PSPACE-complete. However, I've asked both Demaine and Hearn and neither of them saw immediately how to show that chess reachability is PSPACE-complete.

[Edit: Searching more carefully through Hearn and Demaine's book, I see that they list this problem in their list of open problems at the end of the book under the name "Retrograde Chess." I didn't notice it before because for some reason that page is not listed in the index under "chess." I can perhaps be blamed for using the name "Retrograde Chess" for this problem because that's what I called it when I first posted this question to USENET way back when. I think that "reachability" is a better name for it.]

Answer by Zirui Wang for Do there exist chess positions that require exponentially many moves to reach?

2010-06-12T17:30:25Z

If reachability is in PSPACE, then it's in NP because during the search once you reach the target you can immediately stop, without backtracking results. Unlikely Othello, in which a configuration requires children configurations to return a value, reachability can be done with non-deterministic machine. It doesn't require keeping the list of visited configurations. You can forget them immediately. If you still don't understand what I'm saying, contrast the difference between Othello evaluation and reachability.

P.S. The exponential-length possibility is ruled out since it's in PSPACE. Otherwise PSPACE is not enough to store the current path. Here you need to store the path because PSPACE machines are not non-deterministic (or branching), hence it has to backtrack.

Answer by Jirka Hanika for Do there exist chess positions that require exponentially many moves to reach?

2012-02-18T23:52:51Z

I think that you deserve at least a partial answer to your partial question.

You are taking a great leap when not specifying the generalized rules, including the fifty-move rule.

If this rule stays as it is in chess (50), or generalizes to a polynomial of your choice (bounded by $O(n^k)$ for a fixed $k$), then the answer to your question is "No", aside from the possibility of completely unreachable pairs of positions. An upper limit on the length of any legal sequence of moves is $O(n^{k+3})$, given that you allow at most $n^2$ pieces per player and that each piece can contribute less than $n$ pawn moves.

Answer by JHI for Do there exist chess positions that require exponentially many moves to reach?

2013-04-04T08:41:03Z

With n/100 black kings, one white king, its possible.

The idea is to make a "switch", a room which is in one of two states, has 1 entrance, e, and 2 exits; x and y, the white king enters the room through a tunnel of pawns, if its in state 1, it must exit through x, while switching the state of the room to 0, in state 0 it must exit through y leaving the room in state 1.

With k switches labeled 1 to k, connect all the x_i with e_1, and y_j to e_(j+1) for all j. Start it with king in e_1=x_i, and all switches at 0, to turn the last switch on youll see that you need to transition thorugh all possible states, giving a minimum 2^k moves.

The switch really needs a diagram, but the idea is to have a black king for each switch, the black king will block a black rook preventing check, so the white king can get to a next room, where it will block a white rook, so that the black king can get to a third room, blocking a black rook, having the white king exit, the black king cant go back without the white king, but it can continue to the black entrance of a second such sequence of rooms, the black exit of which is connected to the black entrance of this sequence. The two white entrances are connected, and the two white exits are x and y. So the black king is in one of two tunnels, corresponding to the states 0/1, which determines which exit is available for the white king.

There might be some way to construct the switches without kings aswell.

There should be a row of pawns below and above the diagram of the switch component.
Couple 4 of these of each color to make 1 switch.