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: 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. |
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?
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 |
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:
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
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?
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.
E | A priori | Wurf 1 | Auswahl1 | Wurf 2 | Auswahl2 | Wurf 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 |
p | ||||||
1/9 | 2/9 | 2/9 | 1/9 | 2/9 | 1/9 | |
1/3 | 1/3 | 1/3 | 0 | 0 | 0 | |
0 | 1/3 | 0 | 1/3 | 1/3 | 0 | |
0 | 0 | 1/3 | 0 | 1/3 | 1/3 | |
1 | 0 | 0 | 0 | 0 | 0 | |
0 | 1 | 0 | 0 | 0 | 0 | |
0 | 0 | 1 | 0 | 0 | 0 | |
0 | 0 | 0 | 1 | 0 | 0 | |
0 | 0 | 0 | 0 | 1 | 0 | |
0 | 0 | 0 | 0 | 0 | 1 |
d | ||||||||||
1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | |
1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | |
1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | |
1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | |
1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | |
1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 |
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 |
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