Author: Dann Corbit
Date: 00:29:43 05/11/01
Go up one level in this thread
On May 11, 2001 at 01:49:03, Angrim wrote: >On May 10, 2001 at 16:48:39, Dann Corbit wrote: > >>NO big-O stuff in here! I promise! >>;-) >> >>From: >>http://www.clark.net/pub/pribut/chessfaq.html >> >>we have this: >> >>"Subject: [24] Trivia >>How long is the longest possible chess game? >>The basic idea is a player may claim a draw if fifty moves elapse without a >>capture or a pawn advance. Ignoring the special cases where more than 50 moves >>are allowed by the rules, the answer is after Black's 5948th move, White is able >>to claim a draw. The simple calculation is (<Pawn_moves + - + >><Drawing_interval_grace_period) * <Drawing_interval, or (16*6 + 30 - 8 + 1) * 50 >>= 5950; we're able to trim two moves from this total by observing that sequences >>of Captures/Pawn_moves must have (at least) 4 alternations between the two >>players." >> >>Now, the depth of the chess tree is the number of plies. Allowing for the 50 >>move rule, the _depth_ of the tree is 5948 plies deep. Even if it were a binary >>tree (on average), that would be 2^5947-1 choices on the way. >> >>So the actual number is branch factor (about 38 by some estimates) times >>possible moves = 5950 for "real" unique board positions (including all data) >> >>That number (38^5900) is 5.28713e9320 >> >>Now the board positions is another matter. Let's suppose that there are only >>10^50th distinct board positions, including halfmove clock, castle rights, etc. >>We might store those in a linear list, and just have pointers from our tree to >>the list. We would have to use 64 bit pointers because of the size of the list >>(some other clever indexing method might conceivably reduce this). >> >>Even if we could use perfect move ordering and only store sqrt(5.28713e9320) >>elements in the list, that's still a lot of pointers. >> >>Or have I missed something. > >If your goal is to determine how hard it is to solve chess, then yes. >Rather then go into a lengthy rant here, let me give an example. >The following position has pawns advanced a total of 4 squares, so >subtract 4*50 from the max depth, and your math suggests that there are >38^(5900 -200) total games of chess that can result from this position. >However, the position is trivial. No need for sqrt(38^(5900 -200)) >positions to be searched or stored... > >[D]rnbqkbnr/pppp1ppp/4p3/8/6P1/5P2/PPPPP2P/RNBQKBNR b KQkq g3 0 2 Yet there are many quintillions of quintillions of qintillions of games that can sprout from here. Unless we assume optimal play. Positions like this one are intensely interesting, however. We could formally trim all forward branches from here. Unless I am missing something. Which brings up another thought. What percentage of moves are so horrible that they are not even worth considering. Is it 99.99999999999999999999999999%?
This page took 0.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.