Shogi-Komplexität exakt ermittelt: 6,55 × 10^68 erreichbare Positionen

Die Frage nach der genauen Anzahl der erreichbaren Spielpositionen im Shogi, dem japanischen Schach, war lange Zeit ein Rätsel. Frühere kombinatorische Schätzungen ließen einen riesigen Wertebereich zwischen 10^64 und 10^69 zurück, weil es schwierig war, aus der anfänglichen Stellung nur die tatsächlich spielbaren Positionen herauszufiltern.

In einer neuen Studie wurde ein hochpräziser Monte‑Carlo‑Ansatz vorgestellt, der zusätzlich eine innovative Rückwärtssuche nutzt, die sich auf „King‑King‑nur“-Positionen konzentriert. Durch diese Technik wird die Suche nach unspielbaren Positionen deutlich vereinfacht, weil nicht mehr jede Stellung einzeln bis zur Ausgangsposition zurückverfolgt werden muss.

Aus einer Stichprobe von fünf Milliarden zufällig generierten Positionen ergab die Analyse, dass es im Shogi etwa 6,55 × 10^68 legale Positionen gibt – ein Ergebnis mit 3‑Sigma‑Vertrauensniveau. Der gleiche Ansatz zeigte für Mini‑Shogi eine Komplexität von rund 2,38 × 10^18. Damit wird die bisherige Schätzlücke von fünf Größenordnungen drastisch reduziert und ein neues Maß an Genauigkeit in der Spieltheorie erreicht.