Über das perfekte Kniffel-Spiel

10. Juli 2014: Ich habe das Program erweitert auf eine Zweispielerstrategie. Nun in englisch.

16. Dezember 2011: Neben der klassischen HTML-Version gibt es eine Ajax-Version mit etwas anderer Funktionalität.

15. September 2004: Einzelabfragen: Ich wurde gefragt, wie wahrscheinlich es ist, mit drei Würfen einen Kniffel zu würfeln. Dazu macht man eine Einzelabfrage des Spielzustands, bei dem alle Felder bis auf den Kniffel gestrichen sind. Man erhält einen Erwartungswert von 2,301432. Dividiert man diesen durch die 50 Punkte, die man für den Kniffel bekommt, erhält man 4,60%. Das ist die gesuchte Wahrscheinlichkeit. Die Wahrscheinlichkeit für die Große Straße ist übrigens 26,11%. Zur Einzelabfrage muss man (unter Windows ein DOS-Fenster öffnen und dort) folgendes Kommando eingeben:
kniffel 0 0 0 0 0 0 0 0 0 0 0 - 0 0

16. April 2004: Die Zeiten ändern sich. Die erste Version des Programms brauchte damals eine ganze Nacht zur Berechnung der Erwartungswerte. Auf meinem aktuellen Rechner dauert es noch 3 Minuten.

26. August 2003: Nachdem mehrfach die "Optimalität" des Verfahrens in Frage gestellt wurde, hier eine Anmerkung. Das Verfahren optimiert nach dem Erwartungswert, das heißt, die durchschnittlich erreichte Punktzahl ist optimal. Im Spiel mit Gegnern ist diese Strategie nicht unbedingt optimal, da hier das Ziel nur darin besteht, mehr Punkte als die Gegner zu erreichen. Liege ich hinten muss ich riskanter spielen. Habe ich einen Vorsprung kann ich auf Sicherheit spielen. Solche Strategien werden hier nicht berücksichtigt.

17. Januar 2002: Das Programm läuft nun auch unter Windows.

Liebe Kniffelspieler,

habt Ihr euch schon mal Gedanken gemacht, wieviele Punkte man im Durchschnitt erreichen kann? Oder welche Würfel man beim Wurf 11245 auf dem Tisch liegen lässt? Die Antwort auf die erste Frage lautet 245,9 Punkte. Die zweite Frage ist schwerer zu beantworten. Sind noch alle Felder frei, so lässt der perfekte Spieler nach dem ersten Wurf 245 liegen. Würfelt er nochmal das gleiche, bevorzugt er diesmal die beiden Einser?

Warum?

Diese Frage kann nur der Rechenknecht beantworten. Wie's geht kommt jetzt. Oder willst Du erstmal die Webversion ausprobieren? Oder den Artikel darüber im Spektrum der Wissenschaft lesen?


Die Regeln

Kniffel wird mit 5 Würfeln gespielt. Ein Spiel geht über 13 Runden. Pro Runde darf jeder Spieler 3 mal würfeln. Nach jedem Wurf kann er entscheiden, welche Würfel er liegen lässt und mit welchen er weiter würfelt. Nach dem dritten Wurf muss er den Wurf in eines der folgenden Felder eintragen lassen. Wenn alle Felder voll sind wird zusammengezählt. Wer die meisten Punkte hat ist Sieger. Wird ein Kniffel gewürfelt, wenn das Feld bereits voll ist, muss er anderweitig eingetragen werden, beispielsweise beim Full-House oder 4er-Pasch.

Spieler 1 Spieler 2 Punktberechnung
1 1er 1 0 Summe der Einsen
2 2er 8 6 Summe der Zweier
3 3er 9 9 Summe der Dreier
4 4er 16 12 Summe der Vierer
5 5er 20 15 Summe der Fünfer
6 6er 18 18 Summe der Sechser
Bonus 35 0 35 falls Summe bis hier >= 63, 0 sonst
7 3er-Pasch 21 26 Summe aller Würfel falls mindestens 3 gleiche, 0 sonst
8 4er-Pasch 0 26 Summe aller Würfel falls mindestens 4 gleiche, 0 sonst
9 Full-House 25 0 25 falls Wurf der Form xxxyy, 0 sonst
10 Kleine Strasse 30 30 30 falls 4 Würfel in Folge, 0 sonst
11 Grosse Strasse 0 40 40 falls 5 Würfel in Folge, 0 sonst
12 Kniffel 0 50 50 falls alle Würfel gleich, 0 sonst
13 Chance 24 17 Summe aller Würfel
Summe 207 249 Spieler 2 gewinnt

