Der MiniMax Algorithmus

Der Minimax-Algorithmus dient ganz allgemein der Entscheidungsfindung. In Zwei-Personen-Nullsummenspielen, wie Reversi, hilft der Algorithmus herauszufinden, welches der optimale nächste Zug ist gegeben das beide Spieler optimal spielen. Optimal bedeutet dabei, dass beide gegeben der gleichen Strategie ihren Gewinn maximieren. Als "Java Pseudocode" sieht der Algorithmus beispielsweise so aus 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int max(Position pos, int depth) {
    if(depth == 0)
        return eval(pos, me);
    moves = pos.generateMoves();
    int maxWert = -INFINITY;
    foreach(m in moves) {
        pos.makeMove(m);
        int value = min(pos, depth - 1);
        pos.undoMove(m);
        if(value > maxWert) {
            maxWert = value;
        }
    }
    return maxWert;
}

int min(Position pos, int depth) {
    if(depth == 0)
        return eval(pos, foe);
    moves = pos.generateMoves();
    int minWert = INFINITY;
    foreach(m in moves) {
        pos.makeMove(m);
        int value = max(pos, depth - 1);
        pos.undoMove(m);
        if(value < minWert) {
            minWert = value;
        }
    }
    return minWert;
}
Nun sind dies zwei Funktionen, welche quasi dasgleiche machen. Da man als Programmierer gerne faul ist und zudem noch die Anzahl Fehler proportional zu den Anzahl Zeilen Code ist, möchte man dies natürlich reduzieren. Deshalb hier ohne Beweis auf Gleichheit die Alternative Variante in nur einer Funktion, NegaMax genannt: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
int negaMax(Position pos, int depth, int player) {
    if(depth == 0)
        return eval(pos);
    moves = pos.generateMoves();
    int maxWert = -INFINITY;
    foreach(m in moves) {
        pos.makeMove(m);
        int value = -negaMax(pos, depth - 1, otherPlayer(player));
        pos.undoMove(m);
        if(value > maxWert) {
            value = maxWert;
        }
    }
    return maxWert;
}
Die Grundidee dabei ist, dass jeder Spieler seinen Gewinn maximieren will. Deshalb multipliziert man den Wert des anderen Spielers mit -1; daher auch der Name "NegaMax".

Alpha Beta Suche

Nun ist der Minimax Algorithmus nicht sehr effizient, da er auch Knoten auswertet die den finalen Wert an der Wurzel gar nicht mehr beeinflussen können. Deshalb führt man obere und untere Schranken des momentan besten Wertes ein um frühzeitig irrelevante Knoten aus der Suche ausschliessen zu können. Die obenstehende NegaMax-Funktion lässt sich wie folgt ergänzen: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
int negaMax(Position pos, int alpha, int beta, int depth, int player) {
    if(depth == 0)
        return eval(pos);
    moves = pos.generateMoves();
    
    foreach(m in moves) {
        pos.makeMove(m);
        int value = -negaMax(pos, -beta, -alpha, depth - 1, otherPlayer(player));
        pos.undoMove(m);
        if(value >= beta)
            return beta;
        else if(value > alpha)
            alpha = value;
    }
    return alpha;
}

Alpha-Beta Optimierungen

Die Alpha-Beta-Suche findet den gleichen Wert wie der MiniMax-Algorithmus und evaluiert dabei höchstens soviele Knoten wie selbiger. Unser Ziel sollte es nun sein, möglichst wenige Knoten evaluieren zu müssen. Da der Wert sowieso derselbe ist, bringt der Mehraufwand auch nichts.
Bei der Betrachtung des Algorithmuses fällt auf, dass idealerweise der beste Zug zuerst evaluiert wird, weil dann die Anzahl Schnitte maximal wird. Wird beispielsweise das Übungsbeispiel auf der Vorlesungshomepage von rechts nach links durchgerechnet, müssen mehr Knoten evaluiert werden. Dies bedeutet, dass sich eine geschickte Zugvorsortierung lohnen kann. Hierfür kann zum Beispiel die Auswertung des Spielbaums zur Tiefe (d - 1) herbeigezogen werden. In diesem Zusammenhang kann über eine Implementierung einer "Transposition Table" nachgedacht werden. Einerseits werden so wichtige Werte einer vorherigen Suche gespeichert andererseits müssen Positionen der aktuellen Suche nicht neu evaluiert werden. Mit so einer Tabelle lässt sich der Alpha-Beta-Algorithmus mit Erinnerungsvermögen implementieren (hier gefunden). 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
int negaMax(Position pos, int alpha, int beta, int depth, int player) {
    if(depth == 0)
        return eval(pos);

    e = table.lookUp(pos);
    if(e is valid) {
        if(e.lowerBound >= beta)
            return e.lowerBound;
        if(e.upperBound <= alpha)
            return e.upperBound;
        alpha = Math.max(alpha, e.lowerBound);
        beta = Math.min(beta, e.upperBound);
    }

    moves = pos.generateMoves();
    sortMovesByHeuristic(moves, e);
    Move best = null;
    int bestVal = -INFINITY;
    foreach(m in moves) {
        pos.makeMove(m);
        int value = -negaMax(pos, -beta, -alpha, depth - 1, otherPlayer(player));
        pos.undoMove(m);
        if(value > bestVal) {
            best = m;
            bestVal = value;
            if(bestVal >= beta) {
                break;
            }
            else if(bestVal > alpha)
                alpha = bestVal;
        }
    }
    if(bestVal > alpha) {
        e.lowerBound = bestVal;
        e.move = best;
        table.store(e);
    }
    if(bestVal < beta) {
        e.upperBound = bestVal;
        table.store(e);
    }

    return bestVal;
}
Dieser Link stellt zudem noch eine Verbesserung des regulären Alpha-Beta-Algorithmuses vor. Auch hier ist das Ziel die Anzahl Knoten die pro Tiefe analysiert werden müssen zu minimieren.
Eine andere Optimierung ist der Algorithmus PVS/NegaScout.

Viele Informationen finden sich im Computer Schach-Wiki. Zumindest alle Informationen bezüglich der Suche sind auch für Reversi relevant.