🚀 go-pugleaf

Bruce Moreland (brucemo@microsoft.com) wrote:
: Why doesn't GnuChess use nega-scout instead of alpha-beta?
: Nega-scout is very simple to implement, and supposedly speeds
: up the search by about 10%.

: Here's the basic idea:

: In alpha-beta, "search" recurses with an alpha-beta window of
: {-beta, -alpha} all the time.

: In nega-scout, "search" recurses with a window of {-beta,
: -alpha} the first time it looks at a move for a given ply.
: For the rest of the moves you assume that they're not going to
: be as good as the first move you looked at, so you recurse with
: {-alpha-1, -alpha}.  If this fails high (meaning that node->score
: comes back >= alpha + 1), you try again with {-beta, -alpha}.

: The idea is that most of the time you're not going to fail
: high, so you look at fewer nodes since your window is only one
: centi-pawn wide.  You don't fail high very much because:

: 1)	You often have a "best" move from the hash table, which,
: 	although not enough is known about the move to cause a
: 	cutoff, really is the best move.

: 2)	In cases where you don't have a "best" move from the hash
: 	table, your sort key is often good enough that the first
: 	move that "pick" picks is the best one.

: It should be easy to implement this, and easy to verify that it
: does work as advertised.  If it does work as advertised, you
: get a speedup with little work and no down-side.

: I've seen nega-scout called other things.  I think one other
: name is PVS, which stands for "principle variation search".

: bruce


Gnuchess does implement PVS/nega-scout since PL63. 

Kong Sian