Zunächst sei erwähnt, daß der Nega-Scout-Algorithmus nicht zwangsläufig besser ist als der Alpha-Beta. Unter welchen Umständen er für mehr Schnitte sorgt und somit insgesamt zu einer Performance-Steigerung führt, sei im Folgenden erläutert.

   Die Idee des Nega-Scout-Algorithmus besteht darin, nach der Bewertung des ersten Unterbaumes, die analog zum Alpha-Beta-Algorithmus erfolgt, alle weiteren a-priori als unterlegen zu betrachten und eine Nullfenstersuche (d.h. setze Beta := Alpha ± 1) durchzuführen. Dadurch werden mehr Schnitte im Suchbaum vorgenommen. Kann die Unterlegenheit nicht bewiesen werden, d.h. es gab doch noch einen besseren Zug, so muß eine Wiederholungssuche mit offenem Fenster durchgeführt werden.

   Diese Vorgehensweise ist vor allem dann effektiv, wenn mit geeigneten Heuristiken sichergestellt wird, daß auch tatsächlich aussichtsreiche Züge zuerst untersucht werden. Die Ersparnis der Suche mit Nullfenster ist dann in der Regel so groß, daß der Mehraufwand gelegentlicher Wiederholungssuchen bei weitem aufgewogen wird.

   Der nachfolgend vorgestellte Algorithmus implementiert diese Idee. Die Unterschiede zum Alpha-Beta sind (bis auf die Namensgebung) blau gekennzeichnet.

Konventionen: Es gelten die gleichen Konventionen wie beim Alpha-Beta.

Prozeduren: Die zusätzlich verwendete Funktiom First soll das erste Element der Liste zurückgeben. PreHeuristic (optional) sorgt für eine grobe Vorsortierung der Züge in MoveList.

  Function NegaScout (Color, Alpha, Beta, 
                             Depth, MaxDepth : Integer) : Integer; 
  var Value : Integer;  
      Gamma : Integer; 

  begin
    if Depth = MaxDepth then 
       NegaScout := EvaluatePosition (Color)

    end else
    begin
       GenerateMoves(Color, MoveList);      
    */ PreHeuristic        (MoveList); */

       Gamma := Beta;                      

       For Each Move in MoveList do
       begin
           MoveForward (Move);

               Value := NegaScout (-Color, Gamma, Alpha,
                                           Depth +1, MaxDepth);
             
               if ( (Color *Value >  Color *Alpha) and
                    (Color *Value <  Color  *Beta) and
                    (Depth        <  MaxDepth  -1) and
                    (Move         <> First (MoveList)) ) then

                     Value := NegaScout (-Color, Beta, Value,
                                                 Depth +1, MaxDepth);
             
               if Color *Value > 
                  Color *Alpha then Alpha := Value;

           MoveBack (Move);

               if Color *Alpha >= 
                  Color  *Beta then Return Alpha;
                                   
           Gamma := Alpha +Color; 
       end;

       NegaScout := Alpha;
    end;
  end;

   Im wesentlichen ist nur der Teil für die Wiederholungssuche neu. Sie wird durchgeführt, wenn der untersuchte Zug nicht der erste war, das Ergebnis der (ersten) Suche besser als der Alpha-Wert (s.o.) aber nicht schlechter als der Beta-Wert (sonst fällt diese Variante sowieso einem Schnitt zum Opfer) und noch zwei mindestens Halbzüge bis zum erreichen der maximalen Tiefe fehlen. Bei der Wiederholungssuche kann der bessere Wert Value als neuer "Alpha"-Wert genommen werden.

Beispiel: Der unten dargestellte Baum veranschaulicht die Funktionsweise des Nega-Scout-Algorithmus. Die Zahlen an den Knoten stellen dabei die jeweils beste Bewertung für die Suchebene dar. Schnitt heißt hier, daß der Alpha-Beta ebenfalls einen Schnitt machen würde. Nullfensterschnitt ist ein zusätzlicher Schnitt des Nega-Scout.

   Würde die zweite Variante von Schwarz den zweiten Zug von Weiß nicht wiederlegen (also die Bewertungen im gelb markierten Unterbaum wären größer als sechs), so müßte der gesamte rechte Teilbaum nocheinmal durchsucht werden. Die Wiederholungssuche ist unten veranschaulicht: hier befindet sich die korrekte Bewertung sogar in dem zuvor durch die Nullfenstersuche abgeschnittenen Blatt.

An diesem kleinen Beispiel wird bereits klar: Wiederholungssuchen sind gar nicht schön. Es ist daher empfehlenswert nach der Generierung der Züge eine grobe Vorsortierung derselben vorzunehmen; sonst ist es durchaus möglich, daß der Nega-Scout langsamer wird als der Alpha-Beta (hier ist es besonders sinnvoll, die Suchtiefe sukzessiv zu erhöhen und die Züge der Ausgangsstellung zwischendurch zu sortieren; siehe auch Anmerkungen in LittleChess)

Anregungen:

• Die Vorsortierung der Züge sollte keine vollständige Sortierung sein (das wäre zu aufwendig); es reicht die Zugliste zwei- bis dreimal zu scannen und jeweils eine Klasse aussichtsreicher Züge (Schlagzüge, Zentrierung) an den Anfang der Zugliste zu befördern.
• Das Prinzip des Nega-Scout kann für eine echt selektive Zügeauswahl verschärft werden: wenn man etwa in der obersten Suchebene nach einer bestimmten Anzahl untersuchter Varianten (vielleicht zwei bis fünf) das Suchfenster nicht nur schließt, sondern sich sogar überschneiden läßt, werden noch mehr Schnitte im Suchbaum vorgenommen. Mit der Anzahl untersuchter Varianten und dem Maß der Überschneidung des Suchfensters (z.B. zwei Bauerneinheiten) kann recht variabel die Selektivität bestimmt werden. Dies ist insbesondere bei sukzessiver Erhöhung der Suchtiefe, etwa ab Tiefe drei sinnvoll.