Ein Zahlenspiel zur Erläuterung des Monte Carlo Tree Search Algorithmus

Einordnung des Artikels

• Ausgewählte Kapitel der Mathematik (für Programmierer, Informatiker, Ingenieure und Naturwissenschaftler)
  • Monte Carlo Methoden
    • Ein Zahlenspiel zur Erläuterung des Monte Carlo Tree Search Algorithmus

Einführung

Der Monte Carlo Tree Search Algorithmus (kurz MCTS) ist ein relativ einfacher Algorithmus, um eine Entscheidung aus mehreren Möglichkeiten herbeizuführen. Derartige Entscheidungen treten zum Beispiel in Spielen auf, wo in einer gegebenen Spielsituation der optimale Zug gefunden werden muss.

Dazu testet der Algorithmus mehrere Zufallsentscheidungen und baut mit diesen einen Suchbaum auf. Aus den Ergebnissen der zufälligen Auswahlen werden Wahrscheinlichkeiten für die möglichen Entscheidungen hergeleitet, die bei genügend großen Stichproben der optimalen Entscheidung die größte Wahrscheinlichkeit zuordnen. In einem Spiel würde man diese Wahrscheinlichkeiten interpretieren als diejenige Wahrscheinlichkeit, mit der das Spiel gewonnen wird, wenn der entsprechende Zug ausgeführt wird. Und falls es nur einen Gewinnzug gibt und jeder andere Zug zum Verlust führt (weil der Gegner eine zwingende Gewinnstrategie besitzt), sollte für den Gewinnzug die Gewinnwahrscheinlichkeit nahe bei 1 liegen und für die Verlustzüge nahe bei 0.

Der MTCS-Algorithmus verwendet dabei keinerlei "strategisches Verständnis" für das Spiel, sondern befolgt nur dessen Spielregeln und erkennt, ob das Spiel mit einem Gewinn, einem Unenstschieden oder einer Niederlage beendet wird.

Abbildung 1 zeigt eine typische Situation in einem Spiel:

• Gegeben ist eine Ausgangsposition S (rot).
• Der Spieler, der am Zug ist, hat die Auswahl zwischen den drei Zügen 1, 2, 3 (gelb).

Abbildung 1: Ausgangsposition S und drei mögliche Züge 1, 2, 3.

Das Ziel des MTCS-Algorithmus ist es für die in der Ausgangsposition möglichen Züge Gewinnwahrscheinlichkeiten zu berechnen; dies ist in Abbildung 2 angedeutet.

Abbildung 2: Der MTCS-Algorithmus berechnet Gewinn-Wahrscheinlichkeiten p1, p2, p3 für die möglichen Züge.

Diese Wahrscheinlichkeiten stehen nicht dafür, dass ein Zug ausgewählt wird; daher müssen sie sich nicht zu 1 addieren. Sie bedeuten vielmehr die Wahrscheinlichkeit dafür, dass das Spiel gewonnen wird, wenn der entsprechende Zug ausgeführt wird. In Abbildung 2 ist also folgende Situation dargestellt:

• Der Zug 1 wird mit hoher Wahrscheinlichkeit zum Verlust des Spieles führen.
• Der Zug 2 führt mit hoher Wahrscheinlichkeit zum Gewinn.
• Und bei Zug 3 ist keine Vorhersage über den weiteren Verlauf des Spieles möglich.

Der Algorithmus soll nicht "trocken" erklärt werden. Es wird zunächst ein einfaches Zahlenspiel eingeführt, das man als Variation des Nim-Spiels auffassen kann. Das Spiel ist einerseits so einfach, dass man alle Spielzüge und die Aktionen des MCTS leicht nachvollziehen kann, andererseits kann man die Ausgangssituation so wählen, dass es unmöglich erscheint, eine Entscheidung ohne Strategie-Kenntnisse zu treffen.

Hier wird zunächst nur das Zahlenspiel beschrieben; im nächsten Kapitel wird damit der MCTS-Algorithmus erläutert.

Das Zahlenspiel 3, 5, 11

Die Spielregeln

Für das Zahlenspiel zwischen zwei Spielern A und B gelten folgende Regeln:

1. Zu Beginn wird eine natürliche Zahl n aufgeschrieben (über einen zulässigen Zahlenbereich könnte man sich noch zusätzlich einigen).
2. Die Spieler A und B sind abwechselnd am Zug, wobei A beginnt.
3. Bei jedem Zug muss ein Spieler eine der Zahlen 3, 5, 11 von n abziehen; die Differenz ist das neue n.
4. Erreicht ein Spieler mit seinem Zug das Ergebnis n = 0, so hat er gewonnen. Ist n < 0, so hat der Spieler verloren.

