Benutzer:Christian

Aus LM Wettbewerb

Inhaltsverzeichnis 1 Erste Schritte 2 Mein Weg zur Literatur 3 Strategie 4 Seufz

[Bearbeiten] Erste Schritte

Ich habe mich schon gefreut, als ich die Vorankündigung im vorherigen LM las.

Und dann kam die Aufgabenstellung endlich: handhabbar, interessant (jedenfalls auf den ersten Blick...), irgendwie meiner Ansicht nach nichts für meine Lieblingssprache. In welcher Sprache möchte ich eigentlich einen Netzwerk-Client schreiben? Bestimmt nicht in C, da muss man sich so aufwendig darum kümmern, dass auch die ganze Nachricht empfangen bzw. versendet wurde, oder genauer: ob man das bei so kurzen Nachrichten muss, weiß ich nicht mal genau. Wie peinlich, wenn ich das mache, und es gar nicht nötig ist! Ich hatte noch analog zum bash+netcat-Beispiel im Heft an eine Kombination mit awk gedacht, das dann aber doch nicht weiter verfolgt. Was bietet eigentlich Python? Bestimmt gibt es auch was anderes, aber ich fand auf den ersten Blick nur dieselben Low-Level-Befehle, die C auch hat. Hmm, Ruby soll toll sein. Tatsächlich finde ich da die gewünschten einfachen Befehle für die Kommunikation über's Netzwerk, und das Matchen der Servernachrichten geht auch elegant. Ein Bot, der in von der Zugdauer abhängigem Zufall ROLL oder SAVE spielt, ist schnell geschrieben. Zeit, über die Strategie nachzudenken.

So, wie es bald darauf auf der Strategien-Seite an die große Glocke gehängt wurde, habe auch ich mir erstmal überlegt, wie ich den Erwartungswert pro Zug maximiere, und errechnete, dass ich versuchen soll, bis 15 oder 16 zu kommen. Um diese Strategien zu untersuchen, habe ich dann doch zu Haskell gegriffen, um festzustellen, dass man auch in seiner Lieblingsprogrammiersprache häßlichen Code schreiben kann - kein Gameserver, sondern nur genug, um zwei Strategien zu vergleichen, die ich dann sehr kurz formulieren konnte. Aha, ROLL16 ist besser als ROLL15, und spaßeshalber mal mit ROLL17 vergleichen, oh, das ist noch besser. Wenn man drüber nachdenkt, ist es auch ganz klar: ROLL17 reichen drei erfolgreiche Versuche, ROLL16 eventuell nicht. Ich fange an, die Aufgabe richtig gut zu finden. (Bei einem Ziel von 48 ist ROLL16 natürlich besser. Bei einem Ziel von 49 oder 100 übrigens auch.)

Aber auch der Erwartungswert, wieviele Züge man braucht, wenn man allein spielt, ist nicht entscheidend. ROLL50 aka AlwaysRoll braucht im Schnitt bis zum Erreichen des Ziels etwas länger als ROLL1 (man könnte auch sagen: RollOnce), besiegt ihn im direkten Vergleich aber deutlich. Diesmal liegt es an der unterschiedlichen Streuung.

ROLL17 lehrt uns, auf drei erfolgreiche Züge zu setzen. Wenn man das hat, ist die 17 nicht mehr so wichtig. Dann kommt man auf Ideen wie 16+16+X, wobei X der fehlende Rest ist. Oder noch besser, man strebt im zweiten Zug die Hälfte (auf- oder abgerundet?) dessen an, was noch fehlt. Und nimmt man dann im ersten vielleicht doch lieber 17? Hier bewegen wir uns in Bereichen, wo die Simulationen nicht mehr schnell klare Antworten liefern. Und vielleicht soll man zu einer Zwei-Zug-Strategie (ROLL25) wechseln, wenn der Gegner schon die Hälfte der erforderlichen Punkte hat und man selber noch keine? Oh ja, diesmal sind die Simulationsergebnisse deutlich. Aber bei welcher Grenze soll man den Strategiewechsel vornehmen?

