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.
1 Einleitung
Das Strategie-Brett-Spiel Go findet seinen Ursprung vor u¨ ber 3000 Jahren in China1 und ist Teil der chinesischen vier Ku¨ nste (” Qi, Shu, Hua“ ), welche Bestandteile der Kultur in a¨ltesten und traditionellsten Brettspiele der Welt, China sind. Dadurch bietet Go, als eines der einen ganz besonderen Anreiz fu¨ r Informatiker ein Programm zu entwickeln, welches das Spiel beherrscht.
1.1 Motivation
Die Regeln von Go erscheinen zwar einfacher als die von Schach, die Komplexita¨t des Spiels ist jedoch wesentlich gro¨ ßer. Auf einem 19 * 19 großen Go Brett gibt es L (19 , 19) ≈ 2 . 08 * 10170 legale Zu¨ ge2. Beim Schach gibt es im Vergleich dazu 10120 Variationen3 von der initialen Po- sition. Nach dem heutigen4 Kenntnisstand ist es unmo¨ glich alle mo¨ glichen Kombinationen zu bewerten und in einer angemessenen Zeit zu berechnen. Go-Meister ko¨ nnen oft nicht logisch erkla¨ren, warum sie einen bestimmten Zug gemacht haben, sie vertrauen beim Ziehen oft auf ihr Bauchgefu¨ hl. Eine KI muss demnach eine Art Intuition fu¨ r bestimmte Muster auf dem Go-Brett erlernen. Dieser Aufgabe haben sich bereits viele Wissenschaftler gestellt. Das erste Programm, dem es gelungen ist einen Meister im Go zu schlagen, heißt AlphaGo. Wie es gelang, die Meis- ter zu schlagen, wird im Folgenden weiter behandelt.
2 Grundlagen
Im diesem Kapitel werden Grundlagen der Go-Regeln, Problematik sowie Spielsta¨rke beim Go genannt. Ferner wird die Funktionsweise von neuronalen Netzen und der Monte-Carlo Tree Search erlautert.
2.1 Go-Regeln
Beim Go gibt es viele unterschiedliche Regelwerke5, die sich im Laufe der Zeit manifestiert haben. So unterscheiden sich zum Beispiel die Regeln der AGA (Ameraican Go Assosiation) 6 von denen der Chinese Weiqi Association 7.
Grundsa¨tzlich lassen sich die Regeln8 des Go’s folgendermaßen zusammenfassen. Schwarz und Weiß sind abwechselnd dran, jeweils einen ihrer Steine auf einen Schnittpunkt des Go-Bretts zu legen. Sobald ein Stein gespielt wurde, kann er zwar nicht mehr bewegt werden, jedoch kann er vom Gegner gefangen werden. Gruppen von Steinen einer Farbe, die verbunden und benachbart sind, werden Blo¨ cke genannt. Die leeren Schnittpunkte neben einem Stein werden Freiheiten genannt. Wenn ein Block auf null Freiheiten vom Gegner reduziert wird, ist dieser vom Gegner gefangen und wird vom Brett entfernt. Am Ende des Spiels, za¨hlt jeder Spieler die Anzahl der Steine die er gefangen hat plus die Anzahl leerer Schnittpunkte, die er mit seinen Steinen umschlossen hat, genannt Territorium. Der Spieler mit mehr Punkten gewinnt.
2.2 Problematik Go
Go ist eines der komplexesten Spiele u¨ berhaupt. Es bestehen zwei Problematiken fu¨ r Computer, die ein Programm lo¨ sen muss, um gegen Go-Meister zu gewinnen. Wie in Kapitel 1.1 bereits erwa¨hnt ist das erste Problem die große Anzahl an mo¨ glichen Spielzu¨ ge. Da Go ein Spiel der perfekten Information ist, wa¨re es theoretisch mo¨ glich einen perfekten Zug fu¨ r eine Spielsitua- tion zu finden. Mithilfe heutiger Hardware ist es nicht mo¨ glich einen Spielbaum9 zu erstellen um den perfekten Zug zu finden.
Zweitens ergibt sich eine Problematik bei der Spielstellenbewertung10 der einzelnen Spieler. Es ist sehr schwer vorauszusagen, welcher Spieler bei einem Zug die ho¨ here Wahrscheinlichkeit auf einen Sieg hat.
2.3 Spielst¨arke
Die Kompetitivita¨t von Go ermo¨ glicht es Spieler (und Computer) anhand ihrer Spielsta¨rke zu bewerten. Hierfu¨ r wird ein sogenanntes Whole-History Rating11 System verwendet. Go Spieler werden außerdem durch ihre Spielsta¨rke12 in Ra¨nge eingeteilt. Es gibt Kyu¯ -Ra¨nge und Dan- Ra¨nge fu¨ r Amateure sowie weitere neun Dan-Ra¨nge fu¨ r professionelle Go Spieler.
Amateur Range
Abbildung in dieser Leseprobe nicht enthalten
Professionelle Ra¨ nge
Abbildung in dieser Leseprobe nicht enthalten
2.4 Neuronale Netze
Die Grundlage moderner Go-Programme bilden neuronale Netze. Die Entwicklung dieser Netze hat sich biologische Organismen, wie das menschliche Gehirn als Vorbild genommen.
Um Prozesse besser, schneller und effizienter zu verstehen durchla¨uft das Gehirn ein Lern- prozess. Dieses Verfahren wird bei neuronalen Netzen13,14 approximiert. Sie simulieren die Nachahmung kognitiver Fa¨higkeiten biologischer Organismen. Daher finden sie Verwendung in einem breiten Anwendungsbereich, wie bei der Klassifikation, Optimierung und Musterer- kennung. Entgegen des menschlichen, welches ein biologisches Netz ist, ist ein neuronales ein am Computer simuliertes Netz. Die simulierten Neuronen senden sich Aktivierungssignale15 u¨ ber eine gerichtete und ungerichtete Graphen um Informationen zu u¨bertragen.
Ein Netz besteht aus Layern, die sich aus drei Arten von Neuronen16 (Units) zusammensetzen. Die Input-Units empfangen die Signale in Form von Zahlen. Die verarbeiteten Signale wer- den als Zahlenwerte von den Output-Units ausgegeben. Zwischen den In- und Output-Units befinden sich die Hidden-Units, welche fu¨ r die Verarbeitung zusta¨ndig sind. Durch Gewichtun- gen zwischen den Units wird das Erlernte gespeichert. Das Gewicht beschreibt die Sta¨rke mit den Units miteinander verbunden sind. Ist das Gewicht positiv, hat die Unit einen erregenden Einfluss auf die nachfolgende Unit. Wenn es negativ ist, hat es wiederum einen hemmenden Einfluss auf den Nachfolger. Bei einem Gewicht von Null, gibt es auch keinen Einfluss.
[...]
1... the myth of King Yao teaching [...] play the game c. 2100 BC. [Sh94]
2 The L(19, 19) computation took over 250000 CPU-hours and 30PB of disk IO [TF16]
3 vgl. [Sh50]
4.11.2018
5 https://www.britgo.org/rules/compare.html#komi besucht am: 05.11.2018
6 vgl. [Co91]
7 vgl. [SSM07b]
8 Regeln aus [SSM07a]
9 vgl. [Zi17, S.369]
10 vgl. [SSM07a]
11 vgl. [Co08]
12 http://www.mechner.com/david/go/kyu.html besucht am 07.11.2018
13 vgl. [Sc13]
14 vgl. Vorlesungsunterlagen: I165 - Analytische Informationssysteme
15 vgl. [Kr15]
16 vgl. [RW10, S.14]
- Citar trabajo
- Finn von Holten (Autor), Kai Parsiegla (Autor), 2018, Computer-Go-Programme. Wie gelang es, die Meister zu schlagen?, Múnich, GRIN Verlag, https://www.grin.com/document/475012
-
-
-
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X.