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.
| Getestete Verfahren | untersuchte Stellungen für den ersten Zug | 1000 untersuchte Stellungen pro Sekunde (10 Tests) |
|---|---|---|
| Suchen mit MiniMax | 549945 | 4619 - 5138 |
| Suchen mit NegaMiniMax | 549945 | 4553 - 5145 |
| Suchen mit AlphaBeta | 18296 | 2477 - 2619 |
| Suchen mit NegaAlphaBeta | 18296 | 1947 - 2559 |
| Suchen mit NegaAlphaBeta und Zugsortierung | 7955 | 687 - 1217 |
| Suchen mit NegaAlphaBeta, 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.
