Author: Robert Hyatt
Date: 14:57:12 12/03/02
Go up one level in this thread
On December 03, 2002 at 12:54:00, Ingo Lindam wrote: >On December 03, 2002 at 11:29:56, Robert Hyatt wrote: > >>Within the framework of alpha/beta there is no way to do this. >> >>Why? >> >>Because alpha/beta doesn't search the entire tree. It searches the first branch >>at the >>root, for the score, then it uses that score to prove that the other root moves >>are worse, >>without proving exactly how much worse they are. >> >>And therein lies the problem. To get the second best move, you don't just prove >>that it >>is worse than the best, you have to search it completely to see exactly how much >>worse >>it is, and that drives up the time exponentially. > > >Sorry, but to me is not clear... > >WHAT drives up >WHAT TIME >exponentially >in comparisson to the >TIME it takes to >OBTAIN WHAT? > You are going to have to search a tree that you would normally dismiss instantly. And the size of that tree is exponential with respect to search depth... In the normal case, finding the second-best move will take almost exactly as much time as finding the best move did, a 2x time increase. To find the best N moves, will require N times as long. But, in cases where a move or two is really better than the rest, it is possible that finding the second move will take much more than 1x as long as the first, and I have seen cases where it can take 10x or 20x in rare cases. The cost of this can be seen clearly by using Crafty's "annotate" command with N-best mode set to something like 5, and then comparing how long it takes to annotate a game that way vs annotating with just the best move given at each ply... >or in different words: > >It takes time t to obtain ............(single best variation?) >then it takes aprox. time t^n to obtain ............(n best variations?) >where n is ............(n(best variations)?) >assume t = const. (?) > >or exponentially with number of plys...? Yes... I wasn't very clear. Since we are comparing two exponential values, the ratio is somewhat linear although even that isn't true in "interesting" positions... > >(don't need an exact formula, just want to understand what you mean / think of) > >Internette Gruesse, >Ingo
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.