Hallo,

für die Uni muss ich derzeit einen Bot für ein Würfelspiel programmieren.

Spielregeln
Jeweils 3 Bots spielen mit 2 Würfeln gegeneinander. Der Bot, der gerade an der Reihe ist, würfelt immer mit beiden Würfel gleichzeitig. Die Augenzahl der Würfel wird zusammengezählt und immer solange zur eigenen Rundensumme addiert, bis der Bot einen Pasch (d.h. Augenzahl der beiden Würfeln ist gleich) erwürfelt. Mit einem Pasch endet für ihn die Runde und er verliert alle in dieser Runde erwürfelten Punkte. Das kann aber vermieden werden, denn vor dem Würfeln kann sich der Bot entscheiden:
• Würfeln und möglicherweise alle in der aktuellen Runde erspielten Punkte verlieren, oder
• an den nächsten abgeben und die bisherig erspielten Punkte auf jeden Fall behalten?
Die behaltenen Punkte werden immer zur aktuellen Rundensumme addiert. Wer so zuerst 150 Punkte oder mehr erkämpft hat, gewinnt!

Meine Heuristik:
Ich hab mir gedacht: die Wahrscheinlichkeit das ich einen Pasch würfle liegt bei 1/6. Demnach sollte es i.d.R. leicht möglich sein das ich 5 mal würfle ohne die Runde zu verlieren. Nach den 5 Runden wird per Zufall entschieden: Wenn eine Zufallszahl (die zwischen 0 und (Anzahl der Würfe in der Runde) mal (Punkte in der Runde) liegen kann) größer ist als 35 (5 erfolgreiche Runden mit dem häufigsten Wert (7)) dann hör ich mit der Runde auf, anderenfalls mach ich weiter.

Pseudocode:


Meine Frage an euch: Gibt's bessere herangehensweisen? Kann man meine Heurisik irgendwie verbessern? Gibt's bekannte bessere Algorithmen? Habt ihr andere Ideen wie man so eine Heuristik erstellen könnte?

lg elundril

This Signature-Space is intentionally left blank.
Bei Beschwerden, bitte den Beschwerdebutton (gekennzeichnet mit PN) verwenden.

Hallo,

die Wahrscheinlichkeit für einen Pasch ist nicht 1/6. Rechne das nochmal nach.

Beste Grüße

Edit: Sorry, für einen beliebigen schon. /blush

Sondern

Also 6 von 36 Möglichkeiten macht wohl 1/6! (ich gehe mal von einem Standardwürfel mit 6 Seiten aus...)

hab gerade auch nen fehler entdeckt. Hab mir ja ne zufallszahl erzeugt und die dann unbenutzt weggeworfen.

lg elundril

This Signature-Space is intentionally left blank.
Bei Beschwerden, bitte den Beschwerdebutton (gekennzeichnet mit PN) verwenden.

Ich würde das ganze über den Erwartungswert des nächsten Wurfs lösen, bei allen "Nicht-Pasch-Würfen" gewinnt man die entsprechende Augenzahl hinzu, würfelt man einen Pasch verliert man das was man schon hat.

Wenn meine Mathematik richtig ist, kommt man dann dabei raus, dass man bis zum Punktestand von 35 weiterwürfeln sollte, hat man schon mehr Punkte ist es besser aufzuhören.

Das einzige was ich dann noch ändern würde, ist das man volles Risiko geht (also bis zum Sieg oder Pasch), wenn die anderen Bots in der nächsten Runde höchstwahrscheinlich gewinnen werden.

MfG

Jann1k

Definieren wir einen Spielstand S mit den Spielern P und deren gewonnenen Punkten W_P, so lässt sich eine Breitensuche ausführen, die jeden möglichen Spielstand ausgehend von S bewertet. (Diese Aussage ist trivial).

Ferner haben wir hier ein diskretes Optimierungsproblem für die Punktzahl W_p, wobei p der eigene Spieler P ist. (Auch trivial).

Jede Spielsituation kann zudem für jeden Spieler bewertet werden, indem man die Punktzahl des Spielers nimmt und hiervon das Mittel aller Punktzahlen der anderen Spieler abzieht. (Existenz-Beweis durch Beispiel).

