Bei diesem Würfelspiel gewinnt man praktisch nie, oder?

02.11.2024, 09:18

Integer21

Auf diesen Beitrag antworten »

Bei diesem Würfelspiel gewinnt man praktisch nie, oder?

Hallo zusammen,

anbei ein Bild des Spiels um das es geht.

Ziel des Spiels: Jede Ganze Zahl von 1-12 einmal abhaken, bzw. umklappen

Die Regeln:

Wenn man beispielsweise eine 4 würfelt, kann man die 4 oder die 3 und die 1 abhaken. Sind diese Zahlen bereits angehakt, ist das Spiel vorbei.

Ich habe ca. 20 Runden gespielt und nie das Ziel erreicht. Nun frage ich mich, wie hoch die Wahrscheinlichkeit ist, zu gewinnen.

Ich hatte in der Schule keine Stochastik und habe daher nur ein Grundlegendes Verständnis davon.

Ich wäre über Hinweise dankbar, wie man an dieses Problem herangeht und welche Methoden ich benötige.

Liebe Grüße und vielen Dank!

02.11.2024, 12:46

HAL 9000

Auf diesen Beitrag antworten »

Wenn du von "Augenzahl" redest, meinst du jeweils die Summe der beiden gewürfelten Augenzahlen oder?

D.h., wenn man eine 2 und eine 5 würfelt, d.h., Augenzahlsumme 7, darf man nach dieser Regel auch eine 3 und 4 wegstreichen (sofern noch übrig), oder? verwirrt

verwirrt

Zitat:

Original von Integer21
Nun frage ich mich, wie hoch die Wahrscheinlichkeit ist, zu gewinnen.

Diese Wahrscheinlichkeit hängt auch davon ab, welche Strategie man fährt: Gerade am Anfang hat man (bei zwei unterschiedlichen gewürfelten Augenzahlen) ja die Wahl, ob man die beiden Augenzahlen einzeln oder aber die Summe abhakt.

Je nach Wahl der Strategie ergibt sich eine unterschiedliche Siegwahrscheinlichkeit. Jetzt kann man natürlich auch noch danach fragen, was die optimale Strategie ist, um die Gewinnwahrscheinlichkeit zu maximieren. Das macht das Problem noch mal um einiges komplizierter.

Letzteres Problem wird man aber mit einem Backward-Algorithmus lösen können, der die optimalen Siegwahrscheinlichkeiten (und auch zugehörige Strategien!) für alle $\begin{eqnarray*} 2^{12} \end{eqnarray*}$ Teilmengen $\begin{eqnarray*} S\subseteq \{1,2,\ldots,12\} \end{eqnarray*}$ berechnet, ausgehend von der leeren Menge $\begin{eqnarray*} S=\emptyset \end{eqnarray*}$ und dann Stück für Stück aufbauend bis zur "vollen" Menge $\begin{eqnarray*} S= \{1,2,\ldots,12\} \end{eqnarray*}$ .

P.S.: Wenn ich mich beim zugehörigen Python-Programm nicht vertan habe, dann ist selbst bei optimaler Spielweise die Siegwahrscheinlichkeit nur $\begin{eqnarray*} \frac{18\,108\,706\,055}{19\,042\,491\,875\,328}\approx 0.000951 \end{eqnarray*}$ , also etwas weniger als 1 Promille. Augenzwinkern

Augenzwinkern

02.11.2024, 14:08

Integer21

Auf diesen Beitrag antworten »

Zitat:

Wenn du von "Augenzahl" redest, meinst du jeweils die Summe der beiden gewürfelten Augenzahlen oder?

D.h., wenn man eine 2 und eine 5 würfelt, d.h., Augenzahlsumme 7, darf man nach dieser Regel auch eine 3 und 4 wegstreichen (sofern noch übrig), oder?

Genau.

Ca. 1:1000 wäre das also. Vielen Dank für deine Hilfe!

Schade nur, dass ich so gar nichts über die Herangehensweise erfahre. Sieht so aus, als wäre das Thema zu anspruchsvoll, um da an einem Nachmittag durchzusteigen.

02.11.2024, 14:13

HAL 9000

Auf diesen Beitrag antworten »

Ich kann dir noch das Python-Programm listen:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:

#!/usr/bin/python
# -*- coding: utf-8 -*-

import math

movedict = dict()

def cache(fc):
    def cache_fc(f):
        def f_cached(n):
            if not n in fc: fc[n] = f(n)
            return fc[n]
        return f_cached
    return cache_fc

