Adversarische Suche erklärt
Diese Linie fragt nicht *wer gegen wen* (das ist die Turnierplanung-Linie), sondern *wie entscheidet eine Maschine ihren nächsten Zug*, wenn ein Gegner jeden ihrer Vorteile zunichtemachen will. Minimax (Wurzel) durchsucht dafür den gesamten Spielbaum erschöpfend: beweisbar optimal, aber mit der Brett- oder Suchtiefe kombinatorisch explodierend. Zwei Äste beheben dieselbe Schwäche auf unterschiedliche Weise: Alpha-Beta-Pruning und Transpositionstabellen durchsuchen denselben Baum schneller, ohne am Ergebnis etwas zu ändern; Bewertungsfunktionen und Endspiel-Tablebases brechen die Suche stattdessen früher ab und schätzen oder lösen offline vor. Ein sechstes Stück führt beide Äste zusammen: Selbstspiel trainiert die Bewertungsfunktion aus Partien der eigenen, sich verbessernden Suche statt aus reinen Zufallspartien.
Gemeinsames Vehikel ist Mini-Vier-Gewinnt auf kleinen, vollständig durchsuchbaren Brettern, bis auf ein Stück: die Endspiel-Tablebase wechselt bewusst zu einem echten Schach-Endspiel (König und Turm gegen König), weil Retrograde-Analyse dort ihre klassische, historische Heimat hat (Ströhlein löste König und Turm gegen König schon 1970 per Retrograde-Analyse, Ken Thompson übertrug das Verfahren 1986 auf weitere Endspiele).
In short: Covers adversarial search for game engines: minimax, alpha-beta pruning, transposition tables, evaluation functions, endgame tablebases and self-play. Interactive demos show how each technique addresses the cost of exhaustive game-tree search.
Diese Seite gehört zu Algorithmen und Verfahren erklärt. So lesen Sie sie: Das Diagramm zeigt, wie die Stücke zusammenhängen. Jede Kachel darunter öffnet eine interaktive Demo, wo es eine gibt, mit einer Erklärseite für Einsteiger und Fachleute. Auf der Suche nach einer Lösung für ein konkretes Problem? Zu den Interaktiven Demos.
Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.
Zuletzt aktualisiert:
Welches Verfahren passt zu Ihrem Fall? Zum Entscheidungsbaum ↓
Zum Nachlesen: erst einfach, dann fachlich
Minimax verständlich erklärt
Warum man in einem Spiel zu zweit den Zug wählt, dessen schlechtester Ausgang am besten ist, wie eine Maschine das beweist und warum ihre Suche mit der Brettgröße explodiert: erst für Einsteiger ohne Formeln, dann für Fachleute mit Modell, Formel und Messwerten.
Die sechs Stücke im Überblick
Minimax ist die Wurzel: beweisbar optimal, aber durchsucht jeden Zweig vollständig und muss bis zum Spielende suchen. Zwei Kanten führen von dort weg, beide beheben dieselbe Grundschwäche auf unterschiedliche Weise: Alpha-Beta-Pruning beschneidet Zweige, die das Ergebnis nachweislich nicht mehr ändern können; Bewertungsfunktionen brechen die Suche nach wenigen Zügen ab und schätzen die Stellung.
Innerhalb jedes Astes baut das zweite Stück auf der verbliebenen Schwäche des ersten auf: Transpositionstabellen lösen dieselbe, über verschiedene Zugfolgen mehrfach erreichte Stellung nur einmal; Endspiel-Tablebases ersetzen die Schätzung durch einen bewiesenen exakten Wert aus einer einmaligen Offline-Lösung. Selbstspiel führt beide Äste zusammen (Doppelrahmen): es übernimmt die effiziente Suche aus dem ersten Ast und ersetzt die Schwäche des zweiten (Gewichte aus Zufallspartien statt aus echtem Spiel).
Die Kästen sind klickbar und öffnen die jeweilige Demo direkt.
- behebt eine Schwäche des Vorgängers oder baut darauf auf
- Zusammenfluss mehrerer Stränge
Die Endspiel-Tablebase wechselt bewusst das Vehikel (echtes Schach-Endspiel statt Mini-Vier-Gewinnt). Siehe Einleitung.
Verwandt in anderen Linien
- Exakte Suche — Alpha-Beta-Pruning ist strukturell Branch-and-Bound mit dem Minimax-Wert als Zielfunktion: dieselbe Idee (obere und untere Schranken beschneiden Teilbäume, ohne das Ergebnis zu verändern), hier auf ein Nullsummenspiel mit einem Gegenspieler statt auf einen einzelnen Entscheidungsträger angewendet, siehe die Branch-and-Bound-Demo dort.
- Heuristische Baumsuche — Das AlphaZero-Prinzip (Baumsuche plus gelernte Bewertungsfunktion statt Handbewertung) hat dort seine Baumsuche-Komponente: die MCTS-Demo zeigt Monte-Carlo-Baumsuche selbst, während die Selbstspiel-Demo hier bewusst nur die Trainingsschleife zeigt. Die Baumsuche bleibt klassisches Alpha-Beta, kein MCTS.
- Reinforcement Learning — Die lineare Bewertungsfunktion $V(s)=w^\top x(s)$ ist strukturell derselbe lineare Kritiker wie in der Actor-Critic-Demo dort, hier bewertet sie Spielstellungen statt Politik-Zustände. Die Retrograde-Analyse der Endspiel-Tablebases ist zudem dieselbe rückwärtsgerichtete Bellman-Rechnung wie in der Value-Iteration-Demo dort, nur mit einem deterministischen Minimax- statt einem stochastischen Erwartungswert.
- Komplexitätsklassen — Mit abwechselnden Quantoren wird eine Formel zum Spiel: Das QBF-Spiel zählt die Knoten der Tiefensuche wie Minimax und Alpha-Beta und stellt die Größe einer Gewinnstrategie neben die Länge einer Belegung.
Minimax: Adversarische Suche am Beispiel Mini-Vier-Gewinnt
Verfolgen Sie, wie Minimax den vollständigen Spielbaum eines Zwei-Personen-Spiels durchsucht: Eine Seite maximiert das Ergebnis, die andere minimiert es, und so lässt sich der beste Zug beweisen statt schätzen. Ein Brettgrößen-Umschalter zeigt den Haken: Die Baumgröße explodiert, bei gleicher Feldzahl stärker mit der Spaltenzahl als mit der Zeilenzahl, und schon das nächstgrößere Brett braucht 334 Sekunden.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →Alpha-Beta-Pruning: derselbe Wert, viel weniger Suche
Sehen Sie, wie Alpha-Beta-Pruning denselben Spielwert wie Minimax liefert, aber Äste abschneidet, die beweisbar nicht mehr besser werden können als eine schon gefundene Alternative. Ein Vergleich von vier Zugreihenfolgen zeigt, wie sehr die Reihenfolge zählt: Schon naiv braucht 4×4 nur 43 827 statt 83 078 201 Knoten, doch die vermeintlich kluge Reihenfolge „Mitte zuerst“ braucht dort sogar mehr.
Demo starten →Transpositionstabelle: dieselbe Stellung nur einmal lösen
Verfolgen Sie, wie eine Transpositionstabelle dieselbe Stellung nur einmal löst: Weil sich eine Stellung über verschiedene Zugfolgen erreichen lässt, erkennt ein Zobrist-Hash die Wiederholungen und spart die Suche. Ein Brettgrößen-Umschalter zeigt, wie der Gewinn mit dem Brett wächst (24,5-fach auf 4×5), und den Haken: Die Tabelle kostet Speicher, weil sie mit der Stellungszahl wächst.
Demo starten →Bewertungsfunktionen: schätzen statt bis zum Ende suchen
Sehen Sie, wie eine Bewertungsfunktion die Suche nach wenigen Zügen abbricht und die Stellung stattdessen anhand von Merkmalen wie offenen Gewinnlinien schätzt: Das macht das echte Standardbrett spielbar, aber nicht mehr beweisbar exakt. Ein Vergleich von handgewählten und angepassten Gewichten zeigt das Überraschende: Auf einem ungesehenen Brett schlägt bei Suchtiefe zwei die Handgewichtung die gefittete (99,4 % gegen 97,6 %).
Demo starten →Endspiel-Tablebase: König+Turm gegen König, vollständig gelöst
Sehen Sie, wie Retrograde-Analyse ein Schach-Endspiel (König und Turm gegen König) vollständig löst: Statt vorwärts zu suchen, wird der Wert von den Matt-Stellungen rückwärts weitergegeben, bis jede legale Stellung einen exakten Abstand zum Matt hat. Ein Vergleich mit einer naiven Faustregel zeigt den Haken: Sie wählt nur in 31,4 % der Fälle den schnellsten Weg, und in 6,0 % verschenkt sie den Sieg ganz.
Demo starten →Selbstspiel: die Bewertungsfunktion lernt aus eigenen Partien
Verfolgen Sie, wie die Bewertungsfunktion aus eigenen Partien lernt: Jede Generation spielt gegen sich selbst, sammelt die besuchten Stellungen mit ihrem exakten Wert und passt die Gewichte neu an (das AlphaZero-Prinzip, mit klassischer Suche statt MCTS). Ein Vergleich der Trainingsarten zeigt den Haken: Bei nur drei Merkmalen landet Selbstspiel auf demselben Wert wie Training an Zufallspartien (97,6 %), beide hinter der Handgewichtung (99,6 %).
Demo starten →Welches Stück passt zu meiner Frage?
Fünf Fragen führen zu allen sechs Stücken der Linie. Jede Antwort stützt sich auf eine Messung in den Demos.
Welches Stück passt zu meiner Frage?
Beige Kästen sind Fragen (nicht klickbar), weiße Kästen sind Ergebnisse (klickbar, sie öffnen die jeweilige Demo). Die erste Frage ist die wichtigste Weiche der Linie: ein bewiesener Wert (linker Ast) ist grundsätzlich anders erkauft als eine Schätzung (rechter Ast). Keine der beiden Antworten ist ohne Kontext „besser“.
Weitere Linien in diesem Bereich
Multi-Agenten-Koordination
Aufträge ohne zentrale Instanz verteilen: von Contract Net über Verhandlung, DCOP und Multi-Agenten-Lernen bis zu Auktionen und gelernten Mechanismen.
Spieltheorie
Wer hat welchen Anreiz? Zehn Verfahren zu eigennützigen Lkw und zu Spediteuren, die Kosten teilen, jedes mit seinem gemessenen Befund.
Wiederholte Spiele
Zwei Spediteure, die sich jede Woche wiedersehen: elf Stücke von Tit-for-Tat über das Folk-Theorem und Preiskriege bis zu lernenden Preis-Algorithmen.
Turnierplanung
Wie plant man ein faires Turnier mit vertretbarer Rundenzahl, und was zählt sonst noch: Heimrecht, Reisedistanz, eine zweite Chance, der Gleichstand? Acht Antworten, jede gegen echte Referenzdaten oder Literatur geprüft.
Ranking
Wie wird aus Vergleichen eine Rangfolge, und wie sicher ist sie? Ein simuliertes Turnier mit bekannter Stärke, siebzehn Stücke von der Siegtabelle über Bradley-Terry und Elo bis zu Rangintervallen und Learning to Rank.
Abstimmen und Fair Teilen
Wie aus verschiedenen Wünschen eine Entscheidung oder eine faire Verteilung wird: fünfzehn Stücke von der Wahlregel bis zur Kuchenteilung.