Die folgende Tabelle zeigt einen möglichen Spielverlauf, der mit n = 22 startet; gezeigt ist immer die Zahl, die der Spieler bei seinem Zug erzeugt hat:

Tabelle 1: Ein möglicher Spielverlauf mit dem Anfangswert n = 22.

• Hier hat also A im ersten Zug 5 abgezogen, so dass n = 17 entsteht.
• Anschließend hat B ebenfalls 5 abgezogen, wodurch n = 12 ensteht.
• Und so weiter.
• Im letzten Zug hat A die Zahl n = 1 erzeugt, womit B eine negative Zahl erzeugen muss.

Ist das Zahlenspiel determiniert?

Die einfachen Regeln des Zahlenspiels legen einige Fragen nahe:

1. Kann man aus der Anfangszahl n ablesen, für welchen der beiden Spieler es eine Gewinnstrategie gibt?
2. Bei welchen Zahlen n kann A beziehungsweise B den Sieg erzwingen?
3. Wie lautet die Strategie?

Da das Spiel – abgesehen von der Auswahl der Anfangszahl n – kein zufälliges Element enthält, muss es eine derartige Strategie geben; sie ist nur nicht offensichtlich. In diesem Sinne ist das Spiel determiniert, das heißt wenn beide Spieler die Strategie kennen, ist mit der Anfangszahl n der Ausgang des Spiels vorherbestimmt – Spannung kommt höchstens auf, wenn Fehler gemacht werden.

Die Gewinnstrategie

Der falsche Ansatz

Um die Gewinnstrategie zu ermitteln, ist es naheliegend wie in Abbildung 1 mit der Ausgangssituation S = n zu beginnen und zu überlegen:

1. Wenn A im ersten Zug 3 abzieht, ensteht n - 3.

Jetzt gibt es für B drei Möglichkeiten:

• B kann 3 abziehen, es entsteht n - 6.
• B kann 5 abziehen, es entsteht n - 8.
• B kann 11 abziehen, es entsteht n - 14.

2. Wenn A im ersten Zug 5 abzieht, ensteht n - 5.

Wieder gibt es drei Möglichkeiten:

• B kann 3 abziehen, es entsteht n - 8.
• B kann 5 abziehen, es entsteht n - 10.
• B kann 11 abziehen, es entsteht n - 16.

und so weiter.

Führt man diese Gedanken weiter und versucht daraus eine Strategie abzuleiten, erhält man den MinMax-Algorithmus, der hier nicht besprochen werden soll. Es ist aber sofort klar, dass – bei großen Anfangswerten n – ein riesiger Entscheidungsbaum abgearbeitet werden muss, da man diese Überlegungen bis zu einem Ende des Spiels fortsetzen muss.

Der richtige Ansatz

Viel einfacher ist die umgekehrte Sichtweise – man beginnt beim Ende des Spiels:

Ein Spieler gewinnt, wenn er eine der Zahlen 0, 1, 2 erreicht; denn jetzt ist das Spiel beendet oder der Gegner muss im nächsten Zug eine negative Zahl erzeugen.

Dagegen verliert man das Spiel, wenn man n = 3 erzeugt.

Kann man aus diesen Informationen ableiten:

Welche Zahlen (n > 3) muss man erzeugen, um das Spiel zu gewinnen?

Wenn man die Menge dieser Zahlen kennt, kann man die Strategie ableiten, wie man aus einer gegebenen Zahl n eine dieser Gewinnzahlen erzeugt!

Herleitung der Gewinnstrategie

In in Abbildung 3 ist angedeutet, wie man vorgeht, um die Gewinnstrategie herzuleiten, und zu klären, für welche Anfangszahlen n sich ein Gewinn erzwingen lässt.

Abbildung 3: Der Spielgraph wird ausgehend von den Zahlen 0, 1 und 2 aufgebaut (rot). Der Spieler, der eine dieser Zahlen erzeugen kann, wird das Spiel mit Sicherheit gewinnen. Daher wird man das Spiel verlieren, wenn man eine der blauen Zahl erzeugt. Die blauen Zahlen entstehen dadurch, dass man 3, 5 oder 11 zu den roten Zahlen addiert.

Es ist bereits bekannt, dass ein Spieler gewinnt, wenn er eine der Zahlen 0, 1, 2 erzeugen kann; diese Zahlen sind in Abbildung 3 rot dargestellt. Weiter sind sämtliche Verbindungen zu den möglichen Vorgängern der Zahlen 0, 1, 2 eingezeichnet. Die Vorgänger sind blau dargestellt.