Diese Strategien lebten alle nur in meinem Vergleichsprogramm. Die letzte habe ich im Nachhinein noch als Ruby-Programm in einen kompletten Bot umgesetzt und hier veröffentlicht, da das schon veröffentlichte Ruby-Beispiel meines Erachtens der Sprache nicht gerecht wurde. (Nicht, dass ich das von meinem unbedingt behaupten würde, aber ich finde es deutlich schöner.)

Nun hatte ich also eine akzeptable Strategie mit einigen Parametern zum Fein-Tunen, die sich nicht mehr gut durch Simulationen optimieren ließen. Eigentlich wäre mir ja auch Rechnen lieber. Und dann kam es ganz anders.

[Bearbeiten] Mein Weg zur Literatur

Auf der Strategien-Seite hat jemand Markov-Ketten mit absorbing states für Berechnungen erwähnt. Das schien hilfreich für die Fragen, bei denen meine Simulationen inkonklusiv blieben. Mit Hilfe einer Suchmaschine fand ich Literatur dazu:

• Charles M. Grinstead, J. Laurie Snell. Introduction to probability (Kapitel 11)

Glücklicherweise ging ich danach trotzdem noch in die UB. Dort fand ich zwar dazu nichts besseres, nahm aber außer zwei Büchern zu Octave/Matlab, womit ich mich noch nie ernsthaft beschäftigt hatte, noch ein weiteres mit nach Hause:

• Richard A. Epstein. The Theorie of Gambling and Statistical Logic. Second Edition, Elsevier, 2009

  (sehr interessant, nette eingestreute humorvolle Bemerkungen, etliche Ungenauigkeiten)

Das war weniger mit Begeisterung als: naja, kann man ja mal mitnehmen, immerhin schreibt er viel über's Würfeln, da könnte was hilfreiches dabei sein. Tatsächlich hat er aber doch eine Variante des Spiels beschrieben, nur bis 100 und mit 1 statt 6 als Wurf, bei dem man zurückfällt. Dort wird es dann aber doch nicht genauer analysiert, sondern nur festgestellt, dass man, wenn man alleine spielt und möglichst viele Punkte in wenig Zügen erreichen will, bis 20 würfeln soll, entsprechend dem Erwartungswert (entspricht 15 in unserer Variante).

Doch es gab weitere Literaturverweise, denen ich nicht mal mehr gefolgt bin; aber vor allem: ich hatte einen Namen (Piglets, und für eine weitere Variante mit zwei Würfeln den wohl insgesamt gebräuchlicheren Namen Pig) für das Spiel, den man einer Suchmaschine geben konnte.

Und da findet man dann alles:

• Pig Links, dort besonders interssant:
  • Todd W. Neller and Clifton G.M. Presser. Optimal Play of the Dice Game Pig, The UMAP Journal 25(1) (2004), pp. 25-47

    (eine genaue mathematische Analyse)

  • Todd W. Neller and Clifton G.M. Presser. Practical Play of the Dice Game Pig, The UMAP Journal 31(1) (2010), pp. 5-19

    (untersucht Strategien, die Menschen sich ausdenken und merken können, z.B. ROLLn)

• Solving the Dice Game Pig: an introduction to dynamic programming and value iteration

  (hilfreich für die Implementierung)

• ein Applet

  (grandios, selber ansehen!)

• und auch die englischsprachige Wikipedia hat was

[Bearbeiten] Strategie

Nun konnte ich also die optimale Strategie berechnen. Das in Ruby geschriebene Programm brauchte dazu etwa eine Minute. Auf ähnliche Weise kann man dann auch berechnen, wie die Chancen dieser optimalen Strategie gegen eine feste andere Strategie stehen, und man kann alternativ ausrechnen, wie gut eine optimal auf diese andere Strategie angepasste Strategie ist. Gegen ROLL16 und ROLL17 gewinnt man mit optimal angepasster Strategie etwa einen weiteren Prozentpunkt, gegen das eh schon schwache AlwaysROLL steigert man sich dagegen nur um 0,02 Prozentpunkte. (Das bei den Benchmarks angegebene "theoretische Optimum" stimmt mit meinen Berechnungen überein.) Gegen die Strategie, nur einmal zu würfeln, steigert man sich dagegen von 96,8% auf 99,6%. Diese Berechnungen brauchen ein paar Minuten.

