In diesem Abschnitt werden die im Zusammenhang mit der algorithmischen Lösung von Kalah verwendeten Suchalgorithmen und Suchstrategien allgemein erläutert.
Eine Zero-Window-Suche ist eine spezielle Form der Alpha-Beta-Suche, bei der das Suchfenster auf ein minimales Intervall reduziert wird. Anstatt einen breiten Wertebereich [alpha,beta] zu durchsuchen, prüft die Suche ausschließlich, ob der tatsächliche Minimax-Wert eines Zustands größer oder kleiner als ein vorgegebener Grenzwert ist.
Bei der klassischen Alpha-Beta-Suche werden die Parameter alpha und beta üblicherweise mit -inf bzw. +inf initialisiert, sodass der vollständige Wertebereich untersucht wird. Bei einer Zero-Window-Suche wird das Suchfenster hingegen auf ein Intervall der Breite null eingeschränkt. Im diskreten Zahlenraum entspricht dies einem Fenster der Form [alpha,alpha + 1].
Durch die starke Einschränkung des Suchfensters treten in der Regel deutlich mehr Alpha-Beta-Cut-offs auf als bei einer Suche mit breitem Fenster. Dadurch kann die Suche wesentlich effizienter sein. Der Nachteil besteht darin, dass eine Zero-Window-Suche nicht direkt den exakten Minimax-Wert liefert, sondern lediglich eine obere oder untere Schranke. Erst durch wiederholte Zero-Window-Suchen mit angepassten Grenzwerten kann der tatsächliche Spielwert bestimmt werden.[1]
Der Algorithmus MTD(f) (Memory-enhanced Test Driver) ist ein auf Minimax-Suche basierender Suchalgorithmus, der konsequent Null-Window-Alpha-Beta-Suchen verwendet und aus der Forschung von Aske Plaat und Kollegen stammt. Er wurde ursprünglich als effizienter Ersatz für traditionelle Alpha-Beta-Varianten wie NegaScout entwickelt und in verschiedenen Spielkontexten getestet (z. B. Schach, Dame, Othello).
MTD(f) führt wiederholt Alpha-Beta-Suchen mit einem Fenster der Größe 0 durch. Bei einem solchen „Zero-Window“ wird nicht versucht, den gesamten Minimax-Wert direkt zu berechnen, sondern es wird jeweils geprüft, ob der Wert eines Knotens größer oder kleiner als ein gegebener Schätzwert ist. Jeder Aufruf von Alpha-Beta mit Nullfenster liefert dabei entweder eine obere oder eine untere Schranke für den tatsächlichen Minimax-Wert. Durch wiederholte Aufrufe mit angepassten Schätzwerten konvergiert der Algorithmus allmählich auf den exakten Minimax-Wert. Die nullfenster-basierten Suchen führen in der Regel zu deutlich mehr Cut-offs als herkömmliche Alpha-Beta-Suche mit breitem Fenster und können dadurch effizienter sein.
Damit MTD(f) effizient arbeitet, wird eine Transpositionstabelle eingesetzt, die bereits berechnete Zustände und Zwischenwerte speichert. Da MTD(f) mehrfach sehr ähnliche Suchen durchführt, ermöglicht die Zwischenspeicherung, redundante Berechnungen zu vermeiden und die Gesamtsuche zu beschleunigen.
Ein zentrales Element von MTD(f) ist ein Startwert („first guess“) für den Minimax-Wert, der üblicherweise aus vorangegangenen Suchdurchläufen stammt. Je näher dieser Schätzwert am tatsächlichen Minimax-Wert liegt, desto weniger Iterationen sind nötig, bis der Algorithmus konvergiert.
In Pseudocode kann die Kernstruktur von MTD(f) wie folgt dargestellt werden:
function MTDF(root, f, d):
g := f
upperBound := +∞
lowerBound := −∞
repeat
if g == lowerBound then beta := g + 1
else beta := g
g := AlphaBetaWithMemory(root, beta - 1, beta, d)
if g < beta then
upperBound := g
else
lowerBound := g
until lowerBound >= upperBound
return g
Dabei liefert AlphaBetaWithMemory den Rückgabewert aus einer Null-Window-Suche, und das Verfahren wiederholt sich, bis die oberen und unteren Schranken zusammenfallen.
Die iterative Tiefensuche (engl. Iterative Deepening Depth-First Search, IDDFS) ist ein Suchverfahren, das Eigenschaften der Tiefensuche und der Breitensuche kombiniert. Ziel ist es, die Speichereffizienz der Tiefensuche mit der Vollständigkeit und Optimalität der Breitensuche zu verbinden.
Die iterative Tiefensuche arbeitet in mehreren Iterationen. In jeder Iteration wird eine Tiefensuche durchgeführt, jedoch mit einem fest vorgegebenen Tiefenlimit. Dieses Tiefenlimit wird schrittweise erhöht:
function ITERATIVE_DEEPENING_SEARCH(start, goal):
depth <- 0
while true do
result <- DEPTH_LIMITED_SEARCH(start, goal, depth)
if result = FOUND then
return FOUND
depth <- depth + 1
function DEPTH_LIMITED_SEARCH(node, goal, limit):
if node = goal then
return FOUND
if limit = 0 then
return CUTOFF
cutoffOccurred <- false
for each successor in EXPAND(node) do
result <- DEPTH_LIMITED_SEARCH(successor, goal, limit - 1)
if result = FOUND then
return FOUND
if result = CUTOFF then
cutoffOccurred <- true
if cutoffOccurred = true then
return CUTOFF
else
return FAILURE
Die iterative Tiefensuche führt wiederholt eine tiefenbegrenzte Tiefensuche mit sukzessiv wachsendem Tiefenlimit aus. Die Hilfsfunktion DEPTH_LIMITED_SEARCH verhindert, dass die Suche tiefer als das aktuelle Limit vordringt. Ein Abbruch erfolgt, sobald der Zielzustand gefunden wird.
Die iterative Tiefensuche ist vollständig, das heißt, sie findet eine Lösung, sofern eine existiert. Bei gleich gewichteten Kanten liefert sie außerdem eine optimale Lösung, da Zielzustände in aufsteigender Tiefe gefunden werden, ähnlich wie bei der Breitensuche. Der Speicherbedarf ist gering, da wie bei der Tiefensuche nur der aktuelle Suchpfad gespeichert werden muss. Im Gegensatz zur Breitensuche ist kein Speicher für alle Knoten einer Ebene notwendig.
Ein Nachteil der iterativen Tiefensuche ist, dass Knoten in den oberen Ebenen mehrfach besucht werden, da jede Iteration die Suche erneut von der Wurzel aus startet. Dieser zusätzliche Rechenaufwand ist jedoch meist akzeptabel, da der Großteil der Knoten typischerweise in den tiefen Ebenen des Suchbaums liegt. Asymptotisch entspricht die Laufzeit der der Breitensuche.
Bruno Schaffer. Analyse eines Minimax/MCTS Hybriden anhand des Spiels „Catch the Lion“ (2024) (https://doc.neuro.tu-berlin.de/bachelor/2024-BA-BrunoSchaffer.pdf) ↩︎
Aske Plaat. Mtd(f) algorithm, a minimax algorithm faster than negascout (https://people.csail.mit.edu/plaat/mtdf.html) ↩︎
Iterative Tiefensuche (https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search) ↩︎