Turnier mit Künstlicher Intelligenz Go-Genie gegen geniale Software

Ab Mittwoch geht es für die Menschheit mal wieder ums Ganze: Kann der wohl weltbeste Go-Spieler, das koreanische Genie Lee Sedol, eine Google-Software schlagen? Go-Experten wetten auf den Menschen - noch.

Strategiespiel Go
Corbis

Strategiespiel Go

Von


Als Lee Sedol zum ersten Mal gegen Young Sun Yoon antrat, war er fünf Jahre alt und sie elf. Yoon schlug das Wunderkind, aber: "Das war das erste und letzte Mal, dass ich eine Partie gegen ihn gewonnen habe."

Titelbild
Mehr dazu im SPIEGEL
Heft 10/2016
...offene Europa ab und riskieren unsere Zukunft

Yoon ist Südkoreanerin, lebt heute in Deutschland, und ist Go-Profi. Sie hat sogar schon einmal eine Damenweltmeisterschaft gewonnen, 2002. Mit Lee Sedol aber kann sie sich nicht messen, sagt sie: "Er ist ein Genie." Mit elf Jahren, nach fünf Jahren auf einer Spezialschule für Go-Spieler, wurde Lee Sedol Profi. Anfangs wohnte der Junge, der von einer kleinen koreanischen Insel stammt, bei seinem Trainer.

Das Genie wird ab kommendem Mittwoch die Ehre der Menschheit gegen die Computer verteidigen - so sieht es zumindest aus Sicht vieler Go-Spieler rund um die Welt aus. Lee Sedol, der derzeit wohl beste Go-Spieler überhaupt, tritt an gegen AlphaGo, ein kompliziertes Stück Software, geschaffen und trainiert von der Google-Tochter Deepmind. Go galt lange als eine Bastion, die der menschliche Geist noch gegen die wachsende Macht der Rechner verteidigen kann, so wie früher einmal Schach.

AlphaGo vs. Lee Sedol
  • Corbis
    Der wohl weltbeste Go-Profi Lee Sedol spielt fünf Partien gegen die Deepmind-Software AlphaGo. Ausgetragen werden die Partien am 9., 10., 12., 13. und 15. März im Four Seasons Hotel in Seoul, Südkorea. Die Partien beginnen jeweils um fünf Uhr morgens deutscher Zeit und werden bei YouTube als Livestream übertragen.
1997 schlug IBMs Spezialrechner Deep Blue den amtierenden Weltmeister Garri Kasparow in einem Schachturnier und beendete so die Dominanz des Menschen in diesem Spiel. Im Oktober 2015 schlug AlphaGo den chinesischstämmigen Go-Europameister Fan Hui. Jetzt tritt die Software gegen den amtierenden König des Go an. Alle Go-Fans drücken Lee die Daumen. Hochmotiviert dürfte er gleich mehrfach sein - als Preisgeld winkt im Siegesfall eine Million Dollar.

"Schockiert" ist das Adjektiv, das man von Go-Spielern im Zusammenhang mit dem Sieg von AlphaGo am häufigsten hört und liest. Bis zur Veröffentlichung des spektakulären Resultats in "Nature" im Februar 2016 waren Go-Fans sicher gewesen, dass der Sieg einer Maschine über einen Menschen noch mindestens zehn Jahre in der Zukunft liegen würde.

Spielmaterial und Ziel

Go wird auf einem Brett von 19x19-Linien mit schwarzen und weißen Spielsteinen gespielt. Es wird immer abwechselnd auf die Schnittpunkte des Brettes gesetzt, wobei Schwarz beginnt. Ziel des Spieles ist es, mehr Gebiet zu machen als der andere Spieler.

Anfänger spielen meist auf einem 13x13- oder einem 9x9-Brett (siehe Diagramm), um das Spiel während der Lernphase einfacher und übersichtlicher zu halten, die Regeln sind aber identisch. Gebiet wird gemacht, indem man auf dem Brett freie Schnittpunkte mit den eigenen Steinen vollständig abgrenzt. Im Bild hat Schwarz mit den Zügen 1, 3 und 7 begonnen, sich am oberen Rand des Brettes Gebiet abzugrenzen. Die weißen Züge 2 und 6 stellen den Versuch dar, Gebiet in der rechten unteren Ecke zu machen. Der schwarze Zug auf 5 soll es Weiß erschweren, am unteren Rand des Brettes Gebiet abzugrenzen.
Tobias Berben

Freiheiten und Steine fangen

Steine ohne Freiheiten sind gefangen und werden vom Brett genommen.

