Author: Ingo Lindam
Date: 07:28:39 12/05/02
Go up one level in this thread
On December 05, 2002 at 04:27:40, Ingo Lindam wrote: I have to correct myself in atleast one point: >... also in alpha-beta-search there are >no trees dismissed insantly. They will be dismissed, but never instantly. You >need a certain estimation for its score >= beta to dismiss. This ofcourse is just true for the nodes you start to obtain a score. But when you get an estimation of the score for current node >= beta you ofcourse (in alpha-beta) INSTANTLY DISMISS (hopefully a lot of) childs/subtrees of this node. But I keep my opinion that obtaining N-best-trees is worth to think about. Best regards, Ingo >And when you say there are some subtrees taking 10x or 20x the time you need to >evaluate exact than to evaluate the best subtree (in some rare cases).... Then >it is not wrong to say there must be the some number of cases where the second >best tree is to evaluate much faster ten the best tree... if you agree with >evaluating both subtrees doubles the time in average. > >When you hint on the 90% needed to evaluate the best move and just 10% to >dismiss the other moves hten ofcourse therin is also the effect of hashing AND >the effect that sometime all moves are much much weaker then the only single >best move. Here I have no problems to dismiss them also in the N-best search, >when its score is more than DELTA weaker then best score. So N-best search will >profit from this cases also. > >And thank you for the friendly hint... >but ofcourse I am aware of winning nothing and loosing a lot of time when >scoring exactly also the second best move in each node from the point of view >playing games, where I just use the single best move... to play it. > >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 n 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.