Minimax (manchmal minmax) ist eine Entscheidungsregel, die in Entscheidungstheorie, Spieltheorie, Statistik und Philosophie verwendet ist, für den möglichen Verlust für einen Grenzfall (maximaler Verlust) Drehbuch zu minimieren. Wechselweise kann davon als Maximierung des minimalen Gewinns (maximin) gedacht werden. Ursprünglich formuliert für die Zwei-Spieler-Nullsumme-Spieltheorie, sowohl die Fälle bedeckend, wo Spieler abwechselnde Bewegungen als auch diejenigen nehmen, wo sie gleichzeitige Bewegungen machen, ist es auch zu komplizierteren Spielen und zum allgemeinen Entscheidungsbilden in Gegenwart von der Unklarheit erweitert worden.

Spieltheorie

In der Theorie von Simultanspielen ist eine minimax Strategie eine Mischstrategie, die ein Teil der Lösung eines Nullsumme-Spiels ist. In Nullsumme-Spielen ist die minimax Lösung dasselbe als das Gleichgewicht von Nash.

Lehrsatz von Minimax

Der minimax Lehrsatz setzt fest

Gleichwertig Spieler 1 versichert Strategie ihn eine Belohnung V unabhängig vom Spieler 2 Strategie, und ähnlich kann Spieler 2 sich eine Belohnung von V versichern. Der Name minimax entsteht, weil jeder Spieler die maximale Belohnung minimiert, die für den anderen möglich ist —, da das Spiel Nullsumme ist, maximiert er auch seine eigene minimale Belohnung.

Dieser Lehrsatz wurde von John von Neumann gegründet, der zitiert wird, "So weit ich sehen kann, konnte es keine Theorie von Spielen … ohne diesen Lehrsatz … geben ich habe gedacht, dass es nichts Wertes gab zu veröffentlichen, bis der Minimax Lehrsatz bewiesen wurde".

Sieh den minimax Lehrsatz von Sion und den Lehrsatz von Parthasarathy für Generalisationen; sieh auch Beispiel eines Spiels ohne einen Wert.

Beispiel

Das folgende Beispiel eines Nullsumme-Spiels, wo A und B gleichzeitige Bewegungen machen, illustriert minimax Lösungen. Nehmen Sie an, dass jeder Spieler drei Wahlen hat und denken Sie die Belohnungsmatrix für Einen gezeigten am Recht. Nehmen Sie an, dass die Belohnungsmatrix für B dieselbe Matrix mit den umgekehrten Zeichen ist (d. h. wenn die Wahlen A1 sind und B1 dann B 3 zu A zahlt). Dann ist die minimax Wahl für A A2, da das schlechtestmögliche Ergebnis dann 1 zahlen muss, während die einfache minimax Wahl für B B2 ist, da das schlechtestmögliche Ergebnis dann keine Zahlung ist. Jedoch ist diese Lösung nicht stabil, seitdem wenn B glaubt, wird A wählen A2 dann wird B B1 wählen, um 1 zu gewinnen; dann, wenn A glaubt, dass B wählen wird, B1 dann wird A A1 wählen, um 3 zu gewinnen; und dann wird B B2 wählen; und schließlich werden beide Spieler die Schwierigkeit begreifen, eine Wahl zu machen. So ist eine stabilere Strategie erforderlich.

Einige Wahlen werden durch andere beherrscht und können beseitigt werden: A wird A3 nicht wählen, da entweder A1 oder A2 ein besseres Ergebnis erzeugen werden, egal was B wählt; B wird B3 nicht wählen, da einige Mischungen von B1 und B2 ein besseres Ergebnis erzeugen werden, egal was A wählt.

Eine Dose vermeidet, eine erwartete Zahlung mehr machen zu müssen, als 1/3 durch die Auswahl von A1 mit der Wahrscheinlichkeit 1/6 und A2 mit der Wahrscheinlichkeit 5/6, egal was B wählt. B kann einen erwarteten Gewinn mindestens 1/3 durch das Verwenden einer randomized Strategie sichern, B1 mit der Wahrscheinlichkeit 1/3 und B2 mit der Wahrscheinlichkeit 2/3 zu wählen, egal was A wählt. Diese haben sich vermischt minimax Strategien sind jetzt stabil und können nicht verbessert werden.

Maximin

Oft, in der Spieltheorie, ist maximin von minimax verschieden. Minimax wird in Nullsumme-Spielen verwendet, um Minderung der maximalen Belohnung des Gegners anzuzeigen. In einem Nullsumme-Spiel ist das zur Minderung jemandes eigenen maximalen Verlustes, und zur Maximierung jemandes eigenen minimalen Gewinns identisch.

"Maximin" ist ein Begriff, der allgemein für Spiele "nicht Nullsumme" gebraucht ist, um die Strategie zu beschreiben, die jemandes eigene minimale Belohnung maximiert. In Spielen "nicht Nullsumme" ist das nicht allgemein dasselbe als Minderung des maximalen Gewinns des Gegners, noch desselben als die Gleichgewicht-Strategie von Nash.

Kombinatorische Spieltheorie

