Philosophie Lexikon der ArgumenteHome
| |||
|
| |||
| Minimax-Algorithmus: Der Minimax-Algorithmus ist ein rekursiver Algorithmus zur Auswahl des nächsten Zuges in einem Spiel mit zwei Spielern. Er funktioniert, indem er rekursiv alle möglichen Züge des Spielers und seines Gegners betrachtet und dann den Zug wählt, der zum besten Ergebnis für den Spieler führt. Siehe auch Künstliche Intelligenz, Spieltheorie, Strategien._____________Anmerkung: Die obigen Begriffscharakterisierungen verstehen sich weder als Definitionen noch als erschöpfende Problemdarstellungen. Sie sollen lediglich den Zugang zu den unten angefügten Quellen erleichtern. - Lexikon der Argumente. | |||
| Autor | Begriff | Zusammenfassung/Zitate | Quellen |
|---|---|---|---|
|
Peter Norvig über Minimax-Algorithmus – Lexikon der Argumente
Norvig I 164 Minimax-Algorithmus/Spiel/Norvig/Russell: Der Minimax-Wert eines Knotens ist der Nutzen (für MAX), sich im entsprechenden Zustand zu befinden, vorausgesetzt, dass beide Spieler von dort bis zum Ende des Spiels optimal spielen. Norvig I 165 Der Minimax-Algorithmus (...) berechnet die Minimax-Entscheidung aus dem aktuellen Zustand. Es verwendet eine einfache rekursive Computation der Minimax-Werte jedes Nachfolgezustands und implementiert direkt die definierenden Gleichungen. Die Rekursion geht den ganzen Pfad bis zu den Blättern des Baumes hinunter, und dann werden die Minimalwerte durch den Baum gesichert, während sich die Rekursion abwickelt. Der Minimax-Algorithmus führt eine vollständige Tiefenerkundung des Spielbaums durch. Bei echten Spielen sind die Zeitkosten natürlich völlig unpraktisch, aber dieser Algorithmus dient als Grundlage für die mathematische Analyse von Spielen und für praktischere Algorithmen. Norvig I 167 Das Problem bei der Minimax-Suche ist, dass die Anzahl der zu untersuchenden Spielzustände exponentiell in der Tiefe des Baumes ist. Leider können wir den Exponenten nicht eliminieren, aber es stellt sich heraus, dass wir ihn effektiv in zwei Hälften teilen können. Der Trick ist, dass es möglich ist, die richtige Minimax-Entscheidung zu berechnen, ohne jeden Knoten im Spielbaum zu betrachten. Lösung: Alpha-Beta-Pruning. Wenn es auf einen Standard-Minimax-Baum angewendet wird, gibt es den gleichen Spielzug heraus wie Minimax, schneidet aber Äste weg, die die endgültige Entscheidung nicht beeinflussen können. Das allgemeine Prinzip ist folgendes: Betrachten Sie einen Knoten n Norvig I 168 irgendwo im Baum (siehe Abbildung 5.6), sodass der Spieler die Wahl hat, zu diesem Knoten zu wechseln. Wenn der Spieler eine bessere Wahl m hat, entweder am übergeordneten Knoten von n oder an einem beliebigen Auswahlpunkt weiter oben, dann wird n im tatsächlichen Spiel nie erreicht. Sobald wir also genug über n herausgefunden haben (durch die Untersuchung einiger seiner Nachkommen), um zu diesem Schluss zu kommen, können wir ihn beschneiden. Norvig I 190 Der Minimax-Algorithmus geht auf eine Arbeit von Ernst Zermelo(1) aus dem Jahr 1912 zurück, dem Entwickler der modernen Mengenlehre. Die Arbeit enthielt leider mehrere Fehler und beschrieb minimax nicht korrekt. Andererseits hat es die Ideen der retrograden Analyse dargelegt und vorgeschlagen (aber nicht bewiesen), was als Zermelos Theorem bekannt wurde: dass das Schachspiel vorbestimmt ist - Weiß kann einen Sieg erzwingen oder Schwarz oder es ist ein Unentschieden; wir wissen einfach nicht, welches. Zermelo sagt, dass, sollten wir es schließlich wissen, "Schach natürlich den Charakter eines Spiels verlieren würde." Eine solide Grundlage für die Spieltheorie wurde in der wegweisenden Arbeit Theory of Games and Economic Behavior (von Neumann und Morgenstern, 1944)(2) entwickelt, die eine Analyse beinhaltete, die zeigte, dass einige Spiele Strategien erfordern, die zufällig (oder anderweitig unvorhersehbar) sind. Norvig I 191 VsMinimax-Algorithmen: D. F. Beal (1980)(3) und Dana Nau (1980(4), 1983(5)) untersuchten die Schwächen der bei approximativen Evaluationen angewendeten Minimax. Sie zeigten, dass unter bestimmten Annahmen über die Verteilung der Blattwerte im Baum die Minimaxierung an der Wurzel Werte liefern kann, die tatsächlich weniger zuverlässig sind als die direkte Nutzung der Evaluationsfunktion selbst. >Computerspiele/Norvig. 1. Zermelo, E. (1913). Über Eine Anwendung der Mengenlehre auf die Theorie des Schachspiels. In Proc. Fifth International Congress of Mathematicians, Vol. 2, pp. 501–504 2. von Neumann, J. and Morgenstern, O. (1944). Theory of Games and Economic Behavior (first edition). Princeton University Press 3. Beal, D. F. (1980). An analysis of minimax. In Clarke, M. R. B. (Ed.), Advances in Computer Chess 2, pp. 103–109. Edinburgh University Press 4. Nau, D. S. (1980). Pathology on game trees: A summary of results. In AAAI-80, pp. 102–104. 5. Nau, D. S. (1983). Pathology on game trees revisited, and an alternative to minimaxing. AIJ, 21(1–2), 221–244._____________ Zeichenerklärung: Römische Ziffern geben die Quelle an, arabische Ziffern die Seitenzahl. Die entsprechenden Titel sind rechts unter Metadaten angegeben. ((s)…): Kommentar des Einsenders. Übersetzungen: Lexikon der ArgumenteDer Hinweis [Begriff/Autor], [Autor1]Vs[Autor2] bzw. [Autor]Vs[Begriff] bzw. "Problem:"/"Lösung", "alt:"/"neu:" und "These:" ist eine Hinzufügung des Lexikons der Argumente. |
Norvig I Peter Norvig Stuart J. Russell Artificial Intelligence: A Modern Approach Upper Saddle River, NJ 2010 |
||
> Gegenargumente gegen Norvig
> Gegenargumente zu Minimax-Algorithmus ...
