Berechnung der Bewertungen

Optimale Strategie und die Wahl einer Alternative

Über die optimale Strategie ist unter Kniffel - Wahrscheinlichkeiten und Punktzahlen bei optimaler Strategie nachzulesen. Untersuchungen finden sich auch im Artikel "An Optimal Strategy for Yahtzee" von James Glenn. Eingehend mit dem Thema beschäftigen sich auch die Seiten Solitaire Yahtzee: Optimal Player and Proficiency Test.

Es ist also durchaus denkbar, in jeder Situation die stochastisch günstigste Möglichkeit herauszufinden, um im Mittel eine möglichst hohe Punktzahl zu erreichen. Dazu sind allerdings umfangreiche Tabellen nötig, oder aber entsprechende Rechenkapazität. Ein weiterer Gesichtspunkt ist, dass Bots einfach zu gut spielen würden um menschlichen Spielern auf Dauer eine Chance zu lassen.

Aus den obenstehenden Ausführungen heraus wird daher eine alternative Methode verwendet, wie sie weiter unten als Grundidee beschrieben wird. Immerhin werden auch bei dem alternativen Ansatz im Mittel über 95% der mittleren Punktzahl bei optimalem Vorgehen erreicht, wie ein Testlauf mit 500 Spielen nahelegt.

Gewichtungen als Grundidee

Für jeden Eintrag werden Wahrscheinlichkeiten und Erwartungswerte berechnet in Anwendung einiger einfacher Regeln unter der Annahme, dass nur für diesen Eintrag eine möglichst hohe Punktzahl erzielt werden soll. Jeder freie Eintrag wird der Reihe nach abgearbeitet, wobei andere freie Einträge nicht zur einzelnen Bewertung herangezogen werden.

Unter Einhaltung einiger Regeln zur Auswahl der Würfel zum erneuten Werfen, die sich auch aus vereinfachenden Annahmen ergeben können, werden Wahrscheinlichkeiten und Mittelwerte gebildet. Die Regeln sind nicht notwendigerweise optimal, die sich daraus ergebenden Werte hingegen sind korrekt.

Für jeden Eintrag ist der Anfangserwartungswert (noch alle drei Würfe frei) bekannt. Alle schon erzielten Eintragsresultate und die restlichen Anfangserwartungswerte der freien Einträge - bis auf den gerade bearbeiteten - werden addiert. Statt des Anfangserwartungswertes des bearbeiteten Eintrags wird der Erwartungswert unter den gegebenen Umständen (Berücksichtigung des vorliegenden Wurfs und der Anzahl der Restwürfe) hinzu addiert. Insgesamt ergibt dies einen erwarteten Endstand für das laufende Spiel, und zwar für jeden noch freien Eintrag.

Es sind also alle Endstanderwartungswerte bekannt - für jeden freien Eintrag einer. Diese werden nun linear gewichtet: Der kleinste Wert erhält das Gewicht Null, der größte Wert bekommt das Gewicht Eins zugesprochen. Ausnahme: Falls alle Endstanderwartungswerte gleich sind, sind alle Gewichte gleich Eins. Diese Gewichte sind genau die Bewertungen, die auf Wunsch farblich abgesetzt als Tipps angezeigt werden.

Falls es mehrere beste Gewichtungen (also Bewertungen) gibt, wird diejenige ausgewählt, welche weiter oben in der Tabelle steht.

In der Tat wird das folgende äquivalente Verfahren benutzt, das ohne Summation auf einen Endstanderwartungswerts auskommt. Für jeden freien Eintrag wird der erwartete Zuwachs berechnet, der sich aus der Differenz des aktuellen erwarteten Werts und des erwarteten Werts bei drei freien Wurfversuchen ergibt. Genau wie bei den Endstanderwartungswerten werden jetzt diese Zuwächse gewichtet.

Markow-Ketten als Hilfsmittel

Teilweise kommt hier das Konzept der Markow-Ketten zum Einsatz. Insbesondere wird es für die Bonus-Berechnungen verwendet. Es würde auch für die oberen Einträge und auch z.B. für den Eintrag JaFuffy tragfähig sein, dort wird aber der direkte Weg beschritten. Wobei im letzteren Falle die Rekursionsgleichungen in Bezug stehen zur Matrixmultiplikation.

Anfangsmatrix A

