codecentric challenge 2014

7 Kommentare

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!

Dr. Raymond Georg Snatzke

Der promovierte Mathematiker Georg Snatzke ist seit 2007 bei codecentric. Sein Schwerpunkt sind alle Bereiche rund um das Thema Performance: Application Performance Management (APM), insbesondere mit AppDynamics, Performance-Analyse und -Optimierung sowie natürlich Lasttests. Georg ist zufrieden, wenn er schwarzen Rauch aus den Systemen aufsteigen sieht, die er unter Last setzen darf.

Share on FacebookGoogle+Share on LinkedInTweet about this on TwitterShare on RedditDigg thisShare on StumbleUpon

Kommentare

  • Ingo Althöfer

    Hallo Georg,
    ich habe mal eine neugierige Frage: Wie weit ist –
    abgesehen von Dir – das Go-Spiel bei codecentric
    verankert? Gibt es weitere Spieler oder zumindest
    Kollegen, die wissen, dass Go-Steine keine Smarties
    sind?

    Danke für den schönen Eingangsbericht.
    Ingo.

    • Dr. Raymond Georg Snatzke

      In den letzten Jahren konnte ich eine ganze Reihe von Kollegen für Go interessieren. Von „Verankerung“ zu sprechen wäre aber wohl übertrieben.

      • Fabian Lange

        Ich hab mit nem guten Dutzend Vorgabesteinen sogar ne Chance gegen Georg 🙂

        • Klaus Petri

          13. September 2014 von Klaus Petri

          Das ist auch eine Leistung, wenn man bedenkt, dass Georg schon für die deutsche Nationalmannschaft gespielt hat, muss man dafür wohl 9kyu oder 10 kyu sein – also sicher kein Anfänger !!

          • Ingo Althöfer

            Von den vier bisher hier kommentierenden
            Personen bin ich der Go-mäßig dann wohl
            schwächste. Zu meinen Glanzzeiten (Herbst
            2001) war ich 17. kyu.

          • Fabian Lange

            Ich glaub ja, dass er nur nett ist. Er kann ausrechnen was er spielen muss damit es so aussieht als würde ich ne Chance haben. Ich rate nur und vermeide leere Dreiecke. So gesehen wende ich Monte-Carlo selber an 🙂

  • Ingo Althöfer

    The match will start with it’s first
    round on Saturday. Late in September, Franz-Josef
    Dickhut had already to play the German Championships
    in Trier, and got a fourth rank there.

    In an email to me he wrote on Monday:
    > I feel hardly recovered from the German championships,
    > which were tiresome but good practice though…
    > My account name [on KGS] will be „fj“, ready to take
    > the fame or the shame 😉

    Ingo.

Kommentieren

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.