Würfel Analyse

  • Mike schrieb:

    anstelle einer langen Folge von 2^32 Zahlen gibt es jetzt zehntausende von Zyklen mit teilweise nur ~58000 bzw. ~750 verschiedenen Zahlen, andere Zahlen werden je nach Seed nur einmal erzeugt und danach nie mehr (der Generator läuft dann in einen der genannten Zyklen ein).
    Was muss passieren, dass sowas eintritt, bzw. was muss man machen, damit sowas nicht eintritt? Passiert das nur, wenn du den Generator viele tausend mal aufrust oder hängt das auch mit der Startfolge zusammen?
  • RND() befindet sich *immer* entweder in einem (relativ kurzen) Teilstück, das nur einmal durchlaufen wird und dann in einen der genannten Zyklen einläuft, oder in so einem Zyklus selbst. Dabei ist es egal, welchen Seed Du verwendest - da kannst nichts dran ändern. Nur einen anderen, hoffentlich besseren RNG verwenden.

    Ich hab' sogar schon mal geschaut, ob es nicht evtl. einen Seed gibt, wonach RND(1) nur noch immer dieselbe Zahl auswirft (also ein Fixpunkt der Folge), bin aber (noch) nicht fündig geworden...

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von Mike ()

  • Mike schrieb:

    da kannst nichts dran ändern
    Schade, ich dachte mit dem "Aufwärmen" des Generators durch die 100.000 Aufrufe, hättest du ihn damit anfälliger gemacht in diesen Teufekskreis zu geraten.

    Das bedeutet also, im schlimmsten Fall hat man nur eine Zahlenfolge von rund 750 Werten - danach wiederholt sie sich, ohne dass man es beeinflussen kann, oder?

    Was mir dabei aber gerade eingefallen ist, dass ich in meiner Technik anfangs (nachdem ich die Startfolge per Rasterzeile x Timer gebildet habe) ein Logik vorgeschaltet habe, die die Register $8B...$8F manipuliert. Könnte das der Grund sein, warum mir eigentlich nie was Schlimmes aufgefallen ist?

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von DATA-LAND ()

  • Hmm... Nach Mikes ausführlichen Erläuterungen stellt sich für mich die Sache folgendermaßen dar:
    1.) Der Algorithmus ist fehlerhaft, und je nach verwendetem Seed endet er mehr oder weniger schnell in einer Schleife mit nur wenigen Werten. Das bedeutet, man kann ihn nicht zu Beginn mit einem pseudozufälligen Startwert füttern (z. B. Wartezeit bis zum Tastendruck), da sich dann eventuell der Fehler allzu schnell bemerkbar macht.
    2.) Die Routine befindet sich im Rom. Das mag bei kleinen Programmen in Ordnung sein. Bei größeren, die die vollen 64kb verwenden und dazu den IRQ bei $fffe umlenken sowie den Vektor bei $314 umgehen, ist das Einblenden des Roms reichlich umständlich und erfordert unnötigen zusätzlichen Aufwand. Außerdem verwendet die Romroutine Speicherzellen in der Zeropage, was eine freie Belegung dieses wichtigen Bereichs erschwert.
    3.) Für die meisten hier wahrscheinlich nicht so wichtig, aber für verschrobene Typen wie mich, die sich auch gelegentlich mal an anderen Systemen probieren, ist die Verwendung einer Romroutine in einem für die Spielmechanik relevanten Codeteil, da sich dies nachteilig auf eine Portierung des Codes auf weitere Rechner auswirkt. Auch für das Entwickeln von Routinen zunächst auf dem PC (mit anschließender Übertragung auf den C64) sind Romroutinen ungeeignet.
    Fazit: Es gibt keinen Grund, auf RND zurückzugreifen, aber sehr viele Gründe einen PRNG z. B. aus Codebase zu verwenden.
  • @Mike und M.J.: Bitte nicht falsch verstehen - ich stelle nicht eure Aussagen und Kenntnisse in Frage, aber ich chabe nun schon mehrere Versuche unternommen zu erfahren, wann und wie der besagte ROM Fehler auftritt, aber der CeVi, bzw. der RND Befehl hält bis jetzt jeder Bewährungsprobe stand. Habe heute am späten Nachmittag eine "6 aus 49" Lotto Simulation geschrieben. Lt. einer Statistik, kommen 3 Richtige alle 57 mal vor. Konnte es aus zeitlichen Gründen aber nur 1 x testen. Ich brauchte ca. 30 Versuche mit 2 "Kästchen" gleichzeitig - also hier wieder genau das gleiche - zufallsmäßig alles im grünen Breich! Es ist zum Mäuse melken...

    M. J. schrieb:

    Die Routine befindet sich im Rom.
    Meine Kodes sind eng mit den ROMs verwoben, weil ich viele Funktionen nutze. Von Haus aus sind eigentlich nur 5 Adressen in der ZP frei, wenn man aber auf Kassette oder RS-232 verzichtet, kann man diese nutzen - das tut allerdings auch JiffyDOS, sodaß ca. 8 Pärchen für den User übrigbleiben. Die haben aber bis jetzt für all meine Projekte gereicht und so bleibt alles kompatibel zu den ROM Routinen - auf sie verzichten möchte ich nicht!

    M. J. schrieb:

    Es gibt keinen Grund, auf RND zurückzugreifen, aber sehr viele Gründe einen PRNG z. B. aus Codebase zu verwenden.
    Zum einen verwende ich ungern "fremden Kode" aus folg. Gründen:
    - Es macht viel Spaß selber herum zu tüfteln und die daraus entstehenden Erfolgserlebnisse schmieden eine enge Beziehung zum System. Listings abtippen, hat mir schon in BASIC keinen Spaß gemacht. Das Schöne am Koden ist ja gerade die Knobelei und die Erfolgserlebnisse! :)
    - Bei eigenen Entwicklungen kann man die Arbeitsweise am besten nachvollziehen
    - Jehr mehr und länger man programmiert, desto besser und erfahrener wird man automatisch. Hätte ich meistens nur gerippt, hätte ich nie richtig laufen gelernt.

    Und wie gesagt, eigentlich hatte mir RND bis jetzt keinen Ärger gemacht.

    Zum anderen will ich mich aber einer besseren PRNG Technologie nicht verschließen. Ich müsste aber einerseits wissen, wieviel RAM diese verschlingt und anderseits bräuchte ich eine Empfehlung. Hättest du einen Link zu einem bewährten und ausgereiften Algorithmus? Dann kann ich wieder von vorne anfangen in Sachen Test auf Gleichverteilung usw... ^^
  • DATA-LAND schrieb:

    Zum anderen will ich mich aber einer besseren PRNG Technologie nicht verschließen. Ich müsste aber einerseits wissen, wieviel RAM diese verschlingt und anderseits bräuchte ich eine Empfehlung. Hättest du einen Link zu einem bewährten und ausgereiften Algorithmus? Dann kann ich wieder von vorne anfangen in Sachen Test auf Gleichverteilung usw...
    Siehe meine Postings, in der CodeBase gibt es einige ausgereifte (und wirklich kleine) Codes zu dem Thema.
    GREETINGS PROFESSOR FALKEN
    A STRANGE GAME.
    THE ONLY WINNING MOVE IS NOT TO PLAY.
    HOW ABOUT A NICE GAME OF CHESS?
  • BladeRunner schrieb:

    Siehe meine Postings, in der CodeBase gibt es einige ausgereifte (und wirklich kleine) Codes zu dem Thema.
    Ja ich weiß, wir hatten ja neulich kurz über einen PRNG gesprochen. Dachte aber, dass sich evtl. einer durchgesetzt hat. In den nächsten 1, 2 Wochen möchte ich die Tests aber auch noch mit dem SID als Zufallsquelle vergleichen. Da bin ich besonders auf den Langzeittest gespannt...

    Das wirklich Blöde an der ganzen Sachen ist halt, wenn der BASIC RND arbeitet und nicht vorzeitig in diesen Zyklus endet, macht er einen guten Job. Den muss der SID erst noch bestehen!
  • Der SID hat *INTERN* einen fixen Zyklus von 2^12 -1 (= 4095) Werten.

    Da Du aber nicht bei jedem Clock ausliest und auch nur 8 der 12 Bit bekommst, wirst du das erstmal nicht bemerken.

    Warum also nicht selbst ein LFSR "bauen" und den Wertebereich entsprechend beschneiden?
    Beispiele gab es ja genug!? Wobei es wesentlich bessere (auch auch langsamere) PRNG gibt!


    DATA-LAND schrieb:

    Zum einen verwende ich ungern "fremden Kode" aus folg. Gründen:

    Not-invented-here Problem?

    Dieser Beitrag wurde bereits 6 mal editiert, zuletzt von androSID ()

  • DATA-LAND schrieb:

    androSID schrieb:

    Not-invented-here Problem?
    Speak German only, please! ;)
    Habe aufgrund deines Beitrags gestern in der "Bibel" gelesen (lila Intern). Was ich nicht 100% heraushören konnte: Verliere ich zwangsläufig eine Stimme für die Zufallszahlennutzung?
    Ja. Die Stimme ist zumindest nicht mehr frei benutzbar: Du musst z.B. die "Noise" Waveform eingeschaltet haben,
    um die Zufallszahlen zu erhalten.

  • BladeRunner schrieb:

    Hoogo schrieb:

    BladeRunner schrieb:

    Über die Strecke von 00-ff bei jeder Zahl einmal kommt auch Modulo 6 immer in Gleichversteilung heraus.
    Imho nur, wenn 00-ff eine durch 6 Teilbare Anzahl wäre. Bei 255 bleibt aber ein Rest von 3, die Zahlen 4-6 kommen daher 1mal seltener vor.
    Siehe dazu meine Postings vorher - die Verteilung ist nicht komplett gleichförmig, sondern liegt bei 43:43:43:43:42:42. Modulo ergibt ebenfalls diese Verteilung- nicht komplett eben, aber sehr nahe dran. Um das zu umgehen müsste ein Algorithmus direkt nur sechs Zahlen generieren. Da aber eigentlich alle Zufallszahlen im Rechner auf Berechnungen aufbauen und der nunmal im Binärsystem arbeitet wird das schwierig. Der vorgestellte Algo ist schnell und bietet im Binärraum eine Gleichverteilung aller Ergebnisse, das ist schonmal nicht schlecht.Man könnte noch alle $ff Durchläufe zum Ergebnis (also vor dem Modulo) eins mehr addieren, damit verschiebt sich dann die Verteilung immer um eine Spalte nach rechts, also bei der ersten Addition zu 42:43:43:43:43:42, usf.
    Immer noch nicht perfekt, aber auf Dauer nivelliert sich das dann.
    Im Grunde sollte sich nach dem Gesetz der großen Zahlen der Statistik bei nach Unendlich gehenden Würfen die Gleichverteilung einstellen. Nur bei RND mit einem gewissen Zyklus, der nicht durch 6 teilbar ist, bekommt ein Teil der Wurfzahlen auch im Unendlichen immer zu wenig als andere. Deswegen würde ich postulieren, dass sich das auch auf Dauer nicht nivelliert ...
  • androSID schrieb:

    Tale-X schrieb:

    Ja, kann sehr gut hinkommen, dass das Rauschen im SID künstlich generiert wird... mir fiel gestern abend noch ein, dass der SID bei der Tonerzeugung digital arbeitet (Wellenformen sind als "Wavetables" hinterlegt), so dass das Rauschen auch nicht unbedingt von einem Transistor kommen muss. Wobei ich an Rauschen als eine Wellenform in der Tabelle gedacht habe (die Lösung ist sicher nur 2-3 google-Suchen entfernt)
    Der VICE arbeitet in dieser hinsicht exakt; das Rauschen des SID - das in der Tat mit einem 12Bit-LFSR generiert wird - wird dort 1:1 simuliert.
    Von dem LFSR sind dann 8 bestimmte Bits via Registerzugriff auslesbar.

    Die Wellenformen sind NICHT als Wavetable abgelegt!

    Ein Oszillator im SID ist im Grunde "nur" ein Zähler, dessen Wert um den Inhalt der beiden Freq-Register erhöht wird.
    Die obersten 12 Bits dieses Zählers werden dann, je nach eingestellter Wellenform, logisch miteinander verknüpft* und auf
    einen D/A-Wandler gegeben.
    [..]
    Ahaa. Das erklärt dann für mich auch das gewisse Muster, wenn man den Rauschgenerator schnell ausliest und z.B. ein X-Y-Plot daraus macht, z.B. wie im Programm random-plot.prg Ich hab da die Oszillatorfrequenz aufs Maximum gesetzt, was vielleicht gar nicht so gut ist. Meine erste Vermutung war ja, dass die Frequenz etwas mit dem Häufigkeit der Wertänderung zu tun haben könnte ... dem oben genannten also nicht. Vielleicht ist es besser eine Primzahl zu nehmen, um ein Muster zu vermeiden?
  • JeeK schrieb:

    BladeRunner schrieb:

    Hoogo schrieb:

    BladeRunner schrieb:

    Über die Strecke von 00-ff bei jeder Zahl einmal kommt auch Modulo 6 immer in Gleichversteilung heraus.
    Imho nur, wenn 00-ff eine durch 6 Teilbare Anzahl wäre. Bei 255 bleibt aber ein Rest von 3, die Zahlen 4-6 kommen daher 1mal seltener vor.
    Siehe dazu meine Postings vorher - die Verteilung ist nicht komplett gleichförmig, sondern liegt bei 43:43:43:43:42:42. Modulo ergibt ebenfalls diese Verteilung- nicht komplett eben, aber sehr nahe dran. Um das zu umgehen müsste ein Algorithmus direkt nur sechs Zahlen generieren. Da aber eigentlich alle Zufallszahlen im Rechner auf Berechnungen aufbauen und der nunmal im Binärsystem arbeitet wird das schwierig. Der vorgestellte Algo ist schnell und bietet im Binärraum eine Gleichverteilung aller Ergebnisse, das ist schonmal nicht schlecht.Man könnte noch alle $ff Durchläufe zum Ergebnis (also vor dem Modulo) eins mehr addieren, damit verschiebt sich dann die Verteilung immer um eine Spalte nach rechts, also bei der ersten Addition zu 42:43:43:43:43:42, usf.Immer noch nicht perfekt, aber auf Dauer nivelliert sich das dann.
    Im Grunde sollte sich nach dem Gesetz der großen Zahlen der Statistik bei nach Unendlich gehenden Würfen die Gleichverteilung einstellen. Nur bei RND mit einem gewissen Zyklus, der nicht durch 6 teilbar ist, bekommt ein Teil der Wurfzahlen auch im Unendlichen immer zu wenig als andere. Deswegen würde ich postulieren, dass sich das auch auf Dauer nicht nivelliert ...
    Grundsätzlich ja, da ja der Wertebereich in der Tat nicht 2^n entspricht, durch die fortlaufende Addition pro Reihe jedoch wird durch die Verschiebung dessen was Modulo auswirft zumindest eine Verbesserung erzielt:
    1 Reihe: 43-43-43-43-42-42
    2 Reihe: 42-43-43-43-43-42
    3 Reihe: 42-42-43-43-43-43
    4 Reihe: 43-42-42-43-43-43
    5 Reihe: 43-43-42-42-43-43
    6 Reihe: 43-43-43-42-42-43
    usf
    Das Heisst alle 6 Reihen ist eine Gleichverteilung eingestellt, danach verschiebt sich wieder die Verteilung zu Ungunsten zweier Würfelergebnisse bis die 6 Reihen komplett sind.
    Wenn man es nun perfektionieren wollte, lässt man die Addition bei einem restlos durch 6 teilbaren Wert enden und beginnt wieder bei 1.
    Bei 255 als Maximum für ein 8-Bit-Register also bei 252. Damit wird dann auch bei langen Reihen eine Gleichverteilung erzwungen.
    Dieser Maximale Additionswert ist also mit dem zu ermittelnden Wertebereich mittelbar verknüpft und lässt sich auch recht schmerzfrei ermitteln.
    Wenn man dann noch den Generator für verschiedene Wertebereiche nutzt wird es eh hinfällig, denn dann ist die Verteilung nicht mehr auf einzelne Wertebereiche zu verfolgen und wird (so denn die ermittelten Zufallswertebereiche nicht einem starren Schema folgen) wirklich zufällig.
    Alternativ (starre Reihenfolgen) erhält jeder Bereich seinen eigenen Generator und man verfährt wie beschrieben mit einer maximalen Addition.
    Für die normale Spieleprogrammierung wird man das aber meist nicht benötigen.

    EDIT: noch besser als bis 252 hochzählen wäre einfach den Conurt bei 6 neu zu starten- das sit ganz schmerzfrei und gewährleistet über die Reihen hinweg eine Gleichverteilung.
    GREETINGS PROFESSOR FALKEN
    A STRANGE GAME.
    THE ONLY WINNING MOVE IS NOT TO PLAY.
    HOW ABOUT A NICE GAME OF CHESS?

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von BladeRunner ()

  • androSID schrieb:

    Ja. Die Stimme ist zumindest nicht mehr frei benutzbar: Du musst z.B. die "Noise" Waveform eingeschaltet haben,
    um die Zufallszahlen zu erhalten.
    Hab vorhin mal ein wenig mit den SID Registern rumgefummelt. Das Schöne ist, es muss in Stimme 3 nur die Wellenform (z.B. Rauschen) eingestellt sein, das sog. Key-Bit kann aber aus bleiben. So wäre die Stimme nicht ganz verloren, da man ein etwaiges Rauschgeräusch für einen Schuss oder eine Explosion noch nutzen und dabei ein und ausschalten kann. Anders siehts wohl mit der Frequenz aus. Wenn ich die verstelle, verschiebe ich wahrscheinlich den Wertebreich der Zufallszahlen mit, oder? Aber komischerwise - egal ob ich im Hi-Byte der Frequenz einen niedrigen oder hohen Wert einstelle - die Zufallszahlen haben als Extreme immer die "0" und die "255" mit drin - also die volle Bandbreite!?

    Gibt es Unterschiede zwischen SID 6581 und 8580 im Zufallszahlenmodus, bzw. in den Zufallszahlen selber??? Hat da jemand Erfahrungen gemacht?

    JeeK schrieb:

    Nur bei RND mit einem gewissen Zyklus, der nicht durch 6 teilbar ist, bekommt ein Teil der Wurfzahlen auch im Unendlichen immer zu wenig als andere. Deswegen würde ich postulieren, dass sich das auch auf Dauer nicht nivelliert ...

    BladeRunner schrieb:

    Für die normale Spieleprogrammierung wird man das aber meist nicht benötigen.
    @JeeK & BladeRunner: Dass es sich auf Dauer bei zigtausend Aufrufen nicht exakt nevelliert, ist nicht so tragisch, finde ich. Die Abweichung, die ich gemessen habe, war unter +/-3 %. Für Spiele ist das völlig ausreichend. Im Gegenteil, wenn wir gemeinsam mit einem 64'er Programm würfeln würden und dies hätte langfristig eine Abweichung von sogar +/- 10% würde uns das wahrscheinlich immer noch nicht auffallen!? Man konzentriert sich ja schließlich auf das Spiel und zählt nicht die Augenstatistik! ;)

    Bsp.: 120 Würfe - statt für jedes Auge exakt 20 x, kommen nun:
    20 x 1
    18 x 2
    22 x 3
    20 x 4
    19 x 5
    21 x 6
    Hat jemand was gemerkt?

    Drum sagte ich ja bereits, die Kriterien für Spiele erfüllt RND vom BASIC V2 auf jeden Fall. Soll heißen, wenn der RND Befehl ordnungsgemäß arbeitet, sind seine Ergebnisse völlig okay. Schlimm wird's halt nur, wenn er in den vom Mike beschrieben Hexenzyklus gerät! :(
  • DATA-LAND schrieb:

    androSID schrieb:

    Ja. Die Stimme ist zumindest nicht mehr frei benutzbar: Du musst z.B. die "Noise" Waveform eingeschaltet haben,
    um die Zufallszahlen zu erhalten.
    Hab vorhin mal ein wenig mit den SID Registern rumgefummelt. Das Schöne ist, es muss in Stimme 3 nur die Wellenform (z.B. Rauschen) eingestellt sein, das sog. Key-Bit kann aber aus bleiben. So wäre die Stimme nicht ganz verloren, da man ein etwaiges Rauschgeräusch für einen Schuss oder eine Explosion noch nutzen und dabei ein und ausschalten kann. Anders siehts wohl mit der Frequenz aus. Wenn ich die verstelle, verschiebe ich wahrscheinlich den Wertebreich der Zufallszahlen mit, oder? Aber komischerwise - egal ob ich im Hi-Byte der Frequenz einen niedrigen oder hohen Wert einstelle - die Zufallszahlen haben als Extreme immer die "0" und die "255" mit drin - also die volle Bandbreite!?
    Gibt es Unterschiede zwischen SID 6581 und 8580 im Zufallszahlenmodus, bzw. in den Zufallszahlen selber??? Hat da jemand Erfahrungen gemacht?

    Der Wertebereich ist 0-255, weil der vorherige Wertebereich (1-4095; 0 fehlt!) surjektiv auf 8Bit abgebildet (gemappt) wird.

    Der Wertebereich ist nicht von der Frequenz abhängig.

    Der einzige Unterschied zw. 6581 u. 8580 ist die Latenz von 1-Clock-cycle zw. starten des RNG und dem ausgelesenen Wert. Dies
    kann benutzt werden, um zuverlässig per Software zu erkennen welcher Baustein verbaut wurde. Spielt aber sonst keine wirkliche Rolle - zumindest von BASIC aus.

  • androSID schrieb:

    Der Wertebereich ist 0-255
    Und er lässt sich in keiner Weise begrenzen, bspw. 0...5?

    androSID schrieb:

    Der Wertebereich ist nicht von der Frequenz abhängig.
    Immerhin - dann ist man in der Frequenz unabhängig.

    androSID schrieb:

    Der einzige Unterschied zw. 6581 u. 8580 ist die Latenz von 1-Clock-cycle zw. starten des RNG und dem ausgelesenen Wert. Dies
    kann benutzt werden, um zuverlässig per Software zu erkennen welcher Baustein verbaut wurde. Spielt aber sonst keine wirkliche Rolle - zumindest von BASIC aus.
    Okay danke, dann wäre das auch geklärt! :)

    Und danke auch an all die anderen, die immer wieder mal zwischendurch Fragen beantwortet oder interessante Beiträge geschrieben haben! ;)
  • Claude Server schrieb:

    Man könnte es mit einer Division versuchen.
    Oder einer Multiplikation.

    Sprich: Sei x der Zufallszahlenwert (0 <= x <= 255), dann wird berechnet: x / 256 * 6. IIRC hat das eine etwas bessere Charakteristik als die Modulo-Operation. Und ich hoffe, dass diese bessere Charakteristik nicht nur ein Zeitvorteil war, weil die Multiplikation schneller ist als die Division, sondern auch in den Zahlen begründet.

    Man, ist das alles lange her. :(

    Das macht im Übrigen ja auch der Zufallszahlengenerator im BASIC: Er interpretiert die Zahl als Zahl zwischen 0 <= x < 1, die dann mit dem Wertebereich multipliziert wird.
  • Claude Server schrieb:

    Man könnte es mit einer Division versuchen.

    strik schrieb:

    Oder einer Multiplikation.

    Hmmm. da kommen dann aber z.T. diese 0...1 Werte heraus, bei denen man dann die zeitintensive Fließkommaarithmetik braucht. Wenn es der Wertebereich erlaubt, könnten man auch "LSRen" ohne dabei eine ungewollte Gewichtung mit einzubauen.
    Bsp.: Wertebereich 0...15 also 4 x LSR.

    Aber trotzdem danke! ;)

    strik schrieb:

    Man, ist das alles lange her.
    Kein Problem - CeVi hat sich gut gehalten! ^^