Die *-Minimax Algorithmen (Star1, Star2 und Star2.5) sind Erweiterungen des Expectimax Verfahrens, die darauf abzielen, die Anzahl der zu untersuchenden Knoten in stochastischen Spielbäumen zu reduzieren. Während Expectimax für Spiele mit Zufallskomponenten optimale Ergebnisse liefert, ist es aufgrund der hohen Verzweigung häufig rechenintensiv. Die *-Minimax Familie nutzt Schranken (upper/lower bounds) und Suchfenster, um Teile des Baums frühzeitig abzuschneiden (Pruning), ohne das korrekte Ergebnis zu verändern.
Dieser Artikel beschreibt ausschließlich die Implementierungsaspekte der drei Varianten und stellt den vollständigen Pseudocode für das Spiel Carcassonne bereit.[1] (basierend auf [2]) Eine theoretische Einführung findet sich im Artikel MiniMax.
Alle drei *-Expectimax Algorithmen basieren auf dem klassischen Expectimax Algorithmus. Der Suchbaum enthält dabei abwechselnd:
MAX Knoten = der Spieler wählt den besten Zug)
Zufallsknoten = es wird zufällig ein neues Plättchen gezogen
Der MAX Knoten wählt immer den Kindknoten mit der höchsten Bewertung. Der Zufallsknoten berechnet den Erwartungswert seiner Kinder.
In Carcassonne entsteht ein Zufallsknoten durch das Ziehen eines neuen Plättchens. Da verschiedene Plättchentypen unterschiedlich häufig vorkommen, sind die Wahrscheinlichkeiten nicht gleichverteilt. Dies führt zu einem sehr hohen Verzweigungsfaktor, weshalb Expectimax ohne Pruning nur bis Tiefe 2–3 praktikabel ist.
Theoretische Schranken dienen als Ersatzwerte für noch nicht untersuchte Nachfolger:
L = theoretischer Minimalwert der Bewertungsfunktion
U = theoretischer Maximalwert der Bewertungsfunktion
Sie ermöglichen es, den Wert eines Zufallsknotens abzuschätzen, bevor alle Nachfolger untersucht wurden.
Gibt an, welcher Wertebereich für den aktuellen Knoten noch relevant ist
Liegt der geschätzte Werte sicher außerhalb des Fenster, so kann der teilbaum abgeschnitten werden.
Die *-Minimax Algorithmen kombinieren diese Fenster mit den theoretischen Schranken, um Zufallsknoten effizient abzuschneiden.
Negamax ist eine vereinfachte Form von Minimax, die davon ausgeht, dass der Wert eines Zustands aus Sicht des Gegners einfach das Negativ des eigenen Werts ist.
und nutzt die Identität:
Damit kann die gesamte Minimax Logik in eine einzige rekursive Funktion überführt werden, die immer maximiert. Der Algorithmus probiert alle möglichen Züge aus, bewertet den resultierenden Zustand aus Sicht des Gegners (daher das Minuszeichen) und wählt anschließend den besten Wert.
In den *-Expectimax Algorithmen wird Negamax an MAX Knoten eingesetzt. Der einzige Unterschied: Statt expectimax() wird jeweils die aktive Variante aufgerufen.
Psydocode:
float negamax(int depth){
float best = -Infinity;
for (Move move : getPossibleMoves()) {
executeMove(move);
// Bewertung aus Sicht des Gegners
float value = -expectimax(depth - 1);
undoMove();
best = max(best, value);
}
return best;
}
Hinweis: Bei den *-Expectimax Algorithmen wird im obigen Code expectimax() durch die jeweilige Star Variante ersetzt.
Star1 berechnet den Erwartungswert eines Zufallsknotens, prüft aber nach jedem Nachfolger, ob der endgültige Wert sicher außerhalb des Alpha Beta Fensters liegt. Wenn das der Fall ist, wird der Rest des Baums abgeschnitten (Pruning). Für unbesuchte Nachfolger werden die theoretischen Schranken Lund Uverwendet.
Da Carcassonne nicht gleichverteilte Plättchenwahrscheinlichkeiten besitzt, wird jeder Nachfolger mit seiner tatsächlichen Wahrscheinlichkeit gewichtet.
float star1(float alpha, float beta, int depth){
if (gameIsFinished() || depth == 0)
return getValue();
cur_x = 0; // bisher akkumulierte Erwartungswerte
cur_y = 1; // verbleibende Wahrscheinlichkeit
for (Tile newTile : getDifferentTiles()) {
probability = numberOfTiles(newTile) / numberOfRemainingTiles();
cur_y -= probability;
cur_alpha = (alpha - cur_x - U * cur_y) / probability;
cur_beta = (beta - cur_x - L * cur_y) / probability;
ax = max(L, cur_alpha);
bx = min(U, cur_beta);
setNextTileInGame(newTile);
value = negamax(ax, bx, depth);
undoSetNextTile();
if (value >= cur_beta) return beta;
if (value <= cur_alpha) return alpha;
cur_x += probability * value;
}
return cur_x;
}
Star2 führt zuerst eine Probing Phase durch: Für jeden möglichen Zufallsnachfolger wird nur ein einziges Kind untersucht, um eine bessere untere Schranke zu erhalten. Wenn diese Schranken zeigen, dass der Wert außerhalb des Alpha Beta Fensters liegt, kann der gesamte Restbaum verworfen werden. Falls nicht, folgt eine normale Star1 Suche — aber mit engeren Schranken.
Diese Variante ist besonders effektiv in Carcassonne, da die wahrscheinlichsten Plättchen oft ähnliche Strukturen erzeugen und frühe Schranken sehr aussagekräftig sind.
float star2(float alpha, float beta, int depth){
if (gameIsFinished() || depth == 0)
return getValue();
// Probing phase
cur_x = 0;
cur_y = 1;
cur_w = 0;
cur_alpha = (alpha - U * (1 - firstPossibleTile().probability))
/ firstPossibleTile().probability;
ax = max(L, cur_alpha);
for (Tile newTile : getDifferentTiles()) {
probability = numberOfTiles(newTile) / numberOfRemainingTiles();
cur_y -= probability;
cur_beta = (beta - L * cur_y - cur_x) / probability;
bx = min(U, cur_beta);
setNextTileInGame(newTile);
value = nProbe(ax, bx, depth);
undoSetNextTile();
cur_w += value;
if (value >= cur_beta) return beta;
cur_x += probability * value;
}
// Star1 search phase (gekürzt)
...
}
Star2.5 erweitert die Probing Phase von Star2: Statt nur eines Kindes werden mehrere Kinder untersucht (gesteuert durch den probingFactor). Dadurch entstehen noch bessere Schranken, und der Algorithmus kann noch aggressiver prunen. Es gibt zwei verschiedene Varianten, den sequentiellen und den zyklischen Star2.5.
float nProbe(float alpha, float beta, int depth, int probingFactor){
for (int i = 0; i < probingFactor && i < possibleMoves.size(); i++) {
Move move = possibleMoves.get(i);
executeMove(move);
float value = -star2(-beta, -alpha, depth - 1);
undoMove();
if (value >= beta) return beta;
if (value > alpha) alpha = value;
}
return alpha;
}
Der Algorithmus ist derselbe wie bei Star2. Allerdings unterscheidet sich die Methode nprobe, da in der Sondierungsphase mehrere Kinder ausgewertet werden. Während diese Methode bei Star2 nur ein Kind untersucht, erhält sie nun einen Sondierungsfaktor und durchsucht entsprechend viele Kinder. Falls kein Cut-off auftritt, gibt sie den höchsten gefundenen Wert zurück. Der Psydocode zeigt die Methode für den sequentiellen Star2.5.
HEYDEN, Cathleen. Implementing a computer player for Carcassonne. Master's thesis, Department of Knowledge Engineering, Maastricht University, 2009.
pdf ↩︎
BALLARD, Bruce W. The*-minimax search procedure for trees containing chance nodes. Artificial Intelligence, 1983, 21. Jg., Nr. 3, S. 327-350.
pdf ↩︎