Massiver Parallel Proof-Number Search löst Sprouts in Rekordzeit

Ein neuer Ansatz aus dem Bereich der Spieltheorie hat die Analyse von komplexen Brettspielen auf ein völlig neues Niveau gehoben. Der auf der Plattform arXiv veröffentlichte Artikel beschreibt einen massiven Parallel Proof-Number Search, der mit bis zu 1024 CPU-Kernen betrieben wird und die bisherige Leistungsgrenze sprengt.

Der Schlüssel zum Erfolg liegt in der Kombination von zwei parallelen Ebenen und dem Austausch von Informationen zwischen den Arbeitskräften. Durch die Nutzung von Grundy-Zahlen zur Reduktion der Spielbäume konnte die Rechenzeit drastisch verkürzt werden. Im Vergleich zum etablierten Sprouts-Solver GLOP erzielt der neue Ansatz einen beeindruckenden 332,9‑fachen Geschwindigkeitszuwachs und übertrifft ihn in der Laufzeit um vier Größenordnungen.

Dank dieser Leistungssteigerung konnte der Solver nicht nur die Sprouts‑Konjektur für 42 neue Positionen bestätigen, sondern auch Beweise generieren, die tausendmal komplexer sind als bisherige Ergebnisse. Damit wird die Anzahl der bekannten Ausgangspositionen nahezu verdoppelt und ein bedeutender Fortschritt in der Spielanalyse erreicht.