Schneller Zufallsgenerator für Monte Carlo
-
Analytisch kann man nur so Dinge wie "Wie häufig kommt ein Flush an?" o.ä. berechnen. Wenn es wirklich um Gewinn/Verlust/Split geht, gibt es zu viele unterschiedliche Fragestellungen. Ist jedenfalls äußerst komplex da etwas zu erarbeiten, habe das Mal probiert, aber ist alles andere als trivial.
SeppJ: Hm, und würdest Du mein Szenario als komplex betrachten? Die Berechnung ist ja nicht so besonders komplex.
Nexus: Sieht interessant aus, das werde ich mal ausprobieren.
-
Rein gefühlsmäßig sollte man dein Problem mit Durchprobieren aller Möglichkeiten in hinnehmbarer Zeit lösen können, insbesondere wenn man ähnliche Fälle (und von denen gibt es sehr viele) gemeinsam abhandelt. Hast du das mal ausprobiert?
-
Eisflamme schrieb:
SeppJ: Hm, und würdest Du mein Szenario als komplex betrachten? Die Berechnung ist ja nicht so besonders komplex.
Nein. Aber die Fragestellung ist doch auch sicherlich keine, über die du später einen wissenschaftlichen Artikel schreiben und die Ergebnisse veröffentlichen wirst.
-
Michael E.: Na ja, ich wüsste nicht, wie man das Zusammenfassen soll. Es gibt bei fast jeder Handstärke noch eine Tendenz. Selbst, wenn beide Spieler das gleiche Paar haben, entscheidet letztlich der Kicker. Außer auf dem Board sind alle Nicht-Paar-Karten höher als dieser... Und so kann man sich für quasi alle Fälle etwas basteln. Darüber hinaus löst es keine Software in dieser "Branche" analytisch. Könnte man es so lösen, hätte das sicher schon jemand gemacht. Und wenn nicht, aber es ginge, so wäre ich der letzte, der es so lösen könnte.
SeppJ: Ne, sowieso nicht. Mir geht es nur darum, ob eben die Minimalanforderungen an Monte-Carlo auch für mein Szenario ausreichen, sodass eben der hier im Thread aufgeführte Algorithmus genügt.
-
Mersenne Twister ist sehr sehr schnell und für Monte-Carlo Simulationen gut geeignet.
-
Hi,
habe Mersenne Twister probiert und komme auf meine 1 Mio. Berechnungen pro Sekunde, bin also sehr zufrieden, vielen Dank.
Den Rest habe ich gar nicht erst getestet.
Viele Grüße,
Eisflamme
-
Eisflamme schrieb:
Den Rest habe ich gar nicht erst getestet.
Solltest du aber. Der MT ist ehrlich gesagt nicht soooo schnell, selbst verglichen mit anderen "guten" Zufallsgeneratoren. Erst recht, wenn du ihn mit einem ultra-einfachen Generator vergleichst. Irgendwie sehe ich nicht, was hier gegen einen linearen Kongruenzgenerator spricht.
-
Hm, nagut, da kommt halt noch dazu, dass ich vermute, dass der Zufallsgenerator tatsächlich nicht der Flaschenhals ist. Denn die iterative Variante ist in etwa genau so schnell. Ich bin auch einfach nicht sehr in der Zufallstheorie drin. Die Zufallszahlen sollen möglichst zufällig sein, umfassen jedoch einen Zahlenraum von <1 Mio. Einträgen.
-
Eisflamme schrieb:
Hm, nagut, da kommt halt noch dazu, dass ich vermute, dass der Zufallsgenerator tatsächlich nicht der Flaschenhals ist.
Das heißt, du hast optimiert, ohne vorher zu messen. Das macht man einfach nicht.
Denn die iterative Variante ist in etwa genau so schnell. Ich bin auch einfach nicht sehr in der Zufallstheorie drin. Die Zufallszahlen sollen möglichst zufällig sein, umfassen jedoch einen Zahlenraum von <1 Mio. Einträgen.
Ein Münzwurf hat auch nur zwei Werte, ist aber eine Quelle für hochwertige Zufallszahlen. Der Zahlenbereich sagt überhaupt nichts aus.
-
SeppJ schrieb:
Eisflamme schrieb:
Den Rest habe ich gar nicht erst getestet.
Solltest du aber. Der MT ist ehrlich gesagt nicht soooo schnell, selbst verglichen mit anderen "guten" Zufallsgeneratoren. Erst recht, wenn du ihn mit einem ultra-einfachen Generator vergleichst.
Link bitte, sonst glaub ich das mal einfach nicht.
ps: Ich begründe meine Aussage hierauf: http://www.boost.org/doc/libs/1_51_0/doc/html/boost_random/performance.html
-
SeppJ:
Den Algorithmus hatte ich schon vorher optimiert, weil ich ihn erst ohne Monte Carlo liefen ließ, da ich dachte, dass das reicht. Es zeigt sich jedoch, dass es Szenarien gibt, in denen die Laufzeit zu lang wäre, da liefert aber Monte Carlo super Annäherungen.Dass der Zahlenbereich nichts sagt, ist ja ok... ich dachte, vielleicht hilft dieses Detail irgendwie.
-
Wichtig ist die Periodenlänge die du brauchst, und in wie vielen Dimensionen die Zahlen gleichverteilt sein müssen.
MT ist bei beiden Kriterien ziemlich gut.
Und sollte IMO ausreichend schnell sein.
-
hustbaer schrieb:
ps: Ich begründe meine Aussage hierauf: http://www.boost.org/doc/libs/1_51_0/doc/html/boost_random/performance.html
Komisch, ich auch.
Alternativ auch hier:
http://www.gnu.org/software/gsl/manual/html_node/Random-Number-Generator-Performance.htmlWas spricht denn beispielsweise gegen TAUS? Ist auch ein sehr guter Generator.
-
SeppJ schrieb:
hustbaer schrieb:
ps: Ich begründe meine Aussage hierauf: http://www.boost.org/doc/libs/1_51_0/doc/html/boost_random/performance.html
Komisch, ich auch.
naja, wir reden hier von <10% performance unterschied zum absolut schnellsten gemessen Generator. Im Vergleich zu der Bandbreite die die Generatoren da haben ist es für mich reichlich übertrieben zu bhaupten, dass der MT nicht "sooo schnell" ist. Im Gegenteil. dafür dass er eine viel viel längere Zykluslänge erreicht und in hochdimensionalen räumen noch gute Resutlate erzielt, sind 7% gar nichts.
-
Eine dumme Frage. Welche Anforderungen stellen sich neben der Geschwindigkeit an den Zufallsgenerator?
Wäre es auch denkbar den RC4 Algorithmus als eine Zufallszahlengenerator zu missbrauchen?
-
Bitte ein Bit schrieb:
Eine dumme Frage. Welche Anforderungen stellen sich neben der Geschwindigkeit an den Zufallsgenerator?
Das kommt eben drauf an
. Bei den meisten MC-Simulationen sind die Anforderungen sehr gering:
- Die Verteilung der Zufallszahlen sollte stimmen. In den meisten Fällen will man also, dass der Generator statistischen Tests auf Gleichverteilung genügt, daraus kann man sich dann beliebige andere Verteilungen berechnen.
- Die Periodenlänge (falls der Generator eine Periode hat) sollte in der gleichen Größenordnung oder größer als die Zahl der (insgesamt) benutzten Zufallszahlen sein. Auf keinen Fall will man eine Periodenlänge in der Größenordnung eines "Schritts" (was auch immer dies genau für die konkrete Simulation heißt) oder gar kürzer. Dies schließt für viele Simulationen die gaaaaanz einfachen Generatoren aus den 60er Jahren aus.
- Die Zahlen sollten möglichst "zufällig" sein. Die Definition davon ist ein bisschen heikel. Sagen wir: Die Zahlen sollten möglichst viele statistischen Tests auf genügen, denen auch echte Zufallszahlen genügen. Dazu testet man in der Regel Korrelationen zwischen Zahlen und Zahlenpaaren.Insgesamt kommt man bei MC mit erstaunlich viel Schluderei davon. Wichtig ist, dass man richtig sampled und überhaupt das Modell stimmt. Selbst da kann man ein bisschen pfuschen, wenn man weiß, was man tut. Einen LCG würde ich aber dennoch nicht nehmen. Da ist unmittelbar ersichtlich, dass die Hyperflächenverteilung zu Problemen führen könnte und es ist nicht so, als gäbe es keine Alternativen.
Wäre es auch denkbar den RC4 Algorithmus als eine Zufallszahlengenerator zu missbrauchen?
Klar, warum nicht? Ist aber totaler Overkill.
-
Also da ich mit diesem Algorithmus nur Zahlen aus Arrays picken möchte, generiere ich lediglich einen zufälligen Index. Dieser liegt im Bereich von 0 bis (52 über 5). Hilft das irgendwie?
-
Eisflamme schrieb:
Hallo,
es handelt sich um ein Poker-Analyseprogramm, bei dem die Boards ausgewertet werden sollen. "Boards" sind dabei die 5 Karten in der Mitte. Somit handelt es sich um 52 über 5 Möglichkeiten. Diese Möglichkeiten sollen über den Zufallsgenerator ermittelt werden, denn Ziel ist es zu berechnen, wie häufig mehrere Spieler mit unterschiedlichen Händen gewinnen. Dabei kann Spieler 1 z.B. 100 unterschiedliche Handkombinationen halten, Spieler 2 100 andere. Dann haben wir schon 100 * 100 * (48 über 2) Berechnungen. Und das Szenario mit nur zwei Spielern und nur 100 Kombinationen pro Spieler ist optimistisch.
Was willst du berechnen? Die Wahrscheinlichkeit, dass einer gewinnt, obwohl du nicht weißt, was für Karten alle haben?
Geht doch garnicht.
-
Geht wohl, wenn man deren Hände eingrenzen kann. Man muss nicht die genaue Hand kennen, es reicht auch eine Range von möglichen Händen. Auch wenn ein Spieler eine zufällige Hand hält, lässt sich die Wahrscheinlichkeit berechnen. Halten beide zufällige Hände, ist Gewinn + Split/2 natürlich 50%.
