Hacker News Reader

Comment by Waterluvian | Hacker News Reader

Are there any intelligent approaches to automating proof games? Can I just play the position backwards, unwinding it with a bias to returning pieces to their home positions?

Also isn’t this relatively easy if you can just waste turns (pointless moves by a Queen) while returning pieces back home?

This is fascinating because on the surface it seems very do-able but I bet the devil is in the details.

View on HN

Great question. This was foreseen long ago (1500s?); the turn wasting thing is limited by the fifty move rule. A game ends in a draw if no pawn is moved or piece captured for 50 moves. Since pieces can only be removed not added and pawns can only move forward, never backward, this proves that cycles are not possible in chess (they certainly would be without this rule of course)

See https://en.m.wikipedia.org/wiki/Fifty-move_rule

Wouldn’t the 3-fold repetition rule also prevent cycles?

https://en.m.wikipedia.org/wiki/Threefold_repetition

Yes, definitely. I hadn't remembered that one. You could have much longer chains with the 3 fold repetition rule alone though. I guess both together potentially make it easier on the players and arbiters

It seems the 50 move rule is probably older according to Wikipedia (1800s vs 1500s), which is kind of surprising to me, I would have expected the other way around. It's easier to keep track of "moves since last capture/pawn advance" than every board position played so far. Maybe just in theory not in practice. I am a terrible chess player.

You should find it unsurprising that the simpler rule to keep track of came first, right? :)

Well when you put it that way I feel silly thinking otherwise haha

Which begs the question: without the fifty-move rule (only threefold repetition), what is the longest legal chess game?

For a hilarious read, which answers a related question, I recommend the paper "Is this the longest Chess game?", published on April 1st, 2020:

http://tom7.org/chess/longest.pdf

That probably involves creating the maximum number of pieces, by capturing 4 pawns to promote the 12 others. Let's give each side 1 king, 3 queens, 3 rooks, 3 knights, 2 light squared bishops, and 2 dark squared bishops.

Then have these move through as many board permutations as possible without triple repetition. This would give a multinomial of (64 choose 36 1 3 3 3 2 2 1 3 3 3 2 2) ~ 4.6 x 10^41 positions to move through, which could be multiplied by 2 for side to move (over estimating a lot since many positions will have the wrong king in check, or the right king in impossible check) and another factor 2 for first repetition, giving roughly a 2e42 upper bound.

Let's assume the 50-move rule is automatically applied. We can have 49 moves per pawn move, followed by 49 moves per piece captured. A maximum of 8 pawns (4 white and 4 black, for example) can possibly be advanced over the course of the game to the opposite side (6 squares ahead from their home square). Therefore, it seems to me that the maximum number of pawn moves could involve one player advancing their pawns 4 spaces, followed by the opposing player capturing all those pawns (using pieces rather than pawns, as both moving a pawn and capturing a pawn would be a waste), and then advancing their pawns to the back rank. This would be 8x4 + 86 = 80 pawn moves, plus 8 pawn captures. That's 88 allowances for 49-move knight sequences, plus the initial 49-move knight sequence made from move one. So, with no pawns remaining, and all of black's pawns converted to pieces on the back rank, we have 8949=4361 moves. Now, there are 22 pieces and 2 kings remaining on the board. That puts an upper limit of 22 captures, leading to an additional 2249 allowable moves. All together, that is 11149=5439 total moves. I'm probably off by a few.

> A maximum of 8 pawns (4 white and 4 black, for example) can possibly be advanced over the course of the game to the opposite side (6 squares ahead from their home square).

Not so! Pawns move diagonally via capturing, which theoretically could allow white to promote all 8 pawns just in the d column, and black to promote all 8 in the e column (at the expense of various other pieces).

edit: of course, you'd run out of pieces first, but you can accomplish something similar by using multiple columns.

Sample game start that accomplishes a subset of this (2 pawns promoted from each side, 6 pawns remaining from each side):

1. Nf3 Nc6 2. Ng5 Nb4 3. Ne6 Nd3+ 4. exd3 dxe6 5. Ke2 Qd7 6. Kf3 Qc6+ 7. Kg3 e5 8. d4 e4 9. d5 e3 10. d6 e6 11. d7+ Ke7 12. d4 Kf6 13. d8=R e2 14. Rd5 e1=R 15. Ra5 Re5 16. d5 Rh5 17. d6 e5 18. d7 e4 19. d8=R e3 20. Rdd5 e2 21. Rdb5 e1=R

https://lichess.org/wtJoIdT3#42

> A maximum of 8 pawns (4 white and 4 black, for example) can possibly be advanced over the course of the game to the opposite side

I think they all can.

If white’s A pawn takes a black piece in the B file and black’s B pawn takes a white piece in the A file, both white’s two B pawns and black’s two A pawns have a clear route to promotion.

You can do the same for files C and D, E and F, and G and H, at the cost of 8 taken pieces.

Of course, that “white’s A pawn takes a black piece” is wasteful in the sense that it is both a pawn move and a piece being taken, but I think it still is better than letting the pawns end up facing each other without being able to move more.

> http://tom7.org/chess/longest.pdf

This paper concludes 17,697 moves. 50-move rule is not automatically applied per FIDE rules.

The 75 move rule is, though.

Yes, that's the rule used to generate the game in the paper.

There was a sigbovik paper a few years back by the inimitable Tom Murphy that found this.

http://tom7.org/chess/longest.pdf

The threefold repetition has to be claimed, so the game can legally go on if both players overlook (or ignore) it.

There's also the fivefold repetition rule, which draws the game automatically.

3 fold is by mutual agreement, if one side wants to continue they can. At 5 there is no choice

No mutual agreement is needed. Either player can decide to claim a draw by threefold repetition (§9.2) or 50 moves (§9.3). The only difference with the fivefold repetition and 75 move rules (§9.6) is that those draws are automatic.

https://handbook.fide.com/chapter/E012018

I stand corrected.

The rule says a player can claim a draw, but they are not obligated to do. So, if you're a player and want to exhaust the search space, this only helps you if you seek a draw; but perhaps there would be a guaranteed win somewhere if you kept playing (and the opponent didn't claim their draw).

There's the usual limits where one may claim a draw (threefold repetition or 50 moves without capture or pawn move), but there also are limits where a draw is automatic and should be enforced by the arbiter even if players do not request it (fivefold repetition or 75 moves without capture or pawn move).

I think it may be possible to automate finding what I would call proof game kernels, which is just the subsequence of pawn moves (including promotions) and pawn captures.

One could further simplify the search by abstracting away from the exact location of pawns, but recording only their color and order within each file.

Many of the 381 illegal positions can be proven illegal just by absence of such proof kernels.

Proof game kernels can also guide construction of full proof games.

Peter Österlund just outlined his tools and methodology for constructing proof games, which use similar ideas, at

http://talkchess.com/forum3/viewtopic.php?f=7&t=77685&p=9051...

I was thinking about writing a reverse move generator for chessIO just recently. Shouldn't be too hard. The question is how large the tree will grow. Its a fascinating idea looking for useful applications :-)

One could imagine some games require captures, castles and en passants to reach, so maybe in the general case, but devil indeed. I thought I recognized Tromp from Equihash work and indeed same person.

Reply on news.ycombinator.com