Würfeln bei Schlag den Raab

Der erste Spieler beginnt zu würfeln. Die gewürfelten Augen werden addiert. Würfelt der Spieler eine 6, sind die erreichten Augen verloren und der andere Spieler ist am Zug. Würfelt der Spieler keine 6, kann er sich entscheiden aufzuhören, dann sind die bisher erreichten Augen "gesichert". Hört ein Spieler auf und hat mindestens 50 Punkte, gewinnt er das Spiel. Handelt es sich allerdings um den ersten Spieler, hat der zweite Spieler noch einen Nachzug und kann versuchen gleichzuziehen oder den ersten Spieler zu überholen.

Berechnung


Die vollständige Berechnung einer optimalen Strategie erfolgt in einer (Oracle) Datenbank. Am Ende der Seite ist der Quellcode zu finden. In der folgenden Beschreibung verweisen Implementierungsmarken der Form (I00) auf die Umsetzung im Script.

Vorüberlegung A


Zunächst betrachten wir den Zug eines Spielers. Er startet bei 0 Punkten und ist "aktiv" (A=1). Der Spieler beginnt mit Runde R=1 und würfelt. Bei einer 6 wird er "inaktiv" (A=0) und hat eine erreichte Summe S=0. Die Wahrscheinlichkeiten (P) der Zustände ist noch trivial; jeder Zustand tritt mit der Wahrscheinlichkeit 1/6 auf. Jeder Zustand wird durch ein Tupel (R,S,A) gekennzeichnet (I01):
Select * from V Where R = 1;

   R    S  A          P
---- ---- -- ----------
   1    0  0 0,16666666
   1    1  1 0,16666666
   1    2  1 0,16666666
   1    3  1 0,16666666
   1    4  1 0,16666666
   1    5  1 0,16666666
Danach geht es in Runde 2, bei der der Spieler nur noch dann würfeln kann wenn er am Ende der vorigen Runde noch aktiv war. Die Zustandsverteilung nach Runde 2:
Select * from V Where R = 2;

   R    S  A          P
---- ---- -- ----------
   2    0  0 0,16666666  In Runde 1 eine 6 würfeln (P=1/6), danach inaktiv.
   2    1  0 0,02777777  In Runde 1 eine 1 würfeln (P=1/6), in Runde 2 eine 6 (P=1/6), macht 1/36. Spieler ist inaktiv.
   2    2  0 0,02777777  In Runde 1 eine 2 würfeln (P=1/6), in Runde 2 eine 6 (P=1/6), macht 1/36. Spieler ist inaktiv.
   2    2  1 0,02777777  In Runde 1 eine 2 würfeln (P=1/6), in Runde 2 eine 1 (P=1/6), macht 1/36 und der Spieler ist noch aktiv.
   2    3  0 0,02777777  In Runde 1 eine 3 würfeln (P=1/6), in Runde 2 eine 1 (P=1/6), macht 1/36 und der Spieler ist inaktiv.
   2    3  1 0,05555555  In Runde 1 eine 1 oder 2 würfeln (P=2/6), in Runde 2 die fehlenden Augen zur 3 (P=1/6), macht 2/36 und der Spieler ist aktiv.
   2    4  0 0,02777777  In Runde 1 eine 4 würfeln (P=1/6), in Runde 2 eine 1 (P=1/6), macht 1/36 und der Spieler ist inaktiv.
   2    4  1 0,08333333  In Runde 1 eine 1-3 würfeln (P=3/6), in Runde 2 die fehlenden Augen zur 4 (P=1/6), macht 3/36 und der Spieler ist aktiv.
   2    5  0 0,02777777  In Runde 1 eine 5 würfeln (P=1/6), in Runde 2 eine 1 (P=1/6), macht 1/36 und der Spieler ist inaktiv.
   2    5  1 0,11111111  In Runde 1 eine 1-4 würfeln (P=4/6), in Runde 2 die fehlenden Augen zur 5 (P=1/6), macht 4/36 und der Spieler ist aktiv.
   2    6  1 0,13888888  In Runde 1 eine 1-5 würfeln (P=5/6), in Runde 2 die fehlenden Augen zur 6 (P=1/6), macht 5/36 und der Spieler ist aktiv.
   2    7  1 0,11111111  In Runde 1 eine 2-5 würfeln (P=4/6), in Runde 2 die fehlenden Augen zur 7 (P=1/6), macht 4/36 und der Spieler ist aktiv.
   2    8  1 0,08333333  In Runde 1 eine 3-5 würfeln (P=3/6), in Runde 2 die fehlenden Augen zur 8 (P=1/6), macht 3/36 und der Spieler ist aktiv.
   2    9  1 0,05555555  In Runde 1 eine 4-5 würfeln (P=2/6), in Runde 2 die fehlenden Augen zur 9 (P=1/6), macht 2/36 und der Spieler ist aktiv.
   2   10  1 0,02777777  In Runde 1 eine 5 würfeln (P=1/6) und in Runde 2 eine 5 würfeln (P=1/6), macht 1/36 und der Spieler ist aktiv.
