Der Minimax-Algorithmus

   Der Minimax-Algorithmus ist zwar der ineffektivste, aber dafür der einfachste Algorithmus zur Zug-Auswahl. Er probiert einfach alle Möglichkeiten bis zu einer bestimmten Suchtiefe durch.

   Der Namensgebung Minimax liegt eine Besonderheit der Stellungsbewertung zugrunde: Schachprogramme bewerten die Stellung mit ganzen (selten reelen) Zahlen. Die Bewertung mit Null steht für eine ausgeglichene Stellung. Positive Zahlen repräsentieren einen Stellungsvorteil von Weiß, negative Zahlen einen von Schwarz. D.h. um so größer der Wert der Stellungsbewertung, desto größer der Vorteil für Weiß und um so kleiner der Wert der Stellungsbewertung, desto größer der Vorteil von Schwarz. Im Klartext: Weiß versucht die Stellungsbewertung zu maximieren und Schwarz versucht sie zu minimieren.

   Der Minimax-Algorithmus läßt sich auf einfache Weise rekursiv programmieren. Für ihn ist unten ein Pseudocode angegeben.

Konventionen: beim ersten Aufruf enthält Depth erhält den Wert eins, MaxDepth einen Wert größer oder gleich eins und Color erhält je nach Anzugsrecht den Wert der Konstanten White oder Black.

Prozeduren: EvaluatePosition bewertet eine auf dem internen Brett befindliche Stellung und GenerateMoves ermittelt die möglichen Züge. MoveForward und MoveBack ziehen intern Züge vor bzw. zurück.

  Const White      =      1;
        Black      =     -1;

        MaxInteger =  32767;
        MinInteger = -32768;

  Function MiniMax (Color, Depth, MaxDepth : Integer) : Integer; 
  var Value, MaxValue ,
             MinValue : Integer;

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

    else begin
       MinValue = MaxInteger;
       MaxValue = MinInteger;

       GenerateMoves(Color, MoveList);

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

               Value := MiniMax (-Color, Depth +1, MaxDepth);

               if Color = White then
                  if Value > MaxValue then MaxValue := Value;

               if Color = Black then
                  if Value < MinValue then MinValue := Value;

           MoveBack (Move);
       end;

       if Color = White then MiniMax := MaxValue
                        else MiniMax := MinValue;
    end;      
  end;

   Die Vorgehensweise ist recht einfach: zuerst wird überprüft, ob die maximale Rechentiefe erreicht ist. Ist dies der Fall, so wird die vorliegende Endposition bewertet. Ist die maximale Rechentiefe noch nicht erreicht, so werden MinValue und MaxValue zunächst auf die denkbar schlechtesten Werte gesetzt. MinValue für Schwarz auf einen sehr großen Wert und MaxValue für Weiß auf einen klitzekleinen Wert.

   Es sei erwähnt, dass wir innerhalb einer Rekursionsebene eigentlich immer nur einen dieser beiden Werte wirklich benötigen. Das gilt auch bei den Vergleichen mit MaxValue und bei der Funktionswert-Rückgabe.

   Nach der Initialisierung werden die möglichen Züge mit GenerateMoves ermittelt und in der nachfolgenden Schleife durchprobiert. Durch den rekursiven Aufruf werden automatisch alle Varianten nach einem probierten Zug untersucht. Das Ergebnis wird in Value festgehalten.

   Die nachfolgenden Verzweigungen sind klar: werden in der aktuellen Rekursionsebene weiße Züge untersucht (Color=White), so wird maximiert, sonst minimiert. Die bisher beste Bewertung wird in MaxValue oder MinValue gespeichert, und am Ende zurückgegeben (je nachdem).

Beispiel: Der unten dargestellte Baum veranschaulicht die Funktionsweise des Minimax-Algorithmus.

Anmerkungen:

  • Vielleicht wird sich jemand fragen, wo denn die Ruhesuche bleibt. Die Antwort ist: diese kann ohne weiteres in der Funktion EvaluatePosition enthalten sein. Wir können also zunächst einmal von der Vertiefung abstrahieren.
  • Der oben vorgestellte Algorithmus sollte sich den besten Zug natürlich auch merken.

© André Heuner, 1999