Author: Robert Hyatt
Date: 11:07:18 05/16/01
Go up one level in this thread
On May 16, 2001 at 13:05:13, J. Wesley Cleveland wrote:
>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.
>
The precise formula is:
N = W^floor(D/2) + W^ceil(D/2) for all D. floor means round down in integer
math, ceil means round up. For the cases where D is even:
N = 2 * W^(D/2) which is 2 * sqrt(minimax).
If you assume that the total number of positions is roughly 2^168, then you
get 2 * sqrt(2^168) or 2 * 2^84. Which is fairly close to the number of atoms
in the universe. Note that 168 is not cast in stone either. It might be a
few bits more or less, but it is probably close.
>>
>>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
Right. overflow on my calculator tool screwed that up. :)
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.