Unterabschnitte
Es wird immer (LC-Methode) der Knoten expandiert, der momentan den optimalsten Wert hat. So ist sichergestellt, daß stets der kürzeste Weg dorthin verwandt wird.
Beim 15er-Puzzle ist es jedoch möglich, daß eine Konfiguration nicht in Zielkonfiguration zu bringen ist. Der Spielgraph besteht aus zwei unzusammenhängenden starken Zusammenhangskomponenten.
Es wird immer angenommen, daß der Gegner den besten möglichen Zug macht, also den für einen am schlechtesten.
Es wird ein Baum mittels Backtracking bis zu einer bestimmten Tiefe erstellt. Auf dieser Tiefe werden die Konfigurationen bewertet. Ist der darüberliegende Knoten ein MAX-Knoten, d.h. der Spieler selbst ist am Zug, so wird der Knoten mit dem größten Wert unter den Brüdern für den MAX-Knoten verwandt, um den größtmöglichen Gewinn zu haben.
Ist es ein MIN-Knoten, so wird der Knoten mit dem geringsten Wert genommen. Dies entspricht dem Wort-Case, daß der Gegner genau den für einen schlimmsten Zug macht. Kommen wir zur Wurzel des Baumes, einem MAX-Knoten, so nehmen wir dann den Weg mit dem größten Gewinn.
Mittels
-
-Pruning können wir Knoten abschneiden, die sowieso schon übertrumpft oder untertrumpft sind.
Z.B. ist in einer Reihe von MINKNOTEN einer dieser Knoten maximal. Wenn durch Überprüfung der Ebene unter dem MIN-Knoten festgestellt wird, daß dort ein Knoten minimaler als schon der gefundene maximale Wert des MIN-Knoten ist, können wir diesen Knoten gleich wegschneiden.
Spielbäume
Für manche Spiele läßt sich der Spielbaum vollständig konstruieren. Für viele Spiele ist diesr jedoch zu groß. Man verwendet deshalb eine Pay-Off-Funktion, die die Güte einer Konfiguration berechnet und nach dieser Güte über den kommenden Spielzug entscheidet.15er-Puzzle
Die Güte der Konfiguration wird berechnet mit
Anzahl der Plättchen, die an falscher Stelle sind + Baumtiefe (Anzahl schon verschobener Plättchen)
Je höher dieser Wert ist, desto schlechter ist es.
Es wird immer (LC-Methode) der Knoten expandiert, der momentan den optimalsten Wert hat. So ist sichergestellt, daß stets der kürzeste Weg dorthin verwandt wird.
Beim 15er-Puzzle ist es jedoch möglich, daß eine Konfiguration nicht in Zielkonfiguration zu bringen ist. Der Spielgraph besteht aus zwei unzusammenhängenden starken Zusammenhangskomponenten.
Tic-Tac-Toe
Die Pay-Offfunktion berechnet
Anzahl der möglichen Reihen des eigenen Spielers
Anzahl der möglichen Reihen für den Gegner
Je höher dieser Wert ist, desto besser.
Anzahl der möglichen Reihen für den Gegner
Es wird immer angenommen, daß der Gegner den besten möglichen Zug macht, also den für einen am schlechtesten.
Es wird ein Baum mittels Backtracking bis zu einer bestimmten Tiefe erstellt. Auf dieser Tiefe werden die Konfigurationen bewertet. Ist der darüberliegende Knoten ein MAX-Knoten, d.h. der Spieler selbst ist am Zug, so wird der Knoten mit dem größten Wert unter den Brüdern für den MAX-Knoten verwandt, um den größtmöglichen Gewinn zu haben.
Ist es ein MIN-Knoten, so wird der Knoten mit dem geringsten Wert genommen. Dies entspricht dem Wort-Case, daß der Gegner genau den für einen schlimmsten Zug macht. Kommen wir zur Wurzel des Baumes, einem MAX-Knoten, so nehmen wir dann den Weg mit dem größten Gewinn.
Mittels
--Pruning können wir Knoten abschneiden, die sowieso schon übertrumpft oder untertrumpft sind.
Z.B. ist in einer Reihe von MINKNOTEN einer dieser Knoten maximal. Wenn durch Überprüfung der Ebene unter dem MIN-Knoten festgestellt wird, daß dort ein Knoten minimaler als schon der gefundene maximale Wert des MIN-Knoten ist, können wir diesen Knoten gleich wegschneiden.
| -cut: |
Cutting der Söhne eines MAX-Knotens |
| -cut: |
Cutting der Söhne eines MIN-Knotens |