@cache({0: (1,1)})
def prob_rec(v):
    ps,qs = 0,1
    for k in range(2,13):
        opt = 0
        p,q = 0,1
        jv = 1<<k
        if (jv & v) > 0:
            p1,q1 = prob_rec(v - jv)
            if p1*q > p*q1:
                p,q = p1,q1
                opt = k
        j = max(k-6,1)
        je = (k-1)//2
        while j <= je:
            jv = 1<<j
            if (jv & v) > 0:
                j1v = 1<<(k-j)
                if (j1v & v) > 0:
                    p1,q1 = prob_rec(v - jv - j1v)
                    if p1*q > p*q1:
                        p,q = p1,q1
                        opt = j
            j = j+1
        p *= (6-abs(k-7))
        q *= 36
        # Die folgenden Zeilen realisieren nur die rationale Addition pr/qr = ps/qs + p/q
        # inklusive anschließendem Kürzen
        pr = ps*q + p*qs
        qr = qs * q        
        g = math.gcd(pr,qr)
        ps = pr//g
        qs = qr//g
        if opt > 0:
           movedict[(v,k)] = opt
    return ps,qs

def set_to_value(s):
    return sum(1<<k for k in s)

def prob(s):
    return prob_rec(set_to_value(s))
    
if __name__ == '__main__':
    s = set([1,2,3,4,5,6,7,8,9,10,11,12])
    v = set_to_value(s)
    p = prob(s) 
    print(p)
    # Beste Strategie für die Anfangskonfiguration:
    for k in range(2,13):
        if (v,k) in movedict:
            m = movedict[(v,k)]
            print(f"{s},{k} = {m}")

Aber erwarte jetzt nicht, dass ich das ausführlich erkläre - das dauert sicher sehr viel länger als die Zeit, in der ich es geschrieben habe. Augenzwinkern

Augenzwinkern

02.11.2024, 14:38

Integer21

Auf diesen Beitrag antworten »

1000 Dank, das ist wirklich großartig!

Ich weiß sehr zu schätzen, dass du dir diese Zeit genommen hast.

Ich wünsche dir ein tolles Wochenende!

02.11.2024, 16:19

HAL 9000

Auf diesen Beitrag antworten »

Hab mal die zweite Spielregel etwas abgewandelt - verschärft, um es genauer zu sagen:

Zitat:

- Die gewürfelte Augensumme kann entweder abgehakt werden, oder es können genau die beiden gewürfelten Augenzahlen abgehakt werden (aber allenfalls dann, wenn beide verschieden sind)

In dem Fall sinkt natürlich die Gewinnwahrscheinlichkeit noch weiter, und zwar auf $\begin{eqnarray*} \frac{737\,716\,831}{2\,115\,832\,430\,592} \approx 0.000349 \end{eqnarray*}$ .

Anzeige

02.11.2024, 17:15

Integer21

Auf diesen Beitrag antworten »

Meine Tochter hat vorher nach dem 5. Spiel gewonnen, mit Sicherheit ohne optimale Strategie... Big Laugh

Big Laugh

Selbst habe ich jetzt schon bestimmt 40 Mal gespielt. Die beste Strategie, die ich bisher ausarbeiten konnte, ist, nur zwei Zahlen abzuhaken, wenn es nicht anders geht.

Damit komme ich meistens ziemlich weit, aber eine Zwölf habe ich in den 40 Spielen vieleicht 4 Mal gewürfelt.

Sowas könnte mich ewig beschäftigen...

02.11.2024, 17:32

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Integer21
Die beste Strategie, die ich bisher ausarbeiten konnte, ist, nur zwei Zahlen abzuhaken, wenn es nicht anders geht.

Stimmt oft, aber nicht immer: In der Startkonfiguration

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12

sowie gewürfelter Augensumme 6 ist es günstiger das Paar 1,5 wegzustreichen statt der 6 - sagt zumindest mein Python-Script.

Oder ein Beispiel in der Endphase des Spiels: Sind noch

2, 4, 5, 6

übrig und man würfelt Augensumme 6, dann ist es besser 2,4 zu streichen als die 6.

Mit der einfachen Strategie

Streiche stets die Summe, sofern dies noch möglich ist
Andernfalls streiche das erste mögliche Paar mit dieser Summe (d.h. wenn z.B. bei 5=1+4=2+3 beide möglich sind, dann wird 1,4 gestrichen).