Die Unterschiede der Gewinnwahrscheinlichkeiten sind gering, aber nicht zu vernachlässigen. Man muss aber die Strategie der Gegners erst mal kennen, und sie sich dann auch noch in dem wenigen erlaubten Speicherplatz zwischen den Spielen merken. Also doch einfach bei der optimalen Strategie bleiben?

Die optimale Strategie ist ziemlich unregelmäßig, sie ganz abzuspeichern scheint langweilig und unsportlich. Spielstände, die mit der optimalen Strategie erreichbar sind und bei denen man nicht einfach nur immer ROLL spielt, gibt es 193. Für alle diese müsste man bis zu drei, aber meist eine Zahl speichern. Nebenbei deuten Äußerungen anderer Teilnehmer im Wiki darauf hin, dass auch sie die optimale Lösung haben.

Ich reimplementiere die Strategieberechnung in C und optimiere hier und da. Nicht schlecht, Noch eine Idee, und mein Atom-Netbook braucht unter einer Sekunde. Ich spüre die Verlockung, das Ganze doch in C zu machen. Will ich mir das wirklich antun? Zumindest sollte ich, wenn ich schnell rechnen kann, das auch sinnvoll tun und nicht nur immer wieder dieselbe Tabelle berechnen, die ich auch einfach fest in den Code hätte schreiben können.

Was kann ich mir von den Gegnern merken? Eigentlich möchte ich mir merken, wie oft sie in einer bestimmten Situation ROLL bzw. SAVE gespielt haben. Dazu reicht der Platz nicht. Ob sie überhaupt mal in einer Situation das eine oder andere gespielt haben: 2 Bit pro Situation. Wird knapp - wie lang sind eigentlich die Namen?

Schließlich habe ich eine andere dumme Idee: Ich merke mir nur, wie oft ich ROLL bzw. SAVE in einer Spielsituation überhaupt gesehen habe - egal von wem. Daraus berechne ich mir einen ideellen Gesamtdurchschnittsgegner und berechne eine optimale Stategie dagegen. Und damit ich für alles Werte habe und mich nicht allzu leicht von der optimalen Strategie abbringen lassen, tue ich so, als hätte ich den optimalen Zug schon ein paar mal gesehen, vielleicht drei mal.

Verdammt, ich will aber optimal gegen optimale Gegner spielen! Ich kann ausrechnen, welche Zustände erreichbar sind, wenn beide optimal spielen, und die andere Strategie nur anwenden, wenn wir uns außerhalb dieses Bereiches befinden. Oder ich kann für diesen Bereich meine fiktiven optimalen Beobachtungen deutlich erhöhen, vielleicht das zwanzigfache? Nee, das kann trotzdem zu einer falschen Strategie führen. Aber anstatt aus dem Spielstand abzuleiten. ob der Gegner optimal spielt, sollte ich das lieber direkt aus seinen Zügen ablesen, das ist genauer. Seufz, bisher hatte ich mir die Programmlogik, um die Züge des Gegners genau zu analysieren, gespart.

So mache ich es jetzt: ich spiele optimal, solange sich der Gegner optimal verhält. Tut er das nicht, spiele ich die weiteren Züge gemäß einer Strategie, die optimal ist gegen jemanden, der so spielt, wie ich es bisher insgesamt beobachtet habe. Für die fiktiven optimalen Vorab-Beobachtungen habe ich die Zahl noch auf fünf erhöht. Mit Glück sind die abweichenden Strategien ähnlich, und mein gegen den Durchschnitt angepasstes Spiel taugt was. Es ist auch gut denkbar, dass verschiedene nicht-optimale Strategien das Programm so durcheinanderbringen, dass es gegen alle schlecht spielt. Vielleicht ist die Auswirkung auch so gering, dass es gar keinen spürbaren Unterschied, in welche Richtung auch immer, macht gegenüber denen, die immer die optimale Strategie spielen.