Erzeugt ein Spieler eine dieser blauen Zahlen, wird der das Spiel verlieren – weil der Gegner im nächsten Zug eine der roten Zahlen erzeugen wird. Man kann auf diese Weise alle möglichen Spielzüge vom Ende aus aufzeichnen und die Zahlen in zwei Klassen einteilen:

• Zahlen für die man das Spiel gewinnen wird (rot) und
• Zahlen für die man das Spiel verlieren wird (blau); Letzteres unter der Voraussetzung, dass der Gegner keinen Fehler macht.

Abbildung 4: Die Vorgehensweise aus Abbildung 3 wird fortgeführt und sukzessive der kompette Spielgraph aufgebaut. Hier wird bei 22 abgebrochen, da de Systematik erkennbar ist, welche Zahlen man erzeugen muss um zu gewinnen (rot) und welche Zahlen man vermeiden sollte (blau).

In Abbildung 4 ist diese Überlegung bis zu n = 22 fortgeführt und man erkennt sofort die Regelmäßigkeiten in diesem Spielgraph:

1. Alle roten Zahlen haben als Vorgänger blaue Zahlen.
2. Auf eine rote Zahl folgt immer eine blaue Zahl.
3. Eine blaue Zahl kann sowohl von einer blauen als auch einer roten Zahl abstammen.

Übersetzt man diese Eigenschaften des Spielgraphen in "strategische Überlegungen", so lauten sie:

1. Hat mein Gegner eine blaue Zahl erzeugt, so kann ich stets eine rote Zahl erzeugen.
2. Habe ich eine rote Zahl erzeugt, kann mein Gegner keine rote Zahl erzeugen, er muss eine blaue Zahl erzeugen.
3. Liegt eine blaue Zahl vor, kann man sowohl eine rote Zahl erzeugen (Gewinnstrategie) oder eine blaue Zahl (Fehler: jetzt kann der Gegner das Spiel gewinnen).

Damit kann man die optimale Strategie für das Zahlenspiel formulieren:

Man muss immer versuchen, eine der roten Zahlen zu erzeugen.

Allerdings lässt sich der Gewinn nicht mit jeder Anfangszahl n erzwingen: Liegt zu Beginn eine rote Zahl vor, so muss A eine blaue Zahl erzeugen und B kann den Sieg erzwingen.

Während des Spiels sind natürlich die Zahlen n nicht als "farbige" Zahlen gegeben. Aber ein Blick auf Abbildung 4 zeigt, wie man sie leicht charakterisieren kann:

Die roten Zahlen sind alle natürlichen Zahlen, die bei Division durch 8 den Rest 0, 1 oder 2 ergeben. Die blauen Zahlen sind diejenigen, die den Rest 3, 4, 5, 6, 7 ergeben.

Damit lässt sich auch die Strategie umformulieren und besser an die Spielregeln anpassen:

Welche Zahl muss man subtrahieren, wenn eine Zahl n gegeben ist?

Besitzt n bei Division durch 8 den Rest 0, 1 oder 2, so lässt sich kein Gewinn erzwingen.

Besitzt n den Rest 3, 4, 5, 6, 7 so kann man aus folgender Tabelle ablesen, welche Zahl zu subtrahieren ist:

Tabelle 2: Gewinnstrategie im Zahlenspiel 3, 5, 11. Abhängig von der Restklasse bezüglich der Division durch 8 wird rechts gezeigt, welche Zahl subtrahiert werden muss.

In der Tabelle wird der Rest von n bei Division durch 8 wie üblich mit

n mod 8

bezeichnet; die abzuziehende Zahl ist mit d bezeichnet. Für den Fall, dass die Restklasse 5 vorliegt, gibt es die beiden Möglichkeiten d = 3 und d = 5. Bei den Restklassen 0, 1 und 2 kann man den Gewinn nicht erzwingen; hier ist es höchstens ratsam die 3 abzuziehen, damit das Spiel möglichst lange andauert und der Gegner mehr Gelegenheiten hat Fehler zu machen. Wenn eine 3 der beste Zug ist, kann auch 11 subtrahiert werden – natürlich nur unter der Voraussetzung, dass dadurch keine negative Zahl entsteht (daher ist "oder 11" jeweils in Klammern gesetzt).

Aufgabe:

Oben in der Erklärung der Spielregeln ist ein möglicher Spielverlauf dargestellt. Untersuchen Sie, ob A gewinnt,

