Zufallsbit

In der letzten "Schlag den Raab"-Ausgabe wurde ein Spiel gespielt, das mich fasziniert hat. Es geht so:

Der erste Spieler würfelt mit einem Würfel. Ist es eine Zahl von 1-5, wird diese auf sein Punktekonto addiert und er darf nochmal würfeln. Ist es aber eine 6, verliert er alle Punkte wieder und der zweite Spieler ist dran. Man kann jederzeit aufhören zu würfeln, solange man keine 6 bekommt, dann werden die bisher erreichten Punkte auf ein Gesamtpunktekonto gutgeschrieben und der Gegner ist dran. Wer zuerst 50 Gesamtpunkte hat, ist der Sieger. 

Zum Beispiel könnte das Spiel so laufen:

Spieler 1: 1,5,6 (Gesamt: 0)

Spieler 2: 4,4, Aufhören (Gesamt: 8)

Spieler 1: 2,1, Aufhören (Gesamt: 3)

Spieler 2: 3,6 (Gesamt: 8)

usw.

Die Frage die ich mir sofort gestellt habe: Ab welcher Punktzahl lohnt es sich, aufzuhören? Natürlich würde man kaum mit einem Punkt an den Gegner abgeben, aber man würde auch nicht einfach drauflos würfeln, bis man seine 50 Punkte zusammen hat, denn die Wahrscheinlichkeit, dabei einmal eine 6 zu würfeln und alles wieder zu verlieren ist sehr hoch. Nun bin ich aber relativ schwach darin, das passende Wahrscheinlichkeitsmodell für solche Dinge zu finden. Selbst wenn ich eins finde, bin ich mir immer noch wahnsinnig unsicher, ob es das richtige war und ob damit nicht vielleicht die ganze Rechnung falsch ist. Viel besser bin ich darin, einfach ein Programm zu schreiben, das mir das Ganze simuliert.

Source

In dem Programm definiere ich einen "Cutoff", also eine Grenze, wo die virtuellen Spieler aufhören würden zu würfeln. Cutoff 10 bedeutet, dass der Spieler aufhört, sobald er >= 10 Punkte erreicht. Für jeden möglichen Cutoff habe ich dann jeweils 100.000 Spieler simuliert und das Ergebnis war.. nun ja.. interessant. Grafik gefällig?

Das Ergebnis überrascht mich ehrlich gesagt. Zwischen Cutoff 7 und 30 ist es relativ egal, was man macht, immer braucht man im Schnitt 8-9 Würfelnrunden um die 50 Punkte zu erreichen. Das macht irgendwie auch Sinn, denn bei Cutoff 25 bräuchte man ja nur zwei erfolgreiche Runden um zu gewinnen, aber bei Cutoff 7 ist die Wahrscheinlichkeit durch eine 6 gekillt zu werden entsprechend kleiner. Trotzdem läuft das irgendwie gegen meine Intuition, dass eine so breite Spanne von Cutoffs die gleichen Werte hat. Wenn jemand tatsächlich Ahnung von Mathematik hat und mir das erklären könnte, wäre ich sehr dankbar.

Hinter der Uni liegt ein großer Parkplatz. Hinter diesem Parkplatz steht ein Studentenwohnheim, in dem ein Freund von mir wohnt. Wenn ich ihn besuchen will, muss ich von einer Ecke des Parkplatzes zur anderen. Etwa so:

Man könnte natürlich einfach den Gehweg benutzen:

Aber das wäre nicht nur sehr langweilig, sondern auch rasend ineffizient. Die Wegkosten sind natürlich a*b. Die optimale Route kann man eigentlich nur nachts gehen, wenn der Parkplatz leer ist.

Der optimale Weg wäre natürlich genau die Diagonale und damit nach Pythagoras (und meinetwegen noch der Dreicksungleichung) . Dieser Weg geht aber leider nicht immer, weil der Parkplatz tagsüber mit Autos voll steht. Deshalb nehme ich notgedrungen diesen Weg:

Da stellt sich einem chronisch gelangweilten Informatiker natürlich die Frage: Wie viel verliere ich dabei an Optimalität? Die Abmessungen habe ich persönlich vorgenommen (und sah dabei ganz schön blöd aus, wie ich zwischen den Autos einen Fuß vor den anderen setzte und leise mitzählte).

Außerdem gibt es genau 17 solcher Parkinseln c und 17 Zwischenräume d, nicht nur 6 wie auf dem Bild suggeriert. Zeit für Mathematik.

Ich muss die Strecke b überbrücken während ich bei d diagonal gehe. Für die Anschaulichkeit sortiere ich das Problem mal in etwas Äquivalentes um:

 Der Winkel in dem ich gehen muss um von rechts nach links zu kommen ist bzw. , also . In meinem Fall wäre das .

Das ist zu meiner Überraschung und Freude ziemlich nahe an den optimalen 45°. Den kleinen Unterschied bezichtige ich einfach mal als Messfehler. Damit ist der Rest der Rechnung auch noch wahnsinnig einfach, denn der gesamte diagonale Weg ist damit . Der vertikale Weg addiert sich einfach zu 17*10m=170m und der Gesamtweg ist damit etwa 340m.

Vergleichen mit dem optimalen Weg von ist das immer noch ein zu 92% optimaler Weg. Was mich sehr glücklich macht.