Go gehört zu den wenigen Brettspielen, in denen professionelle Spieler noch nicht von Computern geschlagen werden können. Jetzt wurde das Spiel für 7×7 Felder große Bretter vollständig gelöst. Der professionelle Go Spieler Li Zhe und zwei Forscher der Universität von Qingdao präsentierten dieses Ergebnis schon am Samstag.
Aja Huang hat in einem Forum die wichtigsten Ergebnisse beschrieben. Demnach gewinnt der Spieler der mit den schwarzen Steinen anfängt immer mit 9 Punkten, wenn er eine optimale Strategie verfolgt. Abhängig von den ersten sieben Zügen des Spiels entwickelt sich ein optimales Spiel auf eines von fünf grundlegenden Mustern mit dem gleichen Punktergebnis zu. Genauere Details wurden leider noch nicht aus dem Chinesischen übersetzt.
Reguläre Bretter haben 19×19 Felder
Beim Go muss freies Territorium auf dem Brett zu umstellt werden. Wobei Steingruppen auch umstellt und geschlagen werden können. Jeder geschlagene Stein bringt einen Punkt. Keine Brettstellung darf wiederholt werden. Das reguläre Go Brett für Wettkämpfe hat allerdings eine Größe von 19×19 Feldern, wobei neue Spieler meist mit 9×9 Brettern anfangen.
Eine vollständige Lösung des regulären 19×19 Bretts ist nicht abzusehen. Bisher waren vollständige Lösungen des Spiels nur bis zu einer Brettgröße von 6×7 Feldern bekannt. Die Zahl der möglichen Züge auf dem regulären Brett wird auf etwa 10 hoch 170 geschätzt. Die Zahl der Atome bekannten Universum schätzt man dagegen nur auf etwa 10 hoch 80.
Trotzdem werden Computer Go Programme immer besser, seit im Jahr 2006 die ersten Programme auf Basis der Monte-Carlo Methode veröffentlicht wurden. Deren Spielstärke ist inzwischen auf dem Niveau fortgeschrittener Amateure, in den mittleren Dan Rängen. Programme die Brute-Force Ansätze verfolgten, wie beim Schach oder anderen Spielen, erreichten dagegen durchweg nur die Kyu-Ränge der Gelegenheitsspieler.
Zufällige Suchbäume zämen
Bereits im Jahr 2012 wurde ein möglicher Ansatz über Meta-Monte-Carlo-Suchbäume als Lösungsmethode für das 7×7 Brett vorgestellt. Wie bei den Computer-Go Programmen ist der Kern der Idee (pseudo-)zufällige Zugfolgen nach ihrer Siegwahrscheinlichkeit auszuwerten. Allerdings wird die Methode noch ergänzt durch ein bereits bekanntes Eröffnungsbuch. Zusammen mit dem Eröffnungsbuch und der statistischen Auswertung der Siegwahrscheinlichkeit zufälliger Spielvariationen, kann das Eröffnungsbuch erweitert werden. In diesem Prozess werden allerdings Züge mit einer Gewinnwahrscheinlichkeit unter einem bestimmten Schwellenwert ignoriert. Dadurch werden Situationen ausgeschlossen, in der ein schlechter zufällig ausgewählter Spielzug zur Niederlage führt, aber alle folgenden Züge trotzdem noch ausgewertet werden. Das resultierende Programm spielte wesentlich besser als ein rein zufallsbasiertes Programm.
Um den Ansatz als Lösungsverfahren zu verwenden, sollten die pseudozufälligen Zugfolgen durch einen vorgegebenen Seed deterministisch gemacht werden. Danach könnte ein Alpha-Beta-Algorithmus (also Brute Force) die nach der Eröffnung verbliebenen Züge auf dem 7×7 Brett lösen. Das Verfahren ist damit nicht vollständig, weil viele als empirisch Unsinnig bekannte Eröffnungen nie berechnet wurden. Dazu gehören beispielsweise alle Eröffnungen in denen der erste Zug in einer Spielfeldecke liegt, wo er keinerlei Territorium einschließen kann.
Kommentare (2)