MinMax (Spieltheorie)
Spieltheorie in einfachster Form — stets das Beste, gegen einen Gegner, der ebenfalls nichts verschenkt.
Vier Gewinnt
Wirf Chips ein und bilde 4 in einer Reihe. Klicke auf ▼ über einer Spalte.
Vier Gewinnt hat über 4 Billionen mögliche Positionen! Die KI nutzt Heuristiken und Alpha-Beta-Pruning um gute Züge zu finden.
Definition
Was ist der MinMax-Algorithmus?
Analogie
Stell dir vor, du spielst Schach gegen einen Freund und denkst mehrere Züge voraus: "Wenn ich hierhin ziehe, wird er wahrscheinlich dorthin ziehen, und dann kann ich..." - genau so denkt der MinMax-Algorithmus!
Die KI simuliert alle möglichen Spielverläufe in einem Entscheidungsbaum. Sie nimmt an, dass der Gegner immer den für sich besten Zug macht (und damit deinen Vorteil minimiert), während sie selbst ihren Vorteil maximiert.
Das Besondere: Bei perfektem Spiel beider Seiten kann Tic-Tac-Toe nie gewonnen werden - es endet immer unentschieden!
Definition
Der MinMax-Algorithmus ist ein rekursiver Algorithmus zur Entscheidungsfindung in Zwei-Personen-Nullsummenspielen. Er durchläuft den Spielbaum bis zu einer maximalen Tiefe und bewertet Endpositionen. MAX-Knoten maximieren den Wert (KI-Züge), MIN-Knoten minimieren ihn (Gegner-Züge). Alpha-Beta-Pruning kann die Effizienz durch Abschneiden irrelevanter Zweige drastisch verbessern.
Diese Demo lässt dich gegen einen KI-Gegner spielen. Du kannst verschiedene Spiele wählen und beobachten, wie die KI denkt und den besten Zug berechnet.
Die verschiedenen Spiele
Wähle zwischen Tic-Tac-Toe, Vier Gewinnt, Nim, Reversi und Gomoku. Jedes Spiel hat unterschiedliche Komplexität und erfordert verschiedene Strategien.
Schwierigkeitsgrade
Im leichten Modus schaut die KI nur wenige Züge voraus und übersieht deshalb Fallen. Im schweren Modus rechnet sie viel weiter – bei Tic-Tac-Toe bis zum Spielende, dort spielt sie perfekt. Beobachte, wie sich die Anzahl der geprüften Züge ändert.
Der Spielbaum
Die KI denkt in einem Spielbaum: Sie simuliert alle möglichen Züge und Gegenzüge. MAX-Knoten (KI) maximieren den Wert, MIN-Knoten (Spieler) minimieren ihn. So findet sie den bestmöglichen Zug.
Wenn du gegen die KI spielst, denkst du vielleicht: "Warum gewinne ich nie bei Tic-Tac-Toe?" Die Antwort liegt im MinMax-Algorithmus – einem eleganten Konzept, das optimales Spielen mathematisch garantiert.
Die Grundidee: Denken wie der Gegner
Stell dir vor, du spielst Schach und denkst: "Wenn ich hier ziehe, wird mein Gegner wahrscheinlich dort ziehen, und dann kann ich..." Genau so denkt MinMax! Der Algorithmus simuliert alle möglichen Spielverläufe und nimmt dabei an, dass beide Spieler optimal spielen.
Das Besondere: Die KI geht davon aus, dass du immer den für dich besten Zug machst. Sie bereitet sich also auf das Schlimmste vor – und ist deshalb so schwer zu schlagen.
Maximieren und Minimieren
Der Name "MinMax" beschreibt die zwei Rollen im Spiel:
- Maximierer (KI): Will die Bewertung maximieren. Sucht den Zug mit dem höchsten Wert.
- Minimierer (Du): Will die Bewertung minimieren. Die KI nimmt an, du spielst den für sie schlechtesten Zug.
Dieses Wechselspiel setzt sich den gesamten Spielbaum hindurch fort. Bei Tic-Tac-Toe kann die KI den kompletten Baum durchsuchen und garantiert unschlagbar spielen!
Warum ist Tic-Tac-Toe immer unentschieden?
Bei perfektem Spiel beider Seiten endet Tic-Tac-Toe immer unentschieden. Das liegt daran, dass MinMax alle 255.168 möglichen Spielverläufe analysiert hat und weiß: Es gibt keinen Zug, der einen Sieg erzwingt, wenn der Gegner optimal antwortet.
Wenn du gegen die KI gewinnst, hat sie bewusst einen suboptimalen Zug gemacht (leichte Schwierigkeit) oder du hast eine Position gefunden, die die KI unterschätzt hat.
Alpha-Beta-Pruning: Cleveres Abschneiden
Bei komplexeren Spielen wie Vier Gewinnt oder Reversi wäre das Durchsuchen aller Möglichkeiten zu langsam. Hier kommt Alpha-Beta-Pruning ins Spiel:
- Alpha: Der beste Wert, den der Maximierer bisher gefunden hat
- Beta: Der beste Wert, den der Minimierer bisher gefunden hat
- Wenn Beta ≤ Alpha, können restliche Züge ignoriert werden – sie ändern das Ergebnis nicht mehr
Diese Optimierung kann die Anzahl der zu untersuchenden Positionen drastisch reduzieren – manchmal um bis zu 99%!
Spiele selbst und verstehe
Beobachte in der Demo oben, wie viele Züge die KI analysiert. Bei Tic-Tac-Toe sind es anfangs Tausende, bei Vier Gewinnt können es Millionen sein. Aktiviere "KI-Denkzeit animieren" und du siehst, wie die KI verschiedene Züge durchspielt.
Experimentiere: Versuche bei verschiedenen Spielen, die KI auf "Schwer" zu schlagen. Du wirst merken: Je komplexer das Spiel, desto schwieriger wird es – aber auch desto interessanter die strategischen Möglichkeiten!
1
# MinMax-Algorithmus mit Alpha-Beta-Pruning
2
funktion minmax(spielstand, tiefe, ist_maximierer):
3
# Basisfall: Spiel ist zu Ende oder maximale Tiefe erreicht
4
wenn spielstand.ist_endstellung() oder tiefe == 0:
5
return bewerte_stellung(spielstand)
6
7
# Maximierer: KI sucht den höchsten Wert
8
wenn ist_maximierer:
9
bester_wert = -UNENDLICH
10
für jeden zug in spielstand.mögliche_züge():
11
spielstand.führe_aus(zug)
12
wert = minmax(spielstand, tiefe - 1, FALSCH)
13
spielstand.mache_rückgängig(zug)
14
bester_wert = max(bester_wert, wert)
15
return bester_wert
16
17
# Minimierer: Gegner sucht den niedrigsten Wert
18
sonst:
19
bester_wert = +UNENDLICH
20
für jeden zug in spielstand.mögliche_züge():
21
spielstand.führe_aus(zug)
22
wert = minmax(spielstand, tiefe - 1, WAHR)
23
spielstand.mache_rückgängig(zug)
24
bester_wert = min(bester_wert, wert)
25
return bester_wert
26
27
# Optimierung: Alpha-Beta-Pruning
28
funktion alphabeta(spielstand, tiefe, alpha, beta, ist_max):
29
# Schneide Zweige ab, die das Ergebnis nicht mehr ändern können
30
wenn beta <= alpha:
31
abbruch # Pruning: Dieser Zweig ist irrelevant
Basisfall prüfen
Zuerst prüft der Algorithmus, ob das Spiel zu Ende ist (Gewinn, Verlust, Unentschieden) oder die maximale Suchtiefe erreicht wurde. Bei Endstellungen wird direkt der Wert zurückgegeben.
# Basisfall: Spiel ist zu Ende oder maximale Tiefe erreicht
wenn spielstand.ist_endstellung() oder tiefe == 0:
return bewerte_stellung(spielstand)
Spielbaum aufbauen
Der Algorithmus betrachtet das Spiel als Baum: Jeder Knoten ist ein Spielzustand, jede Kante ein möglicher Zug. Der Baum wächst exponentiell mit der Tiefe.
MAX-Knoten: KI am Zug
Die KI will den Spielwert maximieren. Sie betrachtet alle Kindknoten und wählt den mit dem höchsten Wert.
MIN-Knoten: Gegner am Zug
Der Gegner will den Spielwert minimieren. Er wählt den Zug, der für die KI am schlechtesten ist.
Blätter bewerten
Endstellungen oder Knoten an der Suchgrenze werden mit einer Bewertungsfunktion bewertet: Gewinn = +∞, Verlust = -∞, andere Stellungen erhalten heuristische Werte.
Werte nach oben propagieren
Die Bewertungen werden von den Blättern zur Wurzel hochgereicht. Jeder Knoten erhält den besten/schlechtesten Wert seiner Kinder.
Optimalen Zug wählen
An der Wurzel wird der Zug gewählt, der zum besten Wert führt. Bei perfektem Spiel ist dies garantiert der optimale Zug.
Prüfen
Teste dein Wissen
Was bedeutet 'MinMax' im MinMax-Algorithmus?
Wähle eine Antwort
1. Was bedeutet 'MinMax' im MinMax-Algorithmus?
2. Was nimmt MinMax über den Gegner an?
3. Was passiert bei Tic-Tac-Toe mit perfektem Spiel beider Seiten?
4. Was macht Alpha-Beta-Pruning?
5. Was ist ein Spielbaum?
6. Was macht ein MAX-Knoten im Spielbaum?
7. Warum ist Vier Gewinnt komplexer als Tic-Tac-Toe?
8. Was passiert, wenn die KI tiefer im Spielbaum sucht?
9. Was ist eine Heuristik bei Spiel-KIs?
10. Was ist ein Nullsummenspiel?