Expectiminimax-Algorithmus

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 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 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 Erwartungswertes (engl. Expected value).

Pseudo-Code

Der Expectiminimax-Algorithmus wurde zuerst von Donald Michie vorgeschlagen.^[1] 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öchstem Wert bewerteten Zug zurück
        let α := -∞
        FÜR JEDEN Zug des Astes
            α := max(α, expectiminimax(Nachfolger, depth-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 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 $+\infty$ bzw. $-\infty$ 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:
$\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$
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-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. Zudem ist das Pruning wesentlich ineffizienter als beim MiniMax- bzw. Alpha-Beta-Algorithmus, so dass sich der Aufwand einer Implementierung meist nicht lohnt^[2].

Einzelnachweise

1. ↑ D. Michie (1966). Game-playing and game-learning automata. In L. Fox (ed.), Advances in Programming and Non-Numerical Computation, S. 183-200.
2. ↑ Stuart Jonathan Russell, Peter Norvig (2010). Artificial intelligence: a modern approach (3rd edition), S. 177f.