Das Abgrenzen von Gebiet wird dadurch erschwert, dass Steine gefangen werden können, indem man ihnen alle Freiheiten nimmt. Sind ein oder mehrere Steine vollständig von gegnerischen Steinen umzingelt, haben sie keine Freiheiten (freie, angrenzende Schnittpunkte) mehr und werden vom Brett genommen. Am Ende des Spiels zählen sowohl jeder abgegrenzte Gebietspunkt als auch jeder Gefangene einen Punkt. Gewonnen hat, wer in der Summe mehr Punkte hat. Im Diagramm haben alle schwarzen Steine keine Freiheiten mehr, sind damit gefangen und müssen vom Brett genommen werden.
Tobias Berben

Verbotene Züge - Ko und Selbstmord

1. Die Ko-Regel: Das direkte Zurückschlagen eines einzelnen Steines im nächsten Zug ist verboten.
2. Die Selbstmordregel: Selbstmord ist verboten.


1. Hat Weiß - wie im Diagramm - auf 1 gezogen, kann dieser Stein von Schwarz regulär mit 2 gefangen werden, da er nur eine Freiheit besitzt. Danach darf Weiß aber nicht mit 3 wiederum auf 1 setzen, um den schwarzen Stein auf 2 zu schlagen, der ebenfalls nur eine Freiheit besitzt. Wäre das erlaubt, könnte danach Schwarz wiederum mit 4 auf 2 den weißen Stein fangen, danach würde Weiß den schwarzen Stein schlagen usw. - das Spiel würde sich in einer sinnlosen Endlosschleife verfangen! Nachdem Schwarz mit 2 den weißen Stein 1 gefangen hat, muss Weiß daher zunächst mit 3 woanders auf dem Brett setzen.

2. Im Diagramm haben die schwarzen Steine in der rechten oberen Ecke nach einem schwarzen Zuge auf A keine Freiheit mehr, wären damit gefangen und müssten vom Brett genommen werden. Das wäre Selbstmord von Schwarz, da er den Verlust der eigenen Steine selbst bewirkt hat, was verboten ist. Gleiches gilt für den schwarzen Zug auf A rechts unten, der keine Freiheiten hätte. Ist allerdings B mit einem schwarzen Stein besetzt, würde der Zug auf A zugleich allen weißen Steinen die letzte Freiheit nehmen. Dann wäre dieser Zug kein Selbstmord mehr, da mit diesem Zug die weiße Steingruppe vom Brett genommen wird, wonach der schwarze Stein auf A drei Freiheiten hat.
Tobias Berben

Leben, Tod - und Seki

Gruppen von Steinen, die gefangen werden können, sind tot; Gruppen von Steinen, die nicht mehr gefangen werden können, sind lebendig.

Leben: Im Diagramm darf Weiß weder auf 'a' noch auf 'b' setzten, da beide Züge Selbstmord wären (vgl. Lektion 3: Die Selbstmordregel). Also kann die schwarze Gruppe von Weiß nicht mehr gefangen werden, da es Weiß nicht möglich ist, alle Freiheiten von Schwarz zu besetzen.

Tod: Die Gruppe in der linken oberen Ecke des Diagramms kann von Weiß noch gefangen werden. Zwar wäre ein Zug auf 'd' wiederum Selbstmord, nicht aber ein Zug auf 'c', da Weiß damit dem markierten schwarzen Stein die letzte Freiheit nimmt. Diesen schlagenden Stein von Weiß darf nun Schwarz nicht im nächsten Zug zurückschlagen (vgl. Lektion 3: Die Ko-Regel), weshalb Schwarz anderswo auf dem Brett ziehen muss. Dann aber darf Weiß auf 'd' setzen, da dieser Zug nun der schwarzen Steingruppe die letzte Freiheit nimmt.

Seki: In der Situation am unteren Rand handelt es sich um eine Koexistenz (Seki) - weder Schwarz noch Weiß wollen auf 'e' oder 'f' ziehen, da sie sich damit die vorletzte Freiheit nehmen würden, woraufhin der jeweils andere Spieler im darauffolgenden Zug durch das Nehmen der letzten Freiheit die Steine schlagen könnte. Da dies keiner von beiden Spielern will, wird in einer solchen Situation gar nicht mehr gezogen, wobei allerdings auch keiner der beiden Spieler in dieser Stellung Punkte macht.
Tobias Berben

Ende und Auszählen

Eine Partie ist beendet, wenn beide Spieler nicht mehr ziehen wollen. Wer dann mehr Punkte als der andere hat, der hat die Partei gewonnen.