• weil er sich an die hier entwickelte Strategie hält oder
• B einen Fehler macht.

R-Skripte

In den R-Skripten wird einerseits die Berechnung ausgeführt, die zu den Abbildungen 3 und 4 geführt hat und andererseits wird gezeigt, wie man das Zahlenspiel simulieren kann. Dazu werden verschiedene Strategien implementiert, die dann gegeneinander antreten können.

Die hier implementierte Strategien sind sehr einfach und machen entweder den besten Zug oder wählen ihn zufällig aus den erlaubten Zügen aus. Im nächsten Kapitel wird dann der Monte-Carlo-Tree-Search-Algorithmus implementiert, der zwar keine strategischen Kenntnisse über das Zahlenspiel besitzt, der aber durch geschickten Einsatz der Statistik bessere Ergebnisse erzielen sollte als die zufällige Strategie.

Berechnung der "Gewinnzahlen"

Möchte man den bei Abbildung 3 vorgestellten Ansatz zur Herleitung der Gewinnstrategie sofort in ein Programm umsetzen, so kann man die Überlegung mit den Restklassen umgehen und ausgehend von den Zahlen 0, 1, 2, 3 die weiteren "roten" und "blauen" Zahlen berechnen. Das folgende Skript zeigt eine einfache Lösung.

In Zeile 1 werden die drei Zahlen festgelegt, die bei jedem Zug von n abgezogen werden können.

In Zeile 2 und 3 werden die Zahlenmengen vorbereitet.

Die Funktion continue() setzt diese Zahlenmengen fort, indem sie für jede Zahl von i = 4 bis i < N testet, ob eine der drei Differenzen i - d in der Menge A liegt (Zeile 14; dazu wird die interne Funktion test() eingesetzt, Zeile 6 bis 10). Je nach Ausgang des Tests wird die Zahl i der Menge A zugeordnet (Zeile 17) oder der Menge B (Zeile 15).

Die Mengen A und B werden zu einer Liste zusammengefasst und von continue() zurückgegeben (Zeile 20).

d <- c(3, 5, 11)
A <- c(0, 1, 2)
B <- 3

continue <- function(a, b, N){
  test <- function(n, set){
    result <- FALSE
    if( any(is.element(n - d, set = set)) ) result <- TRUE
    return(result)
  }
  
  i <- 4
  while(i < N){
    if(test(i, set = a)){
      b <- append(b, i)
    } else {
      a <- append(a, i)
    }
    i <- i + 1
  }
  return(list(A = a, B = b))
}

continue(a = A, b = B, N = 80)
# $A
# [1]  0  1  2  8  9 10 16 17 18 24 25 26 32 33 34 40 41 42 48 49 50 56 57 58 64 65 66 72 73 74
# 
# $B
# [1]  3  4  5  6  7 11 12 13 14 15 19 20 21 22 23 27 28 29 30 31 35 36 37 38 39 43 44 45 46 47 51 52 53 54 55 59 60
# [38] 61 62 63 67 68 69 70 71 75 76 77 78 79

Zeile 23 zeigt den Aufruf der Funktion continue() und die Ausgabe der Mengen A und B.

Aufgaben:

1. Versuchen Sie nachzuvollziehen, wie die Zahlen 4 bis 14 den Mengen A und B zugeordnet werden (siehe Abbildung 3).

2. Im Skript oben wird in Zeile 1 d <- c(3, 5, 11) gesetzt; dies entspricht den Spielregeln, wonach in jedem Zug eine der Zahlen 3, 5 oder 11 abgezogen werden muss.

Zeigen Sie, dass sich die selben Zahlenmengen A und B ergeben, wenn man in Zeile 1 setzt: d <- c(3, 5) .

3. Bei der Herleitung der Gewinnstrategie wurde die Beobachtung aus der letzten Aufgabe nicht diskutiert. Wo hätte man in der Herleitung sehen können, dass die Zahl 11 in den Spielregeln eigentlich überflüssig ist (sie dient mehr dazu, das Spiel nicht zu leicht vorhersehbar zu gestalten).

Hinweis: 11 mod 8 = 3.

4. Untersuchen Sie: Welche Zahlenmengen A und B ergeben sich mit d <- c(3, 5, 8) ?

Wie lautet jetzt die Gewinnstrategie?

Simulation eines Spiels

Im Folgenden werden Funktionen entwickelt, die verschiedene Spielstrategien für das Zahlenspiel simulieren, anschließend treten diese Funktionen gegeneinander an. Die Strategien sind:

