From: Bill Gosper <billgosper@gmail.com> To: math-fun@mailman.xmission.com Subject: [math-fun] how many chess positions?
WDS>Ignore the 3-time repetition and 50-move rules. rwg> Note that someone has found a 517 move forced mate: http://timkr.home.xs4all.nl/chess2/diary_16.htm See also http://en.wikipedia.org/wiki/Fifty-move_rule
--yes, FIDE after the discovery some endings took longer than 50 reversible moves to make progress, changed "fifty" to higher numbers in specific endings. But eventually it got ridiculous with several "mate in >500" positions being proven and no end in sight to the horror. So then they just said "to hell with them" and changed it to 50 moves, period, to the great relief of all top human players. ........ r......n ........ ........ black (lowercase) to move but then will be mated in 545 moves. .....k.. ...K.... .......N ...b...Q http://chessok.com/?page_id=27966 describes the latest progress in perfect-solve endgame databases. They are trying to solve all 7-man positions, ignoring stupid stuff like 6 men versus bare king or multiple same-square-color bishops, and their answers have consumed 140 TeraBytes so far.
WDS> What is the number P of chess positions reachable via a legal game? Finding the exact answer is too hard, but finding good upper & lower bounds
Note that pawns can only be located on ranks 2-6, not 1,8; rwg> Why not 2-7? --WDS: sorry for this typo.
Tom asked if one should ever promote to a bishop. Can someone construct a case where queening would stalemate? --yes, there are many chess problemists who have made positions where, e.g. the unique best move is underpromotion to anything they wanted. However, in real games it is rare that underpromotion is best, and knight underpromos are way less rare than bishop and rook.
Real games involving underpromotions were found by a game database search and collected here: http://www.chessgames.com/perl/chesscollection?cid=1000028 Apparently this search found only 4 games involving bishop underpromos. Of those, only 1 was real, 2 were stupid jokes or hoaxes, and the remaining 1 was not really played in the game but should have been. http://www.chessgames.com/perl/chessgame?gid=1253800 In this 1972 game Reshko (white) should have played 61. a8=B! If he'd played a8=Q or R then 61... Qf7+! 62.Qxf7 stalemate). Wikipedia claims that the above URL game record is wrong and really Reshko played 61. a8=N? which should have drawn according to analysis by Soltis, but won due to an error by his opponent Kaminsky, whereas 61. a8=B! really was a forced win. In this 1993 game http://www.chessgames.com/perl/chessgame?gid=1287069 Tomic (white) played 44. cxd8=B. If he had played cxd8=Q or R, then immediate stalemate. But the B threatened immediate unstoppable mate. If he'd promoted to an N, this would probably also win, but much slower. In this 1932 game http://www.chessgames.com/perl/chessgame?gid=1094403 Vidmar (white) gets into an opposite-Bs ending 2 pawns up. I suspect this game is fake because Maroczy could & should have called a 50-move draw on him (moves 61-106). Anyhow it has 124. h8=B+ which was just a stupid joke, he should have played h8=Q+ but it made no difference due to immediate 124... Kxh8. Furthermore, the game continued past the point where it automatically would have ended (at least in today's rules) due to insufficient mating material. In this 1978 game http://www.chessgames.com/perl/chessgame?gid=1042976 Meyer's bishop underpromo is another stupid joke. Then he lost. chessgames.com says it has "over 711000 games" so it would appear real bishop underpromos happen about 1 game per million. Same search found about 40 knight underpromo games, of which maybe half of them were jokes. Wikipedia discusses examples of R and B underpromotions, http://en.wikipedia.org/wiki/Promotion_(chess)#Promotion_to_rook_or_bishop but both their B-examples are constructed, not real. Tim Krabbe also did game database searches for underpromo games (as well as discussing constructed positions) http://timkr.home.xs4all.nl/chess2/minor.htm noting that R or B underpromo that win are rare compared to those that salvage draws. He found Grishchuk-Hua 1994 in which 68. axb8=B won, although axb8=N also would win. chessgames.com N-underpromo games: http://www.chessgames.com/perl/chessgame?gid=1037562 white played 71.b8=N+ getting a draw, because 71.b8=other? 72. Ra1 checkmate. Same thing happened in http://www.chessgames.com/perl/chessgame?gid=1400994 In this 1994 game http://www.chessgames.com/perl/chessgame?gid=1046960 Cramling played 39. c8=N+ which is not bad, but she could have done c8=Q and also won. In 1956 Zurakhov played 57.g8=N! http://www.chessgames.com/perl/chessgame?gid=1156733 since 57.g8=other loses it to the knight fork-check. Later in the same game, 79.c8=N+! for the same reason and if 79.c8=other? Nd6+ 80. K moves, Nxc8 then black presumably eventually would draw by playing ..NxP or by sacrificing his N to reach a known fortress position in which the a-pawn cannot promote. So... TWO N-underpromos in the same game, which is amazing and surely qualifies this as "the immortal underpromotion game." In 1948 http://www.chessgames.com/perl/chessgame?gid=1072256 44. f8=N+ looks to be the only winning move. If 44.f8=Q? Qc2+ 45. Ke3 or Kf3, Qe2+ 46. Kf4 Qe4 mate In 1993 http://www.chessgames.com/perl/chessgame?gid=1014437 Adams played b8=N since anything else loses to Ra6 (checkmate or wins both pawns). 45. Kf3
HAKMEM Item 70 misprints a vaguely related subtle chess problem (bishop at KB7 should be KB8).
--rwg
wds> and that if M pieces and P pawns have been captured, then at most 2*M+3*P promotions could have happened. And many pawn configurations are impossible unless enough captures happened...
John Tromp claimed P<=7728772977965919677164873487685453137329736522=2^152.437 as the result of a computer program he has not described, but this is unlikely to be optimal (assuming it is correct).
For somebody determined enough: I think it should be possible to determine the answer accurate to 5% by first creating a good encoding scheme, say which proves P<2^155, and then sampling random positions for each deciding if it really would be reachable. Assuming deciding reachability is actually feasible 99.999% of the time, and assuming P>2^144, we would after 2 million random samples find at least about 1000 reachable positions and at most about 20 whose reachability was unknown. This would be good enough for a 5% accurate (Monte Carlo) estimate.
If P<2^150, then the proof tree of chess (at least ignoring 50-move rule) would presumably be about 2^75 positions, suggesting chess might actually be feasibly solvable (?!). -- Warren D. Smith
------------------------------
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
End of math-fun Digest, Vol 133, Issue 35 *****************************************
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)