¶ Allgemeines
Backgammon ist ein aus England stammendes Würfelbrettspiel für zwei Personen und wurde im 17. Jahrhundert erfunden. Ältere Abwandlungen und Vorgängerversionen gab es bereits seit dem Römischen Reich.[1]
Bis heute ist die Namensgebung des Spiels unklar. Es lässt sich vermuten, dass diese durch das angelsächsische bac gamen geprägt wurde und übersetzt „Rückspiel“ (backgame) bedeutet, da man seine geschlagenen Steine wieder zurück auf das Spielbrett bringen muss. Eine weitere Annahme für die Herkunft des Namens bilden die wasilischen Wörter back („klein“) und cammon („Schlacht“).[1:1]
¶ Spielregeln
Weil es verschiedene Spielvarianten von Backgammon gibt, werden im Folgenden die gängigen Regeln vorgestellt, die auch auf internationalen Turnieren gespielt werden.[2]
¶ Spielbrett und Ausgangsstellung
Gegeben ist ein Spielbrett bestehend aus 24 Dreiecken. Diese stellen die Felder (auch Points genannt) dar, die von 1 bis 24 nummeriert und auf denen die 15 weißen und 15 schwarzen Spielsteine in einer bestimmten Startaufstellung positioniert sind (siehe Abb. 1). Während das obere rechte Viertel des Brettes als das Heimfeld von Weiß bezeichnet wird, ist das untere rechte das entsprechende Heimfeld von Schwarz. Des Weiteren befindet sich in der Mitte eine vertikale Linie (auch Bar genannt), die das Spielbrett in zwei Hälften teilt. Mit zwei Würfeln bewegt Schwarz seine Steine gegen den Uhrzeigersinn. Analog bewegt Weiß seine Spielsteine in die entgegengesetzte Richtung, also im Uhrzeigersinn.
¶ Ziel des Spiels
Ziel ist es, zunächst alle seine Steine ins eigene Heimfeld zu bringen. Sobald alle Steine im Heimfeld angekommen sind, werden diese dann vom Spielbrett entfernt (auch herauswürfeln oder Abtragung genannt). Derjenige, der als erstens alle seine Steine abgetragen hat, gewinnt das Spiel.
¶ Spielablauf
Zu Beginn werfen beide Spieler jeweils mit einem Würfel um den Start. Der Spieler mit der höheren Augenzahl fängt an und bewegt einen oder mehrere Steine (auch ziehen genannt) gemäß den gewürfelten Augenzahlen, die er und sein Gegenspieler gewürfelt haben. Von dort an wechseln sich beide dann mit dem Werfen der zwei Würfel ab. Falls beide dieselbe Zahl werfen, wird einfach erneut geworfen.
¶ Steine bewegen und schlagen
Nachdem ein Spieler seine Würfel geworfen hat, hat er diverse Möglichkeiten, seine Steine zu bewegen. Eine Option wäre, zwei unterschiedliche Steine jeweils entsprechend genau einer gewürfelten Augenzahl zu bewegen. Es besteht aber auch die Möglichkeit, mit beiden Augenzahlen nur einen einzigen Stein zu bewegen und somit mit einem Stein zwei Schritte zu machen. Im letzteren Fall können beide Zahlen allerdings nicht einfach zusammengefügt werden, sondern müssen nacheinander gezogen werden. D.h., Der Spieler bewegt den Stein entsprechend genau einer Augenzahl und macht zunächst einen „Zwischenstopp“ auf einem Feld. Anschließend bewegt dieser den Stein gemäß der anderen Augenzahl. Mit welcher Augenzahl der Spieler anfängt, ist ihm überlassen.
Des Weiteren ist zu beachten, dass ein Stein nur auf einem Feld landen darf, wenn das Feld frei oder mit beliebig vielen eigenen Steinen besetzt ist. Ebenso darf der Spieler seinen Stein auf ein Feld legen, wenn nur ein einziger Stein des Gegners sich dort befindet. In diesem Fall wird der gegnerische Stein geschlagen und auf die Bar gelegt. Befinden sich allerdings mindestens zwei gegnerische Steine, so gilt das Feld als blockiert und der Stein darf nicht dorthin bewegt werden.
Würfelt ein Spieler einen Pasch (also zwei gleiche Zahlen), so wird jede gewürfelte Zahl doppelt gezogen. D.h. der Spieler darf ein bis vier Steine bewegen und somit insgesamt vier Schritte machen.
Es gilt, dass mit den gewürfelten Augenzahlen immer gezogen werden muss. Falls eine Augenzahl nicht gezogen werden kann, muss der Spieler die höhere Zahl verwenden. Kann keine der beiden Zahlen verwendet werden, so muss der Spieler diese Runde aussetzen und der andere ist am Zug.
¶ Geschlagene Steine zurückbringen
Befinden sich ein oder mehrere Steine auf der Bar, so muss der Spieler alle seine geschlagenen Steine erstmal zurück ins Spiel bringen, bevor er wieder mit anderen Steinen ziehen darf. Hierzu würfelt der Spieler wie sonst auch mit beiden Würfeln und setzt seine Steine gemäß einer Augenzahl in das Heimfeld des Gegners, falls das entsprechende Feld im Heimfeld nicht blockiert ist. Ist ein Feld mit mehreren gegnerischen Steinen besetzt, kann mit der gewürfelten Zahl kein Stein zurückgebracht werden. Liegt nur ein einzelner Stein des Gegners auf dem Feld, so wird dieser wie gewohnt geschlagen. Nachdem alle Steine zurückgebracht worden sind, müssen übrig gebliebene Augenzahlen gezogen werden, sofern es möglich ist.
¶ Steine abtragen
Sobald alle Steine im eigenen Heimfeld angekommen sind, darf der Spieler mit der Abtragung beginnen. Dabei kann er einen Stein genau dann abtragen, wenn die gewürfelte Zahl noch geradeso ausreicht, den Stein über den Rand des Spielbrettes zu ziehen, also sozusagen in das „nullte“ bzw. "26ste" Feld zu bewegen. Herausgewürfelte Steine werden einfach vom Brett entfernt.
Ebenfalls ist es möglich, einen Stein im Heimfeld weitervorrücken zu lassen, ohne diesen gleich sofort abtragen zu müssen. Falls auf einem Feld, dessen Nummerierung einer gewürfelten Augenzahl entspricht, keine Steine vorhanden sind, muss vom höchsten noch besetzten Feld gezogen werden. Falls auch auf höheren Feldern sich keine Steine befinden, wird vom nächstkleineren Feld abgetragen.
Wenn ein Stein während der Abtragung geschlagen wird, muss der Spieler diesen Stein wieder ins eigene Heimfeld bringen, damit er mit der Abtragung fortfahren kann.
¶ Gewinnstufen
Bei der Punktevergabe gibt es drei verschiedene Gewinnstufen, mit denen man eine gewonnene Partie werten kann.
¶ Einfaches Spiel
Der Sieger erhält nach Abtragung seiner Steine einen Punkt, wenn der Verlierer mindestens einen Stein herausgewürfelt hat.
¶ Doppeltes Spiel (Gammon)
Der Sieger erhält nach Abtragung seiner Steine zwei Punkte, wenn der Verlierer noch keinen Stein herausgewürfelt hat.
¶ Dreifaches Spiel (Backgammon)
Der Sieger erhält nach Abtragung seiner Steine drei Punkte, wenn der Verlierer noch keinen Stein herausgewürfelt[1:2] und mindestens einen Stein auf der Bar oder im gegnerischem Heimfeld hat.
¶ Verdoppelungswürfel
Der Verdoppelungswürfel ist eine strategische Komponente, die den Wert einer Partie verdoppeln kann. Dieser ist mit den Zahlen 2, 4, 8, 16, 32 und 64 beschriftet. Am Anfang jeder Partie zeigt der Würfel die Zahl 64, es wird aber um den 1-fachen Einsatz gespielt. Sollte während des Spiels einer der beiden Spieler den Eindruck haben, dass dieser das Spiel gewinnen wird, so kann er – falls er am Zug ist und noch nicht gewürfelt hat – seinem Gegner anbieten, den Spielwert zu verdoppeln. Der andere Spieler kann das Angebot akzeptieren oder ablehnen. Lehnt der andere das Angebot ab, so verliert er das Spiel. Nimmt er das Angebot an, so wird der Verdoppelungswürfel so gedreht, dass die nächstgrößere Zweier-Potenz nach oben zeigt, und beide spielen um den verdoppelten Einsatz weiter. Im Verlaufe des Spiels kann die Verdoppelung des Wertes erneut angeboten werden, allerdings nur vom denjenigen Spieler, der als letztes das Verdoppelungsangebot erhalten hat. Bei Annahme des zweiten Angebotes wird um den vierfachen Einsatz gespielt.
¶ Algorithmen
Sowohl Glück als auch strategisches Denken sind erforderlich, um in Backgammon zu gewinnen. Bezüglich der Komplexität hat das Spiel eine Anzahl von Zuständen in Größenordnung von 1020 und ebenso existieren 21 mögliche Würfelkombinationen mit jeweils durchschnittlich 20 legalen Zügen.[3] Entsprechende Algorithmen müssen in der Lage sein, mit dieser stochastischen und komplexen Umgebung umzugehen.
¶ TD-Gammon
TD-Gammon ist ein in den 90er Jahren von Tesauro entwickeltes Multi-Layer Perceptron, das mittels Temporal Difference Learning trainiert wurde. Speziell wurde der TD(λ)-Algorithmus verwendet, der den TD-Error nach jedem Zug zurückpropagierte.[3:1]
Schon bereits gegen Ende der 80er Jahren arbeitete Tesauro an einem neuronalen Netz namens Neurogammon, das mithilfe von Supervised Learning Backgammon lernte, jedoch nur mittlere Spielstärke erreichte. Hingegen erlangte TD-Gammon ein weltklassiges Niveau und war zur damaligen Zeit fast so gut wie die besten Top-Spieler der Welt.
¶ Aufbau
Wie jedes andere Multi-Layer Perceptron hat auch TD-Gammon mehrere diverse Schichten. Die Input-Schicht ab der Version 1.0 beinhaltet 198 Neuronen, mit denen eine Spielsituation wie folgt repräsentiert wird:[4]
- Für jedes einzelne Feld werden acht Neuronen verwendet; vier Neuronen für die Anzahl schwarzer Steine und vier für die der weißen
- zwei Neuronen für die Anzahl der abgetragenen schwarzen bzw. weißen Steine
- zwei Neuronen für die Anzahl der geschlagenen schwarzen bzw. weißen Steine
- zwei Neuronen für die Kodierung, ob Schwarz oder Weiß am Zug ist
Es gilt für die Darstellung der weißen Steine auf einem Feld (analog auch für die der schwarzen) Folgendes:
- wenn keine Steine vorhanden sind, nehmen alle vier Neuronen den Wert 0 an
- Befindet sich dort ein einzelner Stein, wird lediglich ein einziges Neuron auf 1 gesetzt
- Befinden sich dort zwei Steine, werden zwei Neuronen auf 1 gesetzt. Bei drei Steinen nehmen drei Neuronen den Wert 1 an
- Bei mehr als drei Steinen werden ebenfalls drei Neuronen auf 1 gesetzt. Das vierte Neuron erhält den Wert , wobei der Anzahl an Steinen entspricht
Die allererste Version 0.0 hatte weitaus weniger Input-Neuronen und erhielt als Eingabe nur die nötigsten Informationen über das Spiel. Die neu dazugekommenen Neuronen bildeten sogenannte "handcrafted Feartures", die auch in Neurogammon eingebaut waren und wichtige strategische Informationen kodierten. Somit erhielt TD-Gammon bereits vorher spezifisches Wissen über die aktuelle Stellung.
Demgegenüber besteht die Output-Schicht aus vier Neuronen.[3:2] Ein Neuron gibt die generelle Gewinnchance für Schwarz zurück; ein anderes die Chance für Schwarz auf ein Gammon. Analog werden mit den zwei übrigen Neuronen die Wahrscheinlichkeiten für Weiß ausgegeben. Da die Wahrscheinlichkeit, dass ein Spieler ein Backgammon gewinnt, äußerst gering ist, wird diese Gewinnstufe in der Ausgabeschicht nicht dargestellt. Bezüglich der Anzahl an verdeckten Schichten gibt es bei den verschiedenen Entwicklungsstufen von TD-Gammon Unterschiede. Beispielsweise besitzt Version 1.0 genau eine verdeckte Schicht mit 80 Neuronen. Abb. 2 zeigt vereinfacht den Aufbau dieser Version. Darüber hinaus haben alle Neuronen in der verdeckten Schicht und der Output-Schicht die logistische Funktion als Aktivierungsfunktion.
¶ Training
Gelernt hat das neuronale Netz, indem es gegen sich selbst spielte. Zunächst simulierte es einen Würfelwurf, berechnete dann für alle möglichen Züge jeweils die Gewinnchancen und führte den Zug mit der höchsten Wahrscheinlichkeit aus. Zu Beginn wurden die Weights mit zufälligen kleinen reellen Werten initialisiert[4:1] und nach jedem Zug mittels TD(λ) wie folgt angepasst:[3:3]
Es gilt:
- ist der Weight-Vektor zum Zeitpunkt und beinhaltet alle Weights des neuronalen Netzes.
- ist die Lernrate.
- ist die Ausgabe des -ten Output-Neurons zum Zeitpunkt . Alle Outputs werden unter dem Vektor zusammengefasst.
- ist die Zerfallsrate.
- ist der Gradient von mit Bezug auf (jeder Eintrag des Vektors enthält eine partielle Ableitung nach einem Weight).
- der Diskontierungsfaktor wurde auf 1 gesetzt.[4:2]
Am Ende jedes Spiels gab es dann einen ähnlich dem aufgebauten Reward-Vektor , der das Ergebnis der Partie darstellte und ebenfalls für die Anpassung der Weights verwendet wurde (statt wurde in die Gleichung eingesetzt).
In der früheren Entstehungsphase der Version 0.0 galt und .[5] Im Verlaufe der Entwicklung wurde empirisch festgestellt, dass kleine bis mittelgroße Werte für asymptotisch zu einer gleich guten Spielstärke führten, während bei größeren Werten nahe an 1 die Leistungen schlechter waren. Größtenteils wurde in der Weiterentwicklung auf 0 gesetzt.[6]
¶ Erweiterte Versionen
Nach der Fertigstellung der ersten Version entstanden nach ca. ein bis zwei Jahren die Versionen 2.0 und 2.1, die jeweils zwei verdeckten Schichten hatten. Die erste Schicht suchte zunächst durchschnittlich vier bis fünf geeignete Kandidatenzüge heraus. Anschließend simulierte die zweite Schicht für alle 21 möglichen Würfelkombinationen den jeweils besten Zug des Gegners und aus den gegnerischen Zügen bildete man dann einen gewissen Mittelwert. Schlechtere Züge wurden erst gar nicht mit der zweiten Schicht analysiert.[4:3][6:1]
In den folgenden Jahren wurden die Versionen 3.0 und 3.1 entwickelt, in denen jeweils eine dritte Schicht enthalten ist. Mit der dritten Schicht wurden dann erneut alle 21 Würfelkombinationen simuliert. Am Ende hatte die finale Version 3.1 ca. 50,000 Weights.[6:2] Weitere Unterschiede zwischen den verschiedenen Varianten von TD-Gammon sind in Tabelle 1 zu sehen.[4:4]
| Version | Anzahl verdeckter Neuronen | Anzahl der im Training gespielten Spiele |
|---|---|---|
| TD-Gammon 0.0 | 40 | 300,000 |
| TD-Gammon 1.0 | 80 | 300,000 |
| TD-Gammon 2.0 | 40 | 800,000 |
| TD-Gammon 2.1 | 80 | 1,500,000 |
| TD-Gammon 3.0 | 80 | 1,500,000 |
| TD-Gammon 3.1 | 160 | 6,000,000 |
¶ Resultate
Am Anfang des Trainings wurden willkürliche und zufällige Züge gespielt, sodass die ersten gespielten Partien in der Regel mehrere hundert oder tausend Züge andauerten. Erst nach mehreren tausend Spielen lernte das neuronale Netz elementare Konzepte, wie z.B. die Besetzung eines Feldes mit zwei Steinen oder das Schlagen gegnerischer Steine. Nach ein paar zehntausend Spielen lernte es anspruchsvollere Taktiken.[3:4]
Bezüglich der Spielstärke ähnelte bereits Version 0.0 den zuvor existierenden Backgammon-Programmen, die eher mittelmäßig spielten, wohingegen Version 1.0 alle anderen Programme übertreffen konnte und so stark war, dass es auch auf regionalen Turnieren einen ernsthaften Gegner darstellen konnte. Version 2.1 war dann dem ehemaligen zweifachen Backgammon-Weltmeister Bill Robertie ebenbürtig, der nur mit einem einzigen Punkt Vorsprung knapp den Sieg holen konnte. Laut Robertie machte TD-Gammon minimale technische Fehler gegen Ende des Spiels und bei der Verwendung des Verdoppelungswürfels. Kaum Fehler machte hingegen die nahezu perfekt spielende Version 3.1.[6:3]
Ebenfalls beeinflusste TD-Gammon durch das Spielen unkonventioneller Züge nachhaltig die in der Backgammon-Gemeinschaft üblichen Spielweisen und Taktiken. Sowohl Großmeister als auch Amateure adaptierten diese außergewöhnlichen Züge, auch wenn diese teilweise nicht nachvollziehbar waren.[3:5]
Nach dem unerwarteten Erfolg von TD-Gammon wurde TD-Learning auch auf andere Spiele angewandt, wie z.B. Schach, Go und Othello. Allerdings waren die Implementierungen nicht annähernd so gut und erfolgreich.
¶ Gründe für den Erfolg
Ein entscheidender Faktor für den Durchbruch von TD-Gammon ist u.a. der Würfelwurf. Es lässt sich vermuten, dass die Exploration in den deterministischen Spielen wie Schach und Go aufgrund einer fehlenden Zufallskomponente nicht ausreichend stattfand und nur eine kleine Anzahl von Zuständen besucht wurde, sodass die Programme kaum Fortschritte während des Lernprozesses machen konnten. Hingegen begünstigte in Backgammon das Werfen zweier Würfel deutlich die Exploration und damit auch das Lernen.[3:6]
Desgleichen machte der Würfelwurf die zu approximierende Value-Function glatt und stetig, was so viel bedeutet, dass kleine Änderungen auf dem Spielbrett zu kleinen Änderungen in der Gewinnwahrscheinlichkeit führten. Funktionen mit vielen Unstetigkeitsstellen sind im Vergleich schwieriger zu erlernen.[3:7]
Im Rückblick auf die frühen Lernphasen entdeckte man auch, dass grundlegende Strategien und Konzepte in Backgammon sich als lineare Funktion ausdrücken ließen. Diese lineare Funktion wurde bereits nach ein paar tausend Spielen gelernt und war selbstverständlich besser als ein zufallsgesteuertes Spielen. Mit diesem früh erlernten Wissen konnte TD-Gammon im nachfolgenden Training einfacher und schneller komplexere und nicht-lineare Taktiken lernen.[3:8]
¶ Monte-Carlo Tree Search
2007 wurde der Monte-Carlo Tree Search mit Einsatz von UCT von Van Lishout et al auf Backgammon angewandt.[7] Das entsprechende Programm hieß McGammon, das größtenteils noch unausgereift war und mit vereinfachten Regeln spielte. Auch hatte das Programm keine wirkliche Strategie für die Abtragung und ebenso verfolgte es nur die simple Taktik, alle Steine frühestmöglich in das eigene Heimfeld zu bringen. Dementsprechend konzentrierte man sich auf die Eröffnung einer Partie.
¶ Resultate
In Rahmen einer Performance-Analyse machte McGammon für 200.000 simulierte Spiele jeweils den allerersten Zug. Diese ersten Züge wurden dann mit den von Experten verglichen. Tabelle 2 zeigt für jeden Würfelwurf den Zug, den das Programm in der Regel machte, und den Prozentsatz an professionellen Spielern, die denselben Zug spielen würden.[7:1] Zudem ist jeweils ein alternativer Zug gegeben, der damals von einem gewissen Anteil an Experten gespielt wurde. Die Notation "x/y" bedeutet, dass ein Stein vom x-ten zum y-ten Feld bewegt wurde.
| Würfelwurf | McGammons Zug | % an Experten | von Experten gespielter Zug |
|---|---|---|---|
| 1-2 | 8/6, 24/23 | 0% | 13/11, 24/23 (60.1%) |
| 1-3 | 8/5, 6/5 | 99.9% | 8/5, 6/5 (99.9%) |
| 1-4 | 13/8 | 2.2% | 24/23, 13/9 (74.5%) |
| 1-5 | 24/23, 13/8 | 72.8% | 24/23, 13/8 (72.8%) |
| 1-6 | 13/6 | 0% | 13/7, 8/7 (99.8%) |
| 2-3 | 13/10, 8/6 | 0% | 24/21, 13/11 (51.8%) |
| 2-4 | 13/9, 8/6 | 0% | 8/4, 6/4 (99.8%) |
| 2-5 | 13/8, 8/6 | 0% | 13/11, 13/8 (55.4%) |
| 2-6 | 8/2, 8/6 | 0% | 24/18, 13/11 (81.4%) |
| 3-4 | 13/6 | 0% | 24/20, 13/10 (38.8%) |
| 3-5 | 8/3, 6/3 | 97.8% | 8/3, 6/3 (97.8%) |
| 4-5 | 13/9, 13/8 | 30.5% | 24/20, 13/8 (63.1%) |
| 3-6 | 13/4 | 0.0% | 24/18, 13/10 (76.4%) |
| 4-6 | 8/2, 6/2 | 27.3% | 24/18, 13/9 (37.0%) |
| 5-6 | 13-2 | 0% | 24/13 (99.3%) |
In den meisten Fällen wurden fragwürdige Entscheidungen getroffen. Allerdings spielte das Programm drei Eröffnungen, die auch von sehr vielen Profis gespielt wurden. Ebenfalls fand es zwei Züge mit einer Übereinstimmung von 27-30% und einen einzigen Zug mit 2.2%. Es lässt sich somit feststellen, dass der reine Monte-Carlo Tree Search für Backgammon eher ungeeignet ist. Um eine bessere Leistung zu erzielen, muss der Algorithmus abgewandelt oder mit anderen Verfahren kombiniert werden. Beispielsweise kann die Integrierung menschlichen Wissens in den Simulationen zu einer möglichen Verbesserung führen.
¶ Referenzen
¶ Bildquellen
Abb. 1: In Anlehnung an Ptkfgs. (2007, 1. April). Backgammon notation. https://web.archive.org/web/20230328074003/https://en.wikipedia.org/wiki/Backgammon_notation (Abgerufen am 22.01.2024)
Abb.2 : In Anlehnung an Silver, D. (2020, 5. Mai). Lecture 10 - Applying RL to Games [Notes]. https://omkar-ranadive.github.io/posts/rl-l10-ds (Abgerufen am 17.01.2024)
¶ Literaturverzeichnis
Backgammon. (2023, 29. Dezember). In Wikipedia. https://web.archive.org/web/20231229013308/https://de.wikipedia.org/wiki/Backgammon (Abgerufen am 29.12.2023) ↩︎ ↩︎ ↩︎
Deutscher Backgammon-Verband e.V. 2021. (o.D.). Backgammon - Die Spielregeln. https://bgverband.de/wp-content/uploads/2021/06/dbgv_spielregeln-1.pdf (Abgerufen am 29.12.2023) ↩︎
Tesauro, G. (1995). Temporal difference learning and TD-Gammon. Communications of the ACM, 38(3), 58-68. pdf ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎
Sutton, R. S., & Barto, A. G. (2018). Reinforcement learning: An introduction. MIT press. pdf ↩︎ ↩︎ ↩︎ ↩︎ ↩︎
Tesauro, G. (1991). Practical issues in temporal difference learning. Advances in neural information processing systems, 4. pdf ↩︎
Tesauro, G. (2002). Programming backgammon using self-teaching neural nets. Artificial Intelligence, 134(1-2), 181-199. pdf ↩︎ ↩︎ ↩︎ ↩︎
Van Lishout, F., Chaslot, G., & Uiterwijk, J. W. (2007). Monte-Carlo tree search in backgammon. In Computer Games Workshop. pdf ↩︎ ↩︎