Author: Tony Werten
Date: 08:04:57 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: Nonsense: At iteration 0 do a full width search for all moves and you get a score back for all moves. Then do an aspiration search for the first 2 moves. Decide wich is best and 2ndbest. Then search the remaining moves with (2ndbest,2ndbest+1) If a move fails high research it and decide new 2ndbest score. No way this will slow you down factor 4. Tony > >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. > >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 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?" > >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.