1. Der jeweils beste Zug wird auswählt.
2. Der nächste Zug wird zufällig ausgewählt. Nur wenn das Ende des Spiels absehbar ist, wird "intelligent" gespielt: Für n ≤ 11 wird entweder die 0 erzeugt oder 3 subtrahiert.
3. Kombination der beiden Strategien: Mit einer gegebenen Wahrscheinlichkeit p wird der beste Zug ausgewählt, mit Wahrscheinlichkeit 1 - p wird die zufällige Strategie angewendet.

Die Strategien besitzen jeweils als Eingabewert den aktuellen Wert von n, die Kombinations-Strategie zusätzlich die Wahrscheinlichkeit p. Der Ausgabewert ist jeweils das neu berechnete n.

Eine weitere Funktion simuliert ein Spiel. Sie

• erzeugt per Zufall einen Anfangswert für n im Intervall con 20 bis 50,
• ruft die Kontrahenten zum Spiel auf,
• sorgt für eine Aufzeichnung des Spielverlaufs und
• gibt das Ereignis bekannt.

Die Implementierung der Spielstrategien

Im Folgenden werden drei Strategien implementiert, die als Eingabewert jeweils eine Ausgangssituation n besitzen:

1. nextMove.optimal(n) erzeugt stets den besten Zug.
2. nextMove.random(n) wählt aus den erlaubten Zügen zufällig den nächsten Zug aus. Lediglich am Ende (n ≤ 11) wird versucht, keine negative Zahl zu erzeugen.
3. nextMove.prob(n, prob = 0.5) kombiniert die beiden Strategien: Mit Wahrscheinlichkeit prob wird bei jedem Zug die Strategie nextMove.optimal(n) ausgewählt, mit Wahrscheinlichkeit 1 - p die Strategie nextMove.random(n). Weiterer Eingabewert ist die Wahrscheinlichkeit prob.

1. Die optimale Strategie:

nextMove.optimal <- function(n){
  stopifnot(n > 0)
  d.selected <- 3
  # Restklasse von n bestimmen
  r <- n %% 8
  d.selected <- switch(EXPR = r + 1, 3, 3, 3, 3, 3, 3, 5, 5)
  return(n - d.selected)
}

Zentral ist die switch()-Anweisung (Zeile 6): Nachdem für den Eingabewert n die Restklasse bestimmt wurde, wird Tabelle 2 aus dem Theorie-Teil umgesetzt; dabei wird für d.selected der jeweils kleinste Wert gewählt, wenn mehrere Werte zur Auswahl stehen. Rückgabewert ist nicht die abzuziehende Zahl sondern bereits die Differenz n - d.selected .

2. Die Zufallsstrategie:

Solange n > 11 ist, wird eine der Zahlen 3, 5, 11 zufällig (und mit Wahrscheinlichkeit 1/3 ausgewählt). Erst bei n ≤ 11 wird versucht, n = 0 zu erreichen und eine negatives n zu vermeiden

nextMove.random <- function(n){
  stopifnot(n > 0)
  d <- c(3, 5, 11)
  
  if(n < 5){
    d.selected <- 3
  } else {
    if(n == 5 || n == 11){
      d.selected <- n
    } else {
      if(n > 5 || n < 11){
        idx <- sample(x = (1:2), size = 1, replace = TRUE)
        d.selected <- d[idx]
      } else {
        idx <- sample(x = (1:3), size = 1, replace = TRUE)
        d.selected <- d[idx]
      }
    }
  }
  return(n - d.selected)
}

Ist n > 11, wird zufällig ein Zug ausgewählt (Zeile 15).

Ist n = 5 oder n = 11, wird n abgezogen und somit n = 0 erzeugt (Zeile 9).

Für 5 < n < 11 wird eine der Zahlen 3 oder 5 zufällig ausgewählt und abgezogen (Zeile 12).

Ansonsten wird 3 ausgewählt und abgezogen (Zeile 6).

3. Kombinierte Strategie:

Mit "kombinierter" Strategie ist gemeint, dass bei jedem Zug eine der beiden bisher entwickelten Strategien ausgewählt und mit dieser der Zug ausgeführt wird. Dazu gibt es einen weiteren Eingabewert prob, der die Wahrscheinlichkeit dafür angibt, dass die optimale Strategie gewählt wird.

nextMove.prob <- function(n, prob = 0.5){
  stopifnot(n > 0)
  
  nextMove <- list(nextMove.optimal, nextMove.random)
  idx <- 1
  # Auswahl der Strategie
  x <- runif(n = 1)
  if(x > prob) idx <- 2
  return( nextMove[[idx]](n) )
}

