Bonusterne berechnen in Hearthstone

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.

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.

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

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.

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

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.

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

Bengo

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?

Jester

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 $A^{2b} = (A^2)^b$ nutzen, und bei $A^{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 = S^{-1} D S$ , und damit ist $A^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.

Jester

Kenner der algebraische G schrieb:

Gelesen: "Bonusterne berechnen in Hartshorne"

Das ist mir übrigens auch passiert.

Die Kurven $2*x-1$ und $x^3$ schneiden sich 2 mal im Intervall [0;1], bei $x_1=\frac{1}{2}*(\sqrt{5}-1) \approx 0.618$ und $x_2=1$ . Hab nun versucht das zu interpretieren. Das bedeutet doch, dass man "optimal" spielt wenn man mit einer Winrate von $x_{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 $\approx 0.618$ ist der Fleißfaktor größer als der Skillfaktor.