In der kombinatorischen Spieltheorie gibt es einen minimax Algorithmus für Spiellösungen.

Eine einfache Version des minimax Algorithmus, der unten festgesetzt ist, befasst sich mit Spielen wie tic-tac-toe, wo jeder Spieler gewinnen, verlieren oder ziehen kann.

Wenn Spieler A in einer Bewegung gewinnen kann, ist seine beste Bewegung diese gewinnende Bewegung.

Wenn Spieler B weiß, dass eine Bewegung zur Situation führen wird, wo Spieler A in einer Bewegung gewinnen kann, während eine andere Bewegung zur Situation führen wird, wo Spieler A ziehen kann, dann ist die beste Bewegung des Spielers B diejenige, die zu einer Attraktion führt.

Spät im Spiel ist es leicht zu sehen, wie die "beste" Bewegung ist.

Der Minimax Algorithmus hilft, die beste Bewegung durch das Arbeiten umgekehrt vom Ende des Spiels zu finden. An jedem Schritt nimmt es an, dass Spieler A versucht, die Chancen Eines Gewinnens zu maximieren, während auf der folgenden Umdrehung der Spieler B versucht, die Chancen Eines Gewinnens zu minimieren (d. h., die eigenen Chancen von B zu maximieren, zu gewinnen).

Algorithmus von Minimax mit abwechselnden Bewegungen

Ein minimax Algorithmus ist ein rekursiver Algorithmus, für die folgende Bewegung in einem N-Spieler-Spiel, gewöhnlich einem Zwei-Spieler-Spiel zu wählen. Ein Wert wird mit jeder Position oder Staat des Spiels vereinigt. Dieser Wert wird mittels einer Positionseinschätzungsfunktion geschätzt, und er zeigt an, wie gut es für einen Spieler sein würde, um diese Position zu erreichen. Der Spieler macht dann die Bewegung, die den minimalen Wert der Position maximiert, die sich aus den möglichen folgenden Bewegungen des Gegners ergibt. Wenn es Eine Umdrehung ist sich zu bewegen, gibt A einen Wert jeder seiner gesetzlichen Bewegungen.

Eine mögliche Zuteilungsmethode besteht im Zuweisen eines bestimmten Gewinns für als +1 und für B als 1. Das führt zu kombinatorischer Spieltheorie, wie entwickelt, durch John Horton Conway. Eine Alternative verwendet eine Regel, die, wenn das Ergebnis einer Bewegung ein unmittelbarer Gewinn für es ist, positive Unendlichkeit zugeteilt wird und, wenn es ein unmittelbarer Gewinn für B, negative Unendlichkeit ist. Der Wert zu jeder anderen Bewegung ist das Minimum der Werte, die sich aus jeder von B möglichen Antworten ergeben. Deshalb wird A den Maximierungsspieler genannt, und B wird den Minderungsspieler, folglich der Name minimax Algorithmus genannt. Der obengenannte Algorithmus wird einen Wert der positiven oder negativen Unendlichkeit zu jeder Position zuteilen, da der Wert jeder Position der Wert etwas Endgewinnens oder des Verlierens der Position sein wird. Häufig ist das allgemein nur am wirklichen Ende von komplizierten Spielen wie Schach möglich, oder gehen Sie, da es nicht rechenbetont ausführbar ist, vorn zu schauen, so weit die Vollziehung des Spiels außer zum Ende, und stattdessen Positionen begrenzte Werte als Schätzungen des Grads des Glaubens gegeben werden, dass sie zu einem Gewinn für einen Spieler oder einen anderen führen werden.

Das kann erweitert werden, wenn wir eine heuristische Einschätzungsfunktion liefern können, die Werte Nichtendspielstaaten gibt, ohne alle möglichen folgenden ganzen Folgen zu denken. Wir können dann den minimax Algorithmus beschränken, um nur auf eine bestimmte Anzahl dessen zu schauen, geht voran. Diese Zahl wird den "Blick vorn" genannt, der in "Falten" gemessen ist. Zum Beispiel hat der Schachcomputer Tiefblau (die Garry Kasparov prügeln) vorn mindestens 12 Falten geschaut, hat dann eine heuristische Einschätzungsfunktion angewandt.

Vom Algorithmus kann als das Erforschen der Knoten eines Spielbaums gedacht werden. Der wirksame sich verzweigende Faktor des Baums ist die durchschnittliche Zahl von Kindern jedes Knotens (d. h., die durchschnittliche Zahl von gesetzlichen Bewegungen in einer Position). Die Zahl von Knoten, die gewöhnlich Zunahmen exponential mit der Zahl von Falten zu erforschen sind (ist es weniger als Exponential-, wenn das Auswerten Bewegungen gezwungen hat oder Positionen wiederholt hat). Die Zahl von Knoten, die für die Analyse eines Spiels zu erforschen sind, ist deshalb ungefähr der sich verzweigende Faktor, der zur Macht der Zahl von Falten erhoben ist. Es ist deshalb unpraktisch, um Spiele wie Schach mit dem minimax Algorithmus völlig zu analysieren.

