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.]
Best Answer
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".
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.