Ich würfle eine Anzahl von W6 und nur die besten 3 Zählen...

Vor kurzem diskutierte ich mit einigen MitspielerInnen über ein Regelwerk (genauer: Es war Supers!, mit dem wir das Perry Rhodan-Universum abbildeten - tun wir übrigens immer noch).

Dabei kam eine Regel zur Sprache, nach der man bei dem Spiel (in bestimmten Konstellationen) eine Anzahl an Würfeln haben kann. In dem Falle sind das W6. Und man addiert die Ergebnisse auf, es geht also nicht um "Erfolge". Allerdings zählen wohl nur die besten 3 Würfel.

Sprich, man würfelt mit 7 Würfeln 3,2,5,6,1,2,5 und hat also 5+6+5=16 als Resultat.

Der Mathematiker in mir fühlte sich direkt angesprochen. Klar, mehr Würfel verschieben das Ergebnis hin zu "mehr", also hier: Näher zur 18. Aber wie? Ich bin erstmal auf keine guten Formeln gekommen. Klar, die "Ränder" kann man ausrechen, die Wahrscheinlichkeit für 3 ist: Alles muss 1 sein, also 1/6^n, bei n Würfeln, und die Wahrscheinlichkeit für 18 geht mit Binomialkoeffizienten. Aber dazwischen?

Vorweg: Wen der Mathe- bzw. Programmier-Teil nicht interessiert, hier geht es direkt zu meinen Ergebnissen. Ich beschreibe hier im Folgenden meinen Ablauf und die zugrundeliegenden Ideen.

Mir ist dann erst einmal eingefallen, das Ganze zu simulieren. Dazu habe ich z.B. für 6 Würfel erstmal alle Möglichkeiten durchprobiert, per Skript natürlich:

1,1,1,1,1,1

1,1,1,1,1,2

....

5,6,6,6,6,6

6,1,1,1,1,1

....

6,6, 6,6,6,6

Wie man sieht, sind das schon bei 6 Würfeln 6^6 Möglichkeiten, aber gut, das schockt einen Computer nicht. Nur muss man für jeden Würfel mehr 6 mal so lange rechnen, mein Skript brauchte also für 12 Würfel mehrere Stunden.

Das war, wenn ich jetzt nicht nur einige Zahlen haben wollte, sondern einfach mal eine Übersicht, die man auch in anderen Situationen brauchen kann (und hey, wer will das nicht auch für 50 Würfel wissen? 50 W20! Von denen 4 zählen! Oder 5! Genau!) nicht zielführend.

Ich habe mir dann folgenden Ansatz ausgedacht:

Angenommen, jemand hat im 4. Wurf folgende drei Höchstwürfel:

4,2,6

und wir haben schon ausgerechnet, dass diese Kombination in 17 Fällen auftritt (das ist nur ein Beispiel)

Dann kann er nun eine 1 Würfeln, und das ändert das Ergebnis nicht. Das sind also 17 Möglichkeiten.

Dann kann er nun eine 2 Würfeln, und das ändert das Ergebnis nicht. Das sind also nochmal 17 Möglichkeiten. Die kommen dazu.

Dann kann er eine 3 Würfeln, und hat

4,3,6

als neue Kombination.

usw:

4 -> 4,4,6

5 -> 4,5,6

6 -> 4,6,6

Nun setze ich in all diesen Kombinationen für den "nächsten Durchlauf" also die Werte um 17 höher.

Anders ausgedrückt, versuche ich den Algorithmus mal in Pseudocode zu beschreiben ...

Wir möchten die höchsten k aus n Würfeln auswählen. Das sind Wd.

(Im Beispiel: k=3, n=6, d=6, also W6).

* Erzeuge alle d^k Kombinationen an "aktuellen Maximalwürfeln".

* Für jede Kombination werden zwei Werte gespeichert, A und B. Setze überall den Wert A auf 1. Setze überall B auf 0.

* Führe nun n-k mal durch:

** Gehe durch alle Kombinationen durch. Die aktuelle Kombination heisse p.

*** Zähle in t von 1 bis d.

**** Ermittle, wie die neue Kombination aussieht, die sich ergibt, wenn mal von p aus t würfelt. Nenne diese Kombination q.

**** Erhöhe den Wert B in q um den Wert A von p.

** Gehe alle Kobinationen durch.

*** Setze in der aktuellen Kombination den Wert A auf B

*** Setze in der aktuellen Kombination B auf 0.

Danach muss man nur noch zählen, welche Summe welche Kombination ergibt und die A-Werte aufaddieren.

Das geht ... nicht nur ein bisschen schneller. Ein Beispiel: n=8, k=3, d=6 dauert mit der ersten Variante, dem durchzählen, auf meinem Rechner ca. 9 Sekunden. n=20 würde also 6^12-mal so lange dauern. Ich komme auf grob 621 Jahre.

Hiermit habe ich in grob einer Stunde (die W20 5-zaehlenden sind dann doch 3200000 mögliche Kombinationen) dann diese Tabellen ausgerechnet. Ist doch erheblich besser so ...

Hier geht es dann auch zum Sourcecode.

dicer.py muss man mit Paramtern aufrufen, das ist der erste Entwurf. Also z.B. python dicer.py 8 3. Mega-langsam, bei etwas größeren Zahlen, die Dauer nimmt eben exponentiell zu. (Dafür macht dicer.py noch eine Primfaktorzerlegung, weil ich gehofft hatte, dass ich daraus Regeln ableiten kann ... ich Dummerchen. Natürlich hab ich da nix erkannt.)

html.py mit lib_wuerfel.py berchnet die Webseiten. Ja, lib_bruchrechnung braucht man auch. Das ist mega-dilettantisch und sicher sehr unstrukturiert und historisch gewachsener Code ... aber vielleicht interessiert es dennoch jemanden.

Natürlich dürfen meine Ergebnisse beliebig verwendet werden, aber es wäre nun auch wahrlich albern, auf universal gültige Wahrscheinlichkeiten irgend eine Art von Urheberrecht anzuwenden, nur, weil ich sie ausgerechnet habe ... und ich kann auch Fehler gemacht haben, übernehme also keine Garantie.