Author: Dann Corbit
Date: 13:05:01 05/16/01
Go up one level in this thread
On May 16, 2001 at 15:10:33, J. Wesley Cleveland wrote: >On May 16, 2001 at 14:07:18, Robert Hyatt wrote: > >>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. > >2^84 = 1.9*10^25 If these were atoms, it would be 32 moles, or about 1kg of >silicon. 902.13 grams, to be precise. That assumes that one atom of silicon would somehow make a useful transistor. Seems a bit optimistic to me. Perfect move ordering assumes that we never make a mistake. If that were to somehow occur, it would mean that our first choice was correct, and our second choice were correct... all the way to the end. In other words, to get truly perfect move ordering we have to have already solved the problem. In order to know "for sure" you have to search the tree all the way to the end -- including the bad branches. That's why some chess programs which use null move pruning won't see a 7 ply checkmate until ply 9. The null-move+alpha-beta combination rejected that branch as unimportant. But the guess was wrong. And if null-move is not used, it might be the last node searched in the last move from the move list, despite appearances otherwise. Branches that look very bad (and hence don't get probed deeply right away) can suddenly turn into the best route. The only thing that definitely closes a branch is a checkmate or forced draw. Since we don't have any idea where they are or the frequencies at which they occur, most of this pruning guesswork is an angels dancing on the heads of pins thingy.
This page took 0 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.