codecentric challenge 2014

Mensch gegen Computer

Diesen Herbst kommt es im Computer Go zu etwas, das es in dieser Form noch nie gegeben hat: einem Duell zwischen einem Go-Programm und einem europäischen Spitzenspieler ohne Vorgabe bzw. Handicap – und codecentric ist der Sponsor dieses Duells. Dies ist diesmal kein typischer codecentric-Blog-Artikel. Es geht nicht um Tipps oder Strategien zu Java, agiler Entwicklung, Software-Qualität oder ähnlichen Themen. Statt dessen möchte ich über das Spiel Go sowie Computer Go schreiben – einerseits das vielleicht älteste Brettspiel der Welt, andererseits ein Feld hochmoderner Technologie und Forschung.

Go, die letzte Bastion

Das ostasiatische Brettspiel Go gilt als eine der letzten offenen Herausforderungen der Spielprogrammierung, als das eine klassische Spiel, bei dem Menschen noch immer selbst gegen die stärksten Programme gewinnen. Im Schach hat der Mensch das Duell gegen den Computer bereits 1997 verloren, als IBMs Deep Blue den damaligen Schachweltmeister Garry Kasparow bezwingen konnte. Heutzutage kann wahrscheinlich ein normales Schachprogramm auf einem durchschnittlichen Notebook den Schachweltmeister besiegen. In Dame und Backgammon haben Menschen auch längst keine Chance mehr.

Nicht so in Go. Die Spielmechanik ist ausgesprochen einfach, wie ein Blick in die Regeln zeigt (www.dgob.de ). Aber wenn man Go noch nie gespielt und lediglich die Regeln durchgelesen hat, fragt man sich wahrscheinlich ziemlich ratlos, wann das Spiel eigentlich zu Ende ist und wie der Sieger ermittelt wird. Diese Verwirrung liefert einen ersten Hinweis auf die Komplexität von Go: Es ist ausgesprochen schwierig, gute Heuristiken zu finden, um eine Go-Stellung zu bewerten – welcher Spieler liegt in Front und wie weit? Ein anderer Grund, warum es so schwierig ist, die traditionelle Spielbaum-Suche in Go zu nutzen, mit der man in Schach große Erfolge gefeiert hat, ist die schiere Größe des Go-Brettes mit seinen 19 x 19 Schnittpunkten. Im Schach gibt es durchschnittlich ca. 25 verschiedene Zugmöglichkeiten in einer Stellung. Bei Go sind es zu Beginn 361 und bei Spielende immer noch zwischen 50 und 100. Ein Schachspiel dauert durchschnittlich 80 (Halb-)Züge, eine Partie Go zwischen 200 und 300. Bei Go müssen folglich ganz andere Größenordnungen an Daten durchgewälzt werden als bei Schach, so dass die Programme entsprechend deutlich weniger weit vorausrechnen können. Daher konnte bis vor wenigen Jahren selbst ein durchschnittlicher Go-Spieler jedes Go-Programm schlagen.

Monte-Carlo-Algorithmen

Dann kamen Monte-Carlo-Methoden auf. Eine Alternative, sich dem riesigen Spielbaum von Go zu nähern, ist, die wissensbasierte, klassische Baumsuche durch Nutzung des Zufalls zu erweitern. Mittels Zufallszügen werden Spielpositionen vielfach durchgespielt, um auf diese Weise die vielversprechendsten Züge zu ermitteln. Dieser Ansatz wurde lange Zeit weitgehend ignoriert, da er der menschlichen Herangehensweise an ein Spiel wie Go völlig zuwider läuft. Aber in den letzten Jahren haben Go-Programme mit Monte-Carlo-Methoden rasante Fortschritte gemacht. Die stärksten Programme nähern sich inzwischen dem Top-Amateur-Niveau.

Duelle gegen Spitzenspieler

Seit 2007 richtet die Universität für Elektro-Kommunikation in Japan den „UEC Cup Computer Go“ aus, eine Art inoffizielle Weltmeisterschaft der Go-Programme. Bis zu den Fortschritten durch Monte-Carlo-Methoden wurde Computer Go in der Go-Welt nicht sonderlich ernst genommen. Aber 2013 hat der Nihon Ki-in, die bedeutendste japanische Organisation von Go-Profis, eine Vereinbarung getroffen, dass die stärksten Programme des UEC Cups gegen Go-Profis antreten dürfen. In den letzten Jahren waren die zwei stärksten Go-Programme regelmäßig das japanische Programm „Zen“ und das Programm „Crazy Stone“ des französischen Entwicklers Rémi Coulom. In den Spielen gegen Go-Profis 2013 und 2014 haben die Programme jeweils eine Vorgabe von vier Steinen bekommen. Um das besser Einschätzen zu können: Nur ein bereits sehr starker Amateur kann hoffen, mit einer solchen Vorgabe gegen einen Profi zu gewinnen. Während Zen in beiden Jahren verlor, schaffte es Crazy Stone, seine Partien gegen die Profis zu gewinnen, so dass die Frage letztlich offen blieb, wie groß der Spielstärke-Unterschied zwischen den stärksten Go-Programmen und professionellen Go-Spielern tatsächlich ist.

codecentric challenge 2014

In wenigen Wochen nun wird in der „codecentric challenge 2014“ Crazy Stone in einem fünf-Partien-Match gegen Franz-Josef Dickhut antreten. Dickhut ist Amateur-6-Dan und elfmaliger deutscher Go-Meister. Im Amateur-Bereich geht es nicht mehr viel besser. Kein stärkerer Go-Spieler hat sich jemals zu einem ernsthaften Wettkampf gegen ein Go-Programm ohne Vorgabe bereit erklärt. Dass der Gewinner nicht in einer einzigen Partie, sondern in einem Best-of-five-Match ermittelt wird, verleiht dem Wettbewerb zusätzliches Gewicht. Gespielt wird online auf dem KGS Go-Server. Die erste Partie wird am Samstag, dem 4. Oktober gespielt. Jede Woche folgt ein weiteres Spiel, bis eine Seite drei Mal gewonnen hat.

Vorgeschlagen und organisiert wurde der Wettkampf von Prof. Ingo Althöfer von der Universität Jena, der seit Jahrzehnten im Bereich der Spiel-Programmierung und der Spiel-Mathematik forscht. codecentric wiederum hat sich bereit erklärt, als Sponsor aufzutreten und die Webseite des Wettkampfes zur Verfügung zu stellen. Der entsprechende Link wird hier rechtzeitig vor der ersten Partie veröffentlicht.

Ich hoffe, es ist mir gelungen, ein wenig Interesse für dieses faszinierende Spiel und das kommende Mensch-Computer-Duell zu wecken. Bleiben Sie dran!