Berechnung der Gewinn-Wahrscheinlichkeiten für das Zahlenspiel 3-5-11 und Durchführung von Simulationen mit Zufallszügen

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
    • Berechnung der Gewinn-Wahrscheinlichkeiten für das Zahlenspiel 3-5-11 und Durchführung von Simulationen mit Zufallszügen

Einführung

Ein zentraler Bestandteil des Monte-Carlo-Tree-Search-Algorithmus ist es Simulationen von Spielen auszuführen, wobei sämtliche Züge zufällig ausgewählt werden. Hier werden für das Zahlenspiel 3-5-11 die theoretischen Gewinn-Wahrscheinlichkeiten für derartige Spiele berechnet und Simulationen durchgeführt. Mit den Ergebnissen lässt sich dann besser nachvollziehen, ob und wie der Monte-Carlo-Tree-Search-Algorithmus diejenigen Züge aufspürt, für die eine Gewinn-Strategie existiert.

Berechnung der Gewinn-Wahrscheinlichkeiten beim Zahlenspiel 3-5-11

Aufstellen der Rekursionsformeln

In Lösung von Abzählproblemen durch Rekursion wurde die Methode vorgestellt, wie man die rekursive Struktur eines Baumes einsetzen kann, um Abzählprobleme zu lösen. Diese Methode kann ebenfalls auf die Berechnung der Gewinn-Wahrscheinlichkeiten beim Zahlenspiel 3-5-11 übertragen werden.

Dazu werden zusätzlich zu den Spielregeln folgende Voraussetzungen vereinbart:

• Das Spiel startet mit einer Zahl n > 0.
• Bei jedem Zug wird zufällig eine der Zahlen d = 3, 5, 11 ausgewählt, um die Differenz n - d zu bilden. Dies gilt auch dann, wenn mit dem größten d (oder den beiden großeren d) das Spiel verloren ist.
• Eines der drei möglichen d wird mit einer Wahrscheinlichkeit von jeweils 1/3 ausgewählt.

Die Wahrscheinlichkeit dafür, dass der beim Startwert n am Zug befindliche Spieler das Spiel gewinnen wird, wird mit p(n) bezeichnet. Die Wahrscheinlichkeit das Spiel zu verlieren wird mit q(n) bezeichnet; da es kein Unentschieden geben kann, gilt:

p(n) = 1 - q(n).

Für p(n) und q(n) gelten dann die folgenden Rekursionsformeln (1) und (2) in Abbildung 2, die man mit der in Abbildung 1 angedeuteten Überlegung herleitet.

Abbildung 1: Für den Spieler, der bei gegebenem n am Zug ist, gibt es drei Züge zur Auswahl; die Wahrscheinlichkeit für eine Auswahl beträgt jeweils 1/3. Dass der Anziehende gewinnt, ist gleichbedeutend damit, dass der Nachziehende verliert.

Abbildung 2: Formeln zur rekursiven Berechnung der Gewinn-Wahrscheinlichkeiten p(n).

Der Rekursionsanfang ist nicht ganz selbstverständlich:

Wenn bereits n = 0 vorliegt, wurde dieses n vom Gegner erzeugt; somit ist die Gewinn-Wahrscheinlichkeit jetzt gleich null (siehe Gleichung 3 in Abbildung 2).

Ebenso sind negative n zu verstehen: sie wurden vom Gegner erzeugt und somit ist das Spiel gewonnen. Die entsprechenden Werte von q erhält man, indem man Gewinn und Verlust vertauscht (siehe Gleichung 4 in Abbildung 2).

Sowohl bei n = 0 als auch bei n < 0 ist das Spiel beendet; diese Wahrscheinlichkeiten werden nur verwendet, um mit den Rekursionsformeln aus Gleichung 1 und 2 in Abbildung 2 die eigentlich relevanten p(n) und q(n) für n > 0 zu berechnen.

Setzt man die Rekursionsformeln 1 und 2 aus Abbildung 2 ineinander ein, erhält man eine Rekursionsformel nur für p(n), siehe Gleichung 5 in Abbildung 2. Die rechte Seite dieser Gleichung ist aber nicht eindeutig, wenn das Argument von p negativ ist. Denn