erreicht man übrigens nur die deutlich niedrigere Siegwahrscheinlichkeit $\begin{eqnarray*} \frac{16\,069\,585}{22\,039\,921\,152} \approx 0.000729 \end{eqnarray*}$ .

EDIT: Anbei die kompletten Resultate für die optimale Strategie: Sowohl die Siegwahrscheinlichkeiten für sämtliche Restmengen von verfügbaren Zahlen, als auch die zugehörigen optimalen Auswahlen dafür - allerdings nur für die Fälle, wo noch eine Siegchance besteht.

[attach]57975[/attach]

03.11.2024, 13:13

HAL 9000

Auf diesen Beitrag antworten »

Nachgeschoben noch den theoretischen Unterbau:

Die Teilmenge $\begin{eqnarray*} S\subseteq \{1,2,\ldots,12\} \end{eqnarray*}$ repräsentiere die Menge der noch nicht abgehakten Zahlen, und $\begin{eqnarray*} p(S) \end{eqnarray*}$ die zugehörige Siegwahrscheinlichkeit ausgehend von dieser Situation und bei optimaler Spielweise. Dann kann man dieses $\begin{eqnarray*} p(S) \end{eqnarray*}$ folgendermaßen rekursiv bestimmen:

1) Augensumme $\begin{eqnarray*} k\in \{2,3,\ldots,12\} \end{eqnarray*}$ im nächsten Wurf erscheint mit (Fall-)Wahrscheinlichkeit $\begin{eqnarray*} \frac{6-|k-7|}{36} \end{eqnarray*}$ .

2) Für jedes solche $\begin{eqnarray*} k \end{eqnarray*}$ führt man nun folgendes durch:

2.1) Gilt $\begin{eqnarray*} k\in S \end{eqnarray*}$ , so können wir Zahl $\begin{eqnarray*} k \end{eqnarray*}$ streichen und bekommen Wahrscheinlichkeit $\begin{eqnarray*} p(S\setminus\{k\}) \end{eqnarray*}$ für die Restmenge an Zahlen. Wir setzen in diesem Fall $\begin{eqnarray*} M_k := \{ p(S\setminus\{k\}) \} \end{eqnarray*}$ ; für $\begin{eqnarray*} k\notin S \end{eqnarray*}$ hingegen $\begin{eqnarray*} M_k := \emptyset \end{eqnarray*}$ .

2.2) Jetzt betrachten wir noch die evtl. Möglichkeiten, dass wir zwei verschiedene Zahlen $\begin{eqnarray*} j,k-j \end{eqnarray*}$ aus $\begin{eqnarray*} S \end{eqnarray*}$ streichen können. Es reicht, den Fall $\begin{eqnarray*} j<k-j \end{eqnarray*}$ zu betrachten, das führt zu $\begin{eqnarray*} j\leq \frac{k-1}{2} \end{eqnarray*}$ . Andererseits müssen natürlich auch $\begin{eqnarray*} j\geq 1 \end{eqnarray*}$ sowie $\begin{eqnarray*} k-j\leq 6 \end{eqnarray*}$ (umgestellt $\begin{eqnarray*} j\geq k-6 \end{eqnarray*}$ ) gelten. Für jedes $\begin{eqnarray*} j \end{eqnarray*}$ mit $\begin{eqnarray*} \max\{1,k-6\} \leq j\leq \left\lfloor \frac{k-1}{2}\right\rfloor \end{eqnarray*}$ prüfen wir daher nun, ob $\begin{eqnarray*} j,k-j\in S \end{eqnarray*}$ gilt. Falls ja, dann setzen wir $\begin{eqnarray*} M_k:= M_k\cup \{ p(S\setminus\{j,k-j\}) \} \end{eqnarray*}$ .

2.3) Ist $\begin{eqnarray*} M_k=\emptyset \end{eqnarray*}$ , so ist das Spiel an dieser Stelle verloren, wir haben in diesem Fall die bedingte Siegwahrscheinlichkeit $\begin{eqnarray*} p_k = 0 \end{eqnarray*}$ . Andernfalls setzen wir $\begin{eqnarray*} p_k = \max M_k \end{eqnarray*}$ .

3) Wir bekommen über alle Fälle summiert nun einfach die totale Wahrscheinlichkeit $\begin{eqnarray*} p(S) = \sum_{k=2}^{12} p_k\cdot \frac{6-|k-7|}{36}\qquad (*) \end{eqnarray*}$ .

