6 ms·
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 ho
by Waterluvian 5y ago
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.
- galdosdi 5y agoGreat 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 https://en.m.wikipedia.org/wiki/Fifty-move_rule
- nextaccountic 5y agoThe 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).
- PeterisP 5y agoThere'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).
- pedrosorio 5y agoWouldn’t the 3-fold repetition rule also prevent cycles? https://en.m.wikipedia.org/wiki/Threefold_repetition https://en.m.wikipedia.org/wiki/Threefold_repetition
- galdosdi 5y agoYes, 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.
- pedrosorio 5y agoYou should find it unsurprising that the simpler rule to keep track of came first, right? :)
- galdosdi 5y agoWell when you put it that way I feel silly thinking otherwise haha
- nightcracker 5y agoWhich begs the question: without the fifty-move rule (only threefold repetition), what is the longest legal chess game?
- deleted 5y ago[deleted]
- jakeinspace 5y agoLet'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.
- le-mark 5y agoOne 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.
- mlang23 5y agoI 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 :-)
- tromp 5y agoI 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.
- tromp 5y agoPeter Ö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=905179&sid=ae1ea68a19780eaffe3cc12b0a0ad29d#p905179 http://talkchess.com/forum3/viewtopic.php?f=7&t=77685&p=9051...