4. Bonusterne berechnen in Hearthstone

Bonusterne berechnen in Hearthstone

  • ?

    Hi!

    In Hearthstone gibt es ein Ladder-System in der Rang RR eines Spieler anhand der Anzahl seiner Sterne SS bestimmt wird.

    Die Sternvergabe erfolgt nach folgenden Regeln:
    1. Für einen Sieg gibt es einen Stern.
    2. Für eine Niederlage gibt es einen Stern abzug.
    3. Für einen Sieg in einer Serie (3 oder mehr Siege hintereinander) gibt es einen zusätzlichen Stern.

    Beispiel mit 14 hintereinander gespielten Spielen(W=Sieg, L=Niederlage):

    \begin{eqnarray} Spielergebnis:& W&, L&, L&, W&, W&, W&, W&, W&, L&, W&, L&, L&, L&, L& \\ Punktevergabe:& +1&, -1&, -1&, +1&, +1&, +2&, +2&, +2&, -1&, +1&, -1&, -1&, -1&, -1& \end{eqnarray}

    Endergebnis: Winrate WR=50%W_R = 50\%, Gesamtsterne SGes=2S_{Ges}=2

    Die Frage nun:
    Wie hoch ist die erwartet Anzahl Gesamtsterne mit vorgegebener WRW_R nach gg Spielen?

    Ohne Bonussterne wäre es exakt:
    SGes=g∗(2∗WR−1)S_{Ges}=g*(2*W_R-1)

    Mit Bonussterne:
    ???

    Danke für eure Mühe!
    MfG
    Dudeldu

    0
  • ?

    Hat sich ein Fehler im Beispiel eingeschlichen sind natürlich [latex]S_{Ges}=3[\latex]

    0
  • Mod

    Was möchtest du wirklich wissen? Möchtest du wirklich einen analytischen Ausdruck? Der wird nämlich echt ekelig.

    0
  • ?

    Mich interessiert das Problem im allgemeinen. Wie geht man da ran? Wie behandelt man Serien bei Wahrscheinlichkeiten und Erwartungswerten? Wie ist der Anstieg der Bonussterne in Abhängigkeit der Winrate (linear? nicht linear und wie nicht linear?), denn die Abbruchwahrscheinlichkeit einer Serie sinkt ja ebenfalls mit der Winrate. Wenn du was analytisches hast, dann interessiert mich das sehr 😋. Und am ende möchte ich natürlich auch für mich selbst wissen, wie viel ich in etwa Spielen muss um einen gewissen Rang zu erreichen.

    Hab auch die Statistik der letzten Season von mir:
    Gesamtspiele: 378
    Bonussterne: 45

    Die Winrate verrate ich mal nicht, damit man einen Anreiz hat das Anhand der Bonussterne zu schätzen/errechnen ;).

    0
  • M

    Ist es für das Spiel irgendwie tatsächlich interessant? Ich spiele auch Hearthstone, hab mir aber noch nie Gedanken drüber gemacht.

    0
  • ?

    Naja, letztendlich kann man auch nur Spielen und am ende der Saison schauen was bei rum gekommen ist.
    Wenn man aber daran interessiert ist am ende einer Saison Rang 5 oder besser zu sein um die goldenen epische Karte zu erhalten, dann ist es durchaus einen Gedanken wert, ob sich Laddern noch lohnt oder ob man es eh knicken kann.

    0
  • M

    Um sowas brauch ich mir keine Sorgen machen, ich war letzte Saison auf Rang 15 😉

    0
  • Mod

    Dudeldu schrieb:

    Naja, letztendlich kann man auch nur Spielen und am ende der Saison schauen was bei rum gekommen ist.
    Wenn man aber daran interessiert ist am ende einer Saison Rang 5 oder besser zu sein um die goldenen epische Karte zu erhalten, dann ist es durchaus einen Gedanken wert, ob sich Laddern noch lohnt oder ob man es eh knicken kann.

    Die Sache ist: Solch eine Frage kann man schnell mittels einer Simulation beantworten. Dazu braucht man sich nicht stunden- oder tagelang den Kopf über den exakten analytischen Ausdruck (aus dem man letztlich auch nicht wirklich etwas herauslesen kann, ohne ihn numerisch auszuwerten) zu zerbrechen. Daher meine obige Frage, was deine wirkliche Absicht war.

    0
  • ?

    Ok, hab gedacht da kommt ein mehr oder weniger einfacher Ausdruck raus. Schade drum :(. Simuliert (Quick and Dirty) hab ich es schon, ein konkrete Ausdruck hätte mich aber zufriedener gestellt :P.

    Falls wer mit der Simulation spielen möchte:

    std::random_device rd;
    std::mt19937 g(rd());

	bool streakCount = 0;
	bool Won;
	unsigned __int64 Stars = 0;
	unsigned __int64 OutputIntervall = 1000;
	unsigned __int64 Counter = 0;
	unsigned __int64 maxValue =  rd.max();
	double Winrate = 0.500;
	unsigned __int64 starsNeeded = 54;
	vector<double> Samples;

	while(true) {
		Counter++;
		Won = rd() < Winrate*maxValue;
		if(Won) {
			streakCount++;
			Stars++;
			if(streakCount>2) {
				Stars++;
			}
		} else {
			if(Stars > 0) {
				Stars--;
			}
			streakCount=0;
		}
		if(starsNeeded <= Stars) {
			Samples.push_back(Counter);

			double sum = std::accumulate(Samples.begin(), Samples.end(), 0);
			double average = sum / Samples.size();

			if(Samples.size() % 100 == 0) {
				cout<<"Games:	"<<Counter<<", Stars:	"<<Stars<<", Average:	"<<average<<endl;
			}

			streakCount=0; Stars=0; Counter=0;
		}
	}
    0
  • Mod

    Dudeldu schrieb:

    Ok, hab gedacht da kommt ein mehr oder weniger einfacher Ausdruck raus.

    Ich hab's nicht durchgerechnet, bloß durchgedacht. Erfahrungsgemäß stößt man bei solcher Art Problemen aber höchst selten auf Vereinfachungen. Am Ende steht daher meistens irgendeine ekelige Summa da. Da du wissen wolltest, wie man so etwas angeht: Die Wahrscheinlichkeit, dass eine Serie einer gewissen Länge auftritt kann man einigermaßen geschlossen angeben. Dann kann man gucken, in welche Arten von Serien man eine Gesamtmenge von g Spielen aufteilen kann. Dabei muss man beachten, dass die Existenz oder Nichtexistenz einer Serie bedingen kann, ob Serien anderer Länge an ihrer Stelle stehen können. Das wird irgendeine Art von ekeligem verschachtelten Summenkonstrukt, das schnell aus Millionen von Einzelausdrücken bestehen wird, wenn man diese tatsächlich alle einzeln aufschriebe. In jedem steht die Wahrscheinlichkeit einer gewissen Serie und die Anzahl der Sterne für diese Serie. Und nachdem man alles aufsummiert hat teilt man noch durch die Anzahl der möglichen Aufteilungen, um den Erwartungswert zu erhalten. Also ganz einfach 🙂

    0
  • J

    Das ist eine einfache Markovkette. Also Übergangsmatrix aufschreiben und für jeden Schritt erwarteten Gewinn und Zustandswahrscheinlichkeiten mitführen, so kann man es auf jeden Fall mit eine Programm exakt ausrechnen. Man könnte auch die stationäre Verteilung zu grunde legen, das gibt dann nur eine ungefähre(höchstens leicht zu hohe) abschätzung, aber dafür als geschlossene formel. Ich tippe mal darauf, dass man das auch leicht exakt hinkriegt, weil die markovkette nicht so komplex ist.

    0
  • ?

    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.

    0
  • J

    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.

    0
  • ?

    Gelesen: "Bonusterne berechnen in Hartshorne"

    0
  • B

    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.

    0
  • B

    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))

    0
  • ?

    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.

    0
  • S

    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.
    0
  • 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.

    0
  • ?

    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 :).

    0
Anmelden zum Antworten