Author: J. Wesley Cleveland
Date: 10:05:13 05/16/01
Go up one level in this thread
On May 15, 2001 at 22:11:15, Robert Hyatt wrote: >On May 15, 2001 at 12:18:43, J. Wesley Cleveland wrote: > [snip] >>>First, how do you conclude 10^25? assuming alpha/beta and sqrt(N)? >> >>It is a classic alpha-beta search with a transposition table large enough to >>hold *all* positions found in the search. I'm guessing at the number of >>positions, but I feel that the same logic should hold, as only positions with >>one side playing perfectly would be seen. > >I don't follow. We know that within the 50 move rule, the longest game that >can be played is something over 10,000 plies. IE 50 moves, then a pawn push >or capture, then 50 more, etc. Eventually you run out of pieces and it is a >draw. But 38^10000 and 10^25 seem to have little in common. The alpha/beta >algorithm is going to search about 38^50000 nodes to search that tree to max >depth of 10,000. Look at it another way. The only positions that are visited by an alpha/beta search (with perfect move ordering) are those where one side plays perfectly. The question is what fraction of the total number of positions that is. > >Another way of estimating is that somewhere along the way, someone found a >way to represent a chess position (pieces only) in 168 bits. if you take that >as an estimate of the total possible positions then you get 2^168 or roughly >10^165 which is a _huge_ number. 2^168 = 3.7*10^50
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.