Die besten Schachspieler der Welt sind Computer. Sie schaffen es immer häufiger, auch menschliche Elitespieler zu besiegen. Was beim Schach für den Computer mittlerweile so einfach scheint, ist beim populären asiatischen Brettspiel Go momentan noch umso schwieriger. Als Sieger professioneller Go-Partien gehen noch immer die Menschen hervor. Das soll allerdings nicht mehr lange der Fall sein: Seit März 2009 arbeiten Wissenschaftler des Paderborn Center for Parallel Computing (PC²) der Universität Paderborn unter der Leitung von Prof. Dr. Marco Platzner daran, mit dem Computer die Spielstärke der besten menschlichen Go-Spieler zu erreichen und diese möglichst noch zu übertreffen.
Die Berechnung guter Spielzüge, mit denen menschliche Gegner in die Enge getrieben werden, gestaltet sich für Computer allerdings sehr schwierig. Denn anders als beim Schach, wo allein etwa 1043 Stellungen der Figuren möglich sind, übersteigt die Zahl der denkbaren Zugfolgen beim Go-Spiel sogar 10170. Auch für den schnellsten Computer ist es damit völlig unmöglich, alle Varianten des Spiels komplett durchzugehen. Um dennoch einen effektiven Spielzug berechnen zu können, benutzt Lars Schäfers, wissenschaftlicher Mitarbeiter des PC², ein so genanntes Monte-Carlo-Verfahren. „Hier werden vom Computer zufällig einige hunderttausend Spielfortführungen erzeugt und analysiert“, erklärt Lars Schäfers. „Mit Hilfe der Wahrscheinlichkeitsrechnung können wir dann Rückschlüsse auf einen wahrscheinlich guten Zug machen“, sagt er weiter.
Auf dem Weg hin zur Entwicklung eines starken Go-Programms macht sich das Projektteam die Kapazitäten des PC² zu Nutze. Dort besteht die Möglichkeit, Supercomputer mit der Rechenleistung von mehreren hundert PCs für eine parallele Suche nach dem besten Zug zu verwenden. Die Computer sollen in möglichst kurzer Zeit möglichst viele Zufallsspiele durchführen. Zudem wird versucht, Computer in die Lage zu versetzen, mit einer großen Menge aufgezeichneter, professioneller Go-Partien selbständig Spielstrategien erlernen zu können.
Das Ziel, bis März 2012 das möglicherweise beste Go-Programm der Welt zu entwickeln, ist ein ehrgeiziges. Dass sie jedoch in der Lage sind, Computer erfolgversprechend für die Berechnung von anspruchsvollen Brettspielen einzusetzen, haben Wissenschaftler des PC² bereits in der Vergangenheit bewiesen: In den Jahren 2003 bis 2006 wirkten sie an der Entwicklung eines der zu dieser Zeit stärksten Schachcomputers namens Hydra mit. Hydra gelang es im Jahr 2005, den damals viertplatzierten Schachspieler der Weltrangliste in einem aufsehenerregenden Wettkampf in London zu besiegen.
An dem von Microsoft geförderten Projekt sind neben Prof. Dr. Marco Platzner und Lars Schäfers vom PC² auch Dr. Ulf Lorenz von der TU Darmstadt, Wissenschaftler der Microsoft Research Labs Cambridge und mehrere starke Go-Spieler, unter anderem des Paderborner Go-Clubs, beteiligt.
Text/Foto: Katharina Bätz, Institut für Informatik
Der Artikel ist auch als <link fileadmin uni-aktuell pressefotos juli forschung_insight_03_juli_2010.pdf _blank>pdf verfügbar. Weitere Ausgaben der „Forschung inSight“ finden Sie unter www.cs.upb.de/insight.