Jedenfalls steht fest: das Programm verliert nichts im direkten Vergleich mit optimalen Gegnern, und macht ansonsten etwas interessantes. Insofern besteht eine Chance, dass es sich nicht nur zufällig von "nur" optimal spielenden Programmen abhebt. Ob es sich tatsächlich, und noch dazu in der gewünschten Richtung abhebt, bleibt offen. Möglicherweise ist es dafür viel zu vorsichtig. Vielleicht gewinnt auch eine ganz andere Strategie, die nicht so genau hinschaut und sich deshalb in dem wenigen Speicherplatz zumindest ein bisschen von jeden Gegner merken kann.

[Bearbeiten] Seufz

Vorletzter, und das offenbar aus doofem Grund: in dem Datenfile stehen viele Nullen, durch die dann auch noch geteilt wird, wo ich zuerst Fünfen hingeschrieben und dann nur noch inkrementiert habe. Wahrscheinlich liegt das an einer Race-Condition, wenn man das Programm mehrmals gleichzeitig aufruft. Das ist geschehen, laut Logfile hat das Programm sogar gegen sich selbst gespielt. In dem Pseudocode, wie der Wettbewerb angeblich ablaufen sollte, war das nicht vorgesehen. Insofern behaupte ich einfach mal, das Programm wurde spezifikationswidrig eingesetzt.

Nach jedem der ersten 9623 Spielen war der Gewinnanteil über 50%, zum Schluss waren es nicht mal mehr 25%. Trägt man die Anzahl der Spiele gegen die Anzahl der gewonnenen Spiele auf, sieht man ganz gut, wie die Kurve stückweise linear einknickt, interessanterweise sieht es nach drei Stücken aus. Bestätigt wird dies, wenn man die Spielnummer gegen die Anzahl der Siege in den nächsten 1000 Spielen aufträgt - eine Art Ableitung. Das bewegt sich zuerst oberhalb von 500, ab 10000 bei etwa 300, und ab 20000 bei etwa 210. Eine mögliche Erklärung ist folgende: ein Prozess hat ja versucht, Daten zu lesen, als ein anderer die Datei gerade zum Schreiben geöffnet und sie damit erstmal geleert hat. Nachdem der erste Prozess dadurch die Nullen in seinem Array behalten hat, hat der zweite die richtigen Daten geschrieben, die ein neuer Prozess übernehmen konnte, bevor der zweite seine falschen Daten geschrieben hat. So konnten sich eine Weile Prozesse mit guten und Prozesse mit kaputten Daten überlappen, den Zahlen zufolge wohl ein guter und zwei schlechte. Schließlich war dann mal das Timing schlecht, und die guten Daten wurden überschrieben, bevor ein neuer Prozess sie gelesen hat. Oder es war einer der Serverneustarts.

Schade, ich hätte mit solchen Untersuchungen lieber rausgefunden, was meine Lernstrategie nutzt.

Fazit: Verlass dich nicht darauf, wie das Programm angeblich eingesetzt wird, insbesondere wenn schon andere Aspekte geändert worden sind, und hör auf die Compilerwarnungen!

Vielleicht mache ich mir noch mal die Mühe einer eigenen Wettbewerbsauswertung. Falls wer anders das tut: bitte die lernenden Programme nicht mehrmals gleichzeitig aufrufen, und falls nicht eh alles neu eingerichtet wird, die kaputten Daten löschen:

rm bot107/src/mathrolls/data

Spaß gemacht hat es jedenfalls, unabhängig von der unverständlichen Kommunikationskatastrophe, die der Veranstalter sich geleistet hat.