Die beiden Strategien nextMove.optimal() und nextMove.random() werden zu einer Liste zusammengefasst (Zeile 4). Dies erleichtert den Zugriff auf die Strategie in Zeile 9 über den Index; der Index wird aus der Gleichverteilung mit runif() ermittelt (Zeile 7 und 8).

Die Implementierung der Simulation

Die Simulation playout() soll ein Spiel zwischen zwei Kontrahenten ausführen, dazu besitzt sie die folgenden Eingabewerte:

• player1 für die Strategie, die den ersten Zug ausführt.
• player2 : der Gegner. Für player1 und player2 können ide oben entwickelten Strategien eingesetzt werden, man kann natürlich auch weitere Strategien implementieren.
• set = (20:50) : Die Menge, aus der zufällig der Anfangswert von n ausgewählt wird; per default wird hier die Menge von 20 bis 50 gewählt.
• Das Argument ... steht für die Wahrscheinlichkeiten, die eventuell an die Strategie nextMove.prob() übergeben werden können.
• Das Argument graph.output = FALSE wird später besprochen; es wird für eine graphische Aufbereitung des Spielverlaufs sorgen.

Der Rückgabewert ist 1 oder 2, je nachdem ob player1 oder player2 gewinnt.

playout <- function(player1, player2, set = (20:50), ..., graph.output = FALSE){
  player <- list(player1, player2)
  idx <- 1    # idx gibt an, welcher Spieler den nächsten Zug macht
  
  n <- sample(x = set, size = 1, replace = TRUE)
  course <- vector(mode = "integer", length = n %/% 3)
  course[1] <- n
  cnt <- 2
  
  while(n > 0){ 
    n <- player[[idx]](n)
    course[cnt] <- n
    cnt <- cnt + 1
    idx <- 3 - idx
  }
  # cat("course in playout: ", course, "\n")
  
  if(graph.output){
    graph_output(course = course)
  }
  
  # Berechnung des Rückgabewertes aus letztem n und idx
  if( is.null(which(course < 0)) ){    # Spiel endet mit n = 0
    return(3 - idx)             # letzter Zug war Gewinnzug, aber idx wurde nochmal gewechselt
  } else {                      # Spiel endet mit negativem n
    return(idx)                 # letzter Zug war Verlustzug, aber idx wurde nochmal gewechselt
  }
}

Zeile 2: Die beiden Strategien werden zu einer Liste zusammengefasst; dadurch kann leicht über den Index idx gesteuert werden, wer einen Zug ausführt.

Zeile 5: Der Anfangswert für n wird erzeugt.

Zeile 6: Der Vektor course soll den Spielverlauf speichern. Da später auch sehr lange Spiele ausgeführt werden, wird der Vektor mit ausreichender Länge erzeugt (der längste Spielverlauf ergibt sich, wenn immer 3 abgezogen wird); später muss er dann geeignet gekürzt werden.

Zeile 7 und 8: Die erste Komponente von course ist der Anfangswert n. Mit cnt werden die Züge gezählt und die weiteren Komponenten von course gesetzt.

Zeile 10 bis 15: In der while-Schleife wird jeweils ein Zug ausgeführt, der Zähler cnt hochgezählt und der Index idx wechselt von 1 nach 2 beziehungsweise umgekehrt. Abgebrochen wird die Schleife, wenn n = 0 oder eine negative Zahl erreicht wird.

Zeile 16: Mit der cat()-Anweisung kann man den Spielverlauf ausgeben.

Zeile 18 bis 20: Für die graphische Aufbereitung des Spielverlaufes wird später eine entsprechende Funktion implementiert.

Zeile 23 bis 27: Aus dem letzten in der while-Schleife gesetzten Wert von course und dem Index idx kann man berechnen, wer das Spiel gewonnen hat. Dies ist zugleich der Rückgabewert von playout().

Ein Aufruf von playout() könnte dann wie folgt aussehen:

playout(player1 = nextMove.prob, player2 = nextMove.prob, prob = 0.1, prob = 0.9)
# course in playout:  50 47 42 39 34 31 26 21 18 15 12 7 2 -1 0 0

Hier werden die beiden kombinierten Strategien mit den Wahrscheinlichkeiten 0.1 und 0.9 gesetzt. In der zweiten Zeile ist ein möglicher Spielverlauf wie er mit cat() ausgegeben wird zu sehen. Man erkennt, dass der Vektor course zu lange gewählt wurde und das Spiel eigentlich mit n = -1 endet.

