Spiel-KI – Minimax und Alpha-Beta-Pruning bei Tic-Tac-Toe

InformatikDaten, KI und maschinelles LernenAlter 17–18

Mit meiner Klasse nutzen

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

  1. Warum verliert die KI bei Tiefenlimit 9 nie, egal auf welchem Feld Sie beginnen?
  2. Welche Felder kappt Alpha-Beta zuerst, und warum darf es sie überspringen?
  3. Unterhalb welches Tiefenlimits können Sie die KI schlagen, und wie ist es Ihnen gelungen?