Spiel-KI – Minimax und Alpha-Beta-Pruning bei Tic-Tac-Toe
InformatikDaten, KI und maschinelles LernenAlter 17–18
Wofür nutzen Sie diese Simulation hauptsächlich?
Im Unterricht einsetzen: Ihre Schülerinnen und Schüler öffnen sie über einen Link oder QR-Code, ganz ohne Konto.
Spielen Sie Tic-Tac-Toe gegen eine KI, die den Spielbaum mit Minimax durchsucht. Die Baumansicht zeigt jeden Zug, den die KI erwogen hat, die Bewertung, die Minimax ihm gegeben hat, und wie viele Stellungen darunter liegen; öffnen Sie einen Ast, um der Suche nach unten zu folgen. Schalten Sie Alpha-Beta-Pruning ein, um abgeschnittene Äste zu sehen, ohne dass sich der Zug ändert, vergleichen Sie die Zahl der durchsuchten Stellungen und senken Sie das Tiefenlimit, damit die KI schwach genug spielt, um sie zu schlagen.
Lektion: Künstliche Intelligenz in Spielen: Spielbäume, Minimax, tiefenbegrenzte Suche, Bewertungsfunktionen und Alpha-Beta-Suche
Was sie zeigt
Ein Spielprogramm kann vorausschauen: Es probiert jeden Zug, jede Antwort darauf und so weiter und baut so einen Spielbaum auf. Minimax bewertet beendete Stellungen (Sieg, Niederlage oder Remis) und reicht die Bewertungen im Baum nach oben: Wer am Zug ist, wählt die für sich beste Bewertung und nimmt an, dass der Gegner dasselbe tut. Tic-Tac-Toe ist klein genug, um bis zum Ende durchsucht zu werden, daher verliert eine KI mit voller Suchtiefe nie. Echte Spiele sind es nicht, deshalb stoppen Programme an einem Tiefenlimit und schätzen die Stellung. Alpha-Beta-Pruning überspringt Äste, die die Wahl nicht ändern können, und findet so denselben Zug mit weit weniger durchsuchten Stellungen.
So funktioniert es
Tippen Sie auf ein Feld, um zu ziehen; die KI antwortet. Der Baum zeigt die Möglichkeiten der KI und ihre Bewertungen: Tippen Sie auf eine davon, um ihren Ast zu öffnen, und kehren Sie mit ▲ Hoch oder ⤒ Zur Wurzel zurück. Aktivieren Sie Alpha-Beta-Pruning zum Vergleich. Senken Sie das Tiefenlimit oder wählen Sie Bewertung am Tiefenlimit, um die KI zu schwächen. Diese Stellung durchsuchen zeigt Ihre eigenen Möglichkeiten.
Einstellbare Parameter
- Sie spielen X (beginnt), O (zieht nach)
- Tiefenlimit (Züge voraus) 1–9
- Bewertung am Tiefenlimit 0 (unbekannt), Offene Linien
- Alpha-Beta-Pruning
Fragen zum Erkunden
- Warum verliert die KI bei Tiefenlimit 9 nie, egal auf welchem Feld Sie beginnen?
- Welche Felder kappt Alpha-Beta zuerst, und warum darf es sie überspringen?
- Unterhalb welches Tiefenlimits können Sie die KI schlagen, und wie ist es Ihnen gelungen?