Die Matrix (Af,k)f=1…6;k=0…5 beschreibe Anfangsbedingungen, wie folgt: Die Zeile f steht für die Anzahl der freien oberen Einträge, die Spalte k gibt die Anzahl gleicher Augenzahlen an. Das Matrixelement Af,k bedeutet die Wahrscheinlichkeit, k gleiche Augenzahlen bei f verbleibenden freien oberen Einträgen in einem Wurf mit allen fünf Würfeln zu erzielen. Die Anfangsmatrix A sieht einfach genug aus, um sie an dieser Stelle zu zeigen:

  [ 3125  3125  625   125    25    1   ]
  [ ----  ----  ----  ----  ----  ---- ]
  [ 7776  7776  3888  3888  7776  7776 ]
  [                                    ]
  [ 32     40   295   125    25    1   ]
  [ ---    --   ---   ----  ----  ---- ]
  [ 243    81   972   1944  3888  3888 ]
  [                                    ]
  [  1    125   185   125    25    1   ]
  [  --   ---   ---   ----  ----  ---- ]
  [  32   288   432   1296  2592  2592 ]
  [                                    ]
  [  1    155   130   125    25    1   ]
  [ ---   ---   ---   ---   ----  ---- ]
  [ 243   486   243   972   1944  1944 ]
  [                                    ]
  [  1    515   2425  625   125    5   ]
  [ ----  ----  ----  ----  ----  ---- ]
  [ 7776  2592  3888  3888  7776  7776 ]
  [                                    ]
  [        5     25   125    25    1   ]
  [  0     --    --   ---   ----  ---- ]
  [        54    36   648   1296  1296 ]
Einfache Übergangsmatrix M

Hier dreht es sich um die einfache Übergangsmatrix (Mi,j(f))i=0…5;j=0…5, bei welcher der Wert Mi,j(f) bei f freien oberen Einträgen die Übergangswahrscheinlichkeit von einem vorliegenden i-Mehrling auf einen in einem Wurf erwürfelten j-Mehrling angibt. Ein i-Mehrling ist ein Einling (i=1), Zwilling (i=2), Drilling (i=3), Vierling (i=4) oder Fünfling (i=5). Die einfache Übergangsmatrix M(f) sieht etwas komplizierter aus, lässt sich aber bestimmen etwa unter der Zuhilfenahme von der Euler Math Toolbox.



    
Spielmatrix S

Die Spielmatrix (Sf,k)f=1…6;k=0…5 gibt die Wahrscheinlichkeit an, nach drei Würfen bei f freien oberen Einträgen einen k-Mehrling zu erzielen. Die Markow-Kette erlaubt mittels der Anfangsbedingungen A und der Übergangsmatrix M durch Matrixmultiplikation eine einfache Berechnung: (Sf,k)k=0…5 = (Af,k)k=0…5 · M(f)2 mit 1≤f≤6. Da die Brüche in der Darstellung ziemlich groß sind, soll hier eine numerisch gerundete Rundung von S angegeben werden, um eine Vorstellung zu vermitteln:

  [ 0.06491   0.23626   0.34399   0.25042   0.09115   0.01327 ] 
  [ 0.00228   0.11133   0.37655   0.34600   0.14157   0.02228 ] 
  [ 0.00003   0.04705   0.35425   0.39342   0.17590   0.02935 ] 
  [ 0.00000   0.01786   0.32180   0.42204   0.20283   0.03547 ]
  [ 0.00000   0.00517   0.28781   0.44064   0.22543   0.04099 ]
  [ 0         0.00079   0.25601   0.45240   0.24476   0.04603 ]

Erwartungswerte der Würfe

Der Erwartungswert besagt, wie viele Punkte im Mittel erzielt werden können. Das hängt neben den Auswahlregeln natürlich davon ab, wie gut der vorgelegte Wurf schon ist und wie oft noch gewürfelt werden darf.

Obere Einträge

Exemplarisch wird hier ein wenig näher auf die Verfahrensweise eingegangen. Die anderen, folgenden Einträge weiter unten werden kürzer abgehandelt, zumal auch umfangreichere Formeln und Beschreibungen nötig wären.

Auswahlregel: Alle Würfel mit der Augenzahl, die nicht dem gerade bearbeiteten Eintrag entsprechen, erneut würfeln.

Erwartungswert: Im Mittel werden bei n Würfeln in r Restwürfen np Würfel der gewünschten Augenzahl erhalten, wobei p = 1-(5/6)r; die mittlere Punktzahl ergibt sich daher durch die Multiplikation mit der Augenzahl. Die Herleitung erfolgt über ein gedachtes n-stufiges Bernoulli-Experiment: Ein Sammelwurf (ein Würfel r-mal geworfen) wird n-mal hintereinander ausgeführt. Die Aufgabe besteht nun darin zu berechnen, mit welcher Wahrscheinlichkeit eine fest vorgegebene Augenzahl (festgelegt durch den gerade bearbeiteten Eintrag) k-mal vorkommt bei den n Sammelwürfen. Die Augenzahl tritt bei einem Sammelwurf genau dann auf, wenn sie mindestens einmal beim r-maligen Würfeln erzielt wird. Die Wahrscheinlichkeit ergibt sich zu binom(n,k)pk(1-p)n-k .

