Das erste Computer-Programm, dem es gelungen ist einen Meister im Go zu schlagen, heißt AlphaGo. Wie es gelang, die Meister zu schlagen, wird in dieser Arbeit behandelt.
Das Strategie-Brett-Spiel Go findet seinen Ursprung vor über 3000 Jahren in China und ist Teil der chinesischen vier Künste, welche Bestandteile der Kultur in China sind.
Dadurch bietet Go, als eines der ältesten und traditionellsten Brettspiele der Welt, einen ganz besonderen Anreiz für Informatiker ein Programm zu entwickeln, welches das Spiel beherrscht.
Die Regeln von Go erscheinen zwar einfacher als die von Schach, die Komplexität des Spiels ist jedoch wesentlich größer. Nach dem heutigen Kenntnisstand ist es unmöglich alle möglichen Kombinationen zu bewerten und in einer angemessenen Zeit zu berechnen. Go-Meister können oft nicht logisch erklären, warum sie einen bestimmten Zug gemacht haben, sie vertrauen beim Ziehen oft auf ihr Bauchgefühl. Eine KI muss demnach eine Art Intuition für bestimmte Muster auf dem Go-Brett erlernen. Dieser Aufgabe haben sich bereits viele Wissenschaftler gestellt.
Go ist eines der komplexesten Spiele überhaupt. Es bestehen zwei Problematiken für Computer, die ein Programm lösen muss, um gegen Go-Meister zu gewinnen. Wie bereits erwähnt ist das erste Problem die große Anzahl an möglichen Spielzügen. Da Go ein Spiel der perfekten Information ist, wäre es theoretisch möglich einen perfekten Zug für eine Spielsituation zu finden. Mithilfe heutiger Hardware ist es nicht möglich einen Spielbaum zu erstellen um den perfekten Zug zu finden. Zweitens ergibt sich eine Problematik bei der Spielstellenbewertung der einzelnen Spieler. Es ist sehr schwer vorauszusagen, welcher Spieler bei einem Zug die höhere Wahrscheinlichkeit auf einen Sieg hat.
Inhaltsverzeichnis
1 Einleitung
1.1 Motivation
2 Grundlagen
2.1 Go-Regeln
2.2 Problematik Go
2.3 Spielstarke
2.4 Neuronale Netze
2.5 Monte Carlo Tree Search
3 Computer Go
3.1 Entwicklung
3.2 AlphaGo
4 Ausblick
4.1 AlphaZero
4.2 Poker
Zielsetzung & Themen
Die Arbeit untersucht die technologische Herausforderung, Computerprogramme zu entwickeln, die das komplexe Brettspiel Go auf professionellem Niveau beherrschen. Dabei liegt der Fokus auf der Analyse der methodischen Ansätze, insbesondere der Kombination von neuronalen Netzen mit Suchalgorithmen wie der Monte Carlo Tree Search, die es ermöglichten, menschliche Meister zu besiegen.
- Grundlagen des Spiels Go und dessen mathematische Komplexität
- Funktionsweise und Training neuronaler Netze im Kontext von Go
- Die Rolle der Monte Carlo Tree Search bei der Entscheidungsfindung
- Die historische Entwicklung von Computer-Go-Programmen
- Der technische Durchbruch durch AlphaGo
Auszug aus dem Buch
3.2 AlphaGo
In 2015 gelang es AlphaGo und seinen Entwicklern, den ersten professionellen Go-Spieler, Fan Hui ohne Handicap zu besiegen.
In 2.2 werden die zwei hauptsächlichen Probleme im Go erklärt. Die der Suche nach einem „perfekten“ nächsten Zug lässt sich in ihrer Komplexität jedoch reduzieren, indem man die Tiefe und Breite der Suche eingrenzt. Um die Suche zu begrenzen, wurden in AlphaGo zwei neuronale Netze entwickelt. Die Breite bei der Suche wird dabei durch das Policy-Netzwerk reduziert. Es gibt grundsätzlich zwei verschiedene Policy-Netzwerke in AlphaGo, das Supervised learning(SL) Policy-Netzwerk und das Reinforcement learning(RL) Policy-Netzwerk. Das SL Policy-Netzwerk wird mit Daten aus Go-Partien zwischen menschlichen Spielern trainiert und dient dazu, Züge vorzuschlagen, die bereits gespielt wurden. Das RL Policy-Netzwerk wird durch das SL Policy-Netzwerk trainiert, indem es gegen das SL Policy-Netzwerk spielt. Dabei trifft es eine Auswahl, welche vorgeschlagen Züge erfolgversprechend sind. Für eine Reduzierung der Tiefe wurde das Value-Netzwerk entworfen. Es bewertet die aktuelle Position auf dem Go-Brett und bestimmt, welche Seite wahrscheinlicher gewinnt. Das Value-Netzwerk wird mit Trainingsdaten aus Spielen, des RL Policy-Netzwerks trainiert. Die Trainingsdaten bestehen dabei nur aus einzelnen Positionen auf dem Brett und dem jeweiligen Ausgang des Spiels, was ein auftretendes Overfitting des Value-Netzwerks mindert.
Die Netzwerke werden nun über die MCTS miteinander kombiniert. Die MCTS in AlphaGo ändert die Anordnung (aus 2.5) der Funktionen. In jedem Knoten des Baums werden Aktionswert Q(s, a), Besuchsanzahl N(s, a) und die vorherige Wahrscheinlichkeit P(s, a) gespeichert. Zunächst wird ein der Zug mit dem großen Aktionswert plus einem u(P) ∝ P(s, a) / (1 + N(s, a)) gewählt.
Zusammenfassung der Kapitel
1 Einleitung: Diese Einleitung führt in das Spiel Go als historisch gewachsenes Brettspiel ein und motiviert die Entwicklung von KI-Programmen aufgrund der enormen Spielkomplexität.
2 Grundlagen: In diesem Kapitel werden die Spielregeln von Go, die Komplexität der Spielstellenbewertung sowie die theoretischen Fundamente neuronaler Netze und der Monte-Carlo Tree Search erläutert.
3 Computer Go: Dieses Kapitel behandelt die historische Entwicklung von Go-Programmen und die spezifische Architektur von AlphaGo, das neuronale Netze zur Reduktion der Suchtiefe und -breite nutzt.
4 Ausblick: Hier wird der Nachfolger AlphaZero vorgestellt, der ohne menschliche Dateneingabe lernt, sowie ein kurzer Ausblick auf zukünftige Herausforderungen wie das Spiel Poker gegeben.
Schlüsselwörter
Go, AlphaGo, Künstliche Intelligenz, Neuronale Netze, Monte Carlo Tree Search, Spieltheorie, Suchalgorithmen, DeepMind, Spielstärke, Maschinelles Lernen, Reinforcement Learning, Supervised Learning, Strategie, Brettspiel, AlphaZero
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit thematisiert die Informatik-Herausforderung, Computerprogramme zu entwerfen, die in der Lage sind, komplexe Brettspiele wie Go auf menschlichem Meisterniveau zu spielen.
Welche zentralen Themenfelder werden abgedeckt?
Zu den zentralen Themen gehören die Spielregeln von Go, die theoretischen Grundlagen neuronaler Netze sowie Suchmethoden für komplexe Spielbäume.
Was ist das primäre Ziel der Untersuchung?
Das Ziel ist es, den technischen Prozess und die methodischen Ansätze zu erklären, die es Programmen wie AlphaGo ermöglichten, professionelle Go-Spieler zu besiegen.
Welche wissenschaftlichen Methoden werden verwendet?
Die Arbeit basiert auf einer Literaturanalyse zu aktuellen KI-Verfahren wie Reinforcement Learning, Supervised Learning und der Monte-Carlo Tree Search.
Was wird im Hauptteil der Arbeit behandelt?
Der Hauptteil gliedert sich in eine theoretische Einführung der KI-Grundlagen sowie eine detaillierte Analyse der spezifischen Architektur von AlphaGo.
Welche Schlüsselwörter charakterisieren die Arbeit?
Die zentralen Begriffe sind Go, Neuronale Netze, Monte Carlo Tree Search, AlphaGo und Künstliche Intelligenz.
Warum ist Go für Computer schwieriger zu lösen als Schach?
Go besitzt eine deutlich höhere Anzahl an legalen Zügen, was die Berechnung eines vollständigen Spielbaums mit heutiger Hardware unmöglich macht und intuitive Bewertungsmodelle erfordert.
Wie unterscheidet sich AlphaZero von seinem Vorgänger AlphaGo?
AlphaZero benötigt im Gegensatz zu AlphaGo keine menschlichen Trainingsdaten mehr, sondern erlernt die Strategien durch das Spiel gegen sich selbst allein basierend auf den Spielregeln.
Was stellt die nächste große Hürde nach Go für KI dar?
Die nächste Herausforderung sind Spiele mit unvollständigen Informationen, wie beispielsweise Poker, bei denen menschliches Verhalten wie Bluffen eine Rolle spielt.
- Arbeit zitieren
- Finn von Holten (Autor:in), Kai Parsiegla (Autor:in), 2018, Computer-Go-Programme. Wie gelang es, die Meister zu schlagen?, München, GRIN Verlag, https://www.grin.com/document/475012
