Author: Robert Hyatt
Date: 08:59:33 12/05/02
Go up one level in this thread
On December 05, 2002 at 11:23:27, Ingo Lindam wrote: >On December 05, 2002 at 11:04:57, Tony Werten 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: >> >>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 > >Hello Tony, > >I appreciate your comment very much! I am also sure that it will me not slow >down factor 4. But factor N*N (for obtaining the N-best-tree) seemed to be the >lowest factor I got Robert Hyatt to agree with. I think we are not quite communicating on the same channel. If it takes N units of time to search the best move, it will probably take N units of time to search the second-best move and get a score for it also. That is 2N, not N*N... Bob > >I just needed a const. factor for my argumentation. > >Thank again! > >Internette Gruesse, >Ingo > > > >> >>> >>>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.