Gewinnmaximierung

Kniffel ist eine Kombination von Glückspiel und Können. Beim Kniffelspiel handelt es sich um eine Folge von Zustandsübergängen. Startzustand ist der leere Zettel, Endzustand der Volle. Dazwischen gibt es zufällige und berechenbare Übergänge. Erstere bestehen aus dem Würfeln. Berechenbar sind die Entscheidungen die der Spieler trifft, also welche Würfel er liegen lässt und mit welchen er weiter würfelt. Außerdem muss er entscheiden in welches Feld er einen Wurf einträgt.

Zum Verständnis der folgenden mathematischen Betrachtungen sind zwei Begriffe wichtig:

Wahrscheinlichkeit und Erwartungswert

Die Wahrscheinlichkeit p ist ein Wert zwischen 0 und 1. Sie gibt an, in wieviel Prozent der Fälle ein Ereignis durchschnittlich eintritt. Beispiel: Die Wahrscheinlichkeit für das Ereignis: "Ich würfle eine sechs" ist p=1/6.

Werden den Ereignissen Größen zugeordnet, gibt es einen Erwartungswert E, der gewichtete Mittelwert über diesen Größen. Er berechnet sich aus der Summe der Größen aller Ereignisse gewichtet mit deren Wahrscheinlichkeit. Beispiel: Beim Würfeln erreicht man durchschnittlich E= 1/6 1 + 1/6 2 +1/6 3 + 1/6 4 + 1/6 5 + 1/6 6 = 3,5 Punkte


Ein einfaches Beispiel

Zum leichteren Verständnis der Berechnungen rechne ich ein Beispiel eines vereinfachten Spiels komplett durch. Man nehme 2 dreiseitige "Würfel". Wie beim Kniffel darf man dreimal würfeln und Würfe liegen lassen. Das Produkt der beiden Würfel, multipliziert mit 10, soll nach dem dritten Wurf möglichst hoch sein. Welche Strategie ist die beste? Wieviele Punkte macht man durchschnittlich bei einem Spiel?

Die Zustandsübergänge

Das Spiel geht über mehrere Zustände. Die Zustandsübergänge sind zum Teil zufällig (probabilistisch p) und zum Teil berechenbar (deterministisch d). In jedem Spielzustand gibt es einen Erwartungswert. Dieser lässt sich von vom Spielende zurück zum Anfang, hier von rechts nach links, berechnen. Ist das Spiel vorbei, ist der Erwartungswert die erreichte Punktzahl. Die Erwartungswerte vor dem letzten Wurf, also nach der zweiten Auswahl der Würfel, die auf dem Tisch liegen bleiben, berechnen sich durch die Wahrscheinlichkeiten der Zustandsübergänge. Die deterministischen Entscheidungen, also welche Würfel ich liegen lasse, werden einfach nach dem höchsten Erwartungswert gefällt. Auf diese Weise kann ich Schritt für Schritt alle Zustände von rechts nach links berechnen und komme zu einem Erwartungswert vor dem Spiel (a priori) von 65,31 Punkten.

Die folgenden drei Tabellen zeigen die Erwartungswerte jedes Zustands E, die Wahrscheinlichkeiten der gewürfelten Zustandsübergänge P und die zulässigen Auswahlmöglichkeiten D. Nebenbei: Betrachtet man die Spalten von E als Vektoren und die Tabelle P als Matrix, so berechnen sich probabilistischen Übergänge E(Auswahl 2) = P * E(Wurf 3), usw. Die deterministischen Übergänge erfolgen jeweils nach dem Maximum der zulässigen Übergänge.

