Irreversible chess - MathOverflow

Irreversible chess

2011-10-22T12:59:06Z

Suppose we play a chess-variant, where any finite number of pieces are allowed, and the board is as large as we wish, but only two kings in total. And there is no 50 move-rule, no castling and no captures and no pawn-moves.

Then is it possible to have a a pair of positions A and B, such that we can go from configuration A to B by legal moves, but not from B to A?

No stalemates or checkmates allowed, the game must be extendable atleast two moves in both direction from both A and B.

Two configurations are different also if the pieces are in the same places but it is a different player to move.

Answer by Hauke Reddmann for Irreversible chess

2011-10-22T14:18:29Z

Don't you have to rule out pawn checks as well? A trivial example would be Ka6 Pb7 - Ka8. (A) Black plays Kb8. (B). Clearly there is no way back from B to A. The pawn moved only in retroanalysis :-)

I could forward your question to MatPlus forum. If anyone knows, they will.

Answer by Ed Dean for Irreversible chess

2011-10-22T15:33:25Z

According to the rules you have set up, I believe that the following positions A and B give what you are after (even once Hauke's good point that pawn checks shouldn't be allowed is taken into account). In position A, it is black to move, and position B can be reached via 1. ... Bd8+ 2. Ne7++ Kc7. But from there, according to the rules you laid out, white's only moves are to shuffle the bishop between c6-d5-e4 (EDIT: and d7 and e8 too of course, thanks Noam), and black can only play around with the rook on h8.

Position A

Position B

Answer by Noam D. Elkies for Irreversible chess

2011-10-22T18:50:20Z

[Edited to include some 8-unit variations and a new 7-unit setting]

[...and to report on another 7-unit setting by N.Predrag, and 6-unit variations by H.Reddmann]

