Die Retrograde Analyse (Rückwärtsanalyse) ist eine Technik aus der Spieltheorie und der künstlichen Intelligenz, um Spielpositionen zu lösen, indem man vom Spielende rückwärts zum Spielbeginn (oder zu einer gesuchten Stellung) rechnet.
Dieses Verfahren ist die Grundlage für Endspiel-Datenbanken (Endgame Tablebases). Sobald eine solche Datenbank erstellt ist, muss ein Computer nicht mehr "rechnen", sondern führt lediglich einen Speicherzugriff (Lookup) durch, um den perfekten Zug zu finden. [1]
Im Gegensatz zur klassischen Vorwärtssuche, die von der aktuellen Position ausgeht und mögliche Züge in die Zukunft simuliert, beginnt die retrograde Analyse bei den terminalen Zuständen.
Das Verfahren arbeitet oft iterativ über die "Distanz zum Matt" (oder Sieg):
Das bekannteste Einsatzgebiet sind Endspiele in Brettspielen. Da die Anzahl der Spielsteine gering ist, wird der Zustandsraum klein genug, um ihn vollständig zu enumerieren.
Auch für Solitär-Spiele wie den Zauberwürfel (Rubik's Cube) wird retrograde Analyse genutzt, um die "Gottes Zahl" (maximale Anzahl an Zügen zur Lösung aus jeder Position) zu bestimmen.
Die größte Hürde für die retrograde Analyse ist der Speicherplatz. Da der Algorithmus den Status aller möglichen Positionen speichern muss, wächst der Bedarf exponentiell mit der Anzahl der Spielsteine.
Um riesige Datenbanken (wie bei Chinook mit 39 Billionen Einträgen) handhabbar zu machen, sind spezielle Kompressionsverfahren notwendig, die einen schnellen Zugriff ermöglichen, ohne die Daten komplett entpacken zu müssen. [3:1]
THOMPSON, Ken. Retrograde analysis of certain endgames. ICGA Journal, 1986, 9. Jg., Nr. 3, S. 131-139. ↩︎ ↩︎
GASSER, Ralph. Solving nine men's morris. Computational Intelligence, 1996, 12. Jg., Nr. 1, S. 24-41. ↩︎
SCHAEFFER, Jonathan, et al. Checkers is solved. science, 2007, 317. Jg., Nr. 5844, S. 1518-1522. ↩︎ ↩︎