Author: Robert Hyatt
Date: 20:46:31 12/04/02
Go up one level in this thread
On December 04, 2002 at 03:13:34, Ingo Lindam wrote: >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. The only "assumption" I am making is the "alpha/beta assumption". :) > >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. No. alpha/beta depends on searching the _first_ branch _before_ any other branch, and then using that as a bound so that all you do for the remaining branches is prove they are worse than the first, but not by how much. If you want the second-best move, you will search just as many nodes on the second branch as you did on the first. While most programs spend maybe 90% of their time searching the first branch, and 10% searching the remaining N moves using that first score as a proof bound. Now you are going to almost exactly double the search effort to get that second-best move. If you want three, you are almost going to triple the effort. See knuth/moore, "an analysis of alpha/beta pruning" published in 1975. > >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. Because there is nothing to suggest that that is happening... > >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. Absolutely not. Again Knuth/Moore show why. But the second move would take just as long to search as the first... on average... > >>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. Yes. but current programs look at the best move first well over 90% of the time, based on statistics Crafty produces while playing games... > >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. that is what I have been saying. :) > >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. I promise you that it will cost you _many_ plies of depth and get you killed tactically against an engine that only needs to know the _best_ move in any position. :) > >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.