Ed Dean already gave a good example (the White bishop can go to d7 and e8 too but it doesn't change the outcome). I follow up only to point out some variations, all with a much smaller supporting cast of pieces, and two [Edit: now three] with an extra feature of possible interest.

I already showed in a comment how to do without most of the idle pawns and rooks in Dean's position; here's a version that saves two more pawns, reducing the number of units on the board to 10:

Position A: White Kg1, Bd1, Nc4, pawns a6,d6; Black Ka8, Bb1, Bb8, pawns g2,g3;

Position B = Position A after 1...Ba7+ 2 Nb6+ Kb8.

The only irreversible moves from Position B are with the light-squared bishops, which cannot reach the dark-square diagonal g1-a7 to unpin the knight and unlock the king's cage.

Here's a version that uses one fewer unit by replacing the pinning bishop with a rook:

Position A: White Kh5, Nd7, pawns g4,f6; Black Kh7, Rh8, Bb7, pawns g5,f7;

Position B = Position A after 1 Nf8+ Kg8+ 2 Nh7.

This time the White king supplies White's ensuing moves without stepping off the pin-line, so only the Black bishop is needed.

Now consider what would happen if the Black bishop were a knight. Then we could return from B to A by getting the knight to h6, e.g. 2...Nd6 3 Kh6 Nf5+ 4 Kh5 Nh6! 5 Nf8! Rh7! etc. (6 Nd7 Rh8 followed by Kh7, Nf5, Nd6, Nb7); but this works only because b7 is a light square: if we put this knight on a dark square there would be a parity obstruction! Thus (with a dark-squared Black knight) we obtain another example with 9 units.

[EDIT: the White pawn on f6 is not necessary, because if Black ever plays Kg7 then White is stalemated. Thus either the bishop or the knight version works with only 8 units.]

Here's another way, with a rook as the pinned piece:

Position A = White Kf1, Rd1, Bh2, pawn g3; Black Kc4, Ba6, pawns f2,f3,b7;

Position B = Position A after 1 Rd5 Kb3(b4)+ 2 Rb5+ Ka3.

Now the Black king is restricted to {a1,a2,a3,a4} and the White bishop to {g1,h2}. The g3 pawn is needed, even though the White bishop cannot reach the f1-a6 diagonal, to avoid things like 3 Bd6+ Ka2 4 Bb4 Kb3 5 Bd6+ Kc4 6 Rb1 etc.

Likewise with a White knight instead of the bishop:

Position A = White Ke1, Rf2, Nb1, pawn f4; Black Kg3, Bh4, pawns e2,e3,g5; White to move:

Position B = Position A after 1 Rg2+ Kh3+ 2 Rg3+ Kh2.

Again this works only because it's White's turn: moving the Black king to h1 in Position B would be a parity pooper. I initially had this without the f4-pawn; do you see why that 8-unit attempt fails — that is, can you get from B back to A after removing the White pawn from both positions?

[Edit: However, it does work without the f4-pawn if we replace the White Nb1 by a white bishop moving on squares of either color: a dark-squared one could never reach f2, and a light-squared one could play to g2 to allow ...Kg1 but it doesn't matter because the Black king may never play to f2 anyway. So that's another 8-unit construction.]

There's a related genre of unorthodox chess problems called "orthoreconstructions" that features more complicated examples involving parity.

Finally, a new setting using a White queen to reduce the total count units on the board to 7:

Position A: White Ka1, Qa3, pawn b3; Black Kc3, Bd4, pawns a2, b5; Position B = Position A with Qa3, Kc3 switched and White to move, as after 1 Qb2(c1)+ Kb4(+) 2 Qc3+ Ka3:

$\phantom{\Longrightarrow\Longrightarrow}$

The only reversible continuation from Position B is 3 Qb2+ Kb4 4 Qc3+ Ka3 etc.

FURTHER UPDATE Meanwhile Hauke Reddmann reports (in a comment to Ed's initial post) that Nikolas Predrag, on the MatPlus forum, constructed in at most 3 hours an alternative 7-unit setting, with just kings and pawns: A = White Kc7, pawns c5,d6,d7 vs. Black Ka8, pawns a5,c6; B = after 1 Kb6, with 1...Kb8 2 Ka6 Ka8 3 Kb6 (B again) etc. as the only reversible continuation. H.Reddmann later found that I shouldn't have stopped at 7: the scheme with a pinned checking queen has several variations with only 6 units, which need not include even one pawn. Thus Position B can be White Kf1 Qf2, Black Kh1 Re4 Rf4 Nh3, with White to move (1 Qf3+ Kh2 2 Qf2+ Kh1 etc.), and Position A can be almost any one-move retraction from B.

Answer by Noam D. Elkies for Irreversible chess

2011-10-24T05:11:48Z

Here's an "irreversible chess" construction that's fundamentally different from the ones so far based on Ed Dean's scheme. The essential pieces and pawns are in boldface:

Position A: White Kh1, Ra1, Nd1, pawns b2,b3,c3,d2,e3,f2,g2,h7, Bg8; Black Kh8, Bb1, Bg1, pawns f7,g7,h2.

Position D = Position A after 1...Ba2 2 Rc1 Bb1, i.e. with the Rook on c1 and White to move:

I call it D rather than B because the two intermediate positions can be called B and C, and then each arrow in A $\rightarrow$ B $\rightarrow$ C $\rightarrow$ D is irreversible. [This was also possible in some of the previous examples, including Ed's original one; I don't think we've seen "A $\rightarrow$ B $\rightarrow$ C $\rightarrow$ D $\rightarrow$ E" yet.]

In Position A, the rook and a1 and bishop on b1 can reversibly roam the board. But after 1...Ba2 (Position B) the only locally reversible continuation is 2 Rc1 (Position C; if 2 Rb1 Black has no reversible reply) 2...Bb1 (Position D) 3 Rc2 Ba2 4 Rc1 Bb1 and we're back to D; the White rook and Black bishop can no longer escape the corner because they keep getting in each other's way.

The previous constructions all exploit the special behavior of kings, which must not be in check on the opponents' move. This new approach does not need kings at all — it would still work if we removed the kings and their un-boldfaced retinues, except that the problem as posed required each side to have a king. The key ingredient here instead of the check rule is move alternation: if either side were allowed to skip a turn it would be easy to get back to Position A — whereas in several of the check-based constructions, skipping turns would not help as long as neither side is allowed to make a move (even as part of an unanswered series) that leaves its own king in check.

Answer by Noam D. Elkies for Irreversible chess

2011-11-01T21:19:27Z

[Edited to correct the final position (which didn't work before: 2 Bh1+! Bg2 3 Rf1 Bb1 etc.), and — while I'm at it — to remove a few superfluous pawns]

Here's yet another mechanism, which also allows arbitrarily long chains of irreversibility. The new construction is suggested by what may be an unintenional feature/bug in the original question:

[...] the game must be extendable at least two moves in both direction from both A and B.

The number seems arbitrary (why two moves rather than three or 23?), and I'm guessing that the intention was to guarantee that one can continue indefinitely forwards or backwards from both positions but give an easily checked criterion. However, it's possible for a position to be extendable $n$ moves and no further for any given $n$, as long as we're allowed an arbitrarily large board and supply of pieces (as the question proposal did explicitly allow). For example: let Position A have White rook a5, bishops c2,e2,g2, and pawns b3,d3,f3,h3 vs. Black bishops b1,d1,f1,h1, plus any immobile setup that traps both kings above the 3rd row:

and play 1 Ra1 to get Position B. Not only can't we get back from B to A, but after a few moves (but more than 2) we must reach stalemate: 1...Ba2 2 Bb1 (or 2 Rb1 stalemate, or 2 Rc1 Bc2 stalemate) 2...Bc2 3 Bd1 Be2 4 Bf1 and now 4...Bg2 is stalemate.

For a long irreversibility chain not ended by stalemate, remove the White and Black bishops on g2 and h1, put the White king on h1, and add Black pawns on h2 and g3:

Now after 1 Ra1 play can continue indefinitely, but only with 1...Ba2 2 Bb1 Bc2 3 Bd1 Be2

and now 4 Kg2 Bf1+ 5 Kh1 Be2 etc. This extends naturally to wider boards, with a correspondingly longer sequence between 1 Ra1 and the onset of forced repetition.