Author: Robert Hyatt
Date: 08:58:00 12/05/02
Go up one level in this thread
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, 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.