Author: Ingo Lindam
Date: 00:13:34 12/04/02
Go up one level in this thread
On December 03, 2002 at 17:57:12, Robert Hyatt wrote: >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. Sorry, but this sounds like you are making a strange assumption somewhere. Let us in first step just also second best taking into account. So our aim is just to give a tree with every node having two childs and every node still scored with the one and only best score. Dismissing the tree 'instantly' sounds more like having a tree that is obsolete because being easy proofable much weaker than the best subtree of its root, rather than being the second best. I guess in a lot of cases you already scored the second best subtree before finding the best one. But if you assume that you always search the best move first because of an pefect move ordering, why not assume that you search second best move always secondly. Where second best move is as week as you could dismiss this subtree 'instantly' I suggest not to obtain the exact score for this subtree also not for the 2-best-tree. It would be suffitient to show seconds best move with the estimation that makes you sure this move is not worth to obtained in whole. >And >the size of that tree is exponential with respect to search depth... Yes... as trees like to be in general... >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. But than it should be 10 or 20 times faster in the same number of cases to obtain the score for the second best move than the score for the best move. >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... Hard to say what is true in 'interesting positions'. With a non perfect move ordering there should be a lot of second best moves already exactly scored before you see the best move. Unfortunately this information is just thrown away. Within each of this trees however you should have some more work to do in some cases. So I could live with an estimation that to obtain a N-best-tree could rise the effort N*N times. N times for obtaining the N-trees instead of 1 * N times for the additional work within each tree. Ofcourse this is also not a really good estimation... In respect of move ordering will cause to search the second best move in a lot of cases I would suggest to store the second best move and its score atleast whereever you get it before getting the best move and score. I promise that such a N-best tree will give you a lot of benefit when using it e.g. for evaluation of positional evaluation functions. 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.