MinMax (Spieltheorie)
Spieltheorie in einfachster Form — stets das Beste, gegen einen Gegner, der ebenfalls nichts verschenkt.
Was ist der MinMax-Algorithmus?
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!
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.
So funktioniert diese Demo
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 macht die KI absichtlich Fehler. Im schweren Modus spielt sie optimal und berechnet viele Züge voraus. 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.
Interaktive Demo: Spiele gegen MinMax
⚪ Gomoku (5 in einer Reihe)
Setze 5 Steine in einer Reihe auf dem 9x9 Brett. Klicke auf eine Kreuzung.
Gomoku auf 9x9: Die KI fokussiert sich auf Bereiche nahe existierender Steine und bewertet Linienpotential für 5er-Reihen.
Spiel wählen
⭐⭐ Mittel - Großer Spielbaum
Spieleinstellungen
Klicke auf das Spielfeld um zu starten
Anzeige-Optionen
Statistik
Der Algorithmus im Detail
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.
Teste dein Wissen
Was bedeutet 'MinMax' im MinMax-Algorithmus?
1. Was bedeutet 'MinMax' im MinMax-Algorithmus?
- ☐ A) Maximiere den eigenen Vorteil, minimiere den des Gegners
- ☐ B) Minimiere die Zuganzahl, maximiere die Geschwindigkeit
- ☐ C) Finde den minimalen und maximalen Spielstand
- ☐ D) Minimiere Fehler, maximiere Zufälle
2. Was nimmt MinMax über den Gegner an?
- ☐ A) Der Gegner macht zufällige Züge
- ☐ B) Der Gegner spielt immer optimal
- ☐ C) Der Gegner macht manchmal Fehler
- ☐ D) Der Gegner kopiert die eigenen Züge
3. Was passiert bei Tic-Tac-Toe mit perfektem Spiel beider Seiten?
- ☐ A) Der erste Spieler gewinnt immer
- ☐ B) Der zweite Spieler gewinnt immer
- ☐ C) Es endet immer unentschieden
- ☐ D) Das Ergebnis ist zufällig
4. Was macht Alpha-Beta-Pruning?
- ☐ A) Es macht die KI klüger
- ☐ B) Es findet bessere Züge
- ☐ C) Es merkt sich frühere Spiele
- ☐ D) Es schneidet irrelevante Zweige ab und spart Zeit
5. Was ist ein Spielbaum?
- ☐ A) Eine Struktur, die alle möglichen Spielzüge darstellt
- ☐ B) Ein Zufallsgenerator für Spielzüge
- ☐ C) Eine Liste gewonnener Spiele
- ☐ D) Ein Algorithmus zur Zugbewertung
6. Was macht ein MAX-Knoten im Spielbaum?
- ☐ A) Er minimiert den Wert
- ☐ B) Er maximiert den Wert (KI sucht besten Zug)
- ☐ C) Er berechnet den Durchschnitt
- ☐ D) Er wählt zufällig
7. Warum ist Vier Gewinnt komplexer als Tic-Tac-Toe?
- ☐ A) Das Spielfeld ist bunter
- ☐ B) Die Regeln sind komplizierter
- ☐ C) Es gibt viel mehr mögliche Positionen
- ☐ D) Man braucht mehr Spieler
8. Was passiert, wenn die KI tiefer im Spielbaum sucht?
- ☐ A) Sie spielt immer perfekt
- ☐ B) Sie braucht mehr Zeit, findet aber bessere Züge
- ☐ C) Sie macht mehr Fehler
- ☐ D) Sie vergisst frühere Züge
9. Was ist eine Heuristik bei Spiel-KIs?
- ☐ A) Eine Regel zur schnellen Bewertung von Spielpositionen
- ☐ B) Ein Zufallsgenerator für Züge
- ☐ C) Ein Speicher für alte Spiele
- ☐ D) Eine Methode zum Betrügen
10. Was ist ein Nullsummenspiel?
- ☐ A) Ein Spiel ohne Punkte
- ☐ B) Was einer gewinnt, verliert der andere
- ☐ C) Ein Spiel das immer unentschieden endet
- ☐ D) Ein Spiel mit null Zügen
Verwandte Inhalte
Artikel
Algorithmische Komplexität
Die Lehre, dass ein eleganter Algorithmus jeden Supercomputer schlägt — vorausgesetzt, n ist groß genug.
Kontrollstrukturen
Kontrollstrukturen: alles, was zwischen "tu dies" und "tu das" entscheidet.
Datenstrukturen II (Hierarchisch & Vernetzt)
Bäume, Suchbäume und Graphen — Datenstrukturen mit Familienverhältnissen.
Regeln & Logik: Expertensysteme
Die KI, bevor sie aus Daten lernte: Experten gefragt, Regeln aufgeschrieben, gehofft.
Agenten in Konflikten — Spieltheorie
Was ein zweiter rationaler Spieler an einer Optimierung ändert — alles.
Suche im Graphen — Die Anfänge
Graphsuche: das erste, was KI tatsächlich konnte — und immer noch nützlich ist.
Heuristiken & Pfadsuche: Von Dijkstra zu A*
Wie A* funktioniert — und warum Dijkstra ohne Heuristik schnell langweilig wird.
MinMax & Pruning
MinMax in der Praxis: rückwärts denken, vom schlimmsten Gegner ausgehen, abkürzen wo möglich.
Rekursion
Rekursion: die Programmiertechnik, die einfach aussieht, bis man sie versteht. Und dann auch.
Was ist ein Algorithmus?
Was Euklid, IKEA-Anleitungen und Google-Suche gemeinsam haben — alle drei sind Algorithmen.
Demo
Pathfinding (Graphsuche)
Interaktive Visualisierung von Wegfindungsalgorithmen wie A*, Dijkstra und mehr
Q-Learning
Interaktive Demonstration des Q-Learning Algorithmus mit einem intelligenten Agenten im Tempel des Lernens
Regelbasierte KI
Sammle Hinweise und löse Kriminalfälle durch systematische Anwendung regelbasierter Logik. Diese interaktive Demo zeigt, wie KI-Systeme Schritt für Schritt zu Lösungen gelangen.
Travelling Salesman: Algorithmen im Wettstreit
Setze Städte, zeichne deine eigene Route und lass Greedy, Simulated Annealing und Genetic Algorithm gegen dich antreten.