Der Alpha - Beta Algorithmus

Jetzt kommen wir zum schwierigsten Teil unseres Programmierkurses: Der Alpha - Beta Algorithmus. Der Alpha-Beta Algorithmus dient der Reduktion des Rechenaufwandes bei der Zugsuche. Diese Reduktion wird es unserem Schachprogramm erlauben, in vernüftiger Zeit auf 4 Halbzüge zu rechenen.

Der Alpha - Beta Algorithmus ist eine weiterentwicklung des Minimax Algorithmus. Er schliesst Äste des Zubbaumes aus, die nach dem Minimax Algorithmus keine Chance haben, gewählt zu werden. Stellen wir uns folgendes Szenario vor: Der Computer berechnet den Wert eines Knoten auf Tiefe 4. Für den Knoten erhält er einen negativen Wert, d.h. dass der Computer besser steht. Auf der Tiefe 3 wird jetzt ein neuer Zug für den Computer analisiert und die daraus resultierenden Züge des menschen generiert. Der Mensch wird immer den Zug wählen, der seinen Vorteil maximiert, d.h. den Zug mit dem besten Wert. Wenn aber jetzt ein Zug einen Wert erhält, der höher ist als der Wert des Knotens, denn wir vorher berechnet haben, kann der Computer die Überprüfung der restlichen Züge des Menschen für diesen Ast abbrechen. Nach Minimax wird der Computer mit Sicherheit nicht diesen Ast wählen, da er einen möglichst Tiefen Wert will und der Wert dieses Knoten mit Sicherheit über dem des letzen Knotens liegt.

Da jetzt klar sein sollte, worum es beim Alpha - Beta Algorithmus geht, kommen wir zur konkreten implementierung für unser Schachprogramm.

Wir müssen zwei Variablen für den Algorithmus im globalen Namensbereich der Klasse Board definieren:

float alphabeta [] = new float [10]; //Alpha Beta Werte
boolean ababort = false; //Darf AlphaBeta abbrechen

Das Alpha - Beta Wertefeld muss initialisiert werden, daher muss folgender Code im Konstuktor vor dem Aufruf von newgame () stehen:

//AlphaBeta initialisieren
alphabeta [0] = -3000.0f;

Auch die Methode genmove () muss das Datenfeld für die jeweilige Tiefe initialisieren:

deep++; ababort = false;

//Mattbewertung & AlphaBeta Initialisierung
if (deep % 2 != 0) { //Zug des Computers
   minimax [deep] = 2000.0f;
   alphabeta [deep] = 3000.0f;
} else { //Zug des Menschen
   minimax [deep] = -2000.0f;
   alphabeta [deep] = -3000.0f;
}

Auch am Ende der Methode genmove () muss Code eingefügt werden, und zwar diese Linie:

ababort = false;

Am meisten ändern müssen wir die Methode simulize ():

if (ababort) //Dieser Ast wurde ausgeschlossen
   return;

//Zug simulieren
int orgstart = board [start];
int orgend = board [end];

board [end] = board [start];
board [start] = 0;

if (! ischeck ()) {
   if (deep == 1) {
      movelist [movecounter] = start * 100 + end;
      movecounter++;
   }

   //Wert dieses Knotens berechnen
   if (target == deep)
      value = evaluation ();
   else {
      if (color == 1)
         color = 2;
      else
         color = 1;

      genmove ();
      value = minimax [deep + 1];

      //ämderungen am Alphabeta Feld?
      if (deep % 2 != 0) { //Computer
         if (value < alphabeta [deep])
            alphabeta [deep] = value;
      } else { //Mensch
         if (value > alphabeta [deep])
            alphabeta [deep] = value;
      }

      if (color == 1)
         color = 2;
      else
         color = 1;
   }

   //Minimax Algorithmus
   if (deep % 2 == 0) { //Mensch Ebene
      if (value > minimax [deep] )
         minimax [deep] = value;
      //Alphabeta
      if (value > alphabeta [deep - 1])
         ababort = true;
   } else { //Computer Ebene
      if (value <= minimax [deep] ) {
         minimax [deep] = value;
         if (deep == 1)
            move = start * 100 + end;
      }
      //Alphabeta
      if (value < alphabeta [deep - 1])
         ababort = true;
   }
}

Der Rest der Methode bleibt gleich. Jetzt sind wir in der Lage, die Berechnungstiefe in der Methode run () zu erhöhen, da die Berechnung wesentlich beschleunigt wurde.

target = 4;

Damit währe der Alpha-Beta Algorithmus implementiert. Das Schachprogramm spielt bereits auf einer brauchbaren Stärke. An dieser Stelle möchten wir ihnen ein paar Anregungen geben, wie Sie die Spielstärke ihrer KI weiter erhöhen können. Die implementation dieser Anregungen währen allerdings zu viel für diesen Kurs. Zum Teil wurden diese Techniken aber im Chess Partner Applet dieser Internetseite eingesetzt. Da das Applet von uns unter die GPL Lizens gestellt wurde und daher Open Source Software ist, können Sie sich in den entsprechenden Quelltexten Hilfe holen. Unsere Vorschläge sind:

• Bauen Sie eine Eröffnungsbibliothek ein. Sie können die Eröffnungsbibliothek, die wir im Chess Partner Applet einsetzen, herunterladen und benützen.
• Optimieren Sie den Code durch
  • Aufteilen der Figurenspeicherung in drei Datenfelder für Typ, Farbe und Spezialinformationen.
  • Speichern Sie die Königsposition ab (erspart das Suchen der Könige in der ischeck () Methode)
• Verbessern Sie das positionelle Spiel, indem Sie Wertefelder für jeden Figurentyp sowohl für Weiss als auch für Schwarz anlegen

Applet Stufe 9 anzeigen
Quelltexte der Stufe 9

---

Zur Übersicht | Zurück | Weiter