Author: Don Dailey
Date: 21:33:24 06/17/98
Go up one level in this thread
On June 17, 1998 at 22:25:12, Roberto Waldteufel wrote: > > >On June 15, 1998 at 12:41:26, Ren Wu wrote: >> > >>I used to use PVS but switch to NegaScout some time ago, but after that > > >Please would you explain what is the difference? I was under the impression that >PVS and Negascout were one and the same algorithm, namely search first move with >window [alpha,beta], then search remaining moves with window [alpha, alpha+1] >with a research if necessary. If this is wrong, I would like to know. > >Best wishes, > >Roberto PVS and scout are the same as far as I know. PVS means principal variation search. The "nega" in negascout is the practice of negating the scores from level to level and changing the point of view of alpha and beta. This is to provide a consistant frame of reference and turns min-max into maxi-max, both sides try to maximize the score. It is a semantical distinction and changes nothing but makes the code a little more natural to deal with: /* prototype */ int search( int alpha, int beta, int depth ); /* recursive call with nega-max */ score = -search( -beta, -alpha, depth-1 ); Sometimes programmers put a window around even the first move. But the "classic" algorithm searches the first move with alpha and beta which at root of tree is -INF +INF. I use MTD which in a nutshell is ALWAYS using a zero width window. How you pick the window determines which version of MTD you use. I use MTD(f) with my own modifications to improve the behavior of it. All these algorithms are just various manipulations of the window and together they are called "aspiration searches." Using a window other than alpha and beta is speculative and always risks doing a re-search but the net affect (at least when using hash tables) is a general speedup. MTD is the most efficient of all these because it takes the aspiration paradigm to the limit but it is also a pain to deal with and has lots of tricky side affects. Most consider it not worth the trouble. - Don
This page took 0.01 seconds to execute
Last modified: Thu, 07 Jul 11 08:48:38 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.