Im Diagramm hat sich Weiß die obere Bretthälfte abgesteckt und Schwarz die untere. Beide glauben nicht mehr, dass sie noch in das Gebiet des jeweils anderen setzen können, ohne gefangen zu werden. Also ist die Partie beendet und es wird gezählt: Schwarz hat 31 leere Schnittpunkte abgegrenzt, Weiß hat 29 leere Schnittpunkte abgegrenzt, beide haben keine Steine des anderen gefangen. Somit gewinnt Schwarz mit 2 Punkten.
Tobias Berben

Jetzt aber sind die Freunde des Spiels mit dem schlichten Design und den schier unendlichen Möglichkeiten noch einmal zuversichtlich. "Es ist sehr viel Luft zwischen jemandem wie Fan Hui und jemandem wie Lee Sedol", sagt Tobias Berben, der in Hamburg einen Go-Fachverlag betreibt und die Vereinszeitung des deutschen Go-Verbands verantwortet. Sedol sei mit seinen 33 Jahren für einen Go-Profi schon relativ alt.

Eine Abstimmung unter deutschsprachigen Go-Spielern auf der Fach-Website "Go-Baduk-Weiqi" zeigt einen klaren Trend: Über 70 Prozent der etwa 400, die sich dort bis Samstagnachmittag beteiligt hatten, tippten auf Lee als Sieger.

Vor Kurzem erst verlor Lee Sedol allerdings zweimal in internationalen Turnieren - jedes Mal gegen einen 20-jährigen Chinesen namens Ke Jie, der als nächster Go-Superstar gilt.

Hochleistungs-Go ist ein Sport für junge Leute. Wer in Korea mit 19 noch nicht Profi ist, wird es auch nicht mehr. Wer älter sei, rechne einfach nicht mehr so schnell, sagt Yoon. Lee Sedol selbst habe schon immer "unheimlich schnell rechnen" können: "Mathematikaufgaben, für die andere 15 Minuten brauchen, löst er in einer."

"Wir wissen nicht, wie schnell AlphaGo ist"

Ob Geschwindigkeit im Spiel gegen AlphaGo eine Rolle spielen wird, ist auch unter den Go-Experten noch umstritten. Die fünf Partien zwischen der Software und dem Koreaner werden gewissermaßen über die volle Distanz gehen, jeder Spieler bekommt insgesamt drei Stunden Bedenkzeit, danach kann mit kürzeren Zeiteinheiten womöglich noch weitergespielt werden. "Titelmatches dauern oft sieben bis acht Stunden", sagt Tobias Berben, deshalb sei Go auch eine Frage der Fitness.

Offen ist: Profitiert der Computer überproportional von der langen Bedenkzeit? Oder hilft sie eher dem Menschen? "Manche glauben, Blitz-Go wäre für den Menschen besser", sagt Young Sun Yoon, denn ein guter Spieler trifft beim Go viele Entscheidungen eher intuitiv. "Wir wissen nicht, wie schnell AlphaGo ist."

Go-Spielbrett
Corbis

Go-Spielbrett

Demis Hassabis, der Gründer von Deepmind, sagte kürzlich bei einem Vortrag, man habe sich Go genau deshalb als Herausforderung ausgesucht: Weil es "intuitive Mustererkennung mit logischer Planung und Suche verbindet". Hassabis sagt aber auch: AlphaGo wird täglich besser.

Dass Lee Sedol gewinnen wird, glaubt jedenfalls auch Yoon. "Fan Hui hat nicht so gut gespielt", sagt sie, auch für seine Verhältnisse nicht, und Lee Sedol sei nun mal um Klassen besser.

Lee spielt auf dem Niveau eines neunten Profi-Dan (9p), der höchsten Spielstufe für professionelle Spieler. "Wenn er so spielt wie gegen Fan Hui, hat AlphaGo keine Chance", sagt Yoon. Lee Sedol selbst habe gesagt, er werde vielleicht eine der fünf Partien verlieren, "aber ich glaube, er wollte nur nett sein." Go-Verleger Tobias Berben ist sich nicht so sicher: "Ich befürchte, dass Lee Sedol verliert, aber ich hoffe, dass er drei zu zwei gewinnt."

Der Grund für seine Besorgnis: Es ist völlig unklar, wie sehr sich die Go-Software seit dem Match im Oktober 2015 weiterentwickelt hat. AlphaGo basiert maßgeblich auf künstlichen neuronalen Netzwerken (siehe Kasten unten), und die werden durch Training eben besser. Die Netzwerke sind für "den intuitiven Aspekt von Go zuständig", sagt Hassabis.