Kleiner Pasch und großer Pasch

Auswahlregel: Kommen alle Augenzahlen nur einmal vor, werden alle Würfel neu geworfen. Ansonsten werden aus dem Wurf die Würfel ausgewählt, deren Augenzahl am häufigsten vorkommt. Ist die Auswahlmöglichkeit nicht eindeutig, werden die Würfel mit der größten Augenzahl bevorzugt. Ist schon ein kleiner bzw. großer Pasch erreicht, werden die verbleibenden Würfel wie bei der Chance so gewählt, dass im Mittel eine möglichst hohe Augenzahl erreicht wird.

Grundidee:

Full House

Auswahlregel: Behalte einen Drilling, sofern möglich. Ansonsten behalte zwei Zwillinge, sofern vorhanden. Gibt es nur einen Zwilling behalte diesen. Gibt es nur einzelne Augenzahlen, wirf alle Würfel erneut.

Grundidee: Es wird die Wahrscheinlichkeit v(k,r) berechnet, in r Restwürfen die k fehlenden Würfel zum Full House zu erwürfeln. Aus der Anzahl k der fehlenden Würfel ist die Aufteilung des vorliegenden Wurfes in Einlinge, Zwillinge oder Drilling (auch abgeleitet aus Vierling oder Fünfling) bekannt. Daraus lassen sich für alle k ≠ 5 mittels Kombinatorik die Wahrscheinlichkeiten berechnen, für k = 5 wird eine Rekursionsformel benötigt mit v(0,0) := 1 und sonst v(k,0) = 0:

Obenstehend gibt u(k) die Wahrscheinlichkeit an, dass nach dem einem Wurf mit allen Würfeln noch k Würfel zu Full House fehlen.

Kleine Straße

Auswahlregel: Hier wird gezählt, wie viele günstige Augen außen (1 oder 6), innen (2 oder 5) oder mittig (3 oder 4) liegen. Augen werden einfach gezählt, bei mehrfachem Vorkommen wird nur ein Würfel genommen. Die Regeln lauten wie folgt:

  1. Bei zwei inneren Augen werden diese behalten.
  2. Kommt ansonsten nur ein inneres Auge vor und weder {1,2} noch {5,6} treten auf, so wird nur das innere Auge behalten.
  3. Treffen die oberen Fälle nicht zu, wird entweder aus {1,2} oder {5,6} entnommen, je nachdem welche Wahl günstiger ist. Sind beide Paare möglich, entscheidet der Zufall.
  4. Zu guter Letzt werden mittige Augen immer gewählt.

Grundidee: Es hat sich als sehr kompliziert erwiesen, eine geschlossene Darstellung zu finden. Deshalb wird hier ein Tabellenansatz verfolgt. In einer vorberechneten Tabelle steht in Abhängigkeit von einem Schlüssel, welche Wahrscheinlichkeit besteht, eine kleine Straße zu erzielen.

Der Schlüssel besteht aus:

Hierbei werden die Anzahlen so gewählt, wie sich aus der Auswahlregel ergeben. Nur die tatsächlich ausgewählten Würfen tragen zur Zählung bei.

Große Straße

Auswahlregel: Falls eine 1 oder eine 6 vorkommt, wird eine davon zufällig ausgewählt und zurückbehalten. Für jede der Augen 2, 3, 4 oder 5 wird genau ein Würfel behalten, sofern er diese Augenzahl zeigt. Alle anderen Würfel werden in den Becher gelegt zum erneuten Würfeln. Diese Auswahlregel stellt eine Vereinfachung der Strategie dar, mit möglichst großer Wahrscheinlichkeit die große Straße zu erwürfeln. Insbesondere sind für die optimale Strategie die Regeln komplizierter, wann eine 1 oder eine 6 zu behalten sind.

Grundidee: Bei n Würfeln, die zur große Straße fehlen, bleiben n Positionen zur Belegung mit einer Augenzahl. Das Ziel ist, k unterschiedliche Augen, welche zur Straße benötigt werden, auf n Positionen zu verteilen. Mindestens diese k Augen müssen vorkommen (durchaus mehrfach), die restlichen Positionen werden anderweitig belegt. Aus den Positionen {1,…,n} wählt man alle Teilmengen mit j Elementen aus, j ≥ k; diese Teilmengen zerlegt man in k-elementige Partitionen. Die Anzahl der möglichen Partitionen ergibt sich aus den Stirlingzahlen der zweiten Art. Die Belegung der Partitionen der Positionen berechnet sich mit der fallenden Faktoriellen.

