Author: Angrim
Date: 22:49:03 05/10/01
Go up one level in this thread
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 Angrim
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.