[an aside] In a discussion of the 50-move rule and the longest possible (sensible) chess game, I saw a problem position that required around 5000 moves for White to win. The construction was that about 50-100 "progress" moves were needed to win, and a sequence of 50-100 moves with a couple of knights was necessary between each progess move. But I can't find the book to cite it. [end of aside] There's an obvious puzzle about these piece-only endings: Why isn't the depth much greater? There are 2^43 raw positions with 7 pieces, 2^40 after removing gruop-of-the-square symmetries, and perhaps 2^38 after deleting silly positions. We have a bipartite graph of the possible positions, with White trying to move to a terminal position, and Black trying to avoid this -- or maybe to move to a terminal position of another kind. The graphs are very non-random, being nearly a cross-product of the individual piece positions; and the possible moves largely commute, with the move sequence w1 b1 w2 b2 often being equivalent to the sequence w2 b1 w1 b2 or to w2 b2 w1 b1. The diameter of a random graph with 2^40 nodes and average node- degree of 32 should be around 8, but in chess we have the feature that one player is trying to thwart the other. Still, we have the empirical observation that adding another piece or two to the puzzle only increases the longest-game length by 20-50 moves, while the number of positions is multiplied by 64 or 4096. Odd. Rich -----Original Message----- From: math-fun-bounces+rschroe=sandia.gov@mailman.xmission.com on behalf of Guy Haworth Sent: Wed 4/5/2006 4:44 PM To: math-fun@mailman.xmission.com Subject: [math-fun] Chess Endgame Depth Record Broken Again On 10th March 2006, Marc Bourzutschky announced that Yakov Konoval's program had computed the DTC/Z endgame table (EGT) for KQBNKQB and found: maxDTZ/C = 330 moves: maxDTZ position = 1k6/1b5q/N7/8/8/1Q6/8/B1K5+b DTC = Depth to Conversion, i.e., change of force and/or mate DTZ = Depth to (move-count) Zeroing (move), i.e. P-push and/or Conversion This depth leaves all chess records of this kind well behind: 193m = the longest decisive game in classical chess: Stepak-Mashian (1980) 199m = longest (rapid) decisive chess game: Petrosian-Milanovic (2005) 262m = the greatest known EGT maxDTM(ate), in KRNKNN 269m = longest (drawn) chess game: Nikolic-Arsovic (1989), 290m = the deepest known Chess Problem - by O.T.Blathy 290m = the previous maxDTC/Z record - in KRRNKRR Generation and verification of the EGT required 3.5 weeks of a 3.6GHz processor. The first two attempts to generate this EGT were frustrated by interrupted power supplies. guy _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun