Warum neuronale Netze zum ersten Mal die besten menschlichen Go-Spieler schlagen werden

Computer beginnen schnell, Menschen in mehr oder weniger allen Bereichen zu übertreffen. Beispielsweise haben Experten für maschinelles Sehen kürzlich einen Algorithmus vorgestellt, der den Menschen bei der Gesichtserkennung übertrifft. Ähnliche Algorithmen beginnen auch bei der Objekterkennung mit Menschen mithalten zu können. Und menschliche Schachspieler haben den Kampf gegen Computer längst aufgegeben.

Aber es gibt einen Bereich, in dem Menschen immer noch triumphieren. Das ist beim Spielen des alten chinesischen Go-Spiels. Computer haben dieses Spiel nie gemeistert. Die besten Algorithmen erreichen nur das Können eines sehr starken Amateurspielers, das die besten menschlichen Spieler leicht übertreffen.

Das scheint sich dank der Arbeit von Christopher Clark und Amos Storkey von der University of Edinburgh in Schottland zu ändern. Diese Jungs haben die gleichen maschinellen Lerntechniken angewendet, die Gesichtserkennungsalgorithmen transformiert haben, um den nächsten Zug in einem Go-Spiel zu finden. Und die Ergebnisse lassen wenig Hoffnung, dass der Mensch dieses Spiel weiterhin dominieren wird.

Kurz gesagt, Go ist ein Spiel für zwei Spieler, das normalerweise auf einem 19 x 19-Raster gespielt wird. Die Spieler legen abwechselnd schwarze und weiße Steine ​​auf das Gitter, um am Ende des Spiels mehr Platz auf dem Brett zu besetzen als ihr Gegner. Spieler können die Steine ​​ihres Gegners entfernen, indem sie sie mit ihren eigenen umgeben.

Experten glauben, dass es zwei Gründe gibt, warum Computer Go nicht beherrschen. Der erste ist die schiere Anzahl von Zügen, die in jeder Phase des Spiels möglich sind. Go-Spieler haben 19 x 19 = 361 mögliche Startzüge und normalerweise gibt es an jedem Punkt des Spiels Hunderte von möglichen Zügen. Im Gegensatz dazu beträgt die Anzahl der Züge im Schach normalerweise etwa 50.

Das zweite Problem ist, dass es Computern schwer fällt, die Stärken und Schwächen einer Vorstandsposition zu bewerten. Beim Schach gibt das einfache Addieren des Wertes jeder auf dem Brett verbliebenen Figur einen vernünftigen Hinweis auf die Stärke der Position eines Spielers. Aber das funktioniert nicht in Go. Das Zählen der Steine, die jeder Spieler hat, ist ein schlechter Indikator dafür, wer gewinnt, sagen Clark und Storkey.

Moderne Go-Algorithmen gehen dieses Problem an, indem sie nach jedem Zug das gesamte Spiel durchspielen und dies auf viele verschiedene Arten. Wenn der Computer in den meisten dieser Spiele gewinnt, wird dieser Zug als gut angesehen.

Dies ist eindeutig eine zeitaufwändige und rechenintensive Aufgabe. Trotzdem schlägt es im Allgemeinen menschliche Go-Experten nicht, die den Zustand eines Go-Boards normalerweise mit kaum mehr als einem Blick beurteilen können.

Viele Experten glauben, dass das Geheimnis der menschlichen Meisterschaft im Go-Spiel die Mustererkennung ist – die Fähigkeit, Stärken und Schwächen anhand der Form der Steine ​​zu erkennen, anstatt mehrere Züge vorauszusehen.

Aus diesem Grund könnten die jüngsten Fortschritte bei Mustererkennungsalgorithmen Computern helfen, viel besser zu werden. Diese Fortschritte haben riesige Bilddatenbanken verwendet, um tiefe Faltungs-Neuronalnetzwerke zu trainieren, um Objekte und Gesichter mit der Art von Genauigkeit zu erkennen, die jetzt der menschlichen Leistung entspricht. Es liegt also nahe, sich vorzustellen, dass der gleiche Ansatz einen großen Unterschied bei der automatisierten Bewertung von Go-Boards machen könnte.

