Author: Ingo Lindam
Date: 01:27:40 12/05/02
Go up one level in this thread
Thank you. I see we agree in the most important points when estimating the time effort. But you sometimes use words like 'exponentially' and 'instantly' in a way that makes may want to say the same with the contrary words. Is Knuth,Morre 1975 "an analysis of alpha/beta pruning" available somewhere? I am sure that also Knuth/Moore agree that also in alpha-beta-search there are no trees dismissed insantly. They will be dismissed, but never instantly. You need a certain estimation for its score >= beta to dismiss. And when you say there are some subtrees taking 10x or 20x the time you need to evaluate exact than to evaluate the best subtree (in some rare cases).... Then it is not wrong to say there must be the some number of cases where the second best tree is to evaluate much faster ten the best tree... if you agree with evaluating both subtrees doubles the time in average. When you hint on the 90% needed to evaluate the best move and just 10% to dismiss the other moves hten ofcourse therin is also the effect of hashing AND the effect that sometime all moves are much much weaker then the only single best move. Here I have no problems to dismiss them also in the N-best search, when its score is more than DELTA weaker then best score. So N-best search will profit from this cases also. And thank you for the friendly hint... but ofcourse I am aware of winning nothing and loosing a lot of time when scoring exactly also the second best move in each node from the point of view playing games, where I just use the single best move... to play it. BUT... I think engines can do more than this (if we allow them to do so). They can analyse and give a tree to argue for their decission by giving a scored tree, rather than a single variation. And also the developer will save so much time (yes, SAVE time) by doing this (not when playing a game) but when testing and developing. Give the engine a lot of time to analyse some crucial/test positions, store the tree and than enjoy the speedup when testing several evaluation methods on this reduced search tree. And when you agree that doing a N-best search slows down not exponentially, but going deeper into the searchtree does. Then there must be a certain limit for going deeper. And when you have n time to go deeper, why not use a better, more complex evaluation function on the N-best tree in that time. Even more when you think of... a) N is const.!: so = O(N*N * x^ply) = O(c * x^ply) keeps O(x^ply) in O(ply) notation b) rescoring on the N-best tree can given without any problems to another processor or even maschine. c) even generating the N+1-best-tree given a N-best-tree can done by an additional maschine for ply K as soon as N-best tree for play K. d) generation the N+1-best-tree (i the MP case) can be accellerated by giving the hash of generating the N-best tree. Do I miss something? Internette Gruesse, Ingo On December 04, 2002 at 23:46:31, Robert Hyatt wrote: >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.