Wichtig ist eigentlich jetzt weniger, in jedem Zug möglichst viele Punkte zu holen, sondern dafür zu sorgen, dass man seine Punkte sicher hat. Es kann daher überlegenswert sein, eine Runde bereits vorzeitig abzugeben, wenn man im nächsten Zug das Spiel für sich entscheiden kann.

Hier ist also die Verlust-Wahrscheinlichkeit in Abhängigkeit der bereits erzielten Punkte (pro Zug) wichtig. Wenn ich bereits 30 Punkte hab und noch 7 Punkte brauch, dann sollte man lieber aufhören, weil man dann mit sehr hoher Wahrscheinlichkeit im nächsten Zug gewinnt.

Am Ende würd ich einfach mal hergehen und sagen: Programmier Dir nen Simulator und lass diesen das gesamte Spiel mal durchrechnen

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Ist die Wahrscheinlichkeit nicht bei jedem Wurf gleich, einen Pasch zu würfeln? Es wird doch nicht wahrscheinlicher, je öfter ich würfle, oder?

Wenn ich also noch 7 Punkte benötige, ist es egal, ob ich weitergebe oder gleich mein Glück versuche.

Meine Meinung: Liege ich hinten, gehe ich ein Risko ein, und leg noch einen drauf. Liege ich vorne, freu ich mich auf jeden Punkt.

Nettes Spiel. Ich kann mir auch vorstellen, das die beste Taktik von der Taktik der Gegner abhängt.

Da es sich um ein reines Glücksspiel handelt, würde ich eine adaptive Strategie wählen.

Ich kann mich aber auch vollkommen irren. Bei solchen Überlegungen komm ich eh immer ins Schlingern.

alzaimar hat folgendes geschrieben :

Ist die Wahrscheinlichkeit nicht bei jedem Wurf gleich, einen Pasch zu würfeln? Es wird doch nicht wahrscheinlicher, je öfter ich würfle, oder?

Ja, die ist gleich.

alzaimar hat folgendes geschrieben :

Wenn ich also noch 7 Punkte benötige, ist es egal, ob ich weitergebe oder gleich mein Glück versuche.

Theoretisch ja. Rein praktisch hast Du dann aber im nächsten Versuch in jedem Fall schon mal X Punkte mehr, die Du dann nicht mehr brauchst. Du hast also 7, statt X+7 Punkte, die Du erwürfeln musst.

alzaimar hat folgendes geschrieben :

Meine Meinung: Liege ich hinten, gehe ich ein Risko ein, und leg noch einen drauf. Liege ich vorne, freu ich mich auf jeden Punkt. Nettes Spiel. Ich kann mir auch vorstellen, das die beste Taktik von der Taktik der Gegner abhängt. Da es sich um ein reines Glücksspiel handelt, würde ich eine adaptive Strategie wählen. Ich kann mich aber auch vollkommen irren. Bei solchen Überlegungen komm ich eh immer ins Schlingern.

Naja, kurz mal überschlagen:

Für 3 Spieler und 150 Punkte zum Gewinnen hast Du (maximal) 18 Mrd. (=150^3*150*12) Spielzüge zu untersuchen und zu bewerten. Also durchaus machbar. Zumal eine ganze Reihe von Spielzügen ja sogar noch wegfallen, weil der Graph in Bezug auf den aktiven Spieler isomorph sein dürfte und zahlreiche der Punkte-der-aktuellen-Runde-Kombinationen nicht benötigt werden

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Zitat:

Ist die Wahrscheinlichkeit nicht bei jedem Wurf gleich, einen Pasch zu würfeln? Es wird doch nicht wahrscheinlicher, je öfter ich würfle, oder? Wenn ich also noch 7 Punkte benötige, ist es egal, ob ich weitergebe oder gleich mein Glück versuche.

Die Wahrscheinlichkeit für den Pasch bleibt immer gleich, was sich ändert sind die Punkte die man verlieren kann.
Beispiel: Vor dem ersten Wurf wird niemand aufhören zu würfeln, da man keine Punkte verlieren kann, hat man aber schon 40 Punkte in einem Zug zusammengewürfelt, dann kann man eben genau diese 40 Punkte wieder verlieren.

