Sorry this document is currently available in German only
+-------+ |.......| |.......| Wurzel |.......| |.......| |.......| +---+---+ | +------------------+------------------+-----------------+------------------+ Äste 1. HZ +---+---+ +---+---+ | +---+---+ +---+---+ (gelb wift ein) |.......| |.......| |.......| |.......| |.......| |.......| |.......| |.......| 7 Knoten 1. HZ |.......| |.......| |.......| |.......| |.......| |.......| |.......| |.......| |X......| |.X.....| |.....X.| |......X| +---+---+ +---+---+ +--+----+ +---+---+ |1 |2 |6 |7 +--------++---- ------++---------+-- --------+-----+--+--- -----+-+---------+ Äste 2. HZ +---+---+ +---+---+ +---+---+ +---+---+ +---+---+ +--+---+ +---+---+ +---+---+ (rot wirft ein) |.......| |.......| |.......| |.......| |.......| |......| |.......| |.......| |.......| |.......| |.......| |.......| |.......| |......| |.......| |.......| 49 Knoten 2. HZ |.......| |.......| |.......| |.......| |.......| |......| |.......| |.......| |O......| |.......| |.......| |.......| |.......| |......| |.......| |......O| |X......| |XO.....| |.X.O...| |.X..O..| |..O..X.| |..O.X.| |.....OX| |......X| +---+---+ +---+---+ +---+---+ +---+---+ +---+---+ +--+---+ +---+---+ +---+---+ |1.1 |1.2 |2.4 |2.5 |6.3 |6.4 |7.6 |7.7 +--------++---------+--- ------+-+-------+---- -----+---------+--+- -----+---------+-----+---+ Äste 3. HZ +---+---+ +---+---+ +---+---+ +---+---+ +---+---+ +---+---+ +---+---+ +---+---+ +---+---+ +---+---+ (gelb wirft ein) |.......| |.......| |.......| |.......| |.......| |.......| |.......| |.......| |.......| |.......| |.......| |.......| |.......| |.......| |.......| |.......| |.......| |.......| |.......| |.......| 343 Blätter |X......| |.......| |.......| |.......| |.......| |.......| |.......| |.......| |.......| |......X| 3. HZ |O......| |O......| |O......| |...X...| |.......| |.......| |...X...| |......O| |......O| |......O| |X......| |XX.....| |X.X....| |.X.O...| |.X.OX..| |..XO.X.| |...O.X.| |....X.X| |.....XX| |......X| +-------+ +-------+ +-------+ +-------+ +-------+ +-------+ +-------+ +-------+ +-------+ +-------+ 1.1.1 1.1.2 1.1.3 2.4.4 2.4.5 6.4.3 6.4.4 7.7.5 7.7.6 7.7.7
Der Minimax-Algorithmus ist ein Verfahren aus dem Bereich der künstlichen Intelligenz, das sich für alle Spiele, an denen 2 "nicht kooperative" Spieler beteiligt sind, sog. "Nullsummenspiele", wie (Schach, Mühle, Dame, ...) eignet. Am Beispiel dieses Spieles sieht das dann wie im Baumdiagramm von Bild 1 dargestellt aus. Angenommen "Gelb" ist am Zug und der Computer soll 3 Halbzüge (1 Zug = 1 Halbzug von "Gelb" + 1 Halbzug von "Rot") im voraus prüfen: "Gelb" hat bis zu 7 Einwurfsmöglichkeiten für den 1. Halbzug. Für jede der 7 Möglichkeiten des 1. Halbzuges hat "Rot" wieder bis zu 7 Möglichkeiten für den 2. Halbzug. Es ergeben sich also nach dem 2. Halbzug bis zu 7^2 = 49 Möglichkeiten. Für jede dieser Möglichkeiten hat "Gelb" wieder bis zu 7 Einwurfsmöglichkeiten, daher ergeben sich nach dem 3. Halbzug insgesamt bis zu 7^3 = 343 zu bewertende Möglichkeiten. Jeder dieser Endstellungen (den "Blättern" des Baumdiagramms) wird ein Wert zugeordnet, der der Qualität der Stellung für "Gelb" entspricht. Für diese Bewertung sind die Anzahl und Länge der bisher erreichten Ketten maßgebend. Je 7 Möglichkeiten des 3. Halbzuges (Blätter) die aus der selben Möglichkeit des 2. Halbzuges (d. h. aus dem selben Ast) hervorgegangen sind werden zu einem "Knoten" zusammengefasst. Da der 3. Halbzug von "Gelb" ausgeführt wird, wird "Gelb" das Blatt mit dem Maximalen Wert (= günstigste Stellung für "Gelb") aussuchen. Der dazugehörige Knoten erhält also diesen Wert. Auch die 49 Möglichkeiten des 2. Halbzuges werden zu Gruppen mit je 7 Ästen zusammengefaßt, die aus dem selben Ast des 1. Halbzuges hervorgegangen sind. "Rot" wird im 2. Halbzug versuchen einen Knoten zu erreichen, von dem aus "Gelb" möglichst nicht auf eine gute Stellung gelangen kann, d. h. "Rot" wird den Knoten mit dem niedrigsten Wert aussuchen. Der dazugehörige Knoten des 2. Halbzuges erhält also diesen Wert. Im 1. Halbzug wird "Gelb" natürlich versuchen "Rot" auf eine Position zu bringen, von der aus "Rot" "Gelb" nicht auf eine schlechte Position bringen kann, d. h. "Gelb" wird den Knoten des 2. Halbzuges mit dem höchsten Wert aussuchen. Der Zug der zu diesem Knoten führt, wird ausgeführt, denn die 7 Möglichkeiten des 1. Halbzuges können nur noch zu einem Knoten, der "Wurzel" zusammengefasst werden und somit endet die Prüfung hier. Der Wert eines Knotens eines ungeradzahligen Halbzuges ist also gleich dem maximalen Wert der dazugehörigen, Knoten des nächsten Halbzuges, bzw. dem maximalen Wert der dazugehörigen Blätter falls die vorher festgelegte Zugtiefe (= Verästelung, = Anzahl der im voraus zu prüfenden Züge), erreicht wurde. Der Wert eines Knotens eines geradzahligen Halbzuges ist gleich dem minimalen Wert der dazugehörigen Knoten des nächsten Halbzuges, bzw. dem minimalen Wert der dazugehörigen Blätter. Daher der Name Minimax. Um zu vermeiden, daß z. B. "Gelb" versucht im 3. Halbzug eine Kette der Länge 5 zu erreichen, anstatt "Rot" daran zu hindern schon im 2. Halbzug eine Kette der Länge 4 zu erreichen, muß nicht nur nach dem letzten (hier dem 3.) Halbzug, sondern nach jedem Halbzug geprüft werden, ob einer der beiden Spieler schon gewonnen hat.
Der Minimax-Algorithmus läßt sich aber noch verbessern. Angenommen die Blätter 1.1.1 ... 1.1.7 wurden schon ausgewertet und dem dazugehörigen Knoten 1.1 wurde der Wert 10 zugeordnet. Wenn der Wert des Blattes 1.2.1 11 ist, dann erhält auch der dazugehörige Knoten 1.2 mindestens den Wert 11. Dieser Knoten muß also nicht mehr weiter untersucht werden, denn sein Wert könnte ja nur noch weiter steigen und "Rot" wird im 3. Halbzug den Knoten mit dem niedrigsten Wert (bisher 10) aussuchen. Dieses "nicht mehr weiter Untersuchen" eines Knotens nennt man "Alpha-Beta-Abschneidung". Auch bei den Knoten des 2. Halbzuges ist eine Alpha-Beta-Abschneidung möglich. Bei der Wurzel natürlich nicht, denn hier gibt es ja keine weiteren Knoten, die vorher ausgewertet wurden.
Christian Barmala