p(n) = 1 für n < 0

gilt nur, wenn das Spiel mit diesem Zug beendet wird, also das vorhergehende n positiv war. Beachtet man diese Einschränkung nicht, würde man mit Gleichung 5 nur Gewinn-Wahrscheinlichkeiten p(n) = 1 für n > 0 berechnen.

Teilfolgen der Gewinn-Wahrscheinlichkeit für gerade und ungerade n

Setzt man die Rekursionsformeln für p(n) und q(n) ineinander ein, erhält man die Rekursionsformel Gleichung 5 in Abbildung 2 allein für p(n) (analog könnte man sie für q(n) aufstellen). An ihr erkennt man, dass sich p(n) für gerades n allein aus Werten von p für ebenfalls gerades n berechnet. Dies gilt entsprechend für ungerades n (und ebenso für q(n)).

Es ist daher sinnvoll die Folge p(n) in zwei Teilfolgen zu zerlegen:

p(2n), n = 0, 1, ... und

p(2n - 1), n = 1, 2, ...

Abbildung 3 zeigt in den zwei Tabellen die ersten Werte der beiden Teilfolgen.

Abbildung 3: Aufspaltung der Gewinn-Wahrscheinlichkeiten p(n) in zwei Teilfolgen für gerade beziehungsweise ungerade n; ebenso für q(n). Die ersten Werte lassen sich durch direktes Einsetzen in die Rekursionsformeln berechnen.

In der folgenden Abbildung 4 werden die Teilfolgen p(2n) (rot) und p(2n - 1) (blau) für Anfangswerte des Spiels bis n = 200 dargestellt.

Abbildung 4: Graphische Darstellung der Gewinn-Wahrscheinlichkeiten p(n) für gerades n (rot) und ungerades n (blau).

Offensichtlich besitzen die beiden Teilfolgen unterschiedliche Grenzwerte.

Weiter kann man versuchen, die Gewinn-Wahrscheinlichkeiten damit in Beziehung zu setzen, ob zum Anfangswert n der Gewinn erzwungen werden kann oder nicht. In Ein Zahlenspiel zur Erläuterung des Monte Carlo Tree Search Algorithmus wurde die Gewinnstrategie besprochen:

Wenn man am Zug ist und eine Zahl erzeugt, die bei Division durch 8 einen Rest 3, 4, 5, 6, oder 7 ergibt, so kann der Gegner das Spiel zwingend gewinnen. Man muss also stets eine Zahl mit Rest 0, 1 oder 2 erzeugen, um den Gewinn zu erzwingen.

Die Argumentation muss man jetzt umdrehen: für welche vorliegende Zahl gibt es eine Gewinnstrategie? Aus den Differenzen n - d

3 - 3 = 0

4 - 3 = 1

5 - 3 = 2

6 - 5 = 2

7 - 5 = 2

erkennt man, wie sich die Zahlen 0, 1, 2 erzeugen lassen.

Dagegen kann aus einem vorliegenden n = 0, 1, 2 mod 8 nicht wieder eine Zahl mit Rest 0, 1, 2 erzeugt werden:

0 - 3 = 5, 0 - 5 = 3, 0 - 11 = 4, jeweils mod 8,

1 - 3 = 6, 1 - 5 = 4, 2 - 11 = 5, jeweils mod 8,

2 - 3 = 7, 2 - 5 = 5, 2 - 11 = 6, jeweils mod 8.

Somit gilt insgesamt:

Liegt als Anfangswert n eine Zahl mit

n mod 8 = 3, 4, 5, 6 oder 7

vor, lässt sich der Gewinn erzwingen; liegt eine Zahl n mit

n mod 8 = 0, 1 oder 2

vor, gibt es keine zwingende Gewinn-Strategie. Jetzt kann der Gegner den Gewinn erzwingen.

Die folgende Abbildung 5 zeigt wiederum die beiden oben besprochenen Teilfolgen und markiert diejenigen Anfangswerte n, für die man den Gewinn erzwingen kann (Kreis) oder nicht erzwingen kann (Kreuz).