Das ganze funktioniert, weil die Mengen, für die in 2.1) bzw. 2.2) $\begin{eqnarray*} p\left(\ldots\right) \end{eqnarray*}$ bestimmt werden muss, immer kleiner werden, so dass man in maximal 12 Schritten auf $\begin{eqnarray*} p(\emptyset) \end{eqnarray*}$ stößt, und dieser Anfangswert ist $\begin{eqnarray*} p(\emptyset)=1 \end{eqnarray*}$ (das ist, wenn alle Zahlen abgehakt sind, die sichere Gewinnsituation).

P.S.: Ein Teil des Pythoncodes ist nur dazu da, die Maximumbildung in 2.3) sowie auch die Rechnung (*) exakt mit rationalen Zahlen durchzuführen. Wenn man zusätzlich die optimale Strategie erfahren will, muss man in 2.3) noch mitloggen, ob nun $\begin{eqnarray*} k \end{eqnarray*}$ in 2.1) oder welches $\begin{eqnarray*} j \end{eqnarray*}$ in 2.2) zu dem Maximum gehört.

03.11.2024, 21:41

Integer21

Auf diesen Beitrag antworten »

Wow, danke für die ausführliche Erklärung Freude

Freude

Python kann ich nicht besonders gut, und ich war überrascht, dass die zugrundeliegende Logik gar nicht so kompliziert war.

Ich habe die Formeln und Umstellungen nachvollzogen und habe denke ich fast alles verstanden. Wie du allerdings von

$\begin{eqnarray*} j<k-j \end{eqnarray*}$

Zu

$\begin{eqnarray*} j\leq \frac{k-1}{2} \end{eqnarray*}$

Kommst habe ich nicht verstanden.

Ich komme bei

$\begin{eqnarray*} j< \frac{k}{2} \end{eqnarray*}$

an.

Grüße!

04.11.2024, 06:10

HAL 9000

Auf diesen Beitrag antworten »

$\begin{eqnarray*} j<k-j \end{eqnarray*}$ für ganze (!) Zahlen $\begin{eqnarray*} k,j \end{eqnarray*}$ ist gleichbedeutend mit $\begin{eqnarray*} j\leq k-j-1 \end{eqnarray*}$ , und das ergibt umgestellt $\begin{eqnarray*} j\leq \frac{k-1}{2} \end{eqnarray*}$ .

P.S.: Mit $\begin{eqnarray*} \left\lfloor \frac{k}{2} \right\rfloor \end{eqnarray*}$ (statt $\begin{eqnarray*} \left\lfloor \frac{k-1}{2} \right\rfloor \end{eqnarray*}$ ) als letzter $\begin{eqnarray*} j \end{eqnarray*}$ -Index würde man im Fall gerader $\begin{eqnarray*} k \end{eqnarray*}$ falsch liegen, Beispiel:

Für $\begin{eqnarray*} k=6 \end{eqnarray*}$ bedeutet $\begin{eqnarray*} j=\left\lfloor \frac{k}{2} \right\rfloor = 3 \end{eqnarray*}$ das Paar $\begin{eqnarray*} (j,k-j) = (3,3) \end{eqnarray*}$ , aber wir wollen hier ja nur verschiedene Zahlen haben.

Kleine Testfrage am Rande: Bei wie vielen Mengen $\begin{eqnarray*} S \end{eqnarray*}$ gibt es keine Zugmöglichkeit mehr, egal was man würfelt? Und wie sehen diese Mengen aus? Augenzwinkern

Augenzwinkern

10.11.2024, 20:10

HAL 9000

Auf diesen Beitrag antworten »

Als Abrundung (und Kontrolle) habe ich die ganze Sache auch mal simuliert:

Die $\begin{eqnarray*} 10^9 \end{eqnarray*}$ Einzelspiele umfassende Simulation ergab

729344 Siege mit der naiven Strategie (s.o.),
951940 Siege mit der optimalem Strategie.

In 557906 Spielen führten beide Strategien zum Erfolg - das ergibt dann einen Korrelationskoeffizient $\begin{eqnarray*} \approx 0.67 \end{eqnarray*}$ .

12.11.2024, 12:32

graugraugrau

Auf diesen Beitrag antworten »

