Wem Schach zu simpel ist oder Flappy Birds zu einfach, der hat sicherlich schon von dem asiatischen Spiel Go gehört. Dahinter verbirgt sich ein Jahrtausende alter Spielklassiker aus Asien, der unter Fachleuten gern als das komplexeste Strategiespiel der Welt angesehen wird. Kein Wunder, dass Go schon lange in den Fokus der Wissenschaft gerückt ist – kann man hierbei doch perfekt die Fähigkeiten einer künstlichen Intelligenz messen. Und genau diesem Wettbewerb möchte sich der Suchmaschinen-Gigant Google nun stellen und versucht mit der hauseigenen künstlichen Intelligenz Alpha Go – ein Ableger der noch mächtigeren KI DeepMind – niemand anderen zu schlagen als den derzeit amtierenden Go-Meister: den Koreaner Lee Sedol. Warum ein Sieg durch eine künstliche Intelligenz gegen einen menschlichen Profi in dem Spiel Go bis vor wenigen Monaten noch undenkbar schien, was Alpha Go anders macht als bisherige KIs und ob sie auch in einem Online Casino abräumen könnte, erfahrt ihr hier.
Was ist eigentlich Go?
Um die Leistung der Google KI „Alpha Go“ besser verstehen zu können, ist es zuerst nötig die Schwierigkeit von Go zu erfassen. Go ist ein Strategiespiel, das bereits schon im vierten Jahrhundert vor Christus in historischen Überlieferungen Erwähnung findet. Es spielen dabei zwei Personen gegeneinander auf einem Schach-ähnlichen Spielfeld mit 19×19 Feldern (Bei Anfängern ist auch eine einfachere Variante mit 9×9 Feldern beliebt). Die Spieler (weiß und schwarz) setzen dabei abwechselnd einen Stein ihrer Farbe auf einen der Schnittpunkte des Spielfelds. Wurde ein Stein einmal gelegt, darf er nicht wieder verrückt werden. Ziel des Spiels ist es, schlussendlich möglichst große Gebiete auf dem Spielfeld mit den eignen Steinen zu umranden.
Vielleicht interessiert Dich auch das hier: 9 Projekte, mit denen Google die Welt verändern will
Obwohl Schach bereits als ein äußerst komplexes Strategiespiel gilt, übersteigt die Komplexität von Go die des Schachs um Weiten. So besitzen Schachspieler zu Beginn einer Schachpartie „lediglich“ 20 Zugmöglichkeiten. Im späteren Verlauf des Spiels und der größeren Freiheit der Spielfiguren zu verdanken, erhöht sich die Anzahl möglicher Züge auf durchschnittlich ca. 80. Bei so einer Komplexität entstehen nach zwei Zügen bereits 72.084 mögliche Stellungen und nach 10 Zügen sogar schon 169.518.290.100.544.000.000.000.000.000 mögliche Stellungen. Diese Zahl ist so groß, dass Wissenschaftler im Moment davon ausgehen, dass sogar die gesamte Anzahl aller Atome im Weltall kleiner ist als die Anzahl an Möglichkeiten im Schach nach 10 Zügen.
Unvorstellbar, dass ein Mensch all diese Möglichkeiten durchkalkulieren kann und genauso wenig ist es möglich, dass es ein Computer in absehbarer Zeit hinbekommt. Umso erstaunlicher ist es, dass es der künstlichen Intelligenz von IBM „Deep Blue“ bereits 1997 gelang, so gut Schach zu spielen, dass sie gegen den damaligen Weltmeister Gary Kasparov gewann. Dabei kamen mathematische Verfahren zum Einsatz, bei denen versucht wird, so viele Züge wie möglich vorauszuberechnen. Eine tolle Dokumentation zu diesem Spiel findet ihr außerdem in diesem Video.
Im Vergleich dazu besitzt Go nun eine Komplexität die um ein Vielfaches höher ist und somit auch alle bisherigen KIs in die Knie zwang. So besitzt ein Spieler bei Go bereits in der ersten Runde 361 Zugmöglichkeiten und der zweite Spieler darauf 360. Geht man von einer durchschnittlichen Anzahl an Zugmöglichkeiten von 200 aus, dann ergeben sich bei 150 Spielrunden ingesamt 200 hoch 150 Spielzüge. Eine Zahl so groß, dass es für einen Computer unmöglich ist aus allen Spielzügen den besten auszuwählen.
Probleme bei der KI-Entwicklung für Go
Erinnert man sich an seine Schulzeit zurück, erkennt man, dass man die Anzahl der Spielzüge bei Schach und bei Go anhand eines Ereignisbaums darstellen kann. D.h. man beginnt im Punkt 0 von dem dann alle Spielzüge der ersten Runde einen Zweig darstellen. Am Ende jedes Zweigs entstehen dann neue Zweige, die – in Abhängigkeit vom ersten Zug – alle möglichen Spielzüge der zweiten Runde darstellen. Das setzt man so lange fort, bis man das Ende der Partie erreicht hat und man erhält einen Spielbaum. Der stellt alle möglichen Züge des Spiels dar und beinhaltet dabei – wie im oberen Abschnitt erklärt – so viele Züge, dass es für einen PC unmöglich ist, alle durchzukalkulieren, um den besten Pfad zu entdecken.
Damit eine künstliche Intelligenz dennoch herausfinden kann, welcher Zug der bestmögliche ist, nutzen KI-Forscher unterschiedliche Methoden, um die Wertigkeit eines Zugs zu ermitteln. Beim Schach werden z.B. nur eine bestimmte Anzahl an Spielzügen berechnet, um diese dann mit ihrer Wertigkeit zu verrechnen. So besitzt eine Dame z.B. eine höhere Wertigkeit als ein Bauer oder ein Turm. Nimmt man dann noch die Beweglichkeit der Figuren und deren Einfluss auf das Spielgeschehen hinzu, erhält man schon eine sehr grobe Annäherung des besten Zugs.
Bei Go ist so ein Vorgehen jedoch nicht möglich, da die Wertigkeit jedes Steins zu Beginn gleich ist und sich im Spielverlauf sogar noch ändern kann. Was zu Beginn noch ein „guter“ Stein war, kann sich im späteren Verlauf zu einem Fehler entwickeln und der Verlust eines Steins ist nicht mit einer Schwächung des Spielers verbunden. Um dennoch eine möglichst gute KI zu entwickeln, setzten Forscher lange Zeit verstärkt auf Zug-Datenbanken, die dem Computer somit passende Züge anhand der Spielzüge von menschlichen Spielern vorschlugen.
Die Monte Carlo Tree Search als erster Durchbruch für eine künstliche Intelligenz im Go spielen
Erst in der Mitte der 90er Jahre entwickelte man ein neues Verfahren, das als Monte Carlo Tree Search (MTCS) bekannt wurde. Dabei kalkuliert der Computer zufällig einen Zug und berechnet dann ebenfalls zufällig einen kompletten Ast des Ereignisbaums durch. Das Ergebnis ist hierbei natürlich purer Zufall aber der Computer berechnet mit der MTCS-Methode nicht nur einen möglichen Zug sondern macht das für so viele wie möglich. Stellt sich dabei heraus, dass bei einem bestimmten ersten Zug häufiger ein Sieg eintritt als bei einem anderen, dann wird dieser Zug als bester Zug definiert und schlussendlich von der künstlichen Intelligenz gespielt.
Man unterscheidet beim Go allgemein in 3 Klassen der Spielstärke: Schüler (Kyu), Amateur (Dan d) und Profi (Dan p). Jede dieser Klassen lässt sich noch einmal in vier bis fünf weitere Klassen unterteilen, die alle als Zahl dargestellt werden. Bei einem Schüler gilt dabei, dass eine kleine Zahl mehr Spielstärke symbolisiert, während es beim Amateur oder Profi eine größere Zahl ist.
Wie viele Äste des Ereignisbaums vom Computer durchgerechnet werden, hängt dabei von der erlaubten Bedenkzeit ab und erlaubt der künstlichen Intelligenz genauso lange über einen Spielzug „nachzudenken“ wie sein menschlicher Gegenspieler. Trotz stetig steigender Rechenleistung von Computern gelang es KI-Forschern mit dieser Methode aber nie über das Niveau eines ambitionierten Anfängers heranzureichen. Umso überraschter waren Forscher deshalb als Mitarbeiter von Facebook im November 2015 in einem wissenschaftlichem Magazin berichteten, dass sie ein Verfahren mithilfe neuronaler Netze entwickelt haben, bei dem eine künstliche Intelligenz auf dem Amateur-1-Dan-Niveau spielen konnte. Dieses Verfahren erweiterten sie im Januar dann noch mit der MCTS-Methodik und schafften somit ein Spielniveau von 3 Dan.
Die Revolution durch Alpha Go
Trotz der großen Leistung des Facebook-Teams überraschte Google am 28. Januar die wissenschaftliche Welt mit der Äußerung, dass sie ihre KI Alpha Go bereits im Oktober gegen den Profi-Spieler Fan Hui spielen ließ und dabei in fünf Spielen fünf Siege davon trug. Hui Fan ist in der Go-Welt kein Unbekannter. Er ist dreifacher Europameister und gilt in China als einer der besten Spieler des Landes. Alpha Go ist somit die erste künstliche Intelligenz, die auf Profi-Niveau spielen kann. Im Vergleich zu bisherigen künstlichen Intelligenzen nutzt Alpha Go dabei alles, was die aktuelle KI-Forschung hergibt. Zwei synchron laufende neuronale Netze, Supervised Learning, Deep Convolution Networks, Reinforcement Learning und Asynchronous Policy and Value MCTS sowie eine Rechenleistung von mehr als 1.000 parallel laufenden CPUs.
Das Besondere an Alpha Go sind dabei die einzelnen KI-Elemente, die den gesamten Prozess der Wertigkeitsermittlung verbessern. Anstatt zufällig einen ersten Zug zu wählen und darauf aufbauend das Spiel gedanklich zu Ende zu spielen, nutzt Alpha Go eine Datenbank guter Züge, die der KI anhand menschlicher Partien „beigebracht“ wurden. Anstatt zu viel Rechenleistung für uninteressante aber dafür zufällig gewählte Züge zu verschwenden, werden die ersten Züge somit bewusst gewählt und erhöhen dadurch den Output besserer Züge.
Gleichzeitig gelang es den Entwicklern von Alpha Go ein Verfahren zu entwickeln, mit dem die Wertigkeit der Steine bestimmt werden kann. Somit kann also besser ermittelt werden, welche Positionen weiter ausgebaut werden müssen und welche vernachlässigt werden können. Für die Bewertung eines Zugs sind dabei verschiedene Input-Faktoren für die künstliche Intelligenz relevant. Neben der Anzahl der Freiheiten eines Steins wird auch berücksichtigt wie lange ein Stein bereits auf dem Brett liegt, wie viele gegnerische Steine mit einem Zug geschlagen werden könnten und wie viele Freiheiten mit einem Zug geschaffen werden könnten.
Um die Datenbank bzw. das „Gedächtnis“ von Alpha Go mit vordefinierten idealen Spielzügen bzw. mit der Wertigkeit von Steinen zu füllen, mussten die Forscher von Google ihre KI mehrere Monate im Voraus Berechnungen durchführen lassen, damit die künstliche Intelligenz „lernen“ konnte, wie ein guter Spielzug auszusehen hat.
Google bzw. dem Tochterunternehmen DeepMind reicht es allerdings nicht aus, den aktuellen dreifachen Europameister in Go geschlagen zu haben. Sie planen den aktuellen Weltmeister in Go zu schlagen und haben dafür am 09. März 2016 ein Turnier angesetzt bei dem es heißt Lee Sedol vs. Alpha Go. Es werden dabei fünf Partien gespielt mit einer Bedenkzeit von einer Minute pro Zug. Wer gern live dabei sein möchte, der kann dies gern tun, denn DeepMind überträgt die Spiele live über YouTube auf ihrem eigenen Channel. Wer will kann sich für das erste Spiel sogar eine Erinnerung bei YouTube einstellen. Die ganze Redaktion von Bluemind wird dem Spektakel natürlich daheim am PC beiwohnen und mit Alpha Go mitfiebern.
Bei so einer starken KI wird es nicht mehr lange dauern, bis Computer in jedem Lebensbereich besser sein werden als Menschen. Bereits im Moment gelingt es DeepMind ihrer KI, selbständig neue Dinge wie z.B. alte Spielklassiker auf dem Atari beizubringen.
Obwohl es sich bei Go nur um ein Brettspiel handeln mag, ist die Lösung dieses KI Problems dennoch von großer Bedeutung für die Forschung, da sie die Entwicklung von künstlichen Intelligenzen als Grundlagenforschung stark vorantreibt. Bereits jetzt nutzt Google seine KI-Kenntnisse, um ihre eigenen Dienstleistungen zu verbessern. So legen Fahrsimulatoren von Google täglich mehr als drei Millionen Kilometer zurück, um sich das Fahren selbst beizubringen. Dank einer Kooperation mit Movidius sollen Smartphones auch bald auf die Fähigkeiten von künstlichen Intelligenzen zurückgreifen können, um somit das Nutzererlebnis deutlich zu verbessern.
Was sagt ihr aber zu Alpha Go, Google DeepMind und der KI-Forschung? Haltet ihr alles nur für eine kleine Spielerei, setzt ihr darin die Zukunft der Menschheit oder habt ihr wie Elon Musk sogar Angst vor einem möglichen Terminator-Szenario? Schreibt uns eure Meinung dazu doch einfach in die Kommentare und lasst uns darüber diskutieren. Wir freuen uns auf euch.
Titelbild Quelle: Nature.com