Zitat:

Es kann daher überlegenswert sein, eine Runde bereits vorzeitig abzugeben, wenn man im nächsten Zug das Spiel für sich entscheiden kann.

Das hier finde ich noch gut und wichtig, dass es eine zu erreichende Schranke für den Sieg gibt, hatte ich in meinem Post gar nicht bedacht, allerdings weiß ich spontan nicht wie man diese Situation mathematisch ausdrücken kann.

Jann1k hat folgendes geschrieben :

Zitat: Es kann daher überlegenswert sein, eine Runde bereits vorzeitig abzugeben, wenn man im nächsten Zug das Spiel für sich entscheiden kann. Das hier finde ich noch gut und wichtig, dass es eine zu erreichende Schranke für den Sieg gibt, hatte ich in meinem Post gar nicht bedacht, allerdings weiß ich spontan nicht wie man diese Situation mathematisch ausdrücken kann.

Mathematisch: Man ist der führende Spieler und es gibt keinen anderen, bei dem durch Addition der in einer Runde zu erwartenden Punkte die zum Gewinnen benötigte Punktzahl erreicht werden kann.

Ach ja: Hab meine Anzahl zu berechnender Spielzüge noch mal reduziert:



Diese Reduktion ergibt sich durch die angesprochene Isomorphie des Graphen gegenüber der Punktzahl, da die Reihenfolge der Punkte uninteressant ist, solange man unterscheiden kann, welcher der Spieler den aktuellen Zug hat.

Der innerste Term gibt die im aktuellen Zug bereits erhaltenen Punkte an.

Ansonsten bliebe für die Simulation jetzt lediglich noch die Wahrscheinlichkeit einer Transition im Graphen mit dem Spielausgang zu multiplizieren. Schleifen aus 3 Runden ohne zusätzliche Punkte (alle 3 Spieler bleiben wie gehabt) werden mit 0 bewertet, wenn nach einer Runde ein Spieler schlechter dasteht, ist die Wertung des Zuges negativ, ansonsten positiv. Gewinnen sind +(n-1)*1000, Verlieren -1000. Die Wertung eines Zuges ergibt sich aus dem Erwartungswert der Zugmöglichkeiten.

Der Rest sollte über die hinter MinMax stehenden Logik funktionieren.

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Ok, vielen dank für die eifrige Partizipation. Darf ich euch noch bitten das in eine für Idioten lesbare Form bringen, damit ich es auch verstehe.^^ Ich weiß zwar ungefähr was ihr meint, aber nicht so wirklich wie mir das bei einem Würfelspiel, das zufällig zwei zahlen ausspuckt, helfen wird.

lg elundril

This Signature-Space is intentionally left blank.
Bei Beschwerden, bitte den Beschwerdebutton (gekennzeichnet mit PN) verwenden.

Was meinst du jetzt genau? Alles was wir beide bisher gebracht haben oder nur das von BenBe?

Alles wäre ideal, damit ich die disskussion nachvollziehen kann und vielleicht auch zum grübeln angeregt werde.

lg elundril

This Signature-Space is intentionally left blank.
Bei Beschwerden, bitte den Beschwerdebutton (gekennzeichnet mit PN) verwenden.

Hallo

Ich habe mir dazu auch ein paar Gedanken gemacht...

Die wahrscheinlichkeit ein Pansch zu würfeln ist immer gleich, jedoch ist der mögliche Verlust mit jedem wurf zunehmend. Das Risiko ist definiert mit der Wahrscheinlichkeit das die Eintritt (Pansch) * der Schaden der daraus resultiert (Verlust der gesammelten Punkte).

Wieviel Risiko man eingeht hängt vom Spielverlauf ab.
- Am Anfang nimmt man ein mittleres Risiko (ca 30)
- ist man in Führung, reduziert man das Risiko
- ist man hinten muss es etwas mehr Risiko sein
- kommt man wahrscheinlich nicht mehr dran vor Ende der Runde muss man volles Risiko spielen. Ich denke das ist ca ab 120 Punkten...

