imported>Nukelavee: /* growthexperiments-addlink-summary-summary:2|0|0 */

2024-11-13T09:29:01Z

growthexperiments-addlink-summary-summary:2|0|0

Neue Seite

Der '''Expectiminimax-Algorithmus''' ist eine erweiterte Version des [[Minimax-Algorithmus]], welcher Zufallselemente wie das Fallen eines Würfels berücksichtigt. Der Algorithmus findet daher bei der [[Spieleprogrammierung]] von [[Nullsummenspiel|Nullsummenspielen]] mit zwei Teilnehmern wie beispielsweise [[Backgammon]] seine häufigste Anwendung.

== Eigenschaften ==
Der Algorithmus gleicht in weiten Teilen dem herkömmlichen MiniMax-Algorithmus, wird allerdings durch eine Fallunterscheidung erweitert. Alle möglichen Ereignisse (die z. B. aus unterschiedlichen Augenzahlen resultieren) werden getrennt berechnet, als wären sie real. Anschließend werden alle so entstehenden [[Wahrscheinlichkeitsast|Wahrscheinlichkeitsäste]] einer [[Wahrscheinlichkeitstiefe]] dann mit der Wahrscheinlichkeit ihres Eintretens multipliziert und addiert. Die Summe bildet dann das Kriterium für den bekannten Minimierungs-/Maximierungsprozess. Die Werte im Baum gleichen damit formal der mathematischen Definition des [[Erwartungswert]]es (engl. ''Expected value'').

== Pseudo-Code ==
Der Expectiminimax-Algorithmus wurde zuerst von [[Donald Michie]] vorgeschlagen.<ref>[[Donald Michie|D. Michie]]: ''Game-playing and game-learning automata.'' In: Leslie Fox (Hrsg.): ''Advances in Programming and Non-Numerical Computation.'' Pergamon Press, Oxford u. a. 1966, S. 183–200.</ref>
Im Folgenden ist der [[Pseudocode]] gegeben:

'''function''' expectiminimax(Ast, Tiefe)
'''WENN''' Ast ist ein Bewertungsast '''ODER''' Tiefe = 0
'''return''' die heuristische Bewertung der aktuellen Situation
'''WENN''' der Gegner am Zug ist
// Gib den mit dem geringsten Wert bewerteten Zug zurück
'''let''' α := +∞
'''FÜR JEDEN''' Zug des Astes
α := min(α, expectiminimax(Nachfolger, Tiefe-1))
'''SONST WENN''' wir am Zug sind
// Gib den mit dem höchsten Wert bewerteten Zug zurück
'''let''' α := -∞
'''FÜR JEDEN''' Zug des Astes
α := max(α, expectiminimax(Nachfolger, Tiefe-1))
'''SONST WENN''' zufälliges Ereignis
// Gib durchschnittliche Bewertung aller Möglichkeiten zurück
'''let''' α := 0
'''FÜR JEDEN''' Nachfolger des Astes
α := α + (Wahrscheinlichkeit[Nachfolger] * expectiminimax(Nachfolger, Tiefe-1))
'''return''' α

== Bewertungsfunktion ==
Die Bewertungsfunktion muss wie im MiniMax-Algorithmus auf Grundlage von [[Heuristik|Heuristiken]] die aktuelle Stellung im Baum bewerten. Anders als beim MiniMax-Algorithmus spielt der Wertebereich der Funktion jedoch eine entscheidende Rolle. Werden im MiniMax-Algorithmus Gewinn- oder Verluststellungen mit <math>+\infty</math> bzw. <math>-\infty</math> gekennzeichnet, führt eine derartige Handhabung im Expectiminimax-Algorithmus zu [[Informationsverlust]]. Kann ein Spieler beispielsweise mit einer 1, 2 und 3 als Augenzahl eine gute Situation erreichen, verliert aber, wenn er eine 4 würfelt, so ergibt sich im Algorithmus bei gleichen Wahrscheinlichkeiten:<br />
<math>\left(76\frac 1 4\right) + \left(112 \frac 1 4\right) + \left(86 \frac 1 4 \right) + \left(-\infty \frac 1 4\right) = -\infty</math><br />
Der Zug wird verworfen, obwohl er nur mit einer geringen Wahrscheinlichkeit zum Verlieren des Spieles führt. Problematisch wird dieser Effekt besonders zum Ende eines Spiels, wenn sich Gewinn- und Verlustbewertungen häufen und eventuell in der gleichen [[Wahrscheinlichkeitstiefe]] auftreten. Um solche Fehler zu verhindern, müssen feste Wertebereiche definiert und Gewinn- und Verlustbewertungen getrennt behandelt werden. In der Praxis werden meist komplexe Datentypen als Bewertungswerte verwendet, in denen die Bewertung der Situation in Grundbewertung und Gewinn/Verlust-Chance geteilt ist.

== Pruning ==
Eine effizientere Gestaltung der Berechnung durch ein Wegschneiden von Ästen ([[Pruning]]) wie im [[Alpha-Beta-Suche|Alpha-Beta-Algorithmus]] ist auch beim Expectiminimax-Algorithmus möglich. Die Implementierung gestaltet sich jedoch durch die Festlegung bestimmter Wertebereiche komplexer und unterscheidet sich bei unterschiedlichen Anwendungen.<ref>Stuart Jonathan Russell, Peter Norvig: ''Artificial intelligence. A modern approach.'' 3. Auflage. Prentice-Hall, Upper Saddle River NJ u. a. 2010, ISBN 978-0-13-604259-4, S. 177 f.</ref>

== Einzelnachweise ==
<references />

[[Kategorie:Algorithmus]]

Expectiminimax-Algorithmus - Versionsgeschichte

imported>Nukelavee: /* growthexperiments-addlink-summary-summary:2|0|0 */