Um einen Spielverlauf nachzuvollziehen, wird zuerst die Implementierung der graphischen Aufbereitung gezeigt.

Die Implementierung einer graphischen Ausgabe des Spielverlaufs

Der Verlauf des Spiels wird mit Hilfe des Paketes igraph dargestellt; dazu wird zum Vektor course aus der Funktion playout() ein Graph erzeugt und mit Informationen über den Spielverlauf versehen. Einzelheiten zum Paket igraph werden hier nicht erklärt.

Der Graph, der durch den Aufruf von playout() erzeugt wird, ist in Abbildung 5 zu sehen.

Abbildung 5: Graphische Darstellung eines Spieles mit Anfangswert n = 50.

Einige Eigenschaften des Graphen sind erklärungsbedürftig:

1. Der Anfangswert ist oben in der Mitte zu sehen, die Zahlen n, die player1 erzeugt sind immer links, die Zahlen von player2 immer rechts gezeigt.
2. In den Knoten ist die jeweilige Zahl n zu sehen, die Differenzen muss man selbst bilden.
3. Die Farben der Kanten sollen nachvollziehbar machen, ob Gewinnzüge ausgeführt oder Fehler gemacht wurden:
   • Eine rote Kante bedeutet, dass der am Zug befindliche Spieler den Sieg erzwingen kann und den richtigen Zug ausgeführt hat.
   • Eine blaue Kante steht für einen Fehler, das heißt der richtige Zug wurde verpasst und jetzt kann der Gegner das Spiel gewinnen (und dann folgt eine rote Kante).
   • Ist ein Sieg nicht zu erzwingen, ist es eigentlich egal, welcher Zug ausgeführt wird; dies wird mit einer schwarzen Kante signalisiert. Auf eine rote Kante muss daher stets eine schwarze Kante folgen.

In Abbildung 5 erkennt man somit:

• Bei n = 50 kann player1 den Sieg nicht erzwingen und er hat 3 abgezogen (schwarze Kante).
• Jetzt ist n = 47 und player2 kann den Sieg erzwingen, was er auch gemacht hat (5 abziehen, rote Kante).
• Dies setzt sich so fort bis n = 15. Gemäß der Gewinnstrategie müsste player2 jetzt 5 abziehen, er zieht aber 3 ab (Fehler, also blaue Kante).
• Auch player1 könnte bei n = 12 den Sieg erzwingen, macht aber auch einen Fehler (wieder eine blaue Kante).
• Bei n = 7 macht player2 den Gewinnzug (rote Kante) und player1 hat keine Möglichkeit zu gewinnen (schwarze Kante).

Insgesamt sieht man, dass player2 bis auf eine Ausnahme immer den besten Zug gewählt hat; dagegen hatte player1 eine Gewinnchance, hat sie aber nicht genutzt.

Damit die hier beschriebenen Informationen im Graphen sichtbar werden, wird eine Funktion graph_output() implementiert; sie erhält den Spielverlauf als Vektor course als Eingabewert, erzeugt ein graph-Objekt und plottet diesen.

Die Aufgaben der Funktion kann man etwa wie folgt beschreiben:

1. Der Vektor course muss geeignet abgeschnitten werden, da er noch Nullen am Ende haben kann, die im Graphen nicht gezeigt werden sollen. Das Abschneiden erfolgt nach der ersten negativen Zahl beziehungsweise nach der ersten Null.
2. Man muss Knoten für Knoten untersuchen, ob ein Gewinnzug möglich ist und ob dieser erkannt wurde. Entsprechend müssen die Farben für die Kanten gesetzt werden.
3. Die Koordinaten für die Knoten im Graphen müssen berechnet werden.
4. Das graph-Objekt (aus dem Paket igraph) wird erzeugt, konfiguriert und der Plot erzeugt.

Die Implementierung ist im Folgenden zu sehen:

