Оригинал взят с http://www.zib.de/reinefeld/nsc.html

Нега-скаут (NegaScout)

Подобно AlphaBeta, NegaScout - направленный алгоритм поиска для вычисления минимаксного значения узла.

NegaScout эффективнее AlphaBeta: он никогда не исследует узла, который может быть отсечен AlphaBeta.

Ни NegaScout не превосходит SSS*, ни наоборот: Существуют деревья, в которых NegaScout ищет строго меньшее количество узлов чем SSS* и наоборот. На среднестатистических деревьях, однако, SSS* обычно просматривает меньшее количество узлов чем NegaScout.
Тот же самое относится к DUAL*.
Формальные доказательства могут быть найдены в: A. Reinefeld. Spielbaum-Suchverfahren. Informatik-Fachbericht 200, Springer-Verlag, Берлин (1989), ISBN 3-540-50742-6

C-подобный код:

int NegaScout ( position p; int alpha, beta );
{ /* вычислить минимаксное значение позиции p */
   int a, b, t, i;

   determine successors p_1,...,p_w of p;
   if ( w == 0 )
      return ( Evaluate(p) ); /* лист дерева */
   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 ); /* повторный перебор */
      a = max( a, t );
      if ( a == beta )
         return ( a ); /* отсечение */
      b = a + 1; /* установить новое нулевое окно */
   }
   return ( a );
}

© 1999 Konrad-Zuse-Zentrum fur Informationstechnik Berlin (ZIB)
© Перевод с английского - С. Марков, 2000