Bonusterne berechnen in Hearthstone

[Mechanics]

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

[Dudeldu]

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.

[Mechanics]

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

[SeppJ]

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.

[Dudeldu]

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;
		}
	}

[SeppJ]

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

[Jester]

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.

[Markov]

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.

[Jester]

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.

[Kenner der algebraische G]

Gelesen: "Bonusterne berechnen in Hartshorne"

[Bengo]

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.

[Bengo]

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 =

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

[Dudeldu]

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 $g$ mal irgendwas Zustände (für alle möglichen Zustände bei $g$ 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.

[SG1]

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.

[SeppJ]

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 $g$ mal irgendwas Zustände (für alle möglichen Zustände bei $g$ 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 =

$\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.

[Dudeldu]

Ah, leuchtet schon mehr ein.

Komme dann auf eine 5x5 Matrix

$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 $g$ Schritten besucht wurde :).

[Dudeldu]

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

[SeppJ]

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 $g$ 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.

[Dudeldu]

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

[SeppJ]

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