Ich spiele jetzt schon länger ab und zu in der Pause FreeDoku.
Was mir zunehmend auffällt sind verdächtig verwandte Blätter in aufeinander folgenden Spielen.
Die Kombinationen wiederholend sich strukturell manchmal fast mit einem Abstand von 1 bis 4 Spielen).
Auch gibt es ganze Serien von 40 oder 50 Spielen OHNE Armut, dann wieder sind 4 Armute hintereinander.
Weiterhin gibt es Turnier bei denen bekomme ich 98% nur Sch**ss-Blätter während andere Turniere durchweg gute Blätter für mich zeigen.
Ich vermute mal da stimmt was mit dem Zufallszahlengenerator nicht.
Oder der Ableitung der Blättergenerierung basierend auf der Zufallszahl arbeitet nicht korrekt.
Kann das jemand bestätigen?
Vielleicht sollte man man sich die Stelle im Quellecode für die Random Zahlen nochmal genauer anschauen.
Last edit: Thomas 2016-07-03
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Die Zufallszahlen werden nach dem folgenden Algorithmus erzeugt:
x → (7200 * x + 100) modulo 279841
Die Kartenmischung erfolgt folgendermaßen:
Ausgang ist ein sortierter Kartenstapel (Kreuz, Pik, Herz, Karo; As, König, Dame, Bube, Zehn; zum Schluß bei Bedarf die vier Neunen; dann alle Karten nochmal in der Reihenfolge).
Zum Verteilen wird aus den Karten immer eine zufällig rausgezogen (x modulo verbleibende Kartenanzahl) und damit die vier Blätter gefüllt (erst das erste voll, dann das zweite, …). Die vier Blätter werden dann an die Spieler verteilt, ausgehend vom Startspieler.
Wenn das nächste Spiel beginnt, wird der Startwert vom letzten Spiel genommen und 49 Zufallszahlen weitergegangen (48 werden gebraucht, um die Karten zu verteilen). Dies ist dann der Startwert für das nächste Spiel.
Da die Kartenverteilung nicht nur von dem Zufallsgenerator abhängt sondern auch davon, wer das Spiel beginnt, ist ein externes Zufallselement mit enthalten: Die Kartenverteilung für einen Spieler ist anders, wenn ein Blatt geschmissen wird oder wenn ein Solo gespielt wird, bei dem der Startspieler erhalten bleibt. Ein automatisches Untersuchen der Blattqualität ist daher nicht sehr hilfreich, es ist auch abhängig davon, ob mit oder ohne Neunen gespielt wird und ob es Dollen gibt.
Um den Algorithmus etwas zu verändern gibt es zwei Ansatzpunkte:
1) In party/party.cpp, Zeile 684 wird der Startwert für das nächste Spiel ermittelt. Statt
for (unsigned i = 0; i < 49; i++)
wird mit
for (unsigned i = 0; i < 50; i++)
ein anderer Startwert genommen.
Ich teste für die nächste FreeDoko-Version, ob stattdessen auch einfach der Startwert um 1 erhöht werden kann, dann sind die Startwerte der Spiele in der Reihenfolge 10, 11, 12, 13. Damit müsste das erste Problem, falls existent, erledigt sein.
2) In game/game.gameplay.cpp Zeile 1035 werden die Blätter der Spieler gesetzt. Wird
this->players_[(p + this->no(this->startplayer())) % this->number_of_players()]
durch
this->players_[p]
ersetzt, werden die Blätter nicht ausgehend vom Startspieler sondern immer ausgehend vom Spieler unten verteilt.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Ich bin kein Kryptographie- oder Zufallszahlenexperte (aber auch kein völliger Laie ;-), aber ich könnte mir vorstellen, daß der Generator einfach nicht besonders zufällig ist. Warum verwenden Sie nicht einfach die rand()-Funktion aus der stdlib / cstdlib?
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Wir wissen nicht, ob rand() unter verschiedenen Systemen mit demselben Startwert die gleichen Zufallszahlen liefern. Da wir Spiele bislang über den Startwert definieren (zum Beispiel im Fehlerbericht) sind wir auf einen identischen Zufallsgenerator unabhängig vom System angewiesen. Dies haben wir mit unserem eigenen gewährleistet.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Ich habe mir erlaubt, den Algorithmus (ein LCG, woher stammen die Parameter?) zu analysieren.
279841 = 23^4, daher sind alle Zahlen 4-stellig im 23er-System.
Wenn man sich ausgehend von 0 die ersten Zahlen ausgeben läßt
sieht man, daß die 1er-Stelle immer um 8 steigt und nach 3 Iterationen um 1.
(Das hängt damit zusammen, daß 7200 % 23 = 1 und 100 % 23 = 8.)
Bei anderen Moduli sieht die Folge natürlich nicht ganz so regelmäßig aus und insgesamt ist das System wohl genügend chaotisch, daß das nicht unmittelbar auffällt.
Ich spiele jetzt schon länger ab und zu in der Pause FreeDoku.
Was mir zunehmend auffällt sind verdächtig verwandte Blätter in aufeinander folgenden Spielen.
Die Kombinationen wiederholend sich strukturell manchmal fast mit einem Abstand von 1 bis 4 Spielen).
Auch gibt es ganze Serien von 40 oder 50 Spielen OHNE Armut, dann wieder sind 4 Armute hintereinander.
Weiterhin gibt es Turnier bei denen bekomme ich 98% nur Sch**ss-Blätter während andere Turniere durchweg gute Blätter für mich zeigen.
Ich vermute mal da stimmt was mit dem Zufallszahlengenerator nicht.
Oder der Ableitung der Blättergenerierung basierend auf der Zufallszahl arbeitet nicht korrekt.
Kann das jemand bestätigen?
Vielleicht sollte man man sich die Stelle im Quellecode für die Random Zahlen nochmal genauer anschauen.
Last edit: Thomas 2016-07-03
Die Zufallszahlen werden nach dem folgenden Algorithmus erzeugt:
x → (7200 * x + 100) modulo 279841
Die Kartenmischung erfolgt folgendermaßen:
Ausgang ist ein sortierter Kartenstapel (Kreuz, Pik, Herz, Karo; As, König, Dame, Bube, Zehn; zum Schluß bei Bedarf die vier Neunen; dann alle Karten nochmal in der Reihenfolge).
Zum Verteilen wird aus den Karten immer eine zufällig rausgezogen (x modulo verbleibende Kartenanzahl) und damit die vier Blätter gefüllt (erst das erste voll, dann das zweite, …). Die vier Blätter werden dann an die Spieler verteilt, ausgehend vom Startspieler.
Wenn das nächste Spiel beginnt, wird der Startwert vom letzten Spiel genommen und 49 Zufallszahlen weitergegangen (48 werden gebraucht, um die Karten zu verteilen). Dies ist dann der Startwert für das nächste Spiel.
Da die Kartenverteilung nicht nur von dem Zufallsgenerator abhängt sondern auch davon, wer das Spiel beginnt, ist ein externes Zufallselement mit enthalten: Die Kartenverteilung für einen Spieler ist anders, wenn ein Blatt geschmissen wird oder wenn ein Solo gespielt wird, bei dem der Startspieler erhalten bleibt. Ein automatisches Untersuchen der Blattqualität ist daher nicht sehr hilfreich, es ist auch abhängig davon, ob mit oder ohne Neunen gespielt wird und ob es Dollen gibt.
Um den Algorithmus etwas zu verändern gibt es zwei Ansatzpunkte:
1) In party/party.cpp, Zeile 684 wird der Startwert für das nächste Spiel ermittelt. Statt
for (unsigned i = 0; i < 49; i++)
wird mit
for (unsigned i = 0; i < 50; i++)
ein anderer Startwert genommen.
Ich teste für die nächste FreeDoko-Version, ob stattdessen auch einfach der Startwert um 1 erhöht werden kann, dann sind die Startwerte der Spiele in der Reihenfolge 10, 11, 12, 13. Damit müsste das erste Problem, falls existent, erledigt sein.
2) In game/game.gameplay.cpp Zeile 1035 werden die Blätter der Spieler gesetzt. Wird
this->players_[(p + this->no(this->startplayer())) % this->number_of_players()]
durch
this->players_[p]
ersetzt, werden die Blätter nicht ausgehend vom Startspieler sondern immer ausgehend vom Spieler unten verteilt.
Ich bin kein Kryptographie- oder Zufallszahlenexperte (aber auch kein völliger Laie ;-), aber ich könnte mir vorstellen, daß der Generator einfach nicht besonders zufällig ist. Warum verwenden Sie nicht einfach die rand()-Funktion aus der stdlib / cstdlib?
Wir wissen nicht, ob rand() unter verschiedenen Systemen mit demselben Startwert die gleichen Zufallszahlen liefern. Da wir Spiele bislang über den Startwert definieren (zum Beispiel im Fehlerbericht) sind wir auf einen identischen Zufallsgenerator unabhängig vom System angewiesen. Dies haben wir mit unserem eigenen gewährleistet.
Ich habe mir erlaubt, den Algorithmus (ein LCG, woher stammen die Parameter?) zu analysieren.
279841 = 23^4, daher sind alle Zahlen 4-stellig im 23er-System.
Wenn man sich ausgehend von 0 die ersten Zahlen ausgeben läßt
sieht man, daß die 1er-Stelle immer um 8 steigt und nach 3 Iterationen um 1.
(Das hängt damit zusammen, daß 7200 % 23 = 1 und 100 % 23 = 8.)
Bei anderen Moduli sieht die Folge natürlich nicht ganz so regelmäßig aus und insgesamt ist das System wohl genügend chaotisch, daß das nicht unmittelbar auffällt.
Alle Systeme auf Basis der glibc, also alle Linux-Distributionen und cygwin, haben die selbe rand()-Implementierung, die zwar auch nicht perfekt ist (vgl. hier: http://www.mscs.dal.ca/~selinger/random/) aber doch deutlich besser.
OS X benutzt die simple FreeBSD-Implementierung (Park / Miller): https://opensource.apple.com/source/Libc/Libc-997.90.3/stdlib/FreeBSD/rand.c, womit glibc die ersten seed-Werte berechnet.
Da keine Pseudo-Zufallszahlen in Kryptographie-Qualität benötigt werden, würde der vielleicht sogar reichen (2147483647 ist prim):
Woher die Parameter kommen weiß ich nicht mehr, wir haben sie seit dem Anfang. Bei einer Umstellung würde ich wohl (neuer Minimalstandard nach http://en.cppreference.com/w/cpp/numeric/random/linear_congruential_engine) die Parameter 48271 und 2147483647 verwenden.
Ich habe jetzt den Standard-Zufallsgenerator mt19937 eingebaut. Damit sind die Blätter hoffentlich besser verteilt.