Computer-Go-Programme. Wie gelang es, die Meister zu schlagen?


Akademische Arbeit, 2018
9 Seiten, Note: 1.3

Leseprobe

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]

Ende der Leseprobe aus 9 Seiten

Details

Titel
Computer-Go-Programme. Wie gelang es, die Meister zu schlagen?
Hochschule
Nordakademie Hochschule der Wirtschaft in Elmshorn
Note
1.3
Autoren
Jahr
2018
Seiten
9
Katalognummer
V475012
ISBN (eBook)
9783668956629
Sprache
Deutsch
Schlagworte
KI, GO
Arbeit zitieren
Finn von Holten (Autor)Kai Parsiegla (Autor), 2018, Computer-Go-Programme. Wie gelang es, die Meister zu schlagen?, München, GRIN Verlag, https://www.grin.com/document/475012

Kommentare

  • Noch keine Kommentare.
Im eBook lesen
Titel: Computer-Go-Programme. Wie gelang es, die Meister zu schlagen?


Ihre Arbeit hochladen

Ihre Hausarbeit / Abschlussarbeit:

- Publikation als eBook und Buch
- Hohes Honorar auf die Verkäufe
- Für Sie komplett kostenlos – mit ISBN
- Es dauert nur 5 Minuten
- Jede Arbeit findet Leser

Kostenlos Autor werden