Abbildung 5: Zusätzlich zu Abbildung 4 kann man jetzt an der Form der Folgenglieder erkennen, ob sich der Gewinn erzwingen lässt (Kreise) oder nicht (Kreuze).

Simulation von Spielen mit Zufallszügen

Reine Zufallszüge

Die oben berechneten Gewinn-Wahrscheinlichkeiten lassen sich "überprüfen", indem man Spiele ausführen lässt, bei denen alle Züge per Zufall ausgewählt werden und jeder mögliche Zug mit Wahrscheinlichkeit 1/3 gewählt wird. Die Zufallsentscheidung wird auch dann getroffen, wenn für n < 11 eigentlich erkennbar ist, welcher Zug zum sofortigen Verlust führt.

In den folgenden Abbildungen 6 bis 10 werden die theoretischen Gewinn-Wahrscheinlichkeiten wie in Abbildung 5 dargestellt. Zusätzlich sind die relativen Häufigkeiten für die Simulationen eingetragen (Dreiecke). Die Anzahl der Spiele, die zu gegebenem Anfangswert n ausgeführt wurden, sind als Bildüberschrift eingetragen.

Abbildung 6: Simulation mit 1000 Spielen.

Abbildung 7: Simulation mit 300 Spielen.

Abbildung 8: Simulation mit 100 Spielen.

Abbildung 8: Simulation mit 30 Spielen.

Abbildung 9: Simulation mit 10 Spielen.

Man erkennt an den Abbildungen 6 bis 10, dass mit zunehmender Anzahl der Simulationen die relative Häufigkeit des Gewinns immer besser mit der theoretischen Gewinn-Wahrscheinlichkeit übereinstimmt.

Spiele mit verbesserter Gewinnstrategie

Für die folgenden Abbildungen wurden Strategien implementiert, die "bessere" Züge ausführen als bei reinen Zufallsentscheidungen.

In Abbildung 11 spielt der Nachziehende mit der bisher verwendeten Zufallsstrategie. Dagegen spielt der Anziehende mit einer leicht verbesserten Strategie:

• Für n > 12 wird ebenfalls die Zufallsstrategie eingesetzt.
• Für n ≤ 11 werden Fehler in dem Sinn vermieden, dass keine negative Zahl erzeugt wird, wenn es sich vermeiden lässt (so wird zum Beispiel bei n = 10 eine Zufallsentscheidung aus d = 3 und d = 5 getroffen, aber nicht d = 11 zugelassen).
• Falls sich für n ≤ 11 die 0 erzeugen lässt, wird dieser Zug mit Wahrscheinlichkeit 1 ausgewählt.

Abbildung 11 zeigt das Ergebnis einer Simulation mit 300 Spielen für jedes n; die Messpunkte sind wie in den bisherigen Diagrammen gekennzeichnet).

Abbildung 11: Simulation mit 300 Spielen und einer leicht verbesserten Strategie für den Anziehenden (aus dessen Sicht die Gewinn-Wahrscheinlichkeiten berechnet sind).

In Abbildung 12 spielt der Anziehende mit der Zufallsstrategie. Dagegen verwendet der Nachziehende eine Strategie, die aus der Zufallsstrategie und der optimalen Strategie zusammengesetzt ist; dabei heißt "optimale Strategie", dass der optimale Zug ausgeführt wird, wenn es bei dem gegebenen n einen optimalen Zug gibt (siehe Diskussion oben). Gibt es keinen optimalen Zug, wird d = 3 gewählt (so bleibt das Spiel möglichst lange am Laufen und der Gegner hat mehr Möglichkeiten einen Fehler zu machen). "Zusammengesetzt" heißt:

• Mit Wahrscheinlichkeit 0.5 wird jeweils ein Zufallszug ausgeführt.
• Mit Wahrscheinlichkeit 0.5 wird jeweils der Zug gemäß der optimalen Strategie ausgeführt.

Abbildung 12: Simulation mit 300 Spielen und einer deutlich verbesserten Strategie für den Nachziehenden.

R-Skripte

Rekursive Berechnung der Gewinn-Wahrscheinlichkeiten

