🚀 go-pugleaf

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