"Go": Das letzte Spiel, in dem Mensch über Computer triumphiert

13. Mai 2014, 11:34
406 Postings

Computer sind besser in Schach, Poker und Scrabble – aber das antike "Go" stellt ein Mysterium für Programmierer dar

Bereits seit über 2000 Jahren spielen Menschen "Go", wie antike chinesische Schriftstücke belegen. Das oftmals als "fernöstliches Schach" bezeichnete Spiel erfreut sich nach wie vor großer Beliebtheit, vor allem in Japan und Korea, wo Topspieler durch Preisgelder Millionen pro Jahr einnehmen können.

Algorithmus gesucht

Weniger Freude als den rund 27 Millionen Spielern weltweit bereitet "Go" Programmierern: Trotz intensiver Bemühungen gelang es bislang keiner Maschine, gegen einen Profispieler zu gewinnen - obwohl Informatiker bereits seit Jahrzehnten an einem solchen Algorithmus tüfteln.

Das dürfte sich nicht so schnell ändern: Mindestens zehn Jahre könnte es noch dauern, bis "Go" dasselbe Schicksal wie "Schach", "Backgammon", "Scrabble", "Mühle", "Dame" oder sogar "Jeopardy" ereilt.

Schach: Garry Kasparov schon vor 17 Jahren besiegt

Doch woran liegt es, dass all diese Spiele bereits von Computern beherrscht werden, "Schach"-Weltmeister Garry Kasparov sogar schon vor 17 Jahren von IBMs Deep Blue Supercomputer besiegt wurde - und "Go" immer noch nicht? Der Hauptgrund dafür liegt in der Vielzahl möglicher Spielzüge, die den Spielern von Beginn an zur Verfügung stehen: Das "Go"-Spielbrett besteht aus 19 horizontalen und 19 vertikalen Linien, also einem Gitter von 361 Schnittpunkten.

Am Begin des Spiels ist das Brett leer, die Kontrahenten setzen nun abwechselnd schwarze und weiße Steine auf die Verbindungspunkte der 38 Linien. Ziel ist es, möglichst große Teile des Spielbretts zu kontrollieren. Schließen eigene Steine gegnerische Elemente komplett ein, sind diese geschlagen.

129.960 Möglichkeiten - nach zwei Spielzügen

Dadurch, dass das gesamte Spielbrett mit seinen 361 Schnittpunkten zur Verfügung steht, potenzieren sich die Möglichkeiten enorm. Beim Schach stehen beiden Spielern zwanzig mögliche Spielzüge zur Auswahl, nach zwei Runden gibt es 400 Möglichkeiten, wie die Figuren am Spielbrett positioniert sind. Im Gegensatz dazu "Go": Der schwarze Spieler hat 361 Möglichkeiten, seinen Stein zu platzieren, der weiße dann 360. Nach zwei Runden: 129.960 Möglichkeiten.

Selbst für Kenner schwer nachvollziehbar

Aus diesem Grund ist ein Algorithmus für "Go" ungleich komplexer als sein Schach-Konterpart. Die Angelegenheit wird allerdings noch komplizierter: Während bei Schach eindeutige, logische "Regeln" identifiziert werden können, ist "Go" ungleich subtiler und komplexer. Selbst passionierte Amateure verstehen oft nicht, warum "Go"-Profis den einen oder anderen Spielzug ausführen. Es ist sogar fraglich, ob die Experten selbst ihre Aktionen restlos erklären könnten.

Monte-Carlo-Simulation

Auf gut Deutsch: Es gibt keine Möglichkeit, "gute" Spielzüge zu quantifizieren, sie blieben also "unsichtbar für Computer", wie Wired analysiert. Wie gehen Programmierer also vor? Remi Coulom, ein französischer Informatiker, denkt, dass die Monte-Carlo-Simulation helfen könnte: Es handelt sich dabei um ein Verfahren aus der Wahrscheinlichkeitstheorie, die – sehr vereinfacht gesagt – eine intensive Überprüfung aller Möglichkeiten durch ein statistisches Sample weniger Möglichkeiten ersetzt. Entwickelt wurde die Simulation zum Berechnen von nuklearen Explosionen.

