Information Technology Reference
In-Depth Information
In der Methode
execute()
wird die Zugberechnung veranlasst:
if (color == 1) {
color = 2;
th = new Thread(this);
th.setPriority(10);
th.start();
} else {
color = 1;
movecounter = 0;
deep = 0;
target = 1;
generateMove();
if (movecounter == 0)
{
if (isCheckmate()) {
applet.getAppletContext().showStatus("Black ins!");
}
else {
applet.getAppletContext().showStatus("Game draw!");
}
}
}
Mit dieser Implementierungssequenz ist das Schachsystem bereits in der Lage, zu spielen.
Allerdings ist es noch sehr langsam und berechnet nur auf 2 Halbzüge. Alternativ zur
MinMax-Methode kann mit Hilfe des Alpha-Beta-Algorithmus die Geschwindigkeit stark
erhöht werden, da das Programm damit auf 4 bis 6 Halbzüge rechnen kann.
Primär dient der Alpha-Beta Algorithmus der Reduktion des Rechenaufwandes bei der
Zugsuche. Diese Reduktion wird es ermöglichen, in vernünftiger Zeit auf 4 Halbzüge
zu rechnen. Dabei ist der Alpha-Beta Algorithmus zunächst eine Weiterentwicklung des
MinMax-Algorithmus. Er schließt Äste des Zugbaumes aus, die nach dem MinMax-Algo-
rithmus keine Chance haben, gewählt zu werden.
Wenn beispielsweise der Computer den Wert eines Knotens auf Tiefe 4 berechnet und für den Kno-
ten einen negativen Wert erhält, bedeutet dies, dass der Computer im Vorteil ist. Auf der Tiefe 3 wird
jetzt ein neuer Zug für den Computer analysiert und die daraus resultierenden Züge des mensch-
lichen Gegners generiert. Der menschliche Gegner wird immer den Zug wählen, der seinen Vorteil
maximiert, d. h. den Zug mit dem besten Wert. Wenn aber jetzt ein Zug einen solchen Wert erhält,
der höher ist als der Wert des Knotens, der vorher berechnet wurde, kann der Computer die Überprü-
fung der restlichen Züge des menschlichen Gegners für diesen Ast abbrechen. Nach MinMax wird
der Computer mit Sicherheit nicht diesen Ast wählen, da er einen möglichst tiefen Wert anstrebt und
der Wert dieses Knotens mit Sicherheit über dem des letzten Knotens liegt.
Um dieses Prinzip zu implementieren, müssen zwei Variablen für den Algorithmus im
globalen Namensbereich der Klasse
Board
definiert werden:
float alphabeta[] = new float[10];// Alpha Beta
boolean ababort = false;
Das Alpha-Beta Wertefeld muss initialisiert werden, daher muss folgender Code im Kons-
truktor vor dem Aufruf von
newGame()
stehen:
