Minimax (manchmal Minmax, MM oder Sattelpunkt) ist eine Entscheidungsregel, die in künstlicher Intelligenz, Entscheidungstheorie, kombinatorischer Spieltheorie, Statistik und Philosophie verwendet wird. Sie zielt darauf ab, den möglichen Verlust für ein Worst-Case-Szenario (maximaler Verlust) zu minimieren. Bei Gewinnen wird sie als 'Maximin' bezeichnet – um den minimalen Gewinn zu maximieren. Ursprünglich für die Theorie von Nullsummenspielen mit mehreren Spielern formuliert, die sowohl Fälle abdeckt, in denen Spieler abwechselnd ziehen, als auch solche, in denen sie gleichzeitig ziehen, wurde sie auch auf komplexere Spiele und auf allgemeine Entscheidungsfindung bei Unsicherheit ausgeweitet.
Das Konzept ist zentral für adversariale Umgebungen, in denen der Gewinn eines Spielers der Verlust eines anderen ist. In solchen Kontexten bietet Minimax eine konservative Strategie: Nimm an, dass der Gegner immer die Aktion wählt, die für dich am schlechtesten ist, und wähle den Zug, der deine garantierte Auszahlung maximiert. Dieses Prinzip liegt vielen Algorithmen im maschinellen Lernen und Deep Learning zugrunde, insbesondere beim Training von generativen Modellen und beim Entwurf robuster Systeme.
Spieltheoretische Grundlagen
In der Spieltheorie ist der Maximin-Wert der höchste Wert, den ein Spieler sicher erreichen kann, ohne die Aktionen der anderen Spieler zu kennen; äquivalent ist es der niedrigste Wert, den die anderen Spieler den Spieler erhalten lassen können, wenn sie dessen Aktion kennen. Die formale Definition lautet: v_i_underline = max_{a_i} min_{a_{-i}} v_i(a_i, a_{-i}), wobei i der Index des Spielers ist, a_i die vom Spieler i gewählte Aktion, a_{-i} die Aktionen aller anderen Spieler bezeichnet und v_i die Wertfunktion des Spielers i ist.
Die Berechnung des Maximin-Werts verwendet einen Worst-Case-Ansatz: Für jede mögliche Aktion des Spielers werden alle möglichen Aktionen der anderen geprüft und die schlechteste Kombination bestimmt – diejenige mit dem kleinsten Wert. Dann wird die Aktion gewählt, die diesen kleinsten Wert so hoch wie möglich macht. Betrachte zum Beispiel ein Zwei-Spieler-Spiel, bei dem der Zeilenspieler T, M oder B wählen kann und der Spaltenspieler L oder R, mit Auszahlungen in einer Tabelle. Der Zeilenspieler kann T spielen und sich eine Auszahlung von mindestens 2 garantieren (B ist riskant mit −100, M kann −10 ergeben), also ist v_Zeile_underline = 2. Der Spaltenspieler kann L spielen und mindestens 0 sichern (R riskiert −20), also ist v_Spalte_underline = 0. Wenn beide ihre Maximin-Strategien (T, L) spielen, ist der Auszahlungsvektor (3, 1).
Der Minimax-Wert eines Spielers ist der kleinste Wert, den die anderen Spieler den Spieler erhalten lassen können, ohne dessen Aktionen zu kennen; äquivalent ist es der größte Wert, den der Spieler sicher erreichen kann, wenn er die Aktionen der anderen kennt. Die formale Definition lautet: v_i_overline = min_{a_{-i}} max_{a_i} v_i(a_i, a_{-i}). In Nullsummenspielen ist der Minimax-Wert für jeden Spieler gleich dem Maximin-Wert, was zum Minimax-Theorem führt.
Minimax-Theorem und Nullsummenspiele
Das Minimax-Theorem, bewiesen von John von Neumann im Jahr 1928, besagt, dass in endlichen Zwei-Spieler-Nullsummenspielen mit gemischten Strategien der Maximin-Wert dem Minimax-Wert entspricht. Dieses Theorem bildet eine Grundlage für die Gleichgewichtsanalyse. In solchen Spielen ist der Wert des Spiels die erwartete Auszahlung, wenn beide Spieler optimal spielen. Das Theorem stellt sicher, dass ein Spieler mindestens diesen Wert garantieren kann und der Gegner ihn auf höchstens diesen Wert begrenzen kann.
Für Spiele mit gleichzeitigen Zügen erweitert sich das Konzept auf gemischte Strategien, bei denen Spieler über reine Aktionen randomisieren. Das Minimax-Theorem garantiert die Existenz eines Sattelpunkts in gemischten Strategien, also eines Strategiepaars, bei dem kein Spieler seine Auszahlung durch einseitiges Abweichen verbessern kann. Dieses Ergebnis ist fundamental im Training von neuronalen Netzen, wo adversariale Beispiele mit ähnlichen Worst-Case-Prinzipien analysiert werden.
Anwendungen in der künstlichen Intelligenz
In der KI wird Minimax häufig bei der Entscheidungsfindung für Spiele und adversariale Szenarien verwendet. Das klassische Beispiel ist der Minimax-Algorithmus für rundenbasierte Zwei-Spieler-Spiele wie Schach, Dame oder Tic-Tac-Toe. Der Algorithmus bewertet rekursiv den Spielbaum unter der Annahme, dass der Gegner optimal spielt. An jedem Knoten wählt der Spieler den Zug, der seinen minimalen Gewinn maximiert, während der Gegner den Zug wählt, der den maximalen Gewinn des Spielers minimiert. Dies wird oft mit Alpha-Beta-Pruning kombiniert, um die Rechenkomplexität zu reduzieren.
In großen Sprachmodellen und Transformer-Architekturen erscheinen Minimax-Prinzipien im adversarialen Training, bei dem Modelle darauf trainiert werden, gegen Worst-Case-Störungen robust zu sein. Zum Beispiel verwenden generative adversarial networks (GANs) ein Minimax-Ziel: Der Generator versucht, die Fähigkeit des Diskriminators zu minimieren, echte von gefälschten Daten zu unterscheiden, während der Diskriminator versucht, seine Genauigkeit zu maximieren. Dieser adversariale Prozess ist eine direkte Anwendung von Minimax im Deep Learning.
Erweiterungen und Variationen
Minimax wurde auf komplexere Spiele erweitert, einschließlich Spiele mit Zufall (wie Backgammon) unter Verwendung von Expectiminimax und Spiele mit unvollständiger Information unter Verwendung von Techniken wie Counterfactual Regret Minimization. Im Verstärkungslernen wird Minimax in der robusten Steuerung und in Multi-Agenten-Umgebungen verwendet, in denen Agenten Worst-Case-Gegnerverhalten berücksichtigen müssen. Das Konzept erscheint auch in Optimierung und Statistik, wo Minimax-Schätzer das maximale Risiko minimieren.
Im Computerschach und anderen spielenden KI-Systemen bleibt Minimax mit Alpha-Beta-Pruning eine Kerntechnik, obwohl moderne Systeme wie OpenAI und Google DeepMind oft maschinelle Lernansätze verwenden, die minimax-ähnliche Ziele integrieren. Das Prinzip ist auch in der Entscheidungstheorie relevant, um Handlungen unter Unsicherheit zu wählen, wobei ein Entscheidungsträger die Option wählt, die den Worst-Case-Verlust minimiert.
Historischer Kontext und verwandte Konzepte
Die Minimax-Regel hat ihre Wurzeln in der Spieltheorie und Entscheidungstheorie, mit Beiträgen von Mathematikern wie John von Neumann und Oskar Morgenstern. Sie ist eng verwandt mit dem Konzept eines Sattelpunkts in der Optimierung und mit dem Nash-Gleichgewicht in Nicht-Nullsummenspielen. In der Philosophie wird Minimax in Diskussionen über Rationalität und Risikoaversion verwendet.
In der modernen KI wird Minimax oft mit der Bayesschen Entscheidungstheorie kontrastiert, die A-priori-Wahrscheinlichkeiten anstelle von Worst-Case-Annahmen verwendet. Während Minimax konservativ ist, können Bayessche Methoden flexibler sein. Die Wahl zwischen ihnen hängt von der Verfügbarkeit probabilistischer Informationen ab. In der KI-Forschung bleibt Minimax ein Maßstab für die Bewertung von Entscheidungsalgorithmen, insbesondere in adversarialen Umgebungen.
Siehe auch
- Alpha-Beta-Pruning
- Spieltheorie
- Nullsummenspiel
- Adversariales maschinelles Lernen