Die Erwartungswerte E

EA prioriWurf 1Auswahl1Wurf 2Auswahl2Wurf 3
65,31 54,44 40
46,67 20
46,67 40
70 60
54,44 40 40 10 10
54,44 40 40 20 20
70 60 60 30 30
54,44 40 40 40 40
70 60 60 60 60
90 90 90 90 90

Die Übergangsmatrix beim Würfeln P

p
1/92/92/91/92/91/9
1/31/31/3000
01/301/31/30
001/301/31/3
100000
010000
001000
000100
000010
000001

Die möglichen Übergänge D

d
1100100000
1110010000
1101001000
1010000100
1011000010
1001000001

Übertragung auf das Kniffelspiel

Das echte Kniffelspiel wird genauso behandelt wie die vorgestellte Variante. Allerdings ist es wesentlich komplexer und enthält zusätzliche Zustände, nämlich die aktuellen Spielstände, sprich welche Felder frei sind und wieviele Punkte bereits erreicht sind. Maximiert werden soll die Restgewinnerwartung, also die Punkte, die im weiteren Verlauf noch erwirtschaftet werden.

Das vorhergende, vereinfachte Beispiel entspricht einem Übergang eines bestimmten Spielzustandes in einen Folgezustand. Ist nur noch ein Feld frei, beispielsweise die grosse Straße, so kann man die richtige Vorgehensweise genau bestimmen. Will man die Erwartungswerte aller Spielzustände berechnen, so muss man auch hier vom Spielende zum Anfang zurückrechnen. Anstelle der festen Erwartungswerte im Beispiel tritt dann jeweils der Erwartungswert des besten Folgezustandes plus die Punkte die beim Eintrag in das jeweilige Feld erzielt werden.

Spielstände gibt es natürlich sehr viele. Das 1er-Feld kann frei sein oder mit 0, 1, 2, 3, 4 oder 5 belegt. Beim 2er-Feld gibt es die Möglichkeiten: frei, 0, 2, 4, 6, 8 10, und so weiter. Würde man alle diese Zustände betrachten käme man auf über 100 Millarden Zustände. Alle zu berechnen ist selbst für moderne Grossrechner viel. Es ist auch nicht nötig.

Für die perfekte Strategie ist entscheidend, welche der 13 Felder belegt und welche frei sind. Ob der Kniffel gewürfelt wurde oder gestrichen ist unerheblich. Es gibt daher 2^13 Möglichkeiten. Desweiteren ist es für das Erreichen des Bonus entscheidend, wieviel Punkte im oberen Teil bereits geschrieben wurden. Ist die Schwelle 63 bereits erreicht ist es für das weitere Spiel wiederum unerheblich, um wieviel man die Schwelle überschritten hat. Daher muss man weitere 64 Zustände unterscheiden: Summe oben = 0, 1, 2, ... 61, 62 und >=63. Insgesamt kommt man also auf 2^13 * 64 = 524288 Zustände.

Die Zustände werden mit einer 19-Bit-Zahl (In der folgenden Tabelle dezimal) kodiert: Die ersten 13 Bit geben an ob die Felder 1er, 2er, ..., Chance belegt sind. Die hinteren 6 Bit geben die bereits erreichte Summe im oberen Teil an. Ist sie größer als 63 wird sie auf 63 gesetzt.

Die folgende Tabelle zeigt Beispiele für die Kodierung der Zustände und die Restgewinnerwartung. Der zu erwartende Restgewinn sinkt natürlich mit zunehmend ausgefüllten Felder. Es gibt auch unerreichbare Zustände wie 1 oder 2. Deren Restgewinnerwartung wird zwar berechnet, ist aber unerheblich. Sie ist mit "?" gekennzeichnet.

