Steine-Spiel

Beim Steine-Spiel stehen sich zwei Spieler gegenüber. Beide haben zu Beginn 6 Steine und versuchen über mehrere Runden mehr Punkte als der Gegenspieler zu erreichen. Je Runde nimmt man sich verdeckt eine beliebige Anzahl an Steinen in die Hand. Gleichzeitig öffnen beide Seiten ihre Hände. Wer mehr Steine in der Hand hält bekommt zwei Punkte. Bei Gleichheit bekommen beide Seiten einen Punkt. Die benutzten Steine werden aus dem jeweiligen Vorrat entfernt. Für einen Sieg erhält man einen Bonus-Stein. Wer zuerst 6 Punkte erreicht hat, hat gewonnen. Spiel man mehere Partien so gibt es für einen Sieg zwei Siegpunkte und für ein Unentschieden einen Siegpunkt.

Klingt auf dem ersten Blick doch nach einem interessanten und einfachen Spiel. Was hat dies nun mit Mathematik zu tun? In einem Teilgebiet der Mathematik, nämlich der Spieltheorie versucht man verschiedene Spiele zu analysieren und so vielleicht die beste Taktik zu finden. Einen etwas anderen Ansatz wollte ich in diesem Artikel präsentieren. Und zwar mit Computerunterstützung.

In der ersten Stufe habe ich den Computer 1 Millionen mal gegen sich selber spielen lassen. Dabei wurde keine Taktik mitgegeben, sondern alles dem Zufall überlassen. So kann es passieren, dass man in der ersten Runde schon alle Steine los wird. Auch kann folgende Situation entstehen.

• Spieler 1: 4 Punkte, 2 Steine
• Spieler 2: 4 Punkte, 1 Stein

Wenn man sich nun in Spieler 1 versetzt, so würde man sich wahrscheinlich freuen. Nimmt man nun die beiden verbleibenen Steine, so gewinnt man auf jeden Fall diese Runde und erhält 2 Punkte. Mit den 6 Punkten würde man die Partie gewinnen. Da der Computer keine Taktik mitgegeben bekommmen hat, passieren in den 1 Millionen Spielen manchmal auch blöde Züge. So hat Spieler 1 nun keinen Stein genommen und Spieler 2 aber seinen einen verbliebenen. Damit hat Spieler 2 das unmögliche Möglich gemacht und doch noch mit 6 zu 4 gewonnnen.
Dies ist aber in dieser Phase nicht schlimm, da der Computer ja erst einmal Erfahrung sammeln muss. Der Endstand nach den Spielen war:

Heim		Gast
Stufe 1 999.490	:	1.000.510 Stufe 1

In der nächsten Phase kommt nun die gesammelte Erfahrung hinzu. Die eine Millionen Spiele hat man nun als Basis. Man weiß also was gute Züge sind und was eher nicht so gut klappt. Der Computer der Stufe 2 soll nun also die Situation erkennen in der er sich befindet und so clevere Züge spielen. Hierfür braucht er für jeden Zug die folgenden Informationen.

1. Wie viele Steine habe ich übrig?
2. Wie viele Punkte habe ich?
3. Wie viele Steine hat mein Gegner übrig?
4. Wie viele Punkte hat mein Gegner?

Anhand dieser Kombination und der Erfahrung, kann der Computer die durchschnittliche Anzahl an Siegpunkten bestimmen, die er am Ende der Partie bekommt. Da er nicht durchschaubar sein soll, nimmt er nicht immer das beste Ergebnis. Am wahrscheinlichten nimmt er das Ergebnis, was die meisten Siegpunkte bringt, und so weiter. Sollte er in eine komplett neue Situation kommen, so wählt er komplett zufällig die Anzahl an Steinen aus.

Was passiert nun, wenn wir diese Stufe gegen den Zufall aus Stufe 1 antreten lassen?
Sehr wahrscheinlich sollte es zu einem klaren Sieg für unsere neue Stufe kommen. Gesagt getan, wir haben beide Stufen wieder 1 Millionen mal gegeneinander antreten lassen. Als Randbemerkung haben wir an dieser Stelle einen neuen Seed für die Zufallszahlen genommen, damit Spieler 1 nicht dieselben Entscheidungen trifft, wie bei den ersten Spielen. Dies machen wir auch bei allen folgenden Spielen.
Am Ende kam ein klarer Sieg für unsere neue Variante heraus. Fast 5-mal so viele Siegpunkte hat unsere neue Stufe bekommen.

Heim		Gast
Stufe 1 345.286	:	1.654.714 Stufe 2

Wir wollen aber an dieser Stelle bei weitem noch nicht aufhören. Um also weiter zu kommen, lassen wir erst einmal die zweite Stufe gegen sich selber antreten. Das Ergebnis war dank der gleichen Strategie und klein wenig Zufall in den Entscheidungen wieder sehr ausgeglichen.

