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*.

Formal proofs can be found in: A. Reinefeld. Spielbaum-Suchverfahren. Informatik-Fachbericht 200, Springer-Verlag, Berlin (1989), ISBN 3-540-50742-6

---

C Code
 
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 );
}