Um gute Spieler zu programmieren, müssen wir statt zufälligen sinnvolle Züge aus den gültigen auswählen. Diese Auswahl ist der Kern der in diesem Kapitel vorgestellten Algorithmen, die wir im folgenden schrittweise entwickeln.
In einfachen Spielen können wir alle Zugmöglichkeiten systematisch überprüfen, indem wir (ähnlich wie beim Backtracking) alle Folgezüge durchsuchen, bis das Spiel beendet ist. Dadurch entsteht eine Baumstruktur, an deren Blättern beendete Spiele stehen. Jeder innere Knoten verzweigt entsprechend der in diesem Zustand gültigen Züge.
Statt bei jeder Verzweigung Kopien der Spielzustände anzulegen, wollen wir das Spiel-Objekt mutieren. Dazu müssen Spiele neben der Methode make_move eine Methode undo_move definieren, die einen übergebenen Zug rückgängig macht. Dann können Züge probeweise mit make_move ausgeführt und vor dem Ausprobieren weiterer Züge mit undo_move wieder rückgängig gemacht werden.
Für das (vereinfachte) Nim-Spiel definieren wir die Methode undo_move wie folgt.
def undo_move(self, number):
self.count = self.count + number
Die im übergebenen Zug herunter genommen Streichhölzer werden hier also wieder auf den Haufen drauf gelegt.
Verglichen mit Backtracking kommt bei Spielbäumen erschwerend hinzu, dass zwei Spieler mit unterschiedlichen Zielen gegeneinander antreten. Was für den einen Spieler ein günstiger Zug ist, ist für den anderen Spieler ein ungünstiger. Beide Spieler versuchen, Züge so auszuwählen, dass sie ein möglichst gutes Ergebnis erzwingen können. Ist kein Sieg erzwingbar, kann möglicherweise zumindest ein Unentschieden gesichert werden, um eine Niederlage zu vermeiden.
Für Spiele im Endzustand können wir diese drei Ergebnisse als Zahl (1 für einen Sieg, 0,5 für ein Unentschieden und 0 für eine Niederlage) ausdrücken.
Wir verwenden Zahlen zwischen Null und Eins,
um bei Bewertungen einfach die Perspektive wechseln zu können.
Ist e die Bewertung einer Spielsituation aus Sicht des einen Spielers,
dann ergibt sich eine Bewertung aus Sicht des anderen Spielers als 1-e.
Kann der Gegner einen Sieg erzwingen, ist uns eine Niederlage sicher (und umgekehrt).
Alternativ könnten wir beliebige Zahlen erlauben und diese beim Perspektivwechsel negieren.
Unsere Wahl erlaubt die Interpretation der Bewertung als Gewinnwarscheinlichkeit.
Zur Berechnung dieser Bewertung (aus Sicht des Spielers, der an der Reihe ist) fügen wir der Klasse Game die folgende Methode hinzu.
def eval_on_end(self):
if self.winner() == None: # draw
return 0.5
if self.current_player is self.winner():
return 1.0
return 0.0
Wir definieren nun eine Klasse SearchingPlayer für Spieler, die den Spielbaum systematisch bis zum Ende durchsuchen. Die vier ersten Methoden können später von Unterklassen überschrieben werden, um die Suche zu beeinflussen.
class SearchingPlayer(Player):
def make_move(self, move, count):
self.game.make_move(move)
self.game.next_turn()
def undo_move(self, move, count):
self.game.undo_move(move)
self.game.next_turn()
def should_stop(self):
return self.game.has_ended()
def eval_on_stop(self):
return self.game.eval_on_end()
# weitere Definitionen folgen
In der Klasse SearchingPlayer sind die gezeigten Methoden durch bereits besprochene Methoden auf Spielen implementiert. Die teilweise abweichenden Namen und Parameter klären wir später.
Zur Definition der Methode select_move definieren wir zunächst gegenseitig rekursive Hilfsmethoden zur Bewertung von Spielzügen und Spielzuständen.
Die Methode eval_move berechnet die Bewertung eines Zuges anhand der aus diesem Zug resultierenden Spielsituation.
def eval_move(self, moves, index):
self.make_move(moves[index], len(moves))
eval = 1 - self.eval_by_search()
self.undo_move(moves[index], len(moves))
return eval
Hier werden die oben definierten Methoden make_move und undo_move aufgerufen,
denen neben dem Spielzug auch die Anzahl aller verfügbaren Spielzüge übergeben wird,
die wir uns später zunutze machen.
Die Bewertung der Spielsituation nach Ausführung des Zuges erfolgt mit der Methode eval_by_search,
die wie folgt definiert ist.
Da ihr Ergebnis aus Sicht des anderen Spielers zu interpretieren ist,
berechnen wir eine Bewertung aus der Sicht des ursprünglich ziehenden Spielers
mit Hilfe der oben erwähnten Subtraktion von Eins.
def eval_by_search(self):
if self.should_stop():
return self.eval_on_stop()
moves = self.game.valid_moves()
best_eval = -1
for index in range(0, len(moves)):
eval = self.eval_move(moves, index)
if eval > best_eval:
best_eval = eval
return best_eval
Diese Methode berechnet eine Bewertung mit eval_on_stop,
wenn die Suche beendet werden soll und liefert ansonsten die
(rekursiv mit eval_move berechnete)
bestmögliche Bewertung zurück, die durch gültige Züge erreichbar ist.
Die Definition der Methode select_move ähnelt der von eval_search,
liefert aber einen Spielzug zurück und keine Bewertung.
Außerdem wird die rekursive Suche nur gestartet,
wenn es überhaupt mehrere Züge zur Auswahl gibt.
def select_move(self):
moves = self.game.valid_moves()
if len(moves) == 1:
return moves[0]
best_eval = -1
best_move = None
for index in range(0, len(moves)):
eval = self.eval_move(moves, index)
if eval > best_eval:
best_eval = eval
best_move = moves[index]
return best_move
Falls es nur einen einzigen gültigen Zug gibt, wird dieser zurück gegeben. Ansonsten werden alle gültigen Züge der Reihe nach durchsucht. Für jeden Zug wird eine Bewertung berechnet, und am Ende wird der Zug mit der höchsten Bewertung zurück gegeben.
Der von den Methoden eval_move und eval_by_search implementierte Algorithmus berechnet den bestmöglichen Ausgang unter der Annahme, dass beide Spieler versuchen, ihre eigene Bewertung zu maximieren.
Wenn wir nun eine Instanz der Klasse SearchingPlayer im Nim-Spiel gegen einen zufälligen Spieler antreten lassen, sollte in der Regel der zufällige Spieler verlieren. Hier ist eine entsprechende Beispielausgabe.
>>> alice = SearchingPlayer("Alice")
>>> bob = RandomPlayer("Bob")
>>> SimpleNim(alice, bob, 21).play()
21 matches, Alice's turn
20 matches, Bob's turn
17 matches, Alice's turn
16 matches, Bob's turn
13 matches, Alice's turn
12 matches, Bob's turn
11 matches, Alice's turn
9 matches, Bob's turn
7 matches, Alice's turn
5 matches, Bob's turn
4 matches, Alice's turn
1 matches, Bob's turn
0 matches, Alice won
Für größere Streichholzhaufen können wir beobachten, dass die Suche nach dem besten Zug sehr lange dauert.
Für komplexe Spiele ist es nicht praktikabel, den Spielbaum vollständig zu durchsuchen. Es ist daher üblich, Zugfolgen nicht bis zum Ende sondern nur bis zu einer bestimmten Tiefe im Baum zu verfolgen. Die Klasse LimitingPlayer definiert dazu ein Attribut limit für die maximale Anzahl von Verzweigungen, die bei einer durchsuchten Zugfolge durchlaufen werden dürfen.
class LimitingPlayer(SearchingPlayer):
def __init__(self, name, limit):
super().__init__(name)
self.limit = limit
# weitere Definitionen folgen
Um die Suchtiefe wie beschrieben zu beschränken, überschreiben wir die Methode should_stop wie folgt.
def should_stop(self):
return self.limit == 0 or super().should_stop()
Da die Suche nun möglicherweise bei einem Spiel abbricht, das noch nicht beendet ist, müssen wir die Methode eval_on_stop so anpassen, dass sie auch mit nicht beendeten Spielen zurecht kommt.
def eval_on_stop(self):
if self.game.has_ended():
return self.game.eval_on_end()
return random()
Falls das Spiel beendet ist, rufen wir die dafür ausgelegte Implementierung der Oberklasse auf und geben ihr Ergebnis zurück. Falls nicht, geben wir eine zufällige Bewertung zwischen Null und Eins zurück. Für Spiele, für die wir eine spezialisierte Bewertungsfunktion angeben können, können wir eine Unterklasse von LimitingPlayer definieren, in der wir die Methode eval_on_stop überschreiben.
Die Methoden make_move und undo_move überschreiben wir so, dass das Attribut limit manipuliert wird, wenn es Alternativen zum übergebenen Zug gibt.
def make_move(self, move, count):
super().make_move(move, count)
if count > 1:
self.limit = self.limit - 1
def undo_move(self, move, count):
super().undo_move(move, count)
if count > 1:
self.limit = self.limit + 1
Mit diesen Definitionen, implementieren die geerbten Methoden eval_move und eval_by_search die beschriebene tiefenbeschränkte Suche. Wir können damit eine weitere Simulation des Nim-Spiels starten.
>>> alice = LimitingPlayer("Alice", 10)
>>> bob = RandomPlayer("Bob")
>>> SimpleNim(alice, bob, 42).play()
42 matches, Alice's turn
41 matches, Bob's turn
38 matches, Alice's turn
35 matches, Bob's turn
34 matches, Alice's turn
33 matches, Bob's turn
30 matches, Alice's turn
29 matches, Bob's turn
26 matches, Alice's turn
23 matches, Bob's turn
21 matches, Alice's turn
18 matches, Bob's turn
17 matches, Alice's turn
16 matches, Bob's turn
14 matches, Alice's turn
13 matches, Bob's turn
10 matches, Alice's turn
9 matches, Bob's turn
7 matches, Alice's turn
5 matches, Bob's turn
2 matches, Alice's turn
1 matches, Bob's turn
0 matches, Alice won
Trotz der beschränkten Suchtiefe gelingt es Alice am Ende gegen den zufälligen Spieler Bob zu gewinnen.
Bei geschickter Protokollierung von Zwischenergebnissen, gibt es noch mehr Potential, die Suche im Spielbaum vorzeitig abzubrechen. Bei der Suche im Spielbaum speichern wir als Zwischenergebnis den Wert best_eval für die beste bisher gefundene Bewertung. Rekursive Aufrufe speichern entsprechende Werte für uns und den Gegner. Aus diesen Werten ergeben sich Grenzen für solche Bewertungen, die für die Suche interessant sind. Bewertungen, die unterhalb dem bisher gefundenen besten Wert liegen, sind uninteressant, weil sie weniger Erfolg versprechen als ein bereits gefundener Zug. Statt dem niedrigeren Wert können wir gefahrlos den bisher besten gefundenen Wert zurückgeben, ohne das Ergebnis der Suche zu beeinflussen, denn der beste Wert wird nur bei einem noch besseren Wert angepasst.
Interessanterweise lässt sich auch eine Obergrenze für interessante Bewertungen angeben. Bewertungen, die oberhalb der Obergrenze liegen, sind uninteressant, wenn der Gegner bereits eine Möglichkeit gefunden hat, uns eine niedrigere Bewertung aufzuzwingen. Die Obergrenze ergibt sich also aus der bisherigen besten Bewertung des Gegners. Sobald uns eine Zugmöglichkeit zur Verfügung steht, die die Obergrenze überschreitet, können wir die Suche abbrechen, weil wir davon ausgehen können, dass der Gegner den vorherigen Zug, der uns diese Möglichkeiten bescherte, nicht auswählen wird. Statt des größeren Wertes können wir gefahrlos die übergebene Obergrenze zurück liefern, ohne das Ergebnis der Suche zu verändern, weil der Gegner einen bisher gefundenen Wert nur anpasst, wenn er uns eine noch niedrigere Bewertung aufzwingen kann.
Die Klasse PruningPlayer überschreibt die Methoden eval_move und eval_by_search unter Verwendung zusätzlicher Parameter für die besprochenen Grenzen.
class PruningPlayer(LimitingPlayer):
def eval_move(self, moves, index, min, max):
self.make_move(moves[index], len(moves))
eval = 1 - self.eval_by_search(min, max)
self.undo_move(moves[index], len(moves))
return eval
def eval_by_search(self, min, max):
if self.should_stop():
return self.eval_on_stop()
moves = self.game.valid_moves()
best_eval = min
for index in range(0, len(moves)):
if best_eval >= max:
return best_eval
eval = self.eval_move(moves, index, 1 - max, 1 - best_eval)
if eval > best_eval:
best_eval = eval
return best_eval
# weitere Definition folgt
In der Definition von eval_move wurden die Parameter min und max hinzugefügt,
um sie an eval_by_search weiterreichen zu können.
Die Definition von eval_by_search enthält neben den zusätzlichen Parametern eine bedingte Rückgabeanweisung im Schleifenrumpf, die die Suche wie oben diskutiert vorzeitig beendet.
Im rekursiven Aufruf wird als Obergrenze für den Gegner die umgekehrte bisher beste eigene Bewertung übergeben. Analog dazu wird als Untergrenze die umgekehrte Obergrenze verwendet, die dem bisher besten gefundenen Zug des Gegners entspricht.
Die neue Implementierung von select_move unterscheidet sich von der ursprünglichen nur durch den Aufruf von eval_move mit zusätzlichen Argumenten.
def select_move(self):
moves = self.game.valid_moves()
if len(moves) == 1:
return moves[0]
best_eval = -1
best_move = None
for index in range(0, len(moves)):
eval = self.eval_move(moves, index, -1, 1 - best_eval)
if eval > best_eval:
best_eval = eval
best_move = moves[index]
return best_move
Als Bereichsgrenzen übergeben wir solche außerhalb der berechneten Bewertungen. Die Untergrenze ist so klein, dass sie durch den ersten gefundenen Zug angehoben wird. Die Obergrenze ist so groß, dass sie durch den ersten gefundenen Zug des Gegners abgesenkt wird.
Nach diesen Anpassungen liefert die neue Implementierung von select_move den gleichen Zug wie die ursprüngliche. Dabei werden weniger Zugfolgen betrachtet als mit der ursprünglichen Implementierung, weil Teile des Spielbaums, die das Ergebnis nicht beeinflussen, nicht durchlaufen werden. Instanzen der Klasse PruningPlayer verhalten sich also wie Instanzen von LimitingPlayer, berechnen ihren Zug aber schneller. Die Suche ist weiterhin tiefenbeschränkt, und spezialisierte Implementierungen von eval_on_stop können in Unterklassen definiert werden.