Computer Chess Club Archives

Messages

Subject: Re: Zero-width Window Null Move Search

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

```