Author: Robert Hyatt
Date: 15:02:23 12/05/02
Go up one level in this thread
On December 05, 2002 at 12:34:23, José Carlos wrote: >On December 05, 2002 at 11:58:00, Robert Hyatt wrote: > >>On December 05, 2002 at 10:50:47, Ingo Lindam wrote: >> >>>Hello all, >>> >>>quoting myself I would like to start a new discussion about why I think its >>>worth two obtain N-best-trees (as a result of the search process), containing >>>the N-best moves in each exactly evaluated node of the search tree. >>> >>>Robert Hyatt agreed that the effort to do this should be able to estimate by >>>getting N*N times slower. This means 4 times slower to obtain a 2-best-tree >>>instead of just obtaining a single PV: >> >>Not quite. Generally the second-best move will take just as long to search as >>the >>best move. So finding the best _two_ moves should take twice as long, not 4x. >> >>Assuming by "best two" we mean moves at the root of the tree.. >> >> >>> >>>Ofcourse I am aware of winning nothing and just loosing a lot of time when >>>I play games and my aim is just to obtain the best move according to one given >>>evaluation function (at the end of the quote I hint on the possibility to use >>>the N-best-tree for rescoring on basis of a second, improved evaluation function >>>that is more complex and therefor just usable on a reduced search space/tree). >>> >>>" >>>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. >> >> >>Some do this already. Some do it some of the time. IE crafty's annotate >>command >>has done this for years, giving you the ability to say "show the best N moves in >>each >>position" rather than just showing the best move. But it hurts speed >>drastically. >> >> >> >> >>> >>>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. >> >> >>I do this all the time, and probably should have an N-best mode in the normal >>search >>as well, knowing the cost of course... >> >> >> >>> >>>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 no 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?" >> >> >> >>If you want the best two moves, there is no reason that the first has to be >>finished before the second is searched. They are not inter-related >>except thru the possible benefit of hash move ordering, > > I missed the previous discussion, maybe you explained this before (sorry in >that case), but how can I possibly know anything about the second best move >without knowing which one is the best? The idea was to search multiple root moves in parallel. Of course you are correct in that there is no way to really know anything without having done it already. My approach (in annotating games) has been to search all moves and get the best, then remove it from the set and search again to get second-best. Repeat until either tired or done. :) > Let's see: I'm at the root at, say, iteration 10. I search the first move and >get a score back. Then I search the other moves with a null window, researching >at fail highs, etc. After that, I have the best move, and its score. Now I >remove it from the list and repeat the process, getting the second best one and >its score. They're inner-related in this case. > Now let's suppose I have two processors. Processor 1 searches best move from >previous iteration. Processor 2 searches the second best. The first move is >finshed and that processor starts doing null searches with the other moves. If >now the second processor fails low, all those searches are wasted, and you need >to do them again with a different window. If two of them fail high, you've >wasted all the time processor 2 was searching... It seems quite messy; depending >on what each processor is doing and what move is failing high or low, there seem >to be a lot of cases. > > José C. > > > >> since we are not going to be doing alpha/beta at the root anyway. >>>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.