Author: Robert Hyatt
Date: 20:22:57 12/05/02
Go up one level in this thread
On December 05, 2002 at 04:27:40, Ingo Lindam wrote: >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. You forget the transposition/refutation (hash) table. We often do a probe and stop the search _right there_... for obvious reasons... > >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. That is why I said "on average, the second move will take as long to search as the first." -on 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. You need to try it. The first move doesn't have to be way better than the others to make them get searched very quickly. Null-move does that pretty well... > >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. we don't know that we can't go deeper until we are out of time, that is the problem.. > >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. However, you just lost three plies of search at a minimum. For 36 legal moves, you normally require T units of time, with the first taking .9T, and the remaining 35 taking .1T/35 units of time. You just turned that into 36T, which is the equivalent of 3+ plies of search since the typical effective branching factor is about 3.0. 27X slower costs exactly three plies of depth. That is a killer because that is the exponential nature of the tree. >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? > A lot. :) >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.