Wobei die zwei Zahlen die ich genannt habt nur Schätzungen sind. Ich denke mit etwas ausprobieren kommt man auf bessere Werte. Gut wäre es wenn man das Simulieren könnte mit ein paar tausend Runden... Vielleich kommt was ganz anderes raus

Kannst Du uns bitte nachher mitteilen wie Du es gelöst hast, es würde mich interessieren.

Gruss
Bole

Okay, also mein Ansatz ist folgender:

Wir berechnen wie viele Punkte wir im Durchschnitt erhalten würden, wenn wir noch einmal würfeln. Ist dieser Wert positiv, würfeln wir noch einmal (im Schnitt gewinnen wir ja neue Punkte hinzu), ist er negativ hören wir auf und sichern unsere Punkte.

Zur Berechnung des Durchschnittswerts (E(Gewinn)):
Es gibt insgesamt 36 verschiedene Kombinationen wie die beiden Würfel liegen bleiben können (ich unterscheide hier zwischen den beiden Würfeln also W1=3 und W2=5 ist etwas anderes als W1=5 und W2=3).
Haben wir keinen Pasch erwürfelt, gewinnen wir die Augenzahl der beiden Würfel hinzu. Würfeln wir einen Pasch, verlieren wir unsere bisher in diesem Zug erwürfelten Punkte (verlieren heißt hier, dass wir -p Punkte "gewinnen").
Um nun den Durchschnitt daraus zu berechnen, summieren wir alle möglichen Gewinne auf (= 210-6p) und teilen diesen Wert durch die Anzahl der möglichen Würfelergebnisse (=36), im Durchschnitt gewinnen wir also, wenn wir weiterwürfeln, (210-6p)/36 Punkte.

Hier könnten wir eigentlich schon aufhören. Der KI würden wir dann bei jedem neuen Würfeln Folgendes vorgeben: Setze deine in diesem Zug bisher erwürfelten Punkte in (210-6p)/36 ein, ist das Ergebnis positiv würfle weiter, ansonsten höre auf zu würfeln.

Man sieht aber, dass es sich bei dem Graphen zu f(p)=(210-6p)/36 um eine fallende Gerade handelt, d.h. wir können auch direkt berechnen ab wann die Funktionswerte negativ werden. Setzen wir f(p)=0 und stellen die Gleichung nach p um, so ergibt sich das der Graph bei p=35 die x-Achse schneidet. Daraus folgt: Ist p<35 -> f(p)>0 (weiterwürfeln); bei p>35 -> f(p)<0 (aufhören).

Diese KI würfelt also weiter, bis sie 35 Punkte in einem Zug erwürfelt hat, erst ab diesem Wert wird der Verlust durch einen möglichen Pasch so hoch, dass wir unsere Punkte nicht mehr aufs Spiel setzen sollten.

Ich hab auch mal eine Tabelle mit den Werten und Ergebnissen der Würfel angehangen.

BenBE hat folgendes geschrieben :

alzaimar hat folgendes geschrieben : Ist die Wahrscheinlichkeit nicht bei jedem Wurf gleich, einen Pasch zu würfeln? Es wird doch nicht wahrscheinlicher, je öfter ich würfle, oder? Ja, die ist gleich. [...]

Gilt nicht die "Regression zum Mittelwert"? Wenn ich die Pasch's (Päsche, Paschas????) durch die Gesamtanzahl der Würfe teile, wird Q=1/6 herauskommen (Statistik, haben wir ja auch schon festgestellt). Nehmen wir an, dass das der erste Wurf ein Nicht-Pasch ist, dann gilt Q=1. Der Mittelwert muss allerdings Q=1/6 sein, in den folgenden Zügen würde die Wahrscheinlichkeit größer, einen Pasch zu würfeln.

Das kann man auch an einem Baumdiagramm zeigen, oder mit dem Ansatz: Die Wahrscheinlichkeit p nach n Zügen keinen Pasch gewürfelt zu haben, liegt bei p=(1-1/6)^n = (5/6)^n. Je größer n, desto kleiner p...