„Zuerst möchte ich sagen, dass ich die Logik und die Ideen in Deinen Programmen wirklich sehr schätze. Es ist deutlich, dass Du viele Gedanken investiert hast, um eine funktionale Lösung zu kreieren!
Ich habe über einige Möglichkeiten nachgedacht, wie das Programm weiter optimiert werden könnte, falls es Dir recht ist. Eine Option wäre die Verwendung des lru_cache-Features aus dem functools-Modul, um den Cache effizienter zu gestalten. Das könnte die Leistung des Programms mit vielen Funktionsaufrufen verbessern.

Mit lru_cache wird die Verwaltung des Caches einfacher und effizienter, da es automatisch die Prüfung vornimmt. Hier ist ein Vorschlag, wie wir den Cache umsetzen könnten:

CopyReplit
from functools import lru_cache

@lru_cache(maxsize=None) # Unbegrenzt, kannst maxsize für eine bestimmte Anzahl an Caches anpassen
def prob_rec(v):
# ... der restliche Code bleibt unverändert ...
Ich würde mich freuen, deine Meinung dazu zu hören oder wenn andere im Forum Anmerkungen haben. Ich hoffe, dass diese Idee hilfreich ist!“

12.11.2024, 13:01

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von graugraugrau
Eine Option wäre die Verwendung des lru_cache-Features aus dem functools-Modul, um den Cache effizienter zu gestalten. Das könnte die Leistung des Programms mit vielen Funktionsaufrufen verbessern.

Hast du ausprobiert, ob dieser Cache effizienter als der obige ist?

Im übrigen habe ich das ganze (der Simulation wegen - die Wahrscheinlichkeits- und Strategienberechnung war auch in Python schon schnell genug) sowieso nach C++ portiert, und jede Zustandsmenge dort als Integerzahl 0..4095 kodiert - denke nicht, dass das noch wesentlich effizienter geht: Auf einem halbwegs aktuellen i7-Notebookprozessor hat die obige Simulation von $\begin{eqnarray*} 10^9 \end{eqnarray*}$ Spielen 10,6 Sekunden gedauert (bei Nutzung von 20 Threads), also knapp 100 Millionen Spiele pro Sekunde - das ist schon ganz schön flott.

12.11.2024, 13:15

graugraugrau

Auf diesen Beitrag antworten »

Nein, habe ich nicht. Funktioniert eh nicht.

12.11.2024, 13:17

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von graugraugrau
Nein, habe ich nicht. Funktioniert eh nicht.

Du machst Vorschläge, die nicht funktionieren? Das klingt jetzt ziemlich befremdlich. verwirrt

verwirrt

12.11.2024, 13:54

graugraugrau

Auf diesen Beitrag antworten »

Bin davon ausgegangen, daß Du das Programm ausprobierst und mit Deiner Erfahrung sofort erkennst daß was nicht stimmt. Bin noch auf der Suche, es sollte eigentlich gehen, gibt aber immer nur (0,1) zurück.

12.11.2024, 14:07

HAL 9000

Auf diesen Beitrag antworten »

Das Problem wird sein, dass die Zeile

code:
1:	@cache({0: (1,1)})

bereits einen Cache-Eintrag beinhaltet: Nämlich Funktionswert (1,1) für Argument 0.

Das wird natürlich nicht adäquat ersetzt durch bloßes

code:
1:	@lru_cache(maxsize=None)

Ich weiß nicht, ob man diesem Cache auch schon Werte "mitgeben" kann - eine Lösung wäre, als erstes in Funktion prob_rec(v) noch die Zeilen

code:
1: 2:	if v == 0: return 1,1

einzubauen, dann sollte es auch mit lru_cache klappen. Augenzwinkern

Augenzwinkern

12.11.2024, 16:39

graugraugrau

Auf diesen Beitrag antworten »

Ja, das geht. Kannst Du die beiden Versionen testen, ich habe kein reines Testequipment. Da wären die Ergebnisse verfälscht, glaube aber daß Deine Version schneller ist

12.11.2024, 16:52

HAL 9000

Auf diesen Beitrag antworten »

Hmm, ich hab mal die Zeiten gemessen, mit je 5 Wiederholungen:

1) Meine Originalversion: Zeiten zwischen 69 und 71ms
2) lru_cache-Version: Zeiten zwischen 66 und 70ms

2) scheint eine Nuance schneller zu sein, aber so richtig signifikant sieht das nicht aus.

13.11.2024, 10:15

graugraugrau

Auf diesen Beitrag antworten »

Ja, stimmt, danke für die Tests

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »