NegaScout - A Minimax Algorithm faster than AlphaBeta

--------------------------------------------------------------------------------

Like AlphaBeta, NegaScout is a directional search algorithm for computing the minimax value of a node.

NegaScout dominates AlphaBeta: It never examines a node that can be pruned by AlphaBeta.
Neither does NegaScout dominate SSS* nor vice versa: There exist trees in which NegaScout searches strictly fewer nodes than SSS* and vice versa. On averagely ordered trees, however, the best-first procedure SSS* usually searches less nodes than NegaScout.
The same applies to DUAL*.
The formal proofs can be found in: A. Reinefeld. Spielbaum-Suchverfahren. Informatik-Fachbericht 200, Springer-Verlag, Berlin (1989), ISBN 3-540-50742-6


--------------------------------------------------------------------------------

C Code: PRELIMINARY

int NegaScout ( position p; int alpha, beta );
{ /* compute minimax value of position p */
   int a, b, t, i;

   determine successors p_1,...,p_w of p;
   if ( w == 0 )
      return ( Evaluate(p) ); /* leaf node */
   a = alpha;
   b = beta;
   for ( i = 1; i <= w; i++ ) {
      t = -NegaScout ( p_i, -b, -a );
      if (t > a) && (t < beta) && (i > 1) && (d < maxdepth-1)
         a = -NegaScout ( p_i, -beta, -t ); /* re-search */
      a = max( a, t );
      if ( a == beta )
         return ( a ); /* cut-off */
      b = a + 1; /* set new null window */
   }
   return ( a );
}

--------------------------------------------------------------------------------

© 1999 by Konrad-Zuse-Zentrum fur Informationstechnik Berlin (ZIB)
URL: http://www.zib.de/reinefeld/nsc.html