Ich folgere daraus, dass die Chance einen Pasch zu würfeln mit der Anzahl der aufeinanderfolgenden Würfe zusammenhängt.

Gruss,

Lukas

weiterführende Literatur:
"Mit an Wahrscheinlichkeit grenzender Sicherheit", Hans-Hermann Dubben und Hans-Peter Beck-Bornholdt, rororo science
de.wikipedia.org/wik...Regression_zur_Mitte

Zitat:

Das kann man auch an einem Baumdiagramm zeigen, oder mit dem Ansatz: Die Wahrscheinlichkeit p nach n Zügen keinen Pasch gewürfelt zu haben, liegt bei p=(1-1/6)^n = (5/6)^n. Je größer n, desto kleiner p...

Das stimmt, aber hier treffen wir die Entscheidung nach jedem Wurf erneut d.h. n bleibt immer 1 und somit bleibt auch P(Pasch) = 1/6. Kann man auch mit bedingten Wahrscheinlichkeiten sehen P(kein Pasch im zweiten | kein Pasch im ersten) ist gleich P(kein Pasch im zweiten und kein Pasch im ersten) / P(Kein Pasch im ersten) = (5/6)*(5/6)/(5/6) = 5/6.

Zitat:

Ich folgere daraus, dass die Chance einen Pasch zu würfeln mit der Anzahl der aufeinanderfolgenden Würfe zusammenhängt.

Nein, woher soll denn der Würfel wissen, was er die letzten Male gewürfelt hat? Die einzelnen Würfe sind unabhängig voneinander.

BenBE hat folgendes geschrieben :

Jann1k hat folgendes geschrieben : Zitat: Es kann daher überlegenswert sein, eine Runde bereits vorzeitig abzugeben, wenn man im nächsten Zug das Spiel für sich entscheiden kann. Das hier finde ich noch gut und wichtig, dass es eine zu erreichende Schranke für den Sieg gibt, hatte ich in meinem Post gar nicht bedacht, allerdings weiß ich spontan nicht wie man diese Situation mathematisch ausdrücken kann. Mathematisch: Man ist der führende Spieler und es gibt keinen anderen, bei dem durch Addition der in einer Runde zu erwartenden Punkte die zum Gewinnen benötigte Punktzahl erreicht werden kann. Ach ja: Hab meine Anzahl zu berechnender Spielzüge noch mal reduziert: markieren Quelltext     1: sum(p1=0..150,sum(p2=0..p1,p2<150,sum(p3=0..p2,12*sum(i=1..3,150-p_i+1)))) Diese Reduktion ergibt sich durch die angesprochene Isomorphie des Graphen gegenüber der Punktzahl, da die Reihenfolge der Punkte uninteressant ist, solange man unterscheiden kann, welcher der Spieler den aktuellen Zug hat. Der innerste Term gibt die im aktuellen Zug bereits erhaltenen Punkte an. Ansonsten bliebe für die Simulation jetzt lediglich noch die Wahrscheinlichkeit einer Transition im Graphen mit dem Spielausgang zu multiplizieren. Schleifen aus 3 Runden ohne zusätzliche Punkte (alle 3 Spieler bleiben wie gehabt) werden mit 0 bewertet, wenn nach einer Runde ein Spieler schlechter dasteht, ist die Wertung des Zuges negativ, ansonsten positiv. Gewinnen sind +(n-1)*1000, Verlieren -1000. Die Wertung eines Zuges ergibt sich aus dem Erwartungswert der Zugmöglichkeiten. Der Rest sollte über die hinter MinMax stehenden Logik funktionieren.

Sorry, den Post check ich gar nicht. Könntest du mir den nochmal einfacher erklären? Ich hab bei Wikipedia jetzt nach MinMax und dessen Verbesserung, die Alpha-Beta-Suche, gesucht, aber irgendwie weiß ich nicht wie ich das mit meinem problem verknüpfen soll.

Jann1k hat folgendes geschrieben :

