Schneller Zufallsgenerator für Monte Carlo

Eisflamme

Hallo,

ich möchte gerne eine Monte-Carlo-Simulation anstellen, bei der es darauf ankommt, dass möglichst viele Durchläufe in möglichst kurzer Zeit gemacht werden.

Ich bin jetzt nicht sicher, ob ich rand() oder etwa eine boost-Variante nutzen sollte. Von rand wird ja oft abgeraten, weil die Zufallszahlen "nicht gut" seien oder so. Mir ist Performance aber wichtiger, da ich schon gerne so viele Durchläufe wie möglich hätte.

Hat da jemand eine Empfehlung für mich?

Skym0sh0

im neuen standard sind en paar zufallsgeneratoren drin, glaube ich. da kannst mal nachschauen

cooky451

Jop, neuer Standard.

int main()
{
  std::default_random_engine e((std::random_device()()));
  std::uniform_int_distribution<> d(-100, 100);

  for (unsigned i = 100; i-- != 0; )
    std::cout << d(e) << '\n';
}

Alles hübsch konfigurierbar durch Templates falls du was Spezielleres brauchst, und die "Verteiler" können auch die Ungenauigkeiten die sich bei der % Methode ergeben ausbügeln.
http://en.cppreference.com/w/cpp/numeric/random

SeppJ

Ist in deinem Programm wirklich die Ziehung der Zufallszahlen der Flaschenhals? Hersteller von Zufallsgeneratoren werben zwar immer damit, wie schnell ihr Generator wäre, aber meiner Erfahrung nach muss das System schon quasi trivial sein (so dass man das Ergebnis auch anders berechnen könnte), damit die Zufallszahlen der entscheidende Faktor werden. Miss das erst einmal nach, bevor du dir zu viele Sorgen darum machst.

Eisflamme

Vielen Dank für die Antworten, das werde ich demnächst ausprobieren.

SeppJ:
Ein Ansatz, der ohne Zufallszahlen arbeitet schafft einige Millionen Berechnungen pro Sekunde. Wenn der Zufallsgenerator da nicht der Flaschenhals ist, bin ich extrem zufrieden!

Michael E.

Mehrere Millionen pro Sekunde? Darf man fragen, was du berechnest?

Achtung, Halbwissen: Ich weiß nicht, ob es vorgeschrieben ist, aber so weit ich weiß, benutzen alle Implementierungen von rand() mehr oder weniger einen linearen Kongruenzgenerator und haben eine Periodenlänge von maximal 2^32, meistens schlechter. Dann wiederholen sich deine Zufallszahlen alle paar Sekunden bis Minuten.

Edit: Außerdem liegen durch rand() erzeugte Zahlen üblicherweise auf einer ziemlich niedrigdimensionalen Hyperebene. Daher kann es schnell passieren, dass deine "Zufallszahlen" gar nicht mehr so zufällig sind, wie du es bräuchtest, sodass falsche Ergebnisse rauskommen.

Captain Obvious

Michael E. schrieb:

Außerdem liegen durch rand() erzeugte Zahlen üblicherweise auf einer ziemlich niedrigdimensionalen Hyperebene.

Kannst du für die ganz Doofen unter uns kurz erklären, was das bedeuten soll?

cooky451

https://de.wikipedia.org/wiki/Hyperebene

Unterräume eines Vektorraums bezeichnet, die von genau einem Basisvektor weniger aufgespannt werden als der Gesamtraum

https://de.wikipedia.org/wiki/Kongruenzgenerator#Hyperebenen-Verhalten

Captain Obvious

cooky451 schrieb:

https://de.wikipedia.org/wiki/Hyperebene

Unterräume eines Vektorraums bezeichnet, die von genau einem Basisvektor weniger aufgespannt werden als der Gesamtraum

https://de.wikipedia.org/wiki/Kongruenzgenerator#Hyperebenen-Verhalten

Das habe ich gelesen, verstehe es aber mangels entsprechender Bildung nicht. Ich will wissen, was es praktisch bedeutet. Könnte man einfach sagen, die erzeugten Zahlen bilden ein unerwünschtes Muster? So sieht es zumindest aus.

cooky451

Ja, das bedeutet es. Aber die Definition sollte man eigentlich mit Stoff aus der 12/2 verstehen.

Eisflamme

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.

Die Boards bilde ich dadurch über einen int64 ab, da jedes Bit für eine gesetzte Karte auf dem Board steht. Streng genommen brauche ich natürlich nur 52 Bit bzw. sogar 48 (wobei das unsinnig wäre, weil die jeweilige Spielerhand zu Evaluierungszwecken mit dem Board ver-oder-t wird).

Es wäre also in der Tat nicht sehr angenehm, wenn sich dort Muster wiederholen. Kann man das irgendwie umgehen?

Nexus

Volkard hat mir mal einen Multiply-With-Carry-Zufallsgenerator gezeigt, den ich nun in einer Grafikbibliothek verwende. Sollte relativ schnell sein. Ich weiss aber nicht, ob er den Anforderungen für eine Monte-Carlo-Simulation genügt. Wenn du willst, kannst du ja mal die Die-Hard-Tests laufen lassen

// Zur Verwendung innerhalb Std.Random
class Engine
{
	public:
		typedef std::uint32_t result_type;

	public:
		explicit Engine(std::uint32_t seedVal)
		{
			seed(seedVal);
		}

		std::uint32_t operator() ()
		{
			const std::uint64_t a = 1967773755;

			x = a * (x & 0xffffffff) + (x >> 32);
			return static_cast<std::uint32_t>(x);
		}

		void seed(std::uint32_t seedVal = 0)
		{
			x = seedVal + !seedVal;
		}

		static std::uint32_t min()
		{
			return 0;
		}

		static std::uint32_t max()
		{
			return 0xffffffff;
		}

	private:
		std::uint64_t x;
};

SeppJ

Nexus schrieb:

Ich weiss aber nicht, ob er den Anforderungen für eine Monte-Carlo-Simulation genügt.

Die sind eigentlich erstaunlich gering, solange die Simulation selbst komplex genug ist, so dass kleine Fehler in der Komplexität untergehen. Ein Kongruenzgenerator kann wegen der genannten Korrelationen in bestimmten Fällen nicht ausreichend sein, meistens geht es aber doch. Aber es besteht kein Grund, das Risiko einzugehen. Es gibt bessere Generatoren, zum Beispiel der von dir genannte. Der C++11-Standard kennt auch einen subtract and carry, der ist vom Verhalten ziemlich ähnlich wie Volkards Generator.

P.S.: Poker? Kann man da nicht analytisch berechnen, wie die Chancen stehen?

Eisflamme

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.

Michael E.

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?

SeppJ

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.

Eisflamme

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.

hustbaer

Mersenne Twister ist sehr sehr schnell und für Monte-Carlo Simulationen gut geeignet.

Eisflamme

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

SeppJ

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.