Heim		Gast
Stufe 2 998.686	:	1.001.314 Stufe 2

Genauso wie Stufe 2 aus den Spielen aus der vorherigen Stufe gelernt hat, lernt auch unsere nächste Stufe von den 1 Millionen Partien zwischen der Stufe 2 mit sich selber. Die Entscheidungen die nun Stufe 3 trifft funktionieren analog wie in der letzten Stufe, nur mit einer neuen Basis an Informationen.
Die zweite Stufe verfolgte die beste Strategie gegen den Zufall, also gegen wahllose Spieler. Die dritte Stufe überlegt sich nun eine Taktik gegen Spieler die sehr einfach denken. Wir können also erwarten dass unsere neue Stufe die bisher beste Stufe darstellt. Um dies klar zu stellen, lassen wir sie wieder gegen die beiden vorherigen Stufen antreten.

Heim		Gast
Stufe 1 371.720	:	1.628.280 Stufe 3
Stufe 2 254.230	:	1.745.770 Stufe 3

Gegen die erste Stufe schneidet unser neuer Spieler etwas schlechter ab. Dies ist aber nicht so verwunderlich, da seine Strategie ja auch auf einen anderen Gegner basiert. Lassen wir unsere neue Stufe nämlich gegen die Zweite antreten, so spielt die neue Stufe den Gegner in Grund und Boden. Der Zufall ist bei beiden Spielern klein, und so macht die neue Taktik einen sehr guten Eindruck.

Natürlich können wir dieses Prozedur immer weiter machen. Also Stufe 3 gegen sich selber und dann wieder daraus eine neue Strategie entwickeln. Dies wollen wir aber im nächsten Schritt nicht mehr machen.

Ein riesen Nachteil bei den bisherigen Methoden war es, dass man immer erst einmal 1 Millionen Spiele zugucken musste und danach erst eine Strategie hatte. In diesem Abschnitt möchte ich dies nun ändern. Wir fangen an zu spielen, ohne bisher auch nur ein Spiel gespielt zu haben. Hierfür benutzen wir in der ersten Partie den Zufall, also nichts anderes als unsere erste Stufe. Mit jeder weiteren Partie wird unser Gedächtnis immer größer. Dieses Gedächtnis nutzen wir dann analog wie in der zweiten und dritten Stufe für unsere Züge.
Das Problem was man nun noch in den Griff bekommen muss ist der übergang. Hierfür sagen wir, dass die Wahrscheinlichkeit, dass wir einen zufälligen Zug machen exponentiell abnehmen soll. Warum exponentiell? Dies hat den Vorteil, dass unsere neue Stufe ewig lernt. Als Richtwert habe ich angenommen, das die Wahrscheinlichkeit nach 100.000 Partien bei 90 Prozent liegen soll. Man also nur zu 10 Prozent aus den bisherigen Erfahrungen seinen Zug ableitet.

Um einen ultimativen Test zu machen, muss nun und das Lernen der neuen Stufe zu analysieren, lassen wir die neue Stufe gegen alle drei bisherigen Stufen antreten. Es stehen immer 100 Spiele gegen jede Stufe an bis der Gegner gewechselt wird. Nach insgesamt 3 Millionen Partien ist dann Schluss.

Heim		Gast
Stufe 1 537.249	:	1.462.751 Stufe 4
Stufe 2 849.997	:	1.150.003 Stufe 4
Stufe 3 806.310	:	1.193.690 Stufe 4

Gegen alle drei Gegner kann sich unsere neue Stufe durchsetzen, obwohl die beiden letzten Stufen nur knapp besiegt wurden.
Was man an dieser Stelle aber nicht vergessen darf ist die Tatsache, dass in den ersten Partien unsere neue Stufe erst einmal lernen musste. Schauen wir uns hierfür doch einfach einmal an, wie viele Siegpunkte Stufe 4 im Durchschnitt in den ersten 10.000 Partien gemacht hat.

1. Gegen Stufe 1 sind es 1,0135
2. Gegen Stufe 2 sind es 0,3671
3. Gegen Stufe 3 sind es 0,3861

Wir sehen also, dass zu Beginn unsere Stufe noch einiges Lernen muss. Sie verhält sich eben wie Stufe 1, da sie fast immer nach dem Prinzip Zufall spielt. Schauen wir uns doch einfach an, wie sich die Durchschnittswerte in 10.000er Schritten so verändert.



Am Ende kommt unsere neue Stufe gegen jeden Gegner auf einen Durchschnittswert von mindestens 1,5 Siegpunkten je Partie. Dies spricht doch sehr für das ewige Lernen. Man erkennt sehr gut die Lernkurve. Nach rund 900.000 Spielen schafft er es erstmals auch gegen die Stufen 3 und 4 einen Durchschnittswert von über 1 zu erzielen.