Und genau das haben Clark und Storkey getan. Die Frage, auf deren Beantwortung diese Jungs ein Deep Convolutional Neural Network trainiert haben, lautet: Ist es angesichts einer Momentaufnahme eines Spiels zwischen zwei Go-Experten möglich, den nächsten Zug im Spiel vorherzusagen?

Sie gehen dies an, indem sie eine riesige Datenbank von Go-Spielen verwenden, um ein neuronales Netzwerk zu trainieren, um den nächsten Zug zu finden. Clark und Storkey nutzten über 160.000 Partien zwischen Experten, um zusammen mit ihrem nächsten Zug eine Datenbank mit 16,5 Millionen Stellungen zu erstellen. Sie verwendeten fast 15 Millionen dieser Positionsbewegungspaare, um ein achtschichtiges neuronales Faltungsnetzwerk zu trainieren, um zu erkennen, welche Bewegung diese erfahrenen Spieler als nächstes machten. Dies war ein Prozess, der mehrere Tage dauerte.

Anschließend verwendeten sie den Rest des Datensatzes, um das neuronale Netzwerk zu testen. Mit anderen Worten, sie präsentierten dem Netzwerk eine Brettposition aus einem Spiel und baten es, den nächsten Zug auszuwählen. Clark und Storkey sagen, dass das trainierte Netzwerk in der Lage war, den nächsten Schritt in bis zu 44 Prozent der Fälle vorherzusagen und den bisherigen Stand der Technik bei dieser Aufgabe deutlich zu übertreffen.

Das ist nicht zuletzt deshalb interessant, weil der neue Ansatz keinen der vorherigen Schritte verwendet, um seine Entscheidung zu treffen; es bewertet auch keine zukünftigen Positionen.

Nachdem sie das neuronale Netzwerk trainiert hatten, spielten Clark und Storkey es dann gegen zwei der besten Go-Algorithmen, die es gibt. Der erste heißt GNU Go und spielt auf einem Niveau, das einem fortgeschrittenen Amateur mit einem Ranking von 6-8 Kyu entspricht. (Go-Rankings reichen von einem Anfänger mit einem Rang von 30-20 Kyu bis zu einem professionellen Experten mit einem Rang von 1 Kyu).

Das zweite war ein hochmodernes Programm namens Fuego 1.1, das einen Rang von ungefähr 5-4 Kyu hat. Ein menschlicher Spieler würde normalerweise viele Jahre des Studiums benötigen, um dieses Niveau zu erreichen.

Die Ergebnisse deuten eindeutig darauf hin, dass die Schrift für menschliche Go-Spieler an der Wand ist. Das neuronale Netzwerk von Clark und Storkey schlug GNU Go in fast 90 Prozent der Fälle in einer Serie von 200 Spielen. Mit anderen Worten, nach ein paar Tagen Training war das neurale Netz in der Lage, GNU Go konsequent zu schlagen.

Gegen Fuego 1.1 schnitt es weniger gut ab und gewann nur knapp über 10 Prozent seiner Spiele. Trotzdem ist das eine beachtliche Leistung. Selbst ein paar Partien gegen diesen Gegner gewinnen zu können, weist auf ein hohes Maß an Können hin, sagen Clark und Starkey.

Das ist eindeutig sehr vielversprechend. Obwohl die Netzwerke mit einer „Null-Schritt-Vorausschau“-Politik spielen und einen Bruchteil der Rechenzeit wie ihre Gegner verwenden, sind sie immer noch in der Lage, besser zu spielen als GNU Go und Fuego einige Spiele wegzunehmen, sagen sie.

Und es gibt eindeutig Verbesserungspotenzial, indem Sie beispielsweise diesen Ansatz mit anderen kombinieren, die frühere Schritte verwenden und nach vorne schauen. Eine Idee, die Clark und Starkey vorschlagen, besteht darin, das Convolutional Neural Network parallel zum konventionellen Ansatz zu betreiben, um dabei zu helfen, den Baum von möglichen Zügen zu beschneiden, die untersucht werden müssen.

Es gibt keinen Hinweis von Clark und Storkey, dass dieser Ansatz die besten Go-Spieler der Welt schlagen wird. Aber sicherlich ist es nur eine Frage der Zeit, bis sich sogar Go-Spieler ihren computergesteuerten Oberherren beugen müssen.

Ref: arxiv.org/abs/1412.3409 : Deep Convolutional Neural Networks beibringen, Go zu spielen

verbergen