Author: Dann Corbit
Date: 13:48:39 05/10/01
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.
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.