Aus der Grundidee ergibt sich der Erwartungswert unter Einsatz von Rekursionsformeln: Die Wahrscheinlichkeit zu einer großen Straße beträgt p(n,r) bzw. q(n,r), wobei n die Anzahl der fehlenden Würfel zu einer Straße ist, und r die Anzahl der Restwürfe bezeichnet. Im Ergebnis sind zu lesen:

p(n,r) := summe ( u(n,k)p(n-k,r-1), k=0…n )

Obenstehende Rekursion gilt unter dem Fall, dass 1 oder 6 schon zuvor erwürfelt wurden.

q(n,r) := summe ( w(n,k)q(n-k,r-1) + v(n,k)p(n-k,r-1), k=0…n )

Obenstehend Rekursion ist dann anzuwenden, wenn weder 1 oder 6 zuvor erwürfelt wurden.

Dabei sind unter Benutzung der Stirlingzahlen S der zweiten Art und der fallenden Faktoriellen fallend:

Hier sind ein paar Hinweise, wie die Formeln für u, v und w für die Anzahl der möglichen Kombinationen für einen Straßensequenzteil ermittelt werden:

JaFuffy

Auswahlregel: Sind alle Würfel verschieden, nochmals alle Würfel werfen. Ansonsten die Augenzahl mit den meisten Würfeln heraussuchen und alle anderen Würfel werfen; gibt es mehrere Augenzahlen für die höchste Würfelanzahl, wird eine Augenzahl zufällig herausgesucht.

Grundidee: Es wird die Wahrscheinlichkeit berechnet, die fehlende Anzahl von Würfeln mit der benötigten Augenzahl zu erwürfeln. Dabei wird berücksichtigt, dass die zu verfolgende Augenzahl sich auch verändern kann. Wenn etwa ein Zwilling vorliegt, muss man mit einem möglicherweise erwürfelten Drilling fortfahren. Es erweist sich die Notwendigkeit einer Fallunterscheidung, wobei für einen Fall wieder ein Rekursionsansatz zum Tragen kommt.

Die Wahrscheinlichkeit zum Erzielen von JaFuffy bei k Würfeln mit gleicher Augenzahl und r Restwürfen betrage p(k,r). Außerdem bezeichne q(n,r) die Wahrscheinlichkeit bei n freien Würfeln n mal eine gleiche, fest gewählte Augenzahl zu erzielen. Zuletzt wird die Wahrscheinlichkeit gi benötigt, welche zur Erzielung von von maximal i gleichen Augenzahlen gehört, wobei es nicht auf die Augenzahl ankommt.

Die Werte gi lassen sich durch etwas Überlegung ermitteln, sie entsprechen der letzten Zeile der obigen Matrix A der Anfangsbedingungen. Mit ähnlichen Überlegungen wie zum oberen Tabellenteil ergibt sich:

q(n,r) = (1-(5/6)r)n, wobei 00 := 1 ist.

Die Fallunterscheidung richtet sich nach der Anzahl k der fehlenden Würfel zum JaFuffy .

Chance

Auswahlregel: Berechne den Mittelwert der zu erreichenden Punktzahl eines einzelnen Würfels für die Anzahl der bestehende Restwürfe. Ist der Mittelwert größer als die bereits vorliegende Augenzahl dieses Würfels, den Würfel erneut werfen.

Berücksichtigung des Bonus

Der Begriff "Länge" bezieht sich hier auf die Länge eines Mehrlings bzw. auf die kumulierte Länge von mehreren Mehrlingen. Die Idee ist bei f freien oberen Einträgen zu ermitteln, mit welcher Wahrscheinlichkeit die Summe m über alle Mehrlingslängen erzielt wird. Diese Summe aller beiteiligten Mehrlinge wird hier kumulierte Länge genannt.

Längenmatrix U

Die Matrix (Uf,m)f=1…6;m=0…30 enthält die Wahrscheinlichkeiten Uf,m bei f freien oberen Einträgen genau m günstige Augenzahlen zu erzielen. Hierbei ist m die kumulierte Länge aller Mehrlinge, wie sie für jeden freien oberen Eintrag erzielt werden.

