nega-scout in gnuchess
Bruce Moreland
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
David Spencer
>
> 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}.
>
> ...
>
>
> I've seen nega-scout called other things. I think one other
> name is PVS, which stands for "principle variation search".
>
You know, I thought what you're describing is called "minimal window
search" and nega-scout is yet something else. I also thought that
at one point when I looked at the code it was indeed doing this.
Also, one related idea is that at the top level you don't search
subsequent moves with {-alpha-1,-alpha} but rather something like
{-alpha-(PAWN/2),-alpha} so that moves can fail high "a little"
(i.e. (PAWN/2) here) w/o causing a re-search.
--
+ ------------------------+
| David Spencer |
| david-...@retix.com |
+ ------------------------+
Chua Kong Sian
: Why doesn't GnuChess use nega-scout instead of alpha-beta?
: bruce
Gnuchess does implement PVS/nega-scout since PL63.
Kong Sian