Vorschau

Hier wollen wir uns mit folgenden Fragen befassen:

• Was bedeutet das "(book)" hinter den Wertungszahlen bei WZebra?
• Was besagt die Wertungszahl vor dem "(book)"?
• Warum steht bei mir -4 obwohl die Eröffnung angeblich zu einem 31-33 führen soll?

Es geht eigentlich allgemein um Eröffnungsbücher bei Othello-Programmen und eigentlich generell bei Programmen die Eröffnungsbiblitoheken für 2-Spieler-Strategiespiele anlegen. Um dies zu veranschaulichen, werden wir aber vorrangig WZebra betrachten.

Min-Max-Algorithmus

Hier ganz kurz erklärt wie die Wertungszahl aus einem Baum abgelesen wird. Bei Wikipedia findet man diesen Algorithmus ausführlicher beschrieben und wir verwenden auch das Wikipedia-Beispiel. http://de.wikipedia.org/wiki/Minimax-Algorithmus

In Diagramm 1 sehen wir einen Baum, der auf dem Kopf steht. Oben befindet sich die "Wurzel". Die Kanten stehen jeweils für einen Zug. Dies sind die "Äste" oder "Zweige". Die Knoten, die hier mit ganzen Zahlen dargestellt sind, stehen für eine Position. Die Zahlen stehen für die Bewertung der Position. Die untersten Knoten sind die "Blätter". Die Blätter sind genau wie all die anderen Knoten, nur dass von dort aus keine weiteren Kanten abgehen, d.h. keine weiteren Züge betrachtet werden.

Nehmen wir zur Vereinfachung einmal an, wir sind bei Ebene 1 in einem Othello-Endspiel mit drei leeren Feldern. Zu Ebene 2 führen zwei Kanten, also es gibt zwei mögliche Züge für uns (Weiß). Um MinMax zu verstehen müssen wir aber unten anfangen. Schauen wir uns auf Ebene vier die letzten beiden Blätter an, -1 und +4. Wir haben den letzten Zug, wählen also den maximalen Wert, +4. Deshalb bewerten wir den rechten Knoten in Ebene 3 mit +4. Aus demselben Grund steht in der Ebene 3 an zweiter Stelle von rechts die +7. Eine Ebene höher, also jetzt bei zwei leeren Feldern ist unser Gegner dran. Der hat die Wahl zwischen einer Position, die für uns als +4 und einer Position, die für uns als +7 bewertet wird. Er nimmt natürlich den minimalen Wert. Deshalb steht in der Ebene 2 als rechter Knoten die +4. Da wir in Ebene 1 selbst dran sind, wählen wir natürlich den besten und damit ist die Position mit +4 zu bewerten.

Mit diesem Verfahren kann man im Endspiel ganz genau ausrechnen, welcher Zug am besten ist (perfektes Spiel vorausgesetzt). Wenn der Computer aber noch nicht bis zum Ende durchrechnen kann, muss er ab einer gewissen Tiefe (hier 3 Züge) abbrechen, die Blätter mit irgendeiner Funktion bewerten, und dann mit MinMax den besten Weg nehmen. Die Bewertungsfunktion gibt allerdings keinen ganzaligen sondern rationalen Wert (also mit Kommastellen). Wie genau die Bewertungsfunktion arbeitet, ist von Programm zu Programm unterschiedlich und ist nicht Thema dieses Artikels. Eine naive Bewertungsfunktion könnte die Steindifferenz (also wie im Endspiel) sein. Man könnte auch die Differenz der Anzahl der Möglichkeiten bewerten. Gute Programme benutzen aber Mustererkennung und andere Heuristiken.

Bedeutung des Wertes

Der Book-Wert gibt den Wert für die beste noch nicht gelöste Sequenz an.

Um dies zu verdeutlichen, nehmen wir noch einmal das obige Beispiel. Allerdings sind jetzt die Werte der Knoten nicht die exakten Endergebnisse, sondern Ergebnisse der Bewertungsfunktion. Die Blätter (also unterste Ebene) sind Positionen, von denen das Programm anfangen kann, das Endgame wie oben beschrieben vollständig zu lösen, bzw. heraus zu finden, wer gewinnt.

Lassen wir unser Programm jetzt die bisher beste Sequenz durchspielen, also die Position vom rechten Blatt, welches mit +4 bewertet wurde, vollständig ausrechnen. Nehmen wir an, die Bewertungsfunktion lag richtig und es gibt einen Sieg für uns. Damit ist das rechte Blatt mit "Sieg" oder anders ausgedrückt mit "plus unendlich" bewertet. WZebra addiert für einen Sieg einfach mal 32000 Punkte, Ntest addiert 100 Punkte.

In Diagramm 2 sehen wir, dass durch das Wissen über den Sieg beim rechten Blatt, der Wert für die Position in Ebene 1 auf +7 steigt.

Der Book-Wert gibt den Wert für die beste noch nicht gelöste Sequenz an.

Die +7 in Ebene 1 sagt also nicht, dass das Endergebnis +7 sein sollte. Das beste, was der Gegner erreichen könnte, ist wahrscheinlich die knappe Niederlage, die wir zuerst gespielt haben. Wenn er aber nicht verlieren möchte, muss er zu dem +7 Blatt spielen und hoffen, dass die Bewertungsfunktion sich irrt. Schauen wir uns an, wie die Wertung sich ändert, wenn wir auch den +7-Weg ausrechnen. Nehmen wir dafür an, dass dies auch ein Sieg für uns ist.

Nun ist die Position in Ebene 1 als sicherer Sieg errechnet. Anders ausgedrück: Egal was der Gegner macht, wir können mit den richtigen Zügen auf jeden Fall einen Sieg erzwingen. Das wir dies mit nur zwei Spielen beweisen konnten, obwohl wir doch 8 Blätter haben, liegt daran, dass unser Gegner nur einmal rankommt und nur eine Wahl zwischen zwei Zügen hat. Nun wird die Position vor Ebene 1 mit dem nächstbesten Wert der anderen Züge genommen, denn zur Position in Ebene 1 möchte der Gegner lieber nie spielen.

Nehmen wir an, unsere Bewertungsfunktion gibt zwar +7 für das Blatt in der zweiten Sequenz, allerdings findet das Programm beim exakten Berechnen heraus, dass wir an diesem Blatt das Spiel verlieren. Das Ergebnis sehen wir in Diagramm 4.

Der Wert für Ebene 1 ist also auf +6 gesunken. Was passiert nun, wenn wir den +6-Weg weiter verfolgen, und dieser sich auch als Niederlage herausstellt?

Nun ist der Wert für Ebene 1 sogar auf -2 gefallen.