Spiele mit Neuronalen Netzwerken

Wiesbauer Gerald, Manuela Stürzlinger, Rettenbacher Christopher, Mayer August

16. März 1999

Zusammenfassung

Dieses Dokument beschreibt die Planung und Implementierung eines Backgammon-Spiels mit Java, wobei der Computergegner durch ein neuronales Netzwerk möglichst spielstark sein soll.

Inhaltsverzeichnis

1 Einleitung 2

1.1 Spielregeln Backgammon . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.1 Spielidee . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.2 Würfeln und Ziehen . . . . . . . . . . . . . . . . . . . . . . 2 1.1.3 Blockierte Felder . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.4 Schlagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.5 Wiedereinbringen geschlagener Steine . . . . . . . . . . . . . 2 1.1.6 Ausspielen . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.7 Gammon und Backgammon . . . . . . . . . . . . . . . . . . 3 1.1.8 Spielbeginn . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.9 Dopplerwürfel . . . . . . . . . . . . . . . . . . . . . . . . . 3

A Protokolle 3

B Protokoll vom 10. März 1999 3

C Bibliographie 4

C.1 Inhaltsangaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

C.1.1 Temporal Difference Learning and TD-Gammon [Tes95] … 4 C.2 Auflistungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1 Einleitung

1.1 Spielregeln Backgammon

1.1.1 Spielidee

Backgammon ist ein Spiel, bei dem zwei Spieler mit jeweils 15 Steinen auf einem Brett mit 24 Feldern spielen.Ziel des Spieles ist es, alle Steine vom Brett ins Aus zu spielen. Die Spielsteine haben eine bestimmte Startposition und müssen von dort aus alle in das heimfeld gezogen werden. Das sind bei Weiß die Felder 1 bis 6, bei Schwarz die Felder 19 bis 24. Die Spieler ziehen deshalb immer in entgegengesetzte Richtung (Weiß von 24 nach 1; Schwarz von 1 nach 24), wobei sie auf ihrem Weg durch Blockaden des Gegners behindert werden können. Sind alle Steine im Heimfeld versammelt, dann können sie ausgespielt, das heißt durch Würfeln aus dem Spiel genommen werden. Wer zuerst keine Steine mehr auf dem Brett hat, hat gewonnen.

1.1.2 Würfeln und Ziehen

Jeder Spieler würfelt vor seinem Zug mit zwei Würfeln und zieht die geworfene Augenzahl vorwärts (niemals rückwärts!)Als Beispiel nehmen wir an, Weiß hat in der Ausgangsstellung 6+5 geworfen. Er kann jetzt entweder zwei Steine mit jeweils einer Zahl (13 auf 7 und 13 auf 8) oder nur einen Stein mit beiden Zahlen spielen(24 auf 13). Welche der beiden Zahlen der Spieler dabei zuerst zieht, kann er sich aussuchen. Der Wurf muß aber immer vollständig ausgeführt werden, wenn daß nicht durch Blockade des Gegners verhindert wird. Dabei darf man beliebig viele Steine seiner Farbe auf ein Feld stellen. Würfelt man zwei gleiche Zahlen, so nennt man dies einen Pasch. Wird ein Pasch geworfen, gilt folgende Sonderregel: Die Augenzahl ist viermal auszuführen- mit einem, zwei, drei, oder vier Steinen.

1.1.3 Blockierte Felder

Ein Feld ist blockiert, wenn dort zwei oder mehr Steine des Gegners stehen. Auf ein blockiertes Feld kann nicht gezogen werden, man darf es jedoch überspringen. Kann nur eine der beiden gewürfelten Zahlen ausgeführt werden, muß die höhere Zahl ziehen.

1.1.4 Schlagen

Steine können nur geschlagen werden, wenn sie einzeln auf einem Feld stehen. Ein geschlagener Stein wird auf die Bar gestellt, das ist der Balken zwischen den Bretthälften. Im nächsten Zug muß er -wenn möglich- wieder ins Spiel gebracht werden.

1.1.5 Wiedereinbringen geschlagener Steine

Wenn ein geschlagener Stein auf der Bar steht,muß er zunächst wieder ins Spiel gebracht werden, bevor man mit einem anderen ziehen darf. Geschlagene Steine müssen von der Bar ins Heimfeld des Gegners gespielt werden. Hierbei landet ein Stein bei einer 1 auf dem 1er(24er) Punkt,usw. Auf vom Gegner blockierte Felder darf nicht gezogen werden.

1.1.6 Ausspielen

Mit dem Ausspielen darf erst begonnen werden, wenn alle 15 Steine im eigenen Heimfeld sind. Man spielt dabei so als gäbe es ein Feld 0, auf das alle Steine ziehen müssen. Sind von den höheren Punkten alle Steine ausgespielt,so müssen die entsprechenden Zahlen vom nächst niedrigeren Punkt ins Aus gespielt wedren.

1.1.7 Gammon und Backgammon

Ein Spiel ist Gammon gewonnen, wenn eine Parei alle 15 Steine, der Gegner aber noch keinen Stein ausgespielt hat. Ein mit Gammon gewonnenes Spiel zählt doppelt. Hat der Sieger alle 15 Steine abgetragen, während er Gegner noch einen Stein auf der Bar, oder im Heimfeld des Siegers hat, dan zählt das Spiel dreifach, er hat Backgammon gewonnen.

1.1.8 Spielbeginn

Zu Beginn der Partie würfeln beide Spieler jeweils mit einem Würfel. Der Spieler der die höhere Zahl hat beginnt die Partie mit dem sich ergebenden Wurf.

1.1.9 Dopplerwürfel

Zu jedem Spiel gehört ein Würfel, der auf seinen Seiten die Zahlen 2, 4, 8, 16, 32 und 64 hat. Glaubt ein Spieler einen klaren Vorteil zu haben, nimmt er den Würfel und legt ihn mit der 2 oben auf die Spielfläche. Sein Gegner kann nun aufgeben, dies würde ihn einen Punkt kosten. Nimmt er die Herausforderung an, erhält er das alleinige recht, bei einer Wende im weiteren Spielverlauf, ebenfalls zu verdoppeln. Auch diese Herausforderung kann angenommen, oder abgelehnt werden. Der Spielwert verdoppelt sich jedes Mal.

A Protokolle

B Protokoll vom 10. März 1999

• Projekt: Backgammon mittels Artificial Neural Networks

• Anwesende:

– DI Mag.Roland Schwaiger

– August Mayer

– Gerald Wiesbauer – Christopher Rettenbacher

– Manuela Stürzlinger

• Protokollführerin: Manuela Stürzlinger

• Themen:

– Wiederholung des administrativen Teils

– Quellen fuer Lehrmaterial(Java,UML,HTML,Latex)

– Präsentation der Web-Site unserer Projektgruppe

– Informationsmaterial ”Temporal Difference Learning and TD-Gammon “ ”Neural Networks “(s.S. 66) by Müller, Reinhardt

– Besprechung des Dokumentaufbaus bis Punkt Protokolle

• Aufgaben

– Fotos der Projektmitarbeiter (fur Web-Site)

– Auseinandersetzen mit den Zeitungsartikel ev. auftauchende Fragen in Punkt Literaturuebersicht des Dokumentes vermerken

– Ausarbeitung des Dokuments bis Punkt Einleitung konkret:

∗ Titelseite Name des Projekts Name der Projektmitarbeiter

∗ Abstract kurze und prägnante Beschreibung des Projekts

∗ Einleitung Was ist Backgammon? Wie lauten die Spielregeln? Erscheinungsbild des Spielbrettes

• Ziele bis nächste Woche

– Gestaltung der Web-Site(Fotos)

– Lesen des Zeitungsartikels

– Ausarbeitung des Dokuments bis Dienstag, den 16.03.99 Abgabe per E-Mail(.dvi-File)an DI Mag. Schwaiger

C Bibliographie

C.1 Inhaltsangaben

C.1.1 Temporal Difference Learning and TD-Gammon [Tes95]

Dieser Text behandelt das Programm TD-Gammon von Gerald Tesauro, ein ”Backgammon-Lern-System“, das den TD(λ)-Algorithmus zum Lernen verwendet. Dabei spielt das Programm mit sich selbst, bewertet bei jedem Zug die aktuelle Spielsituation und modifiziert die Gewichte des Netzwerks zeitlich abgestuft anhand dieses Fehlersignals. Als Input des Netzes verwendet er neben der Spielposition auch einige ”handgemachte“ Werte.

Im Vergleich zu Neurogammon, das ein von Experten mit menschlichen Regeln trainiertes neuronales Netz realisiert, aber nur gute Fortgeschrittenen-Spielstärke erreicht, erreicht das Programm Weltklasseniveau und findet sogar einige optimale Züge selbständig. So hat eine von TD-Gammon gefundene Zugkombination die alte, in dieser Spielsituation verwendete bereits abgelöst.

TD-Gammon scheint in diesem Zusammenhang tatsächlich zu lernen, und der Autor beobachtet auch verschiedene Stufen der Wissensaneignung beim Lernvorgang, wie das Lernen von Grundzügen und einfachen Strategien (erste paar tausend Spiele), später von komplexeren Strategien (nach einigen zehntausend Spielen).

Fragen zum Text:

• Was sagt die Gewichtung (weights) aus?

• Wie funktioniert das neuronales Netz von TD-Gammon?

• Wie wirken die -two concept features- zusammen?

• Wie entscheidet TD-Gammon über seinen nächsten Zug?

C.2 Auflistungen

Literatur

[Tes95] G[erald] Tesauro. Temporal difference learning and td-gammon. 38(3):58+, March 1995.