Eine Frage ist, welche Rolle das verfügbare Trainingsmaterial spielt. 70.000 bis 80.000 hochklassige Profi-Partien sind in Go-Datenbanken gespeichert, sagt Tobias Berben. Die Version von AlphaGo, die gegen Fan Hui gewann, wurde zunächst anhand von 100.000 Partien trainiert, die zum Teil von einem koreanischen Server für Online-Go stammten. Dann spielte die Software zum Training immer wieder gegen sich selbst. Und AlphaGo trainiert immer weiter, jeden Tag, jede Nacht. "Es hatte nicht mal an Weihnachten frei", scherzte Hassabis kürzlich.

Eine weitere offene Frage betrifft den anderen zentralen Unterschied zwischen Mensch und Maschine - die Gefühle. Beim Go reicht ein Punkt mehr zum Sieg: Wer vorne liegt, tut gut daran, "den Sieg zu verwalten", nicht übermütig zu werden, keine überflüssigen Risiken einzugehen. Tobias Berben fürchtet: "Darin sind die Computer ziemlich gut."

Außerdem ist das Spiel selbst ob seiner gewaltigen Komplexität noch immer im Fluss, da erinnert Go eher als Fußball als an Schach. "Die Dynamik des Spiels hat sich in den vergangenen 30 Jahren unheimlich verändert", sagt Berben. Und: "Wir wissen noch überhaupt nicht, wie stark man im Go überhaupt werden kann - ob Mensch oder Computer."

Neuronale Netzwerke: Die Geschichte
Neuronales Netz: Knoten und gewichtete Verbindungen
David E. Rumelhart/ James L. McClelland

Neuronales Netz: Knoten und gewichtete Verbindungen

Die Idee, dass man die Morphologie des menschlichen Nervensystems nachbilden könnte, um Maschinen so etwas wie denken, lernen oder Wahrnehmung beizubringen, stammt schon aus den Vierzigerjahren des vergangenen Jahrhunderts. Lange Zeit aber blieben die sogenannten neuronalen Netzwerkmodelle eher rudimentär, ein Gebiet für Spezialisten mit besonderer Liebe zur Abstraktion. Dann, in der ersten Hälfte der Achtzigerjahre, änderte sich das vor allem dank einer einzigen Studie. Die Psychologen David Rumelhart und James McClelland zeigten, dass so ein extrem rudimentäres Pseudogehirn lernen kann, die Vergangenheitsformen englischer Verben korrekt zu bilden - und im Laufe des Lernprozesses vorübergehend die gleichen Fehler macht wie ein menschliches Kind beim gleichen Vorgang. Statt "went" warf das Netz als Antwort vorübergehend "goed" aus - es wendete also die Regel korrekt an, aber eben bei einem unregelmäßigen Verb.

Das Netzwerk lernte also Regeln und anschließend auch die Ausnahmen von diesen Regeln - ohne dass eine einzige Regel jemals explizit formuliert worden wäre. Die Studie löste in den Kognitionswissenschaften einen kleinen Boom aus, plötzlich wurden neuronale Netzwerkmodelle auf alle möglichen Fragestellungen angewendet, der Begriff "Konnektionismus" für die neue Wissenschaft kam auf. Dann kam das Internet, die digitale Revolution nahm ihren Lauf, und plötzlich gab es Rechenleistung und entsprechende Computer in Hülle und Fülle. Heute sind neuronale Netzwerke nicht mehr nur Modelle für Psychologen - sie sind zu mächtigen Werkzeugen in den Händen jener geworden, die Computern das Sehen, Denken, Deuten beibringen wollen.

Das Grundprinzip, nach dem solche neuronalen Netzwerke funktionieren, ist immer das gleiche. Sie bestehen aus zwei oder mehr Schichten von Knoten, simulierten Nervenzellen. Verbunden werden diese Schichten mit vielen Verknüpfungen. In der Regel ist jeder Knoten der einen Schicht mit allen Knoten der nächsten verbunden. Die Input-Knoten stehen für elementare Merkmale, sie könnten beispielsweise die Pixel eines vorgegebenen Bildes repräsentieren.

Wird ein Input-Knoten aktiviert, reichte er diese Aktivierung über seine Verbindungen an die Knoten der nächsten Schicht weiter. Die Verbindungen wurden gewichtet - man kann sie sich als unterschiedlich dick vorstellen. Je dicker die Verbindung, desto stärker die Aktivierung, die am nächsten Knoten ankommt. Belehrt wird so ein Netzwerk gewissermaßen rückwärts: Wenn die Output-Schicht nicht das gewünschte Ergebnis produziert, werden die Gewichtungen der Verbindungen mithilfe eines mathematischen Mechanismus Schicht für Schicht so angepasst, dass das Ergebnis beim nächsten Mal besser zum tatsächlichen Input passt. Mit vielen Durchgängen können die Netze so lernen, Inputs korrekt mit Outputs zu verknüpfen.

