🚀 go-pugleaf

In article <CrEqDI.BGv@microsoft.com> brucemo@microsoft.com (Bruce Moreland) writes:

> 
> 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-spencer@retix.com |
     + ------------------------+