Die Funktion getPQ() berechnet die Gewinn- und Verlust-Wahrscheinlichkeiten p(n) und q(n) für n = 1, 2, ..., N; die Zahl N ist der einzige Eingabewert der Funktion.

In getPQ() werden zuerst zwei Vektoren vorbereitet, in denen die Werte von p(n) und q(n) abgespeichert werden (Zeile 2 und 3). Diese Vektoren werden am Ende zu einer Liste zusammengefasst und zurückgegeben (Zeile 25).

Der Kern der Funktion ist die rekursive Berechnung der Werte von p(n) und q(n) in einer Schleife (Zeile 21 bis 24). Dabei werden die Werte auf der rechten Seite mit Hilfe der beiden internen Funktionen p.mem() und q.mem() entweder aus dem Rekursionsanfang oder aus bereits berechneten Werten geholt.

getPQ <- function(N = 24){
  p <- vector(mode = "integer", length = N)
  q <- vector(mode = "integer", length = N)
  
  p.mem <- function(n){
    if( n < 0){
      return(1)
    }  else {
      if(identical(n, 0)) return(0) else return(p[n])
    }
  }    # Ende p.mem()
  
  q.mem <- function(n){
    if( n < 0){
      return(0)
    }  else {
      if(identical(n, 0)) return(1) else return(q[n])
    }
  }    # Ende q.mem()
  
  for(i in (1:N)){
    p[i] <- ( q.mem(i - 3) +  q.mem(i - 5) +  q.mem(i - 11) ) / 3
    q[i] <- ( p.mem(i - 3) +  p.mem(i - 5) +  p.mem(i - 11) ) / 3
  }
  return(list(p = p, q = q))
}

# Aufruf:
options(digits = 4)
probs <- getPQ(N = 9)
probs
# $p
# [1] 0.0000 0.0000 0.3333 0.3333 0.6667 0.5556 0.5556 0.3333 0.3704
# 
# $q
# [1] 1.0000 1.0000 0.6667 0.6667 0.3333 0.4444 0.4444 0.6667 0.6296

Zeile 30 zeigt den Aufruf von getPQ(N = 9) zur Berechnung der Werte von p(n) und q(n), die in den Tabellen in Abbildung 3 gezeigt wurden.

Durchführung von Zufallsspielen

Viele der Funktionen, die zum Durchführen der oben besprochenen Simulationen benötigt werden, wurden bereits in den R-Skripten zu Ein Zahlenspiel zur Erläuterung des Monte Carlo Tree Search Algorithmus gezeigt und erläutert. Es werden hier nochmal sämtliche Skripte aufgeführt, die für die Simulationen oben benötigt werden – die Erläuterungen fallen aber kürzer aus und sind gegebenenfalls in Ein Zahlenspiel zur Erläuterung des Monte Carlo Tree Search Algorithmus nachzulesen.

Die verwendeten Strategien

In Ein Zahlenspiel zur Erläuterung des Monte Carlo Tree Search Algorithmus wurde als Zufallsstrategie diejenige Strategie bezeichnet, die bei n ≤ 11 offensichtliche Fehler vermeidet; diese Funktion wurde auch oben diskutiert und eingesetzt (siehe Abbildung 11).

Die entsprechende Implementierung liefert die Funktion nextMove.random() :

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)
}

Die Implementierung der Strategie, die für alle n eine reine Zufallsentscheidung trifft, und die in den Abbildungen 4 bis 10 eingesetzt wurde, wird mit nextMove.random.strict() bezeichnet. Wie man in Zeile 4 erkennt, wird hier immer eine Zufalls-Entscheidung zwischen den drei Zahlen 3, 5, 11 getroffen:

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

Für Spiele, bei denen beide Spieler ihre Züge gemäß nextMove.random.strict() auswählen, gelten die oben berechneten Gewinn-Wahrscheinlichkeiten (siehe Abbildung 2 und 3).

Durchführung eines Spiels

Die Funktion playout() zur Durchführung eines Spiels mit zufällig gewähltem Anfangswert n wurde in Ein Zahlenspiel zur Erläuterung des Monte Carlo Tree Search Algorithmus ausführlich erläutert. Sie besitzt als Eingabewerte die beiden Strategien player1 und player2 , die gegeneinander antreten sollen.