Die Längenmatrix U berechnet sich aus der Spielmatrix S wie folgt. Bei einem freien oberen Eintrag kann man aus der Spielmatrix die Wahrscheinlichkeit ablesen, nach drei Würfen einen m-Mehrling zu erzielen. Für die erste Zeile der Längenmatrix gilt also U1,m := S1,m. Die weiteren Zeilen ergeben sich rekursiv zu Uf,s := Uf,s + Sf,k · Uf-1,m, wobei Indizes gemäß f=2…6, k=0…5 und m=0…5·(f-1) laufen. Dazu wird noch die Randbedingung s=k+m benötigt, welche dafür sorgt, alle Beiträge einzusammeln, die zur kumulierten Länge s beitragen. Die Rekursion besagt, wie man bei bekannten Verhältnissen f-1 von freien Einträgen auf die neue Situation von f freien Einträgen schließt: Sf,k rührt aus einem Versuch mit drei Würfen; Uf-1,m verbleibt, weil nach diesem Versuch die Anzahl der freien Einträge um Eins reduziert ist.

Mindestlängenmatrix V

Die Matrix (Vf,m)f=1…6;m=0…30 enthält die Wahrscheinlichkeiten Vf,m bei f freien oberen Einträgen mindestens m günstige Augenzahlen zu erzielen. Hierbei ist m wieder die kumulierte Länge aller Mehrlinge. Mit einer unteren Dreiecksmatrix D, welche ausschließlich Einsen erhält, berechnet sich die Mindestlängenmatrix mittels V=UD.

Anwendung auf Bonus

Für jeden oberen freien Eintrag wird wieder der erwartete Zuwachs ermittelt, der sich aus der Differenz des aktuellen erwarteten Werts und des erwarteten Werts bei drei freien Wurfversuchen ergibt. Für beide Werte wird der Bonus hinzugefügt, allerdings multipliziert mit einer Schätzung, mit welcher Wahrscheinlichkeit dieser erreicht wird.

Für die Schätzung wird benutzt, wie viele Punkte noch benötigt werden. Außerdem wird vereinfachend angenommen, dass bei den möglichen verbleibenden Mehrlingen sich die freien Augenzahlen gleichmäßig auf die kumulierte Länge verteilen. Bei einer kumulierten Länge m entspräche also jedem Würfel also das arithmetische Mittel aus allen freien Augenzahlen. Dadurch lässt sich die Mindestlänge bestimmen, welche zur Erreichung des Bonus benötigt wird. Liegt schon ein Wurf vor, muss für jeden Eintrag berücksichtigt werden, dass dieser für seine Augenzahl gemäß des Wurfes vervollständigt wird und dass die Anzahl der freien Einträge um eins reduziert ist, für die noch alle drei Wurfversuche und alle anderen Augenzahlen zur Verfügung stehen.

Spielstärken

Die gewonnenen Prognosen werden mit einer Unsicherheit versehen, so wie bei der Verhaltensbeschreibung für Bots beschrieben.

Berücksichtigung der unterschiedlichen Spielregeln

Die obigen Ausführungen beziehen sich auf die klassischen Spielregeln.

Bei den Im-Hieb-Regeln wird zum Anfangserwartungswert der klassischen Spielregeln noch ein mittlerer Im-Hieb-Bonus hinzu addiert. Der mittlere Zusatzbonus ergibt sich als Produkt der Wahrscheinlichkeit für einen Eintrag mit dem ersten Wurf zu punkten, multipliziert mit dem Bonus (5 oder 30). Dieser um den Zusatzbonusbeitrag ergänzte Wert entspricht dem tatsächlichen Anfangserwartungswert bei der Anwendung von stochastischen Rechnungen für die Im-Hieb-Regeln. Dadurch erhält ein Ergebnis, welche im Hieb erzielt wurde, eine stärkere Gewichtung. Das Vorgehen entspricht genau dem Vorgehen, wie es oben bei den Gewichtungen als Grundidee geschildert ist.

Schwächen

Andere freie Einträge werden nicht zur Bewertung eines einzelnen Eintrags herangezogen. Das ist zum Beispiel ungünstig, falls ein JaFuffy erwürfelt werden soll aus dem Wurf 1, 1, 2, 2, 3. Dann können ohne weiteres die Einser-Würfel zum Verbleib ausgewählt werden, obwohl die Einser im oberen Teil schon gesetzt sein können und die Zweien noch nicht.

Mögliche Erweiterungen

Denkbar zur Beseitigung der eben beschriebenen Schwächen ist, für jeden Eintrag einige alternative Vorschläge abzuspeichern und in einem zweiten Schritt alle Alternativen miteinander abzugleichen. Ebenso können einige Auswahlregeln verbessert werden, beachte etwas das Zufallselement bei JaFuffy.