Die Leistung des naiven minimax Algorithmus kann drastisch verbessert werden, ohne das Ergebnis durch den Gebrauch der Beschneidung des Alpha-Betas zu betreffen.

Andere heuristische Beschneidungsmethoden können auch verwendet werden, aber nicht sie alle werden versichert, dasselbe Ergebnis wie die nicht befreite Suche zu geben.

Ein naiver minimax Algorithmus kann trivial modifiziert werden, um eine komplette Hauptschwankung zusammen mit einer Minimax-Kerbe zusätzlich zurückzugeben.

Beispiel von Lua

fungieren Sie minimax (Knoten, Tiefe)

wenn Tiefe

Pseudocode

Der Pseudocode für die Version von Negamax des minimax Algorithmus (eine Einschätzung verwendend, die heuristisch ist, um an einer gegebenen Tiefe zu enden), wird unten gegeben.

Der Code basiert auf der Beobachtung das. Das vermeidet das Bedürfnis nach dem Algorithmus, um die zwei Spieler getrennt zu behandeln, aber kann für Spiele nicht verwendet werden, wo ein Spieler zwei haben kann, geht in Folge hinein.

ganze

Funktionszahl minimax (Knoten, Tiefe)

wenn Knoten ein Endknoten oder Tiefe ist, die verwendet wird, um einen Parameter zu schätzen. Wir nehmen auch eine Risikofunktion, gewöhnlich angegeben als das Integral einer Verlust-Funktion an. In diesem Fachwerk, wird minimax genannt, wenn es befriedigt

:

Ein alternatives Kriterium in der Entscheidung theoretisches Fachwerk ist der Vorkalkulator von Bayes in Gegenwart von einem vorherigen Vertrieb. Ein Vorkalkulator ist Bayes, wenn er die durchschnittliche Gefahr minimiert

:

Non-probabilistic Entscheidungstheorie

Ein Hauptmerkmal des minimax Entscheidungsbildens ist non-probabilistic: Im Gegensatz zu Entscheidungen damit hat Wert oder erwartetes Dienstprogramm erwartet, er macht keine Annahmen über die Wahrscheinlichkeiten von verschiedenen Ergebnissen, gerade Drehbuch-Analyse dessen, wie die möglichen Ergebnisse sind. Es ist so zu Änderungen in den Annahmen, wie diese anderen Entscheidungstechniken nicht sind. Verschiedene Erweiterungen dieser Non-Probabilistic-Annäherung, bestehen namentlich minimax Reue und Entscheidungstheorie der Info-Lücke.

Weiter, minimax verlangt nur Ordnungsmaß (dass Ergebnisse verglichen und aufgereiht werden), nicht Zwischenraum-Maße (dass Ergebnisse einschließen, "wie viel besser oder schlechter"), und Ordnungsdaten mit nur die modellierten Ergebnisse zurückgibt: Der Beschluss einer minimax Analyse ist: "Diese Strategie ist minimax, wie der Grenzfall (Ergebnis) ist, das weniger schlecht ist als jede andere Strategie". Vergleichen Sie sich mit der erwarteten Wertanalyse, deren Beschluss der Form ist: "Diese Strategie gibt E (X) =n nach." Minimax kann so auf Ordnungsdaten verwendet werden und kann durchsichtiger sein.

Maximin in der Philosophie

In der Philosophie wird der Begriff "maximin" häufig im Zusammenhang von John Rawls Eine Theorie der Justiz gebraucht, wo er sich darauf (Rawls bezieht (1971, p. 152)) im Zusammenhang Des Unterschied-Grundsatzes.

Rawls hat diesen Grundsatz als die Regel definiert, die feststellt, dass soziale und wirtschaftliche Ungleichheit eingeordnet werden sollte, so dass "sie vom größten Vorteil für die am wenigsten geförderten Mitglieder der Gesellschaft sein sollen". Mit anderen Worten kann ein ungleicher Vertrieb gerade darin bestehen, wenn er den mininum Vorteil für diejenigen maximiert, die die niedrigste Zuteilung von Sozialfürsorge zuteilenden Mitteln haben (den er als "primäre Waren" kennzeichnet).

Siehe auch

• Alpha-Beta, das beschneidet
• Claude Elwood Shannon
• Computerschach
• Expectiminimax
• Horizont-Wirkung
• Minimax Condorcet
• Minimax bedauern
• Der minimax Lehrsatz von Sion
• Negamax
• Negascout
• Umstellungstisch
• Das maximin Modell von Wald

Referenzen

Außenverbindungen

• Eine Vergegenwärtigung applet
• "Grundsatz von Maximin" aus Einem Wörterbuch von Philosophischen Begriffen und Namen.
• Spielen Sie ein Spiel des Wettens-Und-Bluffens gegen eine minimax Mischstrategie
• Das Wörterbuch des Algorithmus- und Datenstruktur-Zugangs für minimax
• Minimax (mit oder ohne Beschneidung des Alpha-Betas) Algorithmus-Vergegenwärtigung - Spielbaum (Java Applet)
• CLISP minimax - Spiel. (in Spanisch)
• Maximin Strategie aus der Spieltheorie