Ein im April 2011 veröffentlichter Programmierbeitrag zeigt am Beispiel von Tic-Tac-Toe, wie sich ein kleines Spielbrett mit dem Minimax-Verfahren als Gegner nutzen lässt. Der vollständige Beispielcode ist in Python geschrieben und trennt die Spiellogik von den beiden Spielertypen Mensch und Computer.
Vom Spielbrett zum Zustandsraum
Die Ausgangslage besteht aus neun Feldern und zwei Markierungen. Eine Partie endet mit drei gleichen Zeichen in einer Reihe, Spalte oder Diagonale oder mit einem vollständig belegten Brett. Der Code verwaltet freie Felder, ausgeführte Züge und mögliche Endzustände. Ein Stapel für die letzten Züge erlaubt es, eine Position nach der Prüfung wiederherzustellen und weitere Varianten zu testen.
Minimax bewertet mögliche Züge
Für den Computergegner wird jeder mögliche Zug bis zum Spielende verfolgt. Die Max-Funktion sucht den höchsten Wert für den eigenen Spieler, die Min-Funktion hält den Wert für den Gegenspieler möglichst niedrig. Ein Sieg erhält den Wert 1, eine Niederlage den Wert -1 und ein Remis den Wert 0. So entsteht ein überschaubares Beispiel für rekursive Suche und eine einfache Spiele-KI, ohne dass ein großes Modell oder eine externe Bibliothek nötig ist.
Tic-Tac-Toe ist wegen seines kleinen Zustandsraums besonders geeignet, um das Verfahren im Quelltext nachzuvollziehen. Die Grundidee lässt sich auf komplexere Spiele nicht unverändert übertragen, weil dort die Zahl der möglichen Züge schnell wächst. Als technische Übung verbindet das Beispiel Spielregeln, Objektorientierung, Rücksprünge im Suchbaum und eine klare Bewertungsfunktion in einem kurzen Python-Programm.