Die Zugauswahl

In diesem Abschnitt kommt eine ganze Menge Arbeit auf uns zu. Am Ende des Abschnittes wird unser Schachprogramm für Schwarz ziehen. Dabei implementieren wir die Zugauswahl nach dem Minimax Algorithmus. Dieser besagt, dass jede Partei so zieht, dass ihr Vorteil maximiert und der des Gegners minimiert wird. Konkret bedeutet dass: Wenn der Compuer auf einer Tiefe ist, in der er selber zieht, nimmt der Knoten den Wert des schlechtesten Unterknoten an. Ist es eine Tiefe, in der der menschliche Spieler zieht, nimmt der Knoten den Wert des besten Unterknoten an. Negative Werte für eine Stellung bedeuten immer, das der Computer besser steht, da die Bewertung aus der Sicht des Menschen vorgenommen wird..

Zuerst müssen wir ein paar neue Variablen hinzufügen. Da es globale Variablen sind, werden sie im globalen Namensbereich der Klasse Board definiert:

Thread th = null; //Thread in dem die Berechnungen ablaufen
int deep = 0; //Gegenwärtige Tiefe
int target = 4; //Zieltiefe
float value = 0; //Wertezwischenspiecher für minimax
float minimax [] = new float [10]; //Minimax Algorithmus
int move; //Der KI Zug

Als nächstes müssen wir die Methode genmove () umschreiben. Wir fügen folgenden Code am Anfang ein:

deep++;

//Matterkennung
if (deep % 2 != 0) //Zug des Computers
   minimax [deep] = 2000.0f;
else // Zug des Menschen
   minimax [deep] = -2000.0f;

Da bei einem Matt keine weiteren Züge generiert werden, wird der Wert im Minimax Feld nicht mehr überschrieben und geht an den übergeordneten Knoten zurück. Am Ende der Methode müssen wir diese Linie einfügen:

deep--;

Damit die Zugberechnung nicht gleich das gesammte Anwenderinterface lahmlegt, erfolgt sie in einem eigenen Thread. Der Thread wird in der Methode run () definiert.. In ihr findet die Berechnung des besten Zuges für die KI statt.

//unterbinde Zugriff auf die Zugliste
code = 1;

deep = 0;
target = 2;

//besten Zug suchen
movecounter = 0;
genmove ();

if (movecounter == 0) //Keine Züge -> Spielende
{
   if (ischeck ())
      parent.getAppletContext ().showStatus ("Weiss gewinnt!");
   else
      parent.getAppletContext ().showStatus ("Das Spiel ist Remis");
   return;
}

//Gefundenen Zug ausführen
execute ( move / 100, move % 100 );

//Zugriff auf Zugliste wieder erlauben
code = 0;

Die Methode simulize () muss so umgeschrieben werden, dass sie rekursiv genmove () aufruft, bis die Zieltiefe erreicht wird. Ausserdem muss sie den Minimaxalgorithmus implementieren.

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];

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

   //Minimax Algorithmus
   if (deep % 2 == 0) {
      if (value > minimax [deep])
         minimax [deep] = value;
   } else {
      if (value < minimax [deep]) {
         minimax [deep] = value;

         if (deep == 1)
            move = start * 100 + end;
      }
   }
}

Der restliche Code der Methode bleibt gleich. Wir müssen jetzt noch die Methode execute () so umschreiben, dass sie in der Lage ist, die Zugberechnung anzustossen:

//anderer Spieler
if (color == 1) {
   color = 2;

   //besten Zug suchen
   th = new Thread (this);
   th.start ();
} else {
   color = 1;

   //gültige Züge berechnen
   movecounter = 0;
   deep = 0;
   target = 1;
   genmove ();

   if (movecounter == 0) //Keine gültigen Züge -> Spielende
   {
      if (ischeck ())
         parent.getAppletContext ().showStatus ("Schwarz gewinnt!");
      else
         parent.getAppletContext ().showStatus ("Das Spiel endet Remis!");
   }
}

Auch die Methode newgame () muss geändert werden, da sie sonst die Generierung der Zugliste nicht mehr anstossen kann:

movecounter = 0;
color = 1;
deep = 0;
target = 1;
genmove ();
code = 0;

Jetzt kann unser Schachprogramm bereits selber spielen. Allerdings ist es noch sehr langsam und berechnet nur auf 2 Halbzüge. In nächsten Abschnitt werden wir versuchen, die Geschwindigkeit des Programmes mit Hilfe des Alpha-Beta Algoritms stark zu verbessern, so dass das Programm auf 4 bis 6 Halbzüge rechnen kann.

Applet Stufe 8 anzeigen
Quelltexte der Stufe 8

---

Zur Übersicht | Zurück | Weiter