0 1 2 64 65 134 2072 128679 524286 524287
Binaer 0000000000000
000000
0000000000000
000001
0000000000000
000010
0000000000001
000000
0000000000001
000001
0000000000010
000110
0000000100000
011000
0011111011010
100111
1111111111111
111110
1111111111111
111111
1er       x x       x x
2er           x   x x x
3er                 x x
4er               x x x
5er               x x x
6er             x   x x
3er-Pasch               x x x
4er-Pasch               x x x
Full-House               x x x
Kleine Strasse               x x x
Grosse Strasse               x x x
Kniffel                 x x
Chance                 x x
Summe oben =0 =1 =2 =0 =1 =6 =24 =39 =62 >=63
Restgewinn 245,90 ? ? 229,98 231,71 234,75 237,09 88,45 0 35

Das Programm

Die genannten Berechnungen wurden in c implementiert. Das Programm läuft unter UNIX und Linux. Installation erfolgt durch Speichern der Dateien kniffel.c und kniffel.h. Diese müssen, beispielsweise mit "cc -o kniffel kniffel.c" kompiliert werden. Aufgerufen wird das Spielprogramm mit "kniffel".

Die Erwartungswerte des Restgewinns jedes Spielstands wird beim ersten Aufruf berechnet und in der Datei "restgewinn" gespeichert. Daher dauert der erste Programmaufruf etwa eine halbe Stunde, bei älteren Rechnern mehrere Stunden. Jeder Erwartungswert wird in einem "double" also 8 Byte gespeichert. Die Datei "restgewinn" ist daher 524288 * 8 = 4194304 Byte = 4MB groß. Bei weiteren Programmaufrufen muss nur die Datei eingelesen werden.

"Handicap" gibt an, wieviele Punkte man im laufenden Spiel bereits durch falschen Entscheidungen verschenkt hat.

Die Oberfläche sieht aus, wie Oberflächen von guten Programmen halt aussehen. Wer Lust hat möge eine Klickibunti-Version für Windows oder Mac schreiben.

 ----------------------
| 1 Einser             |
| 2 Zweier           8 |
| 3 Dreier             |
| 4 Vierer          16 |
| 5 Fuenfer         15 |
| 6 Sechser            |
|----------------------|
|   Bonus            0 |
|----------------------|
| 7 3er-Pasch       15 |
| 8 4er-Pasch        9 |
| 9 FullHouse       25 |
|10 Kleine Strasse  30 |
|11 Grosse Strasse  40 |
|12 Kniffel            |
|13 Chance             |
|----------------------|
|   Summe        158   |
|   Erwartung    246.5 |
 ----------------------
1. Wurf: 11456 Auswahl: 11
Beste Auswahl:    6              Handicap: 4.709
2. Wurf: 11336 Auswahl: 33
Beste Auswahl:    33             Handicap: 4.709
3. Wurf: 13345 Wohin:

Einzelabfragen für eine Spielsituation sind ebenfalls möglich:

i81s1%  kniffel - 8 - 16 15 - 15 9 25 30 40 - - 3 13345
 ----------------------                         ^  Wurf
| 1 Einser             |               Wievielter Wurf
| 2 Zweier           8 |
| 3 Dreier             |
| 4 Vierer          16 |
| 5 Fuenfer         15 |
| 6 Sechser            |
|----------------------|
|   Bonus            0 |
|----------------------|
| 7 3er-Pasch       15 |
| 8 4er-Pasch        9 |
| 9 FullHouse       25 |
|10 Kleine Strasse  30 |
|11 Grosse Strasse  40 |
|12 Kniffel            |
|13 Chance             |
|----------------------|
|   Summe        158   |
|   Erwartung    246.5 |
 ----------------------
3. Wurf: 13345:
Bester Eintrag: Dreier
Punkterwartung: 239.713069
i81s1% 

Ungeduldige oder Kommandozeilenunkundige können auch mal die Webversion ausprobieren.


Eine andere Version von Tom Verhoeff und Erik Scheffers. Sie berücksichtigt die 100-Punkte-Bonusregel beim wiederholten Kniffel. Außerdem muss ich dem Programm neidlos eine etwas höhere Professionalität als meinem zugestehen.


Ich wünsche viel Spaß und freue mich über Huldigungen und Kritik wie hier oder hier.


Felix Holderied (felix@holderied.de) 28. Juli 1999