Bonusterne berechnen in Hearthstone



  • Jester schrieb:

    Das ist eine einfache Markovkette.

    Sicher? Die Winrate hat der OP nicht als Siegwahrscheinlichkeit für ein einzelnes Spiel definiert, sondern als den Anteil an Siegen am Ende des Prozesses. Dadurch hast du keine fixen Übergangswahrscheinlichkeiten zwischen den verschiedenen Zuständen.



  • Ich hätte das so aufgefasst, dass es sich um eine Wahrscheinlichkeit handelt. Sonst ist das natürlich deutlich schwieriger, aber imo ist es doch auch mit der Wahrscheinlichkeit aus praktischer Sicht deutlich interessanter -- schließlich verliert man nicht absichtlich die letzten Spiele wenn es am Anfang gut gelaufen ist, damit die Winrate stimmt. Das entspricht übrigens auch der Implementierung des OP.



  • Gelesen: "Bonusterne berechnen in Hartshorne"



  • Jester schrieb:

    Ich hätte das so aufgefasst, dass es sich um eine Wahrscheinlichkeit handelt. Sonst ist das natürlich deutlich schwieriger, aber imo ist es doch auch mit der Wahrscheinlichkeit aus praktischer Sicht deutlich interessanter -- schließlich verliert man nicht absichtlich die letzten Spiele wenn es am Anfang gut gelaufen ist, damit die Winrate stimmt. Das entspricht übrigens auch der Implementierung des OP.

    Das macht schon Sinn, aber ich sehe nicht ganz wo genau du deine Markow Kette siehst. Ich sehe da eigentlich nur eine ganz normale Bernullikette.

    Ok wenn man den Erwartungswert betrachtet kann man tatsächlich eine Markow-Kette draus machen. Es lässt sich damit glaube auch ganz elegant lösen, ich probiere es mal aus.



  • Ok ich hab jetzt eine expliziete Formel für den Erwartungswert, wer ein bischen mehr Ahnung von Mathe hat, kann die bestimmt auch so verbessern, dass man sie tatsächlich einfach ausrechnen kann:
    P =

    (0,50,5000,500,500,5000,50,5000,5)\begin{pmatrix} 0,5 & 0,5 & 0 & 0 \\ 0,5 & 0 & 0,5 & 0 \\ 0,5 & 0 & 0 & 0,5 \\ 0,5 & 0 & 0 & 0,5 \\ \end{pmatrix}

    E = Vector(-1, 1 , 1, 2) * (Vector(0,5;0,5;0;0)*P^(g))



  • Bengo schrieb:

    Ich sehe da eigentlich nur eine ganz normale Bernullikette.

    Die Folge von Siegen und Niederlagen ist eine Bernoulliekette, da wir aber insbesondere an Serien oder "Glücksträhnen" interessiert sind kommt man nicht um die Markovkette rum, weil wir vorherige Ereignisse mit betrachten müssen. So hab ich das zumindest verstanden.

    Die Matrix verstehe ich nicht... kannst du das erläutern? Ich hätte 3 Zustände erwartet (-1,+1,+2) oder aber etwas in die Richtung gg mal irgendwas Zustände (für alle möglichen Zustände bei gg spielen).

    Ich lese mich grad in Markovketten ein. Jemand einen guten Link parat, mit ausführlicher Einführung und umfangreicher Erklärung?

    Das Problem hier scheint eine Kombination aus "Irrfahrt auf Z" und "Warteschlange" zu sein, die beiden Beispiele tauchen in vielen möglichen Markov-Skripts auf.



  • Dudeldu schrieb:

    Ich hätte 3 Zustände erwartet (-1,+1,+2)

    Das sind keine Zustände. Zustände in diesem Fall sind:

    • Letztes Spiel verloren
    • 1 Spiel in Folge gewonnen
    • 2 Spiele in Folge gewonnen
    • 3 oder mehr Spiele in Folge gewonnen.

  • Mod

    Dudeldu schrieb:

    Die Matrix verstehe ich nicht... kannst du das erläutern? Ich hätte 3 Zustände erwartet (-1,+1,+2) oder aber etwas in die Richtung gg mal irgendwas Zustände (für alle möglichen Zustände bei gg spielen).

    Die vier Zustände sind: Niederlage; 1. Sieg; 2. Sieg; und dritter oder mehr Siege.

    Bengo schrieb:

    Ok ich hab jetzt eine expliziete Formel für den Erwartungswert, wer ein bischen mehr Ahnung von Mathe hat, kann die bestimmt auch so verbessern, dass man sie tatsächlich einfach ausrechnen kann:
    P =

    (0,50,5000,500,500,5000,50,5000,5)\begin{pmatrix} 0,5 & 0,5 & 0 & 0 \\ 0,5 & 0 & 0,5 & 0 \\ 0,5 & 0 & 0 & 0,5 \\ 0,5 & 0 & 0 & 0,5 \\ \end{pmatrix}

    E = Vector(-1, 1 , 1, 2) * (Vector(0,5;0,5;0;0)*P^(g))

    Wenn p die Gewinnwahrscheinlichkeit darstellt, dann ist somit der Erwartungswert für die Anzahl der Sterne (pro Spiel!):
    Bei einem oder zwei Spielen: -1+2p
    Bei drei oder mehr Spielen: -1+2p+p^3
    Es reicht also eine durchschnittliche Gewinnwahrscheinlichkeit von p > ~0.453, um unendlich viele Sterne anhäufen zu können.

    Ist mir jetzt schon peinlich, das nicht gesehen zu haben, dabei hab ich das doch studiert :p . Ich habe mich so sehr in den kombinatorischen Ansatz versteift, dass ich die einfache Lösung gar nicht gesehen habe.



  • Ah, leuchtet schon mehr ein.

    Komme dann auf eine 5x5 Matrix

    M=(OLWWWWWWO00000L0,50,50,50,50,5W0,50,5000WW000,500WWW0000,50,5)M=\begin{pmatrix} & O & L & W & WW& WWW\\ O & 0 & 0 & 0 & 0 & 0\\ L & 0,5 & 0,5 & 0,5 & 0,5 & 0,5 \\ W & 0,5 & 0,5 & 0 & 0 & 0\\ WW & 0 & 0 & 0,5 & 0 & 0\\ WWW & 0 & 0 & 0 & 0,5 & 0,5\\ \end{pmatrix}

    Mit dieser Visualiserung. Denke den Anfangszustand O kann man weglassen, dann komme ich auf dieselbe Matrix wie Bengo, nur Transponiert...
    Dann muss man ja nur noch herausfinden wie oft ein bestimmter Zustand nach gg Schritten besucht wurde :).



  • Oh, da hast du schneller gepostet, bezog mich auf SG1. Dann ist das Problem ja gelöst :D. Analytisch! Wunderbar!


  • Mod

    Dudeldu schrieb:

    Denke den Anfangszustand O kann man weglassen

    So ist es. solltest du sogar. Der Anfangszustand ist in bengos Gleichung das (0.5, 0.5, 0, 0) (oder allgemeiner: (1-p, p, 0, 0)), das heißt, das erste Spiel gewinnt man mit einer Wahrscheinlichkeit von 0.5 (bzw p) oder verliert es mit W'keit 0.5 (bzw. p-1).

    Dann muss man ja nur noch herausfinden wie oft ein bestimmter Zustand nach gg Schritten besucht wurde :).

    Eben indem du die Matrix g-mal (beziehungsweise g-1 Mal, wenn du das erste Spiel weg lässt) mit sich selber multiplizierst. Und da kommt nach drei Schritten ein statisches Ergebnis bei heraus.



  • Sehr cool das Ganze. Mit dem einfachen System hat Blizzard direkt zwei Fliegen mit einer Klappe geschlagen. "Schlechte" Spieler machen dennoch Fortschritt und verlieren nicht den Spass am Spielen und "Gute" Spieler werden mit dritter Potenz durch das Bonussystem Belohnt und machen dementsprechend sehr schnell Sprünge nach vorn.

    Danke an alle die hier mitgeholfen haben :). Hat Spass gemacht die Lösung nach und nach zu erarbeiten (naja, "erhalten" trifft es wohl eher 😉 ).


  • Mod

    Dudeldu schrieb:

    "Gute" Spieler werden mit dritter Potenz durch das Bonussystem Belohnt und machen dementsprechend sehr schnell Sprünge nach vorn.

    Denk dran, dass das Maximum immer noch 2 ist, selbst bei 100% Gewinnrate 🙂



  • Dudeldu schrieb:

    Sehr cool das Ganze. Mit dem einfachen System hat Blizzard direkt zwei Fliegen mit einer Klappe geschlagen. "Schlechte" Spieler machen dennoch Fortschritt und verlieren nicht den Spass am Spielen und "Gute" Spieler werden mit dritter Potenz durch das Bonussystem Belohnt und machen dementsprechend sehr schnell Sprünge nach vorn.

    Danke an alle die hier mitgeholfen haben :). Hat Spass gemacht die Lösung nach und nach zu erarbeiten (naja, "erhalten" trifft es wohl eher 😉 ).

    Es ist die dritte Potenz einer Matrix, ich glaube das wirkt sich anders aus als bei reelen Zahlen größer 1. Dazu ist jeder eintrag der Matrix auch noch kleiner gleich 1.

    Ich hab von linearer Algebra leider nicht so viel Ahnung, wie ich gerne hätte, deshalb noch 2 Fragen. Macht es eigentlich einen unterschied, wenn man die Matrix transponiert? und gibt es irgentwelche einfachen wege um eine matrix zu potenzieren?



  • Bengo schrieb:

    Ich hab von linearer Algebra leider nicht so viel Ahnung, wie ich gerne hätte, deshalb noch 2 Fragen. Macht es eigentlich einen unterschied, wenn man die Matrix transponiert? und gibt es irgentwelche einfachen wege um eine matrix zu potenzieren?

    Wenn Du dafür auch die Vektoren transponierst und von der anderen Seite dran multiplizierst macht das keinen Unterschied. 😉 Ein einfacher Check ist, ob eine Wahrscheinlichkeitsverteilung auch wieder auf eine solche abgebildet wird. Zum Potenzieren ist es hier halt so, dass sich schon nach kurzer Zeit nichts mehr tut. Das ist ja auch nicht verwunderlich, schließlich hat man sehr wenige Zustände und schon nach kurzer Zeit ist es fast egal wo man angefangen hat, da immer wenn man einmal verliert man ja wieder an derselben Stelle ist, egal was vorher passiert ist.

    Will man eine Matrix allgemein potenzieren bietet sich natürlich klassisches square&multiply an, also A2b=(A2)bA^{2b} = (A^2)^b nutzen, und bei A2b+1=A2bAA^{2b+1} = A^{2b} \cdot A nutzen. Das nützt natürlich nur am Rechner was.

    Ansonsten kann man natürlich auch versuchen eine geeignete Zerlegung zu finden. Wenn eine Matrix zum Beispiel diagonalisierbar ist, dann lässt sie sich schreiben als A=S1DSA = S^{-1} D S, und damit ist An=S1DnSA^n = S^{-1} D^n S. Die Diagonalmatrix D lässt sich leicht potenzieren. Im Zweifelsfall kann man sich hier bestimmt auch mit einer Jordan-Normalform behelfen, das ist sicher besser als nichts. Das wird wohl nicht immer zum Ziel führen, aber ich denke damit kriegt man schon einiges in den Griff.



  • Kenner der algebraische G schrieb:

    Gelesen: "Bonusterne berechnen in Hartshorne"

    Das ist mir übrigens auch passiert. 😃



  • Die Kurven 2x12*x-1 und x3x^3 schneiden sich 2 mal im Intervall [0;1], bei x1=12(51)0.618x_1=\frac{1}{2}*(\sqrt{5}-1) \approx 0.618 und x2=1x_2=1. Hab nun versucht das zu interpretieren. Das bedeutet doch, dass man "optimal" spielt wenn man mit einer Winrate von x1,2x_{1,2} spielt, da man dort die meisten Sterne für die investierte Zeit erhält, nicht wahr?
    Oder auch anders ausgedrückt bei einer Winrate über 0.618\approx 0.618 ist der Fleißfaktor größer als der Skillfaktor.



  • Das Argument verstehe ich nicht. Das ist ja die Anzahl der Sterne pro Spiel. Je höher die Winrate, desto höher die Sterne pro Spiel, ergo: mehr spielen -> mehr Sterne. Fleiß gewinnt also auf jeden Fall. Allerdings wächst der Anteil eben nicht linear mit der Winrate, sondern anfangs etwas schneller und später etwas langsamer.



  • Hier noch eine Alternativlösung ohne Markov-Kette:
    Sei xix_i die ZV für das Resultat im i-ten Spiel mit win = 1, loss = 0 und E[x_i] =: p
    Dann ist die Anzahl der Sterne nach n >= 3 Spielen
    s=i=1n(2x_i1)+_i=3nx_ix_i1xi2s = \sum_{i=1}^n (2 x\_i - 1) + \sum\_{i=3}^n x\_i x\_{i-1} x_{i-2}
    Dann ist mit Linearität des Erwartungswert und Produkt von Erwartungswerten von unabhängigen ZVn:
    E[s] = n \cdot (2p-1) + (n-2) \cdot p^3



  • Dudeldu schrieb:

    bei x1=12(51)0.618x_1=\frac{1}{2}*(\sqrt{5}-1) \approx 0.618

    Welch überraschendes Auftauchen des https://de.wikipedia.org/wiki/Goldener_Schnitt


Anmelden zum Antworten