Allerdings ist die Funktion so wie sie dort implementiert wurde ungeeignet; denn der Anfangswert n muss jetzt frei wählbar sein. Man könnte dies auch erreichen, indem man für die Menge set = (20:50) nur einen einzigen Wert vorgibt.

Im folgenden Skript ist eine einfachere Implementierung gezeigt, die es erlaubt:

• entweder einen festen Startwert start vorzugeben
• oder den Startwert zufällig aus der Menge set auszuwählen; Letzteres geschieht, wenn der Startwert start nicht gesetzt wird, also gleich NULL ist.

# player1,2 sind die Strategien
# Rückgabewert: 1 oder 2: der Spieler, der gewinnt

playout <- function(player1, player2,
                    start = NULL,
                    set = (20:50), ..., 
                    graph.output = FALSE, 
                    debug = FALSE, graph.output.debug = FALSE){
  
  player <- list(player1, player2)
  idx <- 1    # idx gibt an, welcher Spieler den nächsten Zug macht
  
  # kein Startwert gegeben -> zufällige Auswahl aus set
  if(is.null(start)){
    n <- sample(x = set, size = 1, replace = TRUE)  # x = (20:50)
  } else {
    n <- start
  }
  
  # cat("n = ", n, "\n")
  course <- vector(mode = "integer", length = (n %/% 3) + 1)
  course[1] <- n
  cnt <- 2
  
  while(n > 0){ 
    n <- player[[idx]](n)    # hier wird eine nextMove() aufgerufen, die ein neues n zurückgibt
    course[cnt] <- n
    cnt <- cnt + 1
    idx <- 3 - idx
    # cat("in while: n: ", n, " | idx: ", idx, "\n")
  }
  
  if(debug){
    cat("course in playout: ", course, "\n")
  }
  
  if(graph.output){
    graph_output(course = course, debug = graph.output.debug)
  }
  
  # Berechnung des Rückgabewertes aus letztem n und idx
  if( identical( length(which(course < 0)), 0L) ){    # Spiel endet mit n = 0
    if(debug) cat("Spiel endet mit 0. Rückgabe playout: ", 3 - idx, "\n")
    return(3 - idx)    # letzter Zug war Gewinnzug, aber idx wurde nochmal gewechselt
  } else {    # Spiel endet mit negativem n
    if(debug) cat("Spiel endet != 0. RÜckgabe playout: ", idx, "\n")
    return(idx)    # letzter Zug war Verlustzug, aber idx wurde nochmal gewechselt
  }
}

Die Funktion graph_output() aus Ein Zahlenspiel zur Erläuterung des Monte Carlo Tree Search Algorithmus wird hier nicht gezeigt und erklärt.

Durchführung von Simulationen

Für die Funktion playout() muss noch ein Wrapper angeboten werden, der dafür sorgt, dass

• die Anzahl der Simulationen vorgegeben werden kann und
• die anderen Eingabewerte an playout() weitergereicht werden.

Um die in Ein Zahlenspiel zur Erläuterung des Monte Carlo Tree Search Algorithmus besprochene kombinierte Strategie einzusetzen, muss man zusätzlich das Argument ... anbieten, um die Wahrscheinlichkeiten für nextMove.prob() einzugeben; diese Erweiterung der Implementierung ist hier nicht gezeigt.

#### n: Anfangswert
#### n.sim: Anzahl der Simulationen
#### Rückgabewert: Anzahl der gewonnenen Spiele

rollout <- function(n = 24, n.sim = 10, 
                    player1 = nextMove.random.strict, 
                    player2 = nextMove.random.strict){
  win <- 0
  for(i in (1:n.sim)){
    result <- playout(player1 = player1, 
                      player2 = player2, 
                      start = n)
    if(result == 1) win <- win + 1
  }
  return(win)
}

Die Abbildungen 4 bis 10 wurden dit Hilfe von rollout() ersellt, indem für die Anfangswerte n = 1, 2, ..., 200 die relativen Häufigkeiten des Gewinns berechnet und zusammen mit den theoretischen Gewinn-Wahrscheinlichkeiten in ein Diagramm eingetragen wurden.