cis



Forum - Diskutieren Sie über diesen Artikel
insgesamt 32 Beiträge
Alle Kommentare öffnen
Seite 1
mhwse 07.03.2016
1. Neuronale Netze werden mit Hilfe von
Matrizen abgebildet. Da ist nichts geheimnisvolles dran. Da sich in einer Matrix Wege-Diagramme mit Gewichtung leicht abbilden lassen - als noch Fahrpläne auf Papier die häufigere Version waren, kannte so etwas jeder Bahnreisende .. (Fahrtdauer von München nach Bonn x Minuten; Fahrtdauer von Berlin nach Bonn y Minuten; Fahrtdauer von München nach Berlin z Minuten .. etc. für alle grösseren Städte) Das Neuronale Netz hat den Vorteil, dass man nun nicht alle Kombinationen von Hand eintragen muss, sondern die Gewichtung für einen Spielzug durch Versuch und Irrtum "gelernt" wird. Wenn also die Go Software gewinnt, dann liegt das daran, dass sie zuvor 50 Tage lang oder mehr mit 1200 Rechenkernen, per Versuch und Irrtum quasi schon alle möglichen Partien gespielt hat. Es ist nicht klar ob Mensch nur basierend auf solchen Entscheidungsbäumen agiert. Sicher übt der Go Spieler (wie jeder Schüler) und es werden sicher solche Matrizen im Gehirn gebildet - nur ist die Frage, ob die Alltags Entscheidungen ausschliesslich darauf basieren .. Das Go Brett hat bereits die Form einer n x n Matrix. Das heisst, die sonst nötige Standardisierung (wie z.B. bei der Handschriften Erkennung, auf Grösse und Graustufen) entfällt. Das macht die Umsetzung als Software so verlockend aber eben auch einfach .. Es gibt "Spielsoftware" (die sich für realistische Szenarien eignet) sowohl für LINUX als auch für Microsoft.
Hans Blafoo 07.03.2016
2. Mein Tipp
der Mensch gewinnt 4:1
From7000islands 07.03.2016
3. Eigentlich irreführend
Wachsen Softwares im Gemüsegarten? Software ist ein Produkt von intelligenten Menschen. Sie ist ein Tool, nichts weiter. Es muss bei angeblich "künstlicher Intelligenz" immer heissen: Mensch mit konstruierter Intelligenz gegen Mensch ohne Hilfsmittel.
dreiq 07.03.2016
4. Das wird spannend
Ich habe seinerzeit schon die IBM und Hydra-Kämpfe im Schach weitestgehend live verfolgt. Und jetzt ist Go dran. Beim Computer-Schach werden in der gängigen Software aktuell noch keine neuronalen Netzwerke eingesetzt. Es ist allerdings nicht mal annähernd möglich, alle Zugfolgen durch neuronale Netzwerke durchzuprobieren. Erstens ist die Anzahl der Zugmöglichkeiten (s. "Tablebases") um Größenordnungen zu hoch. Da würden auch alle Rechner der Welt zusammen nicht ausreichen. Zweitens würde das ja auch die neuronalen Netzte überflüssig machen, man könnte dann einfach Brute-force rechnen, was viel schneller ginge, da bei Berechnung bis zum Ende keine Bewertung notwendig wäre. Die neuronalen Netze sollen ja gerade dann durch Mustererkennung den Besten Zug finden, wenn dem Rechner die Stellung unbekannt ist. Auf alle Fälle spannend. weiß allerdings nicht, für wen ich bin. Sowohl die Leistung des menschlichen Spielers, als auch die Leistung der Menschen, die die Ideen für die Software und die Hardware enwickelt haben, ist beeindruckend.
var 07.03.2016
5. Evolution
Im Schach gings es viel viel viel schneller als erwartet, das Computer die besten Humans übertrumpfen. Das wird im GO genauso sein. Wenn die Prognosen jetzt unklar sind kanns nur eines bedeuten: AlphaGO wird sich durchsetzen.
Alle Kommentare öffnen
Seite 1

© SPIEGEL ONLINE 2016
Alle Rechte vorbehalten
Vervielfältigung nur mit Genehmigung der SPIEGELnet GmbH


TOP
Die Homepage wurde aktualisiert. Jetzt aufrufen.
Hinweis nicht mehr anzeigen.