Die Summe der Wahrscheinlichkeiten ist 1. Hier noch die Tabelle für Runde 3:
Select * from V Where R = 3;

   R    S  A          P
---- ---- -- ----------
   3    0  0 0,16666666
   3    1  0 0,02777777
   3    2  0 0,03240740
   3    3  0 0,03703703
   3    3  1 0,00462962
   3    4  0 0,04166666
   3    4  1 0,01388888
   3    5  0 0,04629629  Entweder in Runde 1 eine 5 und danach eine 6 (P=1/6*1/6) oder in Runde 1 eine 1-4, dann die fehlenden Augen zur 5 und dann eine 6 (P=4/6*1/6*1/6), Summe = 10/216
   3    5  1 0,02777777
   3    6  0 0,02314814
   3    6  1 0,04629629
   3    7  0 0,01851851
   3    7  1 0,06944444
   3    8  0 0,01388888
   3    8  1 0,08333333
   3    9  0 0,00925925
   3    9  1 0,08796296
   3   10  0 0,00462962
   3   10  1 0,08333333
   3   11  1 0,06944444
   3   12  1 0,04629629
   3   13  1 0,02777777
   3   14  1 0,01388888
   3   15  1 0,00462962
Gruppiert man diese Tabellen nach S und addiert die Wahrscheinlichkeiten erhält man für das Beispiel R=2 die folgende Tabelle:
Select S, SUM(P) P From V Where R=2 Group by S Order by S;

   S          P
---- ----------
   0 0,16666666
   1 0,02777777
   2 0,05555555
   3 0,08333333
   4 0,11111111
   5 0,13888888
   6 0,13888888
   7 0,11111111
   8 0,08333333
   9 0,05555555
  10 0,02777777
Interpretation: Nach 2 Runden hat der Spieler mit der Wahrscheinlichkeit P eine Summe S erreicht (unabhängig davon ob er noch aktiv ist oder nicht). Summiert man alle Wahrscheinlickeiten der Summen >= S erhält man (I02)
Select * from ER Where R = 2;

   R    S          P      P_SUM
---- ---- ---------- ----------
   2    0 0,16666666 1,00000000
   2    1 0,02777777 0,83333333
   2    2 0,05555555 0,80555555
   2    3 0,08333333 0,75000000
   2    4 0,11111111 0,66666666
   2    5 0,13888888 0,55555555
   2    6 0,13888888 0,41666666
   2    7 0,11111111 0,27777777
   2    8 0,08333333 0,16666666
   2    9 0,05555555 0,08333333
   2   10 0,02777777 0,02777777
Die Spalte P_SUM gibt die Wahrscheinlichkeit wieder, dass der Spieler nach 2 Runden mindestens S Augen erreicht hat. Das gilt insbesondere auch dann wenn ein Spieler die Strategie verfolgt mindestens S Punkte zu erreichen und dann aufhört. Das brauchen wir weiter unten wenn es darum geht, dass der Spieler mit dem Nachzug den ersten Spieler noch einholen muss. In der folgenden Tabelle E (I03) sind diese Wahrscheinlichkeiten für Werte bis S=40 zu finden (es wurden dabei 200 Runden berechnet, was aufgrund der weiter unten folgenden Überlegungen ausreichend ist).
Select * from E Where S <= 50;

   S          P      P_SUM