Crazy Stone wird zum Videospiel

Coulom kombinierte die Monte-Carlo-Methode mit klassischen Suchbaum-basierten Verfahren und machte sein "Crazy Stone"-Programm damit zum aussichtsreichsten Anwärter auf den ersten maschinellen "Go"-Sieg. Das weckte auch das Interesse der Videospielindustrie: 2010 lizensierte er das Programme an die japanische Firma Unbalance, die ein Computerspiel daraus entwickelte.

Gegen Meister Yoda

Vor kurzem trat Coulom im Rahmen eines japanischen Wettbewerbs mit seinem "Crazy Stone"-Algorithmus gegen einen japanischen Großmeister mit dem passenden Namen Yoda an. Um eine reelle Chance zu haben, bekam die Maschine einen Vorsprung, den sie zum allgemeinen Erstaunen der Anwesenden gegen Norimoto Yoda verteidigen konnte. Ein Etappensieg, denn ohne Handicap hätte Yoda sicher gewonnen, so Wired.

IBM: Noch ein Jahrzehnt

Auch IBM glaubt nicht an einen baldigen "Go"-Sieg seiner Supercomputer. Genauso wie Coloum schätzen sie, dass es noch mindestens ein Jahrzehnt dauern könnte. Dennoch unterscheidet IBM in Punkto Philosophie einiges von Coulom: Während der US-Konzern die Stimmung verbreitet, seine Maschinen würden durch Triumphe bei "Schach" und "Jeopardy" "klüger" als Menschen sein und das Gehirn imitieren, sagt Coulom, dass solche Programme nichts mit dem Erschaffen einer menschlichen Intelligenz zu tun hätten.

Maschine "gewinnt" nicht

Die Aussage, "Go" sei die letzte Bastion menschlicher Intelligenz gegen Maschinen, sei daher aus seiner Sicht falsch, so Coulom gegenüber Wired. Denn: "Computer können nichts gewinnen', solange sie sich dabei nicht freuen oder über eine Niederlage ärgern." Solche Algorithmen zeigten bloß, wie weit Maschinen noch von der menschlichen Intelligenz entfernt seien. "Mir macht das Programmieren Spaß", so Coulom, "das war's aber auch schon." (fsc, derStandard.at, 13.5.2014)

Links:

Wired

Remi Coulom

Unbalance

IBM

Go (Wikipedia)

Monte-Carlo-Simulation (Wikipedia)

  • Go: Zwei Spieler treten gegeneinander an und versuchen, möglichst große Teile des Spielbretts zu erobern
    foto: creative commons/wikipedia:shizhao

    Go: Zwei Spieler treten gegeneinander an und versuchen, möglichst große Teile des Spielbretts zu erobern

  • Das "Schach Asiens" wird bereits seit Jahrtausenden gespielt, wie Malereien belegen
    foto: creative commons/public domain

    Das "Schach Asiens" wird bereits seit Jahrtausenden gespielt, wie Malereien belegen

  • Computerprogramme sind bislang noch immer chancenlos gegen menschliche Go-Meister
    foto: creative commons/wikipedia:signbrowser

    Computerprogramme sind bislang noch immer chancenlos gegen menschliche Go-Meister

  • Mittels Monte-Carlo-Simulation versucht der Programmierer Remi Coulom, einen besseren Algorithmus für Go zu entwickeln
    foto: creative commons

    Mittels Monte-Carlo-Simulation versucht der Programmierer Remi Coulom, einen besseren Algorithmus für Go zu entwickeln

  • Sein "Crazy Stone"-Programm wurde in Japan zum Videospiel
    foto: screenshot/unbalance

    Sein "Crazy Stone"-Programm wurde in Japan zum Videospiel

Share if you care.