graph_output <- function(course){
  stopifnot(length(course) > 1)    # mind. 2 Knoten zu untersuchen
  
  STATES.WIN <- (3:7)       # Gewinn ist möglich
  STATES.LOSS <- (0:2)    # Gewinn ist eigentlich nicht möglich
  
  colorOfEdge <- function(n1, n2){
    color <- "black"
    
    if( is.element(el = n1 %% 8, set = STATES.WIN) ){    # Gewinn ist möglich
      if( is.element(el = n2 %% 8, set = STATES.LOSS) ){    # Gewinnzug erkannt
        color <- "red"
      } else {
        color <- "blue"    # Gewinn verschenkt
      }
    }
    return(color)
  }
  
  colorsOfEdges <- function(course){
    lgth.course <- length(course)
    clrs <- vector(mode = "character", length = lgth.course - 1)
    for( i in 1: (lgth.course - 1) ){
      clrs[i] <- colorOfEdge(n1 = course[i], n2 = course[i + 1])
    }
    return(clrs)
  }
  
  coordsOfNodes <- function(course){
    lgth.course <- length(course)
    y <- - (1:lgth.course)
    x <- sapply(X = seq_along(course), FUN = function(i){if(i %% 2 == 0) return(0) else return(20)})
    x[1] = 10
    
    return( cbind( x, y) )
  }
  
  # 1. course geeignet abschneiden: nach neg. Zahl bzw. nach erster 0 abschneiden
  lgth <- which(course < 0)

  if( length(lgth) == 0L ){    # Spiel endet mit n = 0
    lgth <- min( which(course == 0L) ) 
  }
  newCourse <- head(course, n = lgth)
  cat("neues cours: ", newCourse, "\n")
  
  # 4. igraph erzeugen und ausgeben
  # 2. und 3. geschehen in den internen Funktionen colorOfEdge(), colorsOfEdges() und coordsOfNodes
  lgth.edges <- 2 * (length(newCourse) - 1 )
  edges <- vector(mode = "character", length = lgth.edges )
  n <- 1
  
  for( i in (1:(lgth - 1)) ){    # hier Länge von newCourse einsetzen, da über newCourse iteriert wird
    edges[n] <- as.character(newCourse[i])
    edges[n+1] <- as.character(newCourse[i+1])
    n <- n + 2
  }
  
  cat("edges: ", edges, "\n")
  g <- graph(edges = edges, directed = FALSE)
  plot(g, vertex.color = "yellow", 
       edge.color = colorsOfEdges(course = newCourse), 
       layout = coordsOfNodes(course = newCourse), 
       edge.width = 3, 
       arrow.mode = 0,
       frame = TRUE)
}

Einige Testläufe

Lässt man die optimale Strategie gegen die zufällige Auswahl spielen, ist klar wer gewinnt. Der entsprechende Aufruf von playout() und die Ausgabe des Spielverlaufs und des Rückgabewertes (1 heißt, dass player1 gewinnt) lauten:

playout(player1 = nextMove.optimal, player2 = nextMove.random, graph.output = TRUE)
# course in playout:  44 41 38 33 30 25 22 17 14 9 6 1 -2 0 
# [1] 1

Der zugehörige Graph ist in Abbildung 6 zu sehen.

Abbildung 6: Graphische Darstellung eines Spieles zwischen der optimalen Strategie und der zufälligen Auswahl.

Lässt man die zufällige Auswahl gegen sich selbst spielen, ist das Ergebnis nicht vorhersehbar. Der Aufruf von playout() und die Ergebnisse lauten:

playout(player1 = nextMove.random, player2 = nextMove.random, graph.output = TRUE)
# course in playout:  45 42 39 36 31 26 21 18 15 12 7 2 -1 0 0 
# [1] 1

Abbildung 7: Graphische Darstellung eines Spieles, wenn beide Spieler immer zufällig entscheiden.

Selbst wenn die zufällige Auswahl gegen eine kombinierte Strategie spielt, ist nicht klar, ob die kombinierte Strategie tatsächlich gewinnen muss. Hier ein Beispiel:

playout(player1 = nextMove.random, player2 = nextMove.prob, prob = 0.6, graph.output = TRUE)
# course in playout:  50 45 42 39 34 31 26 23 18 13 10 7 4 1 -2 0 
# [1] 1

Abbildung 8: Graphische Darstellung eines Spieles zwischen der zufälligen Auswahl und einer kombinierten Strategie.

Hier gewinnt tatsächlich player1, obwohl player2 lange alles richtig macht; erst kurz vor Ende des Spiels unterläuft player2 ein Fehler (bei n = 7 hat er die Wahl, ob er 5 oder 3 abzieht und greift fehl).

Aufgabe: Die Implementierung der optimalen Strategie nextMove.random() wirkt sehr einfach; die eigentliche Schwierigkeit der Implementierung besteht darin, in der switch-Anweisung switch(EXPR = r + 1, 3, 3, 3, 3, 3, 3, 5, 5) die richtigen Werte zu setzen.

Schätzen Sie ab: Wie aufwendig ist es, nextMove.random()zu implementieren, wenn anstelle von d = c(3, 5, 11) die Spielregeln durch drei andere Zahlen für d vorgegeben sind.