Okay, also mein Ansatz ist folgender: Wir berechnen wie viele Punkte wir im Durchschnitt erhalten würden, wenn wir noch einmal würfeln. Ist dieser Wert positiv, würfeln wir noch einmal (im Schnitt gewinnen wir ja neue Punkte hinzu), ist er negativ hören wir auf und sichern unsere Punkte. Zur Berechnung des Durchschnittswerts (E(Gewinn)): Es gibt insgesamt 36 verschiedene Kombinationen wie die beiden Würfel liegen bleiben können (ich unterscheide hier zwischen den beiden Würfeln also W1=3 und W2=5 ist etwas anderes als W1=5 und W2=3). Haben wir keinen Pasch erwürfelt, gewinnen wir die Augenzahl der beiden Würfel hinzu. Würfeln wir einen Pasch, verlieren wir unsere bisher in diesem Zug erwürfelten Punkte (verlieren heißt hier, dass wir -p Punkte "gewinnen"). Um nun den Durchschnitt daraus zu berechnen, summieren wir alle möglichen Gewinne auf (= 210-6p) und teilen diesen Wert durch die Anzahl der möglichen Würfelergebnisse (=36), im Durchschnitt gewinnen wir also, wenn wir weiterwürfeln, (210-6p)/36 Punkte. Hier könnten wir eigentlich schon aufhören. Der KI würden wir dann bei jedem neuen Würfeln Folgendes vorgeben: Setze deine in diesem Zug bisher erwürfelten Punkte in (210-6p)/36 ein, ist das Ergebnis positiv würfle weiter, ansonsten höre auf zu würfeln. Man sieht aber, dass es sich bei dem Graphen zu f(p)=(210-6p)/36 um eine fallende Gerade handelt, d.h. wir können auch direkt berechnen ab wann die Funktionswerte negativ werden. Setzen wir f(p)=0 und stellen die Gleichung nach p um, so ergibt sich das der Graph bei p=35 die x-Achse schneidet. Daraus folgt: Ist p<35 -> f(p)>0 (weiterwürfeln); bei p>35 -> f(p)<0 (aufhören). Diese KI würfelt also weiter, bis sie 35 Punkte in einem Zug erwürfelt hat, erst ab diesem Wert wird der Verlust durch einen möglichen Pasch so hoch, dass wir unsere Punkte nicht mehr aufs Spiel setzen sollten. Ich hab auch mal eine Tabelle mit den Werten und Ergebnissen der Würfel angehangen.

Der Ansatz ist nicht schlecht, nur leider schaff ich mit der Vorgangsweise nur einen Prozentsatz an gewonnenen Spielen von rund 50%-52%. Blöderweise hat der beste aus unserer Vorlesung einen Gewinnprozentsatz von 60%.

Lg elundril

This Signature-Space is intentionally left blank.
Bei Beschwerden, bitte den Beschwerdebutton (gekennzeichnet mit PN) verwenden.

Zum ersten Teil meiner Aussage: Du liegst in Führung und keiner deiner Verfolger hat X-35 Punkte (Deine Punktzahl).

Ansonsten zum zum zweiten Teil meines Posts: Du rechnest das Spiel (bzw. alle Spielsituationen, sind nicht soooo viele) einmal vollständig durch und merkst Dir für jeden der Spieler und die Anzahl der bereits gewürfelten Punkte, ob er fortsetzen sollte zu würfeln, bzw. mit welcher Wahrscheinlichkeit er dies tun sollte). Danach kannst Du für jeden Zug einfach im Vorfeld in diese Tabelle schauen, wo Du basierend auf der Spielsituation und deiner bereits gewürfelten Punktzahl nachschauen kannst, ob Du durch Fortsetzen des Würfelns deine Gewinnchance erhöhst oder senkst.

Ist so ein wenig der BruteForce-Ansatz, aber er sollte passen. Im Zweifelsfalle dürfte sogar das Betrachten der Gewinnwahrscheinlichkeit bei mehr als 3 Spielern dadurch möglich sein, nur die 3 Führenden zu betrachten (bzw. zwei führenden und den eigenen Spieler, wenn 4. oder weiter hinten).

Der Rest vom Post sind ein paar mathematische Überlegungen, wie man die Zugtabelle stark reduzieren kann vom Umfang.

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.