52
$\begingroup$

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

$\endgroup$
9
  • 1
    $\begingroup$ The retros mailing list has discussed record-length retroanalysis problems on a normal chessboard in the past; exploring those might offer ideas at least - see pairlist.net/pipermail/retros for the archives of the mailing list. I think the primary impediment is usually dodging the 50-move rule, and in any case proofs are likely to be simpler if you throw that one out. $\endgroup$ Jun 12, 2010 at 16:59
  • 19
    $\begingroup$ Open problems are not illegal in MO; rather they are appropriate with certain limitations. You have to accept the current status of a problem as the "answer" to the MO posting, even if it doesn't answer the problem. If you happen to already know that status, then you're not really asking a question. If a problem, like this one, doesn't have a clear-cut status, then in my view the posting is fine. $\endgroup$ Jun 12, 2010 at 17:01
  • 1
    $\begingroup$ @Zsban: Othello, GoMoku, Amazons. Via Hearn & Demaine, most 2-person games with a bounded number of moves. $\endgroup$ Jun 12, 2010 at 18:50
  • 3
    $\begingroup$ If the only allowed pieces are queens and rooks, I believe the answer is no because in any configuration with at least one empty square it is possible to swap two adjacent pieces in poly(n) time and any other permutation can be built from poly(n) adjacent swaps. Still thinking about knights pawns and bishops. $\endgroup$ Aug 18, 2010 at 5:50
  • 2
    $\begingroup$ @mmm: Could you please elaborate? $\endgroup$ Mar 2, 2012 at 14:53

4 Answers 4

17
$\begingroup$

Here is a summary of solution proposed in this arXiv paper. A pair of positions on the $n\times n$ chessboard is constructed for which (1) there is a sequence $\sigma$ of legal chess moves leading from $P$ to $P'$; (2) the length of $\sigma$ cannot be less than $\exp\Theta(n)$.

The idea is to construct a position which consists essentially of $m$ tracks each of which is in some state in every moment. The set of possible states of $i$th track is a cycle group of order equal to $(i+3)$rd prime, and the position is defined uniquely by states of all tracks. A "move" increases every state by $1$ or decreases every state by $1$. Transforming $(0,0,\ldots,0)$ to $(1,0,\ldots,0)$ is possible by Chinese remainders but requires at least $p_5\ldots p_{m}=\exp(p_m+o(p_m))$ "moves".


  (source)


The chess positions representing tracks use the above pattern, which is a specific example corresponding to $m=3$. The dots denote pawns, and we assume that the kings are located somewhere else on the board. In the paper it is explained (in different terms) why we can think of dark cycles as tracks, the positions of white bishops on them as states, and "moves" as minimal sequences of legal chess moves whose initial and resulting positions coincide up to a color of pieces.

$\endgroup$
0
8
$\begingroup$

With $n/100$ black kings and one white king, it's 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 you'll see that you need to transition through all possible states, giving a minimum of $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 can't 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 as well.

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.

enter image description here

$\endgroup$
1
  • 1
    $\begingroup$ This looks like a good start; in particular if the switches work as advertised then I agree that this should solve the problem. However, without some further details, I'm not yet convinced. For example, it seems you must somehow prevent the rooks from moving around and destroying the intended functionality of the switches. Also, having multiple kings, none of which is allowed to be in check at any time, seems like an inelegant generalization of chess. But I'm not too worried about this detail for now. $\endgroup$ Apr 4, 2013 at 20:27
2
$\begingroup$

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.

$\endgroup$
3
  • 3
    $\begingroup$ I disagree that chess is more rarely studied the context of complexity than any other board game. The Fraenkel-Liechtenstein paper shows that generalized chess is EXPTIME-complete. I also disagree that the generalizations are artificial. I'd even argue that the 50-move rule, the castling rule, the en passant rule, the dead reckoning rule, the stalemate rule, the promotion rule, and even the checkmate rule (i.e., checkmate and not the capture of the king ends the game) are the artificialities that are introduced for practical reasons. Eliminating them yields the most natural generalization. $\endgroup$ Feb 20, 2012 at 18:51
  • 2
    $\begingroup$ @Timothy Chow - Consider editing your question to list the most natural rules. Details matter when attempting reductions. @Dan Brumleve - Pawns get quite interesting as you can form almost arbitrary "mazes" out of them (same maze in both positions) which forces all the other pieces to only move inside those. The pawns themselves cannot rearrange because there would be no way to get them back into positions (well, depending on their behavior on the last row). $\endgroup$ Feb 22, 2012 at 10:16
  • $\begingroup$ The answer originally included an unhelpful remark based on an interpretation of a statement in the Fraenkel-Lichtenstein paper, I have now deleted it. $\endgroup$ Mar 1, 2012 at 22:57
-6
$\begingroup$

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.

$\endgroup$
7
  • 3
    $\begingroup$ “PSPACE machines are not non-deterministic”: you can also take them to be nondeterministic if you need it, since polynomial-space NDTMs also characterise PSPACE (it’s an immediate corollary of Savitch’s theorem). $\endgroup$ Jun 12, 2010 at 20:54
  • 4
    $\begingroup$ @Zirui: I don't think your argument is correct. As Antonio points out, Savitch's theorem tells us that PSPACE = NPSPACE. All the Rush-Hour-type puzzles are obviously in NPSPACE because you can just guess the solution and move the pieces accordingly. Therefore they are in PSPACE. But we can't conclude that they are in NP; in fact they are PSPACE-complete. $\endgroup$ Jun 12, 2010 at 22:25
  • $\begingroup$ My argument is like this: 1) reachability is in PSPACE. This implies no exponential path exists. 2) reachability does not require backtracking. Therefore it's in NP. QED Two points: a) Whether PSPACE = NPSPACE or not is not relevant to my argument at all. b) If "Rush-Hour-type" puzzles are PSPACE-complete, then they require backtracking because Othello is in PSPACE and requires backtracking. $\endgroup$
    – Zirui Wang
    Jun 20, 2010 at 7:41
  • 9
    $\begingroup$ @Zirui: No, your argument is not correct. The fact that reachability is in PSPACE does not imply that no exponential path exists. Rush-Hour-type puzzles are reachability problems in PSPACE for which exponential paths exist. Furthermore, your analogy with Othello is flawed because what is in PSPACE is determining whether a winning strategy exists, which is not a reachability problem. $\endgroup$ Jun 28, 2010 at 16:18
  • 4
    $\begingroup$ @Zirui Wang: It is possible to decide reachability without storing the whole path, which is the key point to prove PSPACE=NPSPACE (Savitch’s theorem). $\endgroup$ Aug 23, 2010 at 12:33

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.