Das asiatische Brettspiel Go ist für Computer eine harte Nuss. Die Regeln sind einfacher als etwa die von Schach, und dennoch ist das Spiel ausgesprochen komplex: Auf einem 19x19 Linien großen Spielfeld werden abwechselnd schwarze und weiße Steine gesetzt, die sich anschließend nicht bewegen. Komplett umzingelte Gruppen werden geschlagen, wer am Ende das meiste Gebiet mit seinen Steinen umschlossen hat, gewinnt.

Die klassischen Baumsuchverfahren scheitern beim Go an der schier unendlichen Größe des Baums: Beim ersten Zug gibt es 361 Möglichkeiten, beim zweiten 360, beim dritten 359 ... da kommt man mit einer vollständigen Suche nicht weit. Außerdem hat eine Go-Partie in der Regel mehr Züge als eine Schach-Partie, der Baum ist also nicht nur breiter, sondern auch noch höher.

1997 schlug der eigens dafür entwickelte Schachcomputer Deep Blue den amtierenden Schachweltmeister Kasparow erstmals unter Turnierbedingungen. Beim Go dagegen sah es vergleichsweise düster aus: Die besten Programme hatten damals eine Spielstärke von etwa 10 kyu, ein Niveau, das ein Mensch in einigen Monaten intensiver Beschäftigung mit dem Spiel erreichen kann, und 10 Grade unter dem niedrigsten Meistergrad Shodan (1 dan), vergleichbar vielleicht mit dem schwarzen Gürtel in Karate. Während vergleichsweise viele Amateure es bis 10 kyu schaffen, ist Shodan eine Spielstärke, die längst nicht jeder erreicht.

Darren Cook machte damals eine Umfrage in der Computer-Go-Szene, wann denn wohl die Computer die Spielstärke Shodan erreichen würden. Die Schätzungen, veröffentlicht in einer Mail an die Computer-Go-Mailing-Liste, reichten von 1999 bis 2500, wobei doch viele Programmierer zuversichtlich waren, dass es bis 2010 zu schaffen sei.

John Tromp, damals 1 kyu stark, teilte diesen Optimismus nicht und wettete 1000 Dollar, dass ihn kein Computer vor 2011 schlagen würde. Darren Cook nahm die Wette an, und jetzt ist es so weit: John Tromp (heute starker 2 dan) tritt in einem Match über sieben Partien und vier Tage gegen den Computer an. Die erste Partie läuft soeben, live übertragen auf dem KGS-Go-Server (English Game Room, User BGAmatches).

Ursprüngliche Bedingung der Wette war, dass Tromps Gegner ein Computer sein musste, den man zum Austragungsort bringen konnte. Später einigte man sich auf Hardware, die nicht mehr als 5000 Dollar kosten durfte. Einen Supercomputer remote antreten zu lassen, war damit ausgeschlossen. So spielt Tromp nun gegen einen Core i7-740QM, einen Quad-Core mit Hyper-Threading bei 1,7 GHz. Gegner der ersten Runde ist das Programm Many Faces of Go, das auf KGS zurzeit als 2 dan spielt.

Während diese Zeilen entstehen, ist die erste Partie bereits entschieden: Darren gab nach 158 Zügen auf – stellvertretend für Many Faces, das sich seiner Niederlage wohl noch nicht ganz so sicher war. Die nächste Partie startet gegen 17 Uhr mitteleuropäischer Zeit. Weitere Details zur Shodan-Wette und Ergebnisse finden sich auf der Website zur Wette. Das Turnier läuft noch bis zum 31. 12.

Update: Tromp konnte auch die zweite Partie für sich entscheiden. Nach 261 Zügen gab Many Faces of Go – endlich – auf. Menschliche Beobachter hatten das Ergebnis der Partie schon lange vorher gesehen, doch das Programm schätzte offenbar eine Leben-und-Tod-Situation falsch ein und spielte immer weiter. Die einzige Gefahr für den in dieser Partie Schwarz spielenden Tromp war am Ende vielleicht die Uhr: Er hatte nur noch weniger als 10 Minuten Bedenkzeit übrig, während Many Faces noch 20 hatte (gespielt wurde mit sudden death). Morgen soll es auf leistungsfähigerer Computer-Hardware weiter gehen.

2. Update: Am 29. 12. gewann Tromp auch die dritte Partie. Diesmal lief Many Faces of Go remote in der Amazon Elastic Compute Cloud mit einer Rechenleistung von 26 ECU – grob überschlagen doppelt so viel wie bei den ersten beiden Partien. (Da die beiden Teilnehmer der Wette beide anwesend sind, steht es ihnen selbstverständlich frei, einvernehmlich die Bedinungen zu ändern.) In dieser dritten Partie sah es lange so aus als hätte der Computer eine Chance, und Tromp drohte ernsthaft in Zeitnot zu geraten. Doch im Endspiel ging Many Faces dann unter. Ab etwa dem 200. Zug spielte der Computer nur noch "verzweifelten Blödsinn" und ritt sich immer tiefer in den Verlust – nicht untypisch für Monte-Carlo-Algorithmen, denn für sie geht es nur nach der Gewinn-Wahrscheinlichkeit, nicht nach der Höhe des Verlusts. Nach dem 234. Zug gab Darren die Partie auf und erlöste den Computer von seinem nicht empfundenen Leiden.

3. Update: Nach 263 Zügen endete nun auch die vierte Partie mit Aufgabe durch den Computer. Damit hat Tromp die Wette gewonnen. Many Faces of Go lief diesmal in einer 64-Bit-Version mit 12 GByte Speicher und sollte eigentlich dadurch noch ein bisschen stärker gewesen sein – bisher lief nur die 32-Bit-Version. Aber es hat alles nichts genützt: Bereits nach 100 Zügen waren sich die Hochdans unter den Kiebitzen sicher, dass Tromp gewinnen würde.
(bo)

Quelle: Heise.de