---- ---------- ----------
   0 0,16666666          1
   1 0,02777777 0,83333333
   2 0,03240740 0,80555555
   3 0,03780864 0,77314814
   4 0,04411008 0,73533950
   5 0,05146176 0,69122942
   6 0,03226094 0,63976766
   7 0,03300813 0,60750671
   8 0,03310826 0,57449857
   9 0,03232486 0,54139031
  10 0,03036066 0,50906544
  11 0,02684381 0,47870478
  12 0,02594095 0,45186097
  13 0,02476309 0,42592001
  14 0,02337223 0,40115692
  15 0,02188012 0,37778469
  16 0,02046670 0,35590456
  17 0,01940385 0,33543786
  18 0,01831433 0,31603400
  19 0,01723954 0,29771967
  20 0,01621742 0,28048013
  21 0,01527364 0,26426270
  22 0,01440813 0,24898906
  23 0,01357551 0,23458093
  24 0,01278570 0,22100541
  25 0,01204340 0,20821970
  26 0,01134773 0,19617630
  27 0,01069341 0,18482857
  28 0,01007429 0,17413515
  29 0,00949075 0,16406086
  30 0,00894160 0,15457010
  31 0,00842463 0,14562849
  32 0,00793745 0,13720386
  33 0,00747812 0,12926641
  34 0,00704542 0,12178828
  35 0,00663787 0,11474286
  36 0,00625391 0,10810498
  37 0,00589213 0,10185106
  38 0,00555124 0,09595893
  39 0,00523009 0,09040769
  40 0,00492754 0,08517759
  41 0,00464249 0,08025004
  42 0,00437391 0,07560755
  43 0,00412088 0,07123363
  44 0,00388248 0,06711275
  45 0,00365788 0,06323026
  46 0,00344627 0,05957237
  47 0,00324690 0,05612609
  48 0,00305907 0,05287918
  49 0,00288210 0,04982011
  50 0,00271537 0,04693800
  ...
  79 0,00048228 0,00833686
  80 0,00045438 0,00785457
  81 0,00042810 0,00740018
Eine Erkenntnis dieser Tabelle: Die Wahrscheinlichkeit, in einem Zug mindestens 32 Augen zu erreichen, beträgt etwa 13,7%.

Vorüberlegung B


Würde man alleine spielen (mit "Sichern" von erreichten Punkten) und versuchen, pro Zug möglichst viele Punkte zu erreichen, so muss man sichern wenn man mindestens 15 Punkte erreicht hat. Hat man bisher S Augen gesammelt, so erreicht man Man sollte weitermachen, wenn (5*S+15)/6 > S ist, das ist äquivalent zu 5*S+15 > 6*S und das zu S < 15.
Allerdings spielt man das Spiel nicht alleine, und das ändert die optimale Strategie.

Zustände im 2-Personen-Spiel


Um das Spiel vollständig zu erfassen werden alle Zustände betrachtet, in die man im Verlauf des Spiels gelangen kann. Die Zustände werden definiert aus der Sicht des Spielers, der gerade entscheiden muss ob er würfelt oder aufhört. Als Variablen definieren wir Durch diese vier Werte ist der aktuelle Zustand des Spielers, der vor einer Entscheidung steht, vollständig beschrieben. Für jeden Zustand werden weitere Attribute definiert: Hier einige Beispiele:
       ID TS  MSP  MAP  TSP        S0        S3
--------- -- ---- ---- ---- --------- ---------
        1  0    0    0    0   1000001       301   Der Startzustand
      301  0    0    3    0   1000004       601   Der Startspieler hat eine 3 gewürfelt
  1000004  1    0    0    3     30001   1000304   Nach dem Würfeln einer 3 hat der Startspieler gesichert
Zunächst werden Zustände betrachtet, in denen einer der Spieler gewonnen hat: Auch dafür einige Beispiele:
       ID TS  MSP  MAP  TSP          P
--------- -- ---- ---- ---- ----------
  1450741  1   45    7   40          1  Der andere Spieler hatte als Startspieler bei 40 Punkten gesichert, wie haben bei 45 begonnen und 7 gesammelt => Gewonnen.
   450054  0   45    0   53          0  Wir sind der Startspieler, der andere hat 53 Punkte und damit gewonnen (wir haben keinen Nachzug).
   520048  0   52    0   47          1  Wir sind der Startspieler und hatten 52 Punkte, der andere hat bei 47 aufgehört (unsinnig). Wir gewinnen.
  1490446  1   49    4   45          1
Der Zustand ID=450054 ist dabei nicht erreichbar, weil bereits der Vorgängerzustand (z.B. ID=1490446) als Spielende markiert ist.
Für die "Folgezustände" S1 bis S6 erfolgt in bestimmten Situationen eine Reduktion (I11). Man kann sich überlegen, dass es im Fall von MSP>=50 und TSP>=50 nicht darauf ankommt, wie hoch die Spieler jenseits der 50 liegen, so lange ihr Abstand gleich ist. Ein solcher Zustand ist äquivalent zum Zustand mit MSP2 = MSP-MIN(50-MSP,50-TSP) und TSP2 = TSP-MIN(50-MSP,50-TSP). Die Siegeswahrscheinlichkeit der beiden Zustände sind gleich.
       ID TS  MSP  MAP  TSP        S2
--------- -- ---- ---- ---- ---------
   520353  0   52    3   52    500551  Wenn wir nun eine 2 würfeln, kommen wir eigentlich in den Zustand 520553
   520553  0   52    5   52    500751  Dieser Zustand ist aber äquivalent zur folgenden Zeile
   500551  0   50    5   50    500751  .. und dies ist dann auch der Zustand, der in der ersten Zeile als S2 verdrahtet ist.
Theoretisch kann ein Spiel in unendlich viele Zustände geraten: Wenn der vorlegende Spieler immer eine 5 würfelt und dann aufhört und der nachziehende Spieler ebenfalls immer eine 5 würfelt und aufhört werden unendlich viele Zustände erreicht. Durch die obige Zustandsreduktion wird das vermieden. Zunächst werden in die Zustandstabelle auch solche Zustände eingefügt, die in einem Spiel nicht erreichbar sind.

Zwischenüberlegung


Wir betrachten die Situation, in der der andere Spieler als Startspieler vorgelegt hat und mindestens 50 Punkte gesichert hat. Wir müssen nun würfeln, bis wir mindestens die Punktzahl des anderen erreicht haben. Was machen wir, wenn wir die Punktzahl des anderen genau treffen? Sollte man dann sichern oder noch einmal würfeln, um mit einer Wahrscheinlichkeit von 5/6 das Match für sich zu entscheiden? Dazu betrachten wir den Zustand, den wir erreichen, wenn wir bei Gleichstand aufhören. Dann legt der andere vor, und wir müssen mindestens dessen Punktzahl erreichen um im Spiel zu bleiben. Wir gehen exemplarisch davon aus, dass der andere Spieler grundsätzlich 2 mal würfelt und dann sichert - wenn er nicht vorher schon eine 6 gewürfelt hat. Mit dieser Strategie hat der andere Spieler nach seinem Zug die folgende Verteilung
Select A, S, SUM(P) P From V Where R = 2 Group by A, S Order by A, S;
 
 A    S          P
-- ---- ----------
 0    0 0,16666666
 0    1 0,02777777
 0    2 0,02777777
 0    3 0,02777777
 0    4 0,02777777
 0    5 0,02777777
 1    2 0,02777777
 1    3 0,05555555
 1    4 0,08333333
 1    5 0,11111111
 1    6 0,13888888
 1    7 0,11111111
 1    8 0,08333333
 1    9 0,05555555
 1   10 0,02777777
Als nachziehender Spieler müssen wir die vorgelegte Punktzahl erreichen (wenn A=0, dann hat der andere Spieler eine 6 gewürfelt und hat keine Punkte vorgelegt, die Wahrscheinlichkeit gleichzuziehen ist dann 1). Die Wahrscheinlichkeiten mindestens gleichzuziehen sind in der folgenden Tabelle in der Spalte P2 ausgewiesen. Die Summe der Produkte E = P * P2 gibt den Erwartungswert an, dass der nachziehende Spieler bei der genannten Strategie des vorlegenden Spielers mindestens ausgleicht.
With H1 As ( Select A, S, SUM(P) P From V Where R = 2 Group by A, S Order by A, S ),
     H2 As ( Select H1.A, H1.S, H1.P, E.P_SUM P2, H1.P * E.P_SUM E From H1, E Where E.S = H1.A * H1.S ),
     H3 As ( Select H2.A, H2.S, H2.P, H2.P2, SUM(H2.E) From H2 Group by ROLLUP(A,S,P,P2) )
Select * From H3 Where P2 is Not NULL Or A is NULL;
 
 A    S          P         P2  SUM(H2.E)
-- ---- ---------- ---------- ----------
 0    0 0,16666666          1 0,16666666
 0    1 0,02777777          1 0,02777777
 0    2 0,02777777          1 0,02777777
 0    3 0,02777777          1 0,02777777
 0    4 0,02777777          1 0,02777777
 0    5 0,02777777          1 0,02777777
 1    2 0,02777777 0,80555555 0,02237654
 1    3 0,05555555 0,77314814 0,04295267
 1    4 0,08333333 0,73533950 0,06127829
 1    5 0,11111111 0,69122942 0,07680326
 1    6 0,13888888 0,63976766 0,08885661
 1    7 0,11111111 0,60750671 0,06750074
 1    8 0,08333333 0,57449857 0,04787488
 1    9 0,05555555 0,54139031 0,03007723
 1   10 0,02777777 0,50906544 0,01414070
                              0,75741652

Das Ziel dieser Überlegung: Die Wahrscheinlichkeit, dass der nachziehende Spieler gewinnt, ist nicht größer als 76%. Zum einen hat der nachziehende Spieler ja noch nicht gewonnen, wenn er nur gleichzieht, und außerdem gibt es für den vorlegenden Spieler vielleicht noch eine bessere Strategie. Hier interessiert aber nur die Abschätzung der Siegeswahrscheinlichkeit für den nachziehenden Spieler nach oben. Wenn der nachziehende Spieler entscheiden muss, ob er bei Gleichstand noch einmal würfelt (um mit einer Wahrscheinlichkeit von 5/6 = 83% das Match zu gewinnen) oder aufhört (um in die obige Situation zu gelangen, in der er mit einer maximalen Wahrscheinlichkeit von 76% gewinnt) dann entscheidet er sich grundsätzlich dafür, noch einmal zu würfeln.

Aufhören im Zielbereich

Der Zustandsraum ist auch mit den obigen Überlegungen immer noch unendlich: Der vorlegende Spieler kann jenseits der 50 Punkte - solange er keine 6 würfelt - beliebig lange weiter würfeln. Intuitiv ist klar, dass das ab einem bestimmten Vorsprung keinen Sinn mehr macht, weil die Gefahr eine 6 zu würfeln zu groß ist und die Wahrscheinlichkeit, dass der nachlegende Spieler den Vorsprung noch aufholt ausreichend klein.
Doch wie hoch muss der Vorsprung sein, damit Aufhören die bessere Entscheidung ist? Wir wissen (in der Situation TSP<50, MSP<50, TS=0)

Beschränkung des Zustandsraumes

Da 80 Punkte Vorsprung ausreichen, braucht man den Zustandsraum nur bis 50 + 80 = 130 zu berechnen. Wir sind zunächst etwas großzügiger und betrachten alle Zustände bis 199.

Es erfolgt nun eine weitere Kategorisierung von Zuständen:

Erzwungene Entscheidungen


Mit der Zwischenüberlegung können wir weitere Zustände abschließend berechnen: In den Fällen, in denen TS=1 und TSP>=50 ist, würfelt der Spieler weiter bis er gewonnen hat. Dafür braucht er mindestens TSP-MSP-MAP+1 Augen und die Wahrscheinlichkeit das zu erreichen kann aus der Tabelle aus Vorüberlegung A entnommen werden (I09).
       ID TS  MSP  MAP  TSP          P
--------- -- ---- ---- ---- ----------
  1490053  1   49    0   52 0,73533950  Der andere Spieler hat 52 Punkte vorgelegt, wir müssen 4 Punkte holen um zu gewinnen.
Hier bietet sich die Möglichkeit, die im folgenden Abschnitt implementierte Iteration zu überprüfen: Die ermittelte Wahrscheinlichkeit wird nicht verwendet, sondern in einem separaten Feld PX gespeichert und mit dem Ergebnis der Iteration verglichen.

Allgemeines Vorgehen


Wir nehmen an, dass es eine "optimale Strategie" gibt: Für jeden unserer Zustände gibt es eine Entscheidung "Stoppen" oder "Weitermachen", so dass die Wahrscheinlichkeit, "P" das Match zu gewinnen, maximiert wird (unter der Annahme dass der andere Spieler ebenfalls die optimale Strategie verfolgt). Dazu werden für jeden Zustand bestimmt. Die optimale Entscheidung ist die mit der höheren Siegeswahrscheinlichkeit. Für Zustände die als Spielende markiert sind gibt es keine Entscheidung, die Siegeswahrscheinlichkeit P ist 0 oder 1. Für mache Zustände kennen wir aus den obigen Betrachtung bereits die optimale Entscheidung. Für alle anderen Zustände anderen gilt: Die obigen Definitionen bilden ein Gleichungssystem, das es zu lösen gilt. Wir lösen das allerdings nicht deterministisch, sondern führen eine Iteration durch und stellen fest dass das System gegen einen Fixpunkt konvergiert, in dem das Gleichungssystem erfüllt ist. Von diesem nehmen wir an dass er die optimale Strategie repräsentiert.

Auswertung


Ein paar Aussagen zur optimalen Strategie: Der Startspieler .. Die komplette Ergebnisliste findet sich hier.
Der SQL-Quellcode findet sich hier (nicht optimal, rechnet ein paar Stunden).
Stefan-Taube.de