Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
What about pawns? IS A and B considered equal if one can get A from B by shifting every piece two steps to the right? –  Per Alexandersson Oct 22 '11 at 13:25
6  
Crossposted on math.SE: math.stackexchange.com/questions/74776/irreversible-chess GM2001, in the future, please wait some time before posting your question in multiple fora, and when you do, provide links to the other posts. –  Zev Chonoles Oct 22 '11 at 14:47
1  
Since it is cross-posted, I vote to close here. (I would not if it were not.) –  quid Oct 22 '11 at 15:18
6  
Since answers are coming in here rather then on math.SE; I retract my suggestion to close it here. (Perhaps close it there?) –  quid Oct 22 '11 at 19:02
4  
@quid: It's now closed on math.SE. –  Zev Chonoles Oct 22 '11 at 19:14
show 3 more comments

5 Answers 5

up vote 17 down vote accepted

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.

share|improve this answer
    
...Though come to think of it A → B → C → D → E isn't too hard to arrange in the check-dependent setup: starting from the first example in my previous answer, move White's a6-pawn to a5, and add a Black pawn on b7 and White rook b6: call that Position A, and then 1 Ra6+(B) starts the forced sequence 1...Ba7+(C) 2 Nb6+(D) Kb8(E). –  Noam D. Elkies Oct 24 '11 at 5:30
1  
@Noam: it would be interesting if this set-up could be done completely without pawns. (Maybe by some cheating: a very small board where knights can hardly move and thus serve as "stoppers", and by re-utilizing the kings again.) –  Hauke Reddmann Oct 24 '11 at 10:35
    
@Hauke: as you suggested, it works on a $3\times 3$ board a1-c3 if we replace pawns b2,b3,c3 with Nb2, Rb3, Bc3 and add Ba3. That looks more like a Rush Hour puzzle than chess... –  Noam D. Elkies Oct 24 '11 at 14:20
    
Correction to the A → B → C → D → E comment: doesn't work as it stands because the sequence is not forced throughout (2 Rb6, 2 Re3). Instead start with White Ra5, Na7, pawns a4,b5, and then 1 Nc8+ Ba7+ 2 Nb6+ etc. Then the White rook can oscillate a5-a6 so the White bishop is not necessary. –  Noam D. Elkies Oct 25 '11 at 1:42
add comment

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

share|improve this answer
1  
Just figured out how to get the count down to 8: remove White's f6 pawn from the second A/B pair. The pawn was not needed, because if Black ever plays Kg7 White is stalemated.$$ $$ Now can anybody do this in a "miniature" setting (7 units or fewer) on the orthodox $8 \times 8$ board? –  Noam D. Elkies Oct 22 '11 at 20:18
    
Another 8: in the final A/B pair, remove White's pawn, and replace the knight by a White bishop, either light- or dark-squared. A dark-squared bishop cannot reach f2, and a light-squared bishop could reach g2 but Black's king still doesn't get out of the corner (and even if it could it wouldn't matter because the king could never play to f2). –  Noam D. Elkies Oct 22 '11 at 22:17
    
OK, got it down to 7. Will post the positions in a day or two if nobody else finds them first. –  Noam D. Elkies Oct 22 '11 at 23:42
1  
@Noam: I took the liberty of editing so that your images are included directly in the posting. Hope I got them all correct... –  Joseph O'Rourke Oct 23 '11 at 2:41
    
@Joseph: looks right to me, thanks! –  Noam D. Elkies Oct 23 '11 at 3:06
show 2 more comments

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

share|improve this answer
2  
Yes, this works! Same idea but fewer pieces: Position A = White Kh2, Bd1, Nb5, pawns a5,a6; Black = Ka8, Bb1, Ba7, pawns f2,g2,h3,h4. Position B arises after 1...Bb8+ 2 Nc7+ Ka7, when the only irreversible moves remaining are with the light-squared Bishops.$$ $$ To see the positions, enter the following FEN codes into your browser after janko.at/Retros/d.php?ff= : A = k7/b7/P7/PN6/7p/7p/5ppK/1b1B ; B = 1b6/k1N5/P7/P7/7p/7p/5ppK/1b1B (I tried to give the full URL but the comment viewer truncated them). –  Noam D. Elkies Oct 22 '11 at 16:04
    
I took the liberty of editing so that your images are included directly in the posting, as J. O'Rourke did for mine. Hope I got them both right. –  Noam D. Elkies Oct 24 '11 at 15:59
    
@Noam: Thanks, that looks nice. And thanks as well for pointing out in your first answer my embarrassing omission of d7 and e8; the kind of "tactical" oversight that keeps me from being a better chessplayer :-) –  Ed Dean Oct 24 '11 at 17:41
    
@Ed: You're welcome on both counts. I don't think you need the pawns on b5/c4/d3/f3 either: Ne7 already controls c6 so the bishop can go anywhere without reversibly untangling the knot. –  Noam D. Elkies Oct 24 '11 at 18:14
2  
Nikola Predrag's position: A: White Kc7 Pd7 Pd6 Pc5/Black Ka8 Pc6 Pa5 B: after 1.Kb6, no king can get out of the cage. BTW, your 7-piece gave me an idea: B: White Ka5 Qb6 Pb7 - Black Kb8 Qc4 Bd8 A: almost any last move pair Same mechanism: B: White Kf1 Qf2 - Black Kh1 Re4 Rf4 Nh3 Again, Black can only run from the white checks. –  Hauke Reddmann Oct 27 '11 at 10:45
show 3 more comments

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

share|improve this answer
add comment

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.

share|improve this answer
1  
Edit: This includes retrocheats like Bb8 Rc7/Ka7, which force a pawn promotion in the history, or in general any position B with a retro-forced pawn move or capture. –  Hauke Reddmann Oct 28 '11 at 12:52
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.