Author: Ingo Lindam
Date: 08:23:27 12/05/02
Go up one level in this thread
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 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.