Algorithmen wie Minimax verleihen Computergegnern die Fähigkeit, fehlerfrei zu spielen. Wir zeigen die Algorithmen am Beispiel des Klassikers Tic-Tac-Toe.
(Bild: KI / Collage: c’t)
16.05.2025, 08:00 Uhr
Lesezeit: 16 Min.
-
Python-Programm: Wie Sie einen unbesiegbaren Tic-Tac-Toe-Gegner erschaffen
- Programmüberblick
- Minimax in der Theorie
- Negamax
- Statistiken
- Fazit
Computerprogramme dominieren ihre menschlichen Gegner in Spielen wie Schach, Dame oder Vier Gewinnt. Hinter den unfehlbaren Computerspielern stecken häufig Algorithmen wie Minimax, die einige Züge in die Zukunft schauen, dabei alle möglichen Spielverläufe bewerten und sich so sicher für den besten Zug entscheiden können. Wie das funktioniert, zeigen wir am Spieleklassiker Tic-Tac-Toe.
Den Algorithmus aus der Spieltheorie kann man auch an komplexeren Spielen wie Schach nachvollziehen, aber Tic-Tac-Toe ist aufgrund seiner Einfachheit besonders gut dafür geeignet, und so gut wie jeder hat es mal gespielt.
- Um Algorithmen der Spieltheorie wie Minimax an einem konkreten Beispiel zeigen zu können, haben wir das Spiel Tic-Tac-Toe mithilfe der Python-Bibliothek PyGame nachprogrammiert.
- Minimax ist ein rekursiver Algorithmus, der für ein Brettspiel mögliche Spielverläufe durchkalkuliert und dadurch den besten Zug findet.
- Der Computer kommt schneller zu einem Ergebnis, wenn er mithilfe der Alpha-Beta-Methode die Anzahl der bewerteten Spielzüge drastisch reduziert.
Programmüberblick
Damit Sie das Spiel in einer grafischen Oberfläche ausprobieren können, haben wir es mit der Python-Bibliothek PyGame realisiert. Sie finden es im GitHub-Repository zu diesem Artikel. Das Python-Programm öffnet beim Start ein leeres Tic-Tac-Toe-Spielbrett: Sie spielen immer mit Kreuz und der Computer mit Kreis, nach jeder Partie wechselt der startende Spieler. Endet das Spiel in einem Remis, einer Niederlage oder in einem Sieg, erscheint ein Dialog mit der Frage, ob man noch einmal spielen möchte.
Das war die Leseprobe unseres heise-Plus-Artikels "Python-Programm: Wie Sie einen unbesiegbaren Tic-Tac-Toe-Gegner erschaffen". Mit einem heise-Plus-Abo können sie den ganzen Artikel lesen und anhören.
English (US) ·