Gute Züge bei 2 Personen Nullsummen Spielen mit vollständiger Information

Worum geht's

Gute Züge sind solche, die zum Gewinn führen. 2 Personen ist wohl klar. :-) Nullsumme bedeutet: des einen Spielers Gewinn ist des andern Spielers Verlust. Vollständige Information bedeutet: beide Spieler haben vollständige Kenntnis über die aktuelle Spielsituation.

Nim, TicTacToe, 4Gewinnt, Reversi, Kalaha, Dame, Mühle, Schach, Backgammon usw. sind solche Spiele. Aus unterschiedlichen Gründen gehören Poker, Bauernskat oder Roulett (egal ob russisch oder nicht) jedoch nicht zu dieser Gruppe.

Es wird mit Varianten der MiniMax- und AlphaBeta Alogrithmen, mit und ohne Hashtables, Zugsortierung usw. experimentiert. Beide Verfahren und ihre Erweiterungen sind spielunabhängig und lassen sich für alle Spiele dieser Art verwenden. Sie unterscheiden sich jedoch erheblich im Aufwand für die Suche, wie die untere Tabelle am Beispiel TicTacToe zeigt.

Laufzeitverhalten für Suchverfahren für TicTacToe.
Suchverfahren untersuchte Stellungen für den ersten Zug 1000 untersuchte Stellungen pro Sekunde (10 Tests)
MiniMax 549945 4619 - 5138
NegaMiniMax 549945 4553 - 5145
AlphaBeta 18296 2477 - 2619
NegaAlphaBeta 18296 1947 - 2559
NegaAlphaBeta mit Zugsortierung 7955 687 - 1217
NegaAlphaBeta mit Zugsortierung und Transpositions Hashtable 3300 248 - 400

Bei Laufzeiten um 0,1 Sekunden und weniger spielen andere Aufgaben, mit denen sich der Rechner beschäftigt, eine zu große Rolle und verursachen die Geschwindigkeitsschwankungen. Jeder zusätzliche Aufwand bei der Suche senkt natürlich die Anzahl der pro Sekunde berechneten Stellungen. Andererseits sinkt die Anzahl der Stellungen, die bei gleicher Ergebnisqualität überhaupt berechnet werden, beträchtlich.