Hallo Besucher, der Thread wurde 25k mal aufgerufen und enthält 85 Antworten

letzter Beitrag von Mike am

Würfel Analyse

    Hallo zusammen,


    ich verwende in den Spielen der TMF schon seit Jahren eine speziell entwickelte Zufallszahlentechnik, die von der Hauptschleife ausgeführt wird, während der Raster-/Timer-IRQ mit anderen Dingen beschäftigt ist - also im Grunde eine Art "Multi-Tasking". Der eigene Maschinesprachekode verwendet dafür also auch die erforderlichen BASIC ROM Routinen - funktioniert alles harmonisch, sofern man nicht die Zeropage missbraucht! ;)


    Nun habe mittels eines kleinen Programms mal erforscht, wie "neutral" denn der RND(x) Befehl unseres BASIC V2 ist. Auf der eine Seite wünscht man sich ja wirklich zufällige Werte, deren Grenzen man vorgibt. Also am liebsten ein chaotisches und unberechenbares Durcheinander. Gleichzeitig möchte man aber auch, dass die Werte auf einen längeren Zeitraum dann doch irgendwie gleichmäßig verteilt sind, damit kein Ungleichgewicht entsteht.


    Bevor ich gleich ein paar Ergebnisse nenne, kann ich jetzt schon sagen - der RND-Befehl des oft so abwertend betrachteten BASIC V2, tut nicht nur das, was man von ihm erwartet - nein, er tut es mit Perfektion!!! :)


    Ich chabe euch ein Progrämmchen zum Runterladen angehängt, mit denen ihr selber die Ergebnisse analysieren könnt. Hier schon mal ein paar Auszüge:


    Es besteht damit die Möglichkeit einen virtuellen Würfel 6 x, 60 x, 100 x oder 60.000 x würfeln zu lassen. Am Ende kann man vergleichen, wieviel mal die [1], die [2], ... die [6] vorgekommen ist.


    Den Langzeittest mit 60.000 Würfen habe ich 4 mal wiederholt (CeVi brauchte dafür jeweils nicht mal 6 Minuten!) - hier die Ergebnisse:


    [1]: 9889
    [2]: 10065
    [3]: 9807
    [4]: 10092
    [5]: 10007
    [6]: 10140


    Abweichung/Gleichmäßigkeit -1,9% / + 1,4%


    [1]: 9899
    [2]: 10055
    [3]: 9861
    [4]: 10100
    [5]: 10001
    [6]: 10084


    Abweichung/Gleichmäßigkeit -1,4% / + 1,0%


    [1]: 9797
    [2]: 10010
    [3]: 10235
    [4]: 9831
    [5]: 10031
    [6]: 10096


    Abweichung/Gleichmäßigkeit -2,0% / + 2,4%


    [1]: 9937
    [2]: 10056
    [3]: 9901
    [4]: 9947
    [5]: 10103
    [6]: 10056


    Abweichung/Gleichmäßigkeit -1,0% / + 1,0%


    Das bedeutet also, dass auf lange Sicht hier im Bsp. alle 6 Würfelaugen gleichmäßig vorkommen (Abweichung +/-3 %) und es somit kein Ungleichgewicht gibt.


    Im Kurzzeittest mit nur 6 Würfen, dauert es sehr lange, bis jedes Würfelauge nur 1 x vorkommt - also alle gleich verteilt sind.


    Eine bessere Grundlage für Zufallszahlen/-werte in Spielen bspw. gibt es doch gar nicht! ;)


    Wer sich's mal anschauen und selber ausprobieren möchte, kann sich hier das D64 Image runterladen. Ist alles selbsterklärend! ;) Natürlich wird gemäß Handbuch mit einer negativen Zufallszahl gestartet, damit nach einem Reset odr Einschalten nicht immer die gleiche Reihenfolge kommt. Solange das Programm nach einem Reset noch im Speicher steht, lässt es sich mit SYS 2100 wieder starten.


    Es wird dabei immer die aktuelle Startfolge angezeigt (eine von 65536 Möglichkeiten). Somit ist die Wahrscheinlichkeit, dass ihr 2 x hintereinander die gleichen Zahlenfolge bekommt praktisch null! ;)


    Viel Spaß! ;)

    Zitat von TheRyk

    Deshalb kommen nach Kaltstart oft immer gleiche Zahlenfolgen, vor allem auf alten Emulatoren.

    Nicht nur oft, sondern immer.



    Zitat von DATA-LAND

    Bevor ich gleich ein paar Ergebnisse nenne, kann ich jetzt schon sagen - der RND-Befehl des oft so abwertend betrachteten BASIC V2, tut nicht nur das, was man von ihm erwartet - nein, er tut es mit Perfektion!!!

    Nö, tut er nicht. Es gab sogar mal in der 64er einen Artikel dazu. IIRC reicht es schon aus, auf einem Hires-Bildschirm Punkte zu malen, deren X- und Y-Koordinate per RND bestimmt werden. Es ergeben sich sehr interessante, sich immer wiederholende Muster.


    Es gibt für Zufallszahlengeneratoren sehr viele Faktoren, die stimmen müssen. RND erfüllt nicht einmal die "uralten" Kriterien, die in TAOCP (http://www.amazon.com/Art-Comp…Algorithms/dp/0201038226/) aufgestellt werden, um auch nur halbwegs brauchbar als Zufallszahlengenerator durchzugehen.

    Ok, einfaches Beispiel, aus Faulheitsgründen mit Simons' BASIC geschrieben:

    Code
    1. 100 hires 0,1
    2. 110 for i = 1 to 10000
    3. 120 x=rnd(0)*320
    4. 130 y=rnd(0)*200
    5. 140 plot x,y,1
    6. 150 next i
    7. 160 geta$:ifa$=""goto160

    Sieht mir nicht so direkt zufällig aus:

    Zitat "Mit Null als Argument erzeugt der Commodore 64 die Zufallszahl direkt aus den Werten des Timers[3] und der Echtzeituhr[4] desCIA-Ein-/Ausgabe-Chips. Die Verteilung der Werte ist unter gewissen Umständen (z.B. schnelle aufeinander folgende Abfragen) nicht ganz so zufällig. "


    Quelle: https://www.c64-wiki.de/index.php/RND

    @strik und Draco: Könntet ihr bitte eure Kritik und Gespräche über SIMON's BASIC, Emulatoren und TACP von diesem Thread trennen? Diese "Würfel-Analyse" wurde bist jetzt (22:20 Uhr) 0 x herunter geladen, folglich hat es auch niemand von euch getestet!


    Ich hingegen habe mehrere Kurz-/ und Langzeittests, sowie Neustarts nach einem Reset gemacht und bin höchst(!) zufrieden. Ihr kommt mit irgendwelchen Listings und verallgemeinert dann. Das ist so nicht okay und auch nicht fair! :(

    Meine Ergebnisse mit x128 im 64er Modus: (Startfolge #56647)
    [1]: 9868
    [2]: 10110
    [3]: 9877
    [4]: 10039
    [5]: 10061
    [6]: 10045


    Die Analyse der Abweichungen überlasse ich dem geneigten Leser als Hausaufgabe ;)


    Für mich steht fest: wenn der c64 würfelt, würde ich nicht unbedingt auf 1 und 3 als Ergebnis setzen (beide scheinen ja fast immer vernachlässigt zu werden).

    @DATA-LAND - Du hast nur die statistische Verteilung der Zufallszahlen untersucht und dabei recht gleichmäßge Ergebnisse erhalten. Das ist durchaus legitim und erstmal ein gutes Ergebnis. Was du aber nicht untersucht hast, ist ob diese Würfelaugen nicht immer in der gleichen Reihenfolge fallen. Dazu etwas verleichbares leistet das kleine Programm von strik. Eine vollständige Untersuchung eines Zufallsgenerators muss beides umfassen.


    Interessant wäre eher, wie man auf dem C-64 zu wirklich zufälligen Zufallszahlen kommt. Das Digitalisieren von Transistorrauschen wäre z.B. so ein Ansatz, nur wo bekommt man sowas in einem unmodifizierten C-64? Evtl an den Paddle-Eingängen, wenn kein Paddle angesteckt ist? Oder Auslesen der X/Y-Position eines nicht angeschlossenen Lichtgriffels, oder ein sich schnell und ständig änderndes Register im Vic (X/Y-Position des Elektronenstrahls), irgend ein ständig aktualisierter Zähler in der Zeropage, , der zeitliche Abstand zwischen zwei Tastendrücken, die Timer in den CIAs? Oder eine Kombination aus all dem zusammen?

    Man KANN RND tweaken, indem man besagte Register (nämlich $8b ff und die Timer) mit $KRAM vollschreibt, z.B. einem Press-Key-Counter, SID-Rauschen, $D012 value when executed.
    So erhält man bessere i.S.v. "zufälligere" Werte.
    Man KANN sich aber auch ne Frikadelle ans Knie nageln und warme Milch draufgießen.
    Ein Problem an RND ist die Langsamkeit, für live Zahlen nicht zu gebrauchen.
    Mit Tabellen (die man in Initialisierung durchaus auch mal mit RND generieren kann) und einem fixen Pointer ist man imho besser davor.


    @Download-Faulheit: Welcome to my world :D Hab neulich auch den Goldohren Kram auf Anfrage auf Silbertablette serviert und dann fanden die, ich hab die Musik doof gecrackt (sic(k)!), weil sie nicht so klang wie auf Youtube... und das bei Zero Leech :nixwiss: :blah! halbe Stunde meines Lebens vertan, ich prangere das an!

    Zitat von 1st1

    Was du aber nicht untersucht hast, ist ob diese Würfelaugen nicht immer in der gleichen Reihenfolge fallen.

    In dem Kurzzeittest mit 6 Würfen erhält man stets andere Reihenfolgen. Die ist so chaotisch, da kann ich keine Methode ableiten. Der Maschinensprachekode beeinflusst die ROM Routine mit einer Kombination aus Rasterzeile und CIA Timer.


    Ich chabe also weder gleiche Startfolgen, noch ähnliche Abfolgen und langfristig auch keine Gewichtung festgestellt. Kurz um - ich bin sehr zufrieden! :)


    Allerdings kann ich nur für diese Würfel-Analyse sprechen und habe es bis jetzt auch nur auf realer Hardware getestet.

    Zitat von TheRyk

    Ein Problem an RND ist die Langsamkeit, für live Zahlen nicht zu gebrauchen.

    Ja, das stimmt! Lt. Langzeittest benötigten die 60.000 Würfe ca. 5:45 Minuten. Also grob 3 Zufallszahlen pro Frame. Das deckt sich mit dem, was ich aufgrund der Rahmensfarbenänderung während des ROM Aufrufs auch festgestellt habe. Aber ich habe von dieser Technik in fast allen Spielen Gebrauch gemacht, mit dem großen Vorteil, dass der Spieler praktisch nie(!) die gleiche Spielsituation ein 2. Mal vorfindet.


    Außerdem sind ja bspw. Gegner, deren Merkmale mit Zufallszahlen ausgestattet wurden, länger auf dem Bildschirm präsent, als der Generator für Nachschub braucht. Dafür sind die ROMs also immerhin noch schnell genug! ^^


    Deinen letzten Absatz habe ich aufgrund der Ausdrucksweise leider nicht ganz gerafft, ich glaube aber ich weiß was du meinst! ;) Geht mir ja nur darum, bevor man etwas kritisiert, sollte man es auch getestet haben. Wie gesagt, mir ist beim Würfeln nix Negatives aufgefallen.

    Zitat von DATA-LAND

    Diese "Würfel-Analyse" wurde bist jetzt (22:20 Uhr) 0 x herunter geladen, folglich hat es auch niemand von euch getestet!

    Was soll man da auch gross testen? Das Ding spuckt ein paar Zahlen auf den Bildschirm, aber ohne einen Disassembler zu bemühen weiss man nicht wie sie entstehen und nur eine Gleichverteilung der Werte ist jetzt noch kein so richtig tolles Qualitätsmerkmal für Zufallszahlen.

    Danke für den Test und das Zahlenmaterial! :) Das ist bisher der 5. Langzeittest a 60.000 Würfe und immer lag eine andere Zahl vorne. Jetzt fehlt nur noch die [1]. Man kann also nicht sagen, das der CeVi schummelt oder die Würfel gezinkt sind! ;)


    Zitat von Tale-X

    wenn der c64 würfelt, würde ich nicht unbedingt auf 1 und 3 als Ergebnis setzen (beide scheinen ja fast immer vernachlässigt zu werden).

    Abweichung/Gleichmäßigkeit -1,3% / + 1,1%!


    Ja, bei max. 3% der Fälle liegst du mit dieser Einschätzung (bisher) richtig! Bei solchen Wahrscheinlichkeiten würde ich aber nicht um Geld spielen... ^^

    Aber [1] lag bisher stets unter 10000 und [3] lag bis auf einmal auch immer unter 10000. Ist zwar nur ne kleine Abweichung, aber sie ist nun mal da. Ich würd' dennoch sagen, für die meisten Spiele zufällig genug. Und Kryptographie macht man eh nicht auf dem C64.


    Der Ansatz von TheRyk mit dem Rauschen vom SID klingt für mich vielversprechend (wenn man tatsächlich die Werte vom Rauschen abgreifen kann). Im Emulator ist's imho müßig, weil das Rauschen dort mittels Zufallsgenerator simuliert wird (würd' mich wundern, wenn nicht).

    Es gibt sehr gute PRND-Generatoren die auch mit wenig Code umzusetzen sind.
    Siehe zB hier: http://codebase64.org/doku.php?id=base:small_fast_8-bit_prng
    Vorteil: jeder Wert im Spektrum kommt gleichverteilt vor, da der Generator alle 256 Werte exakt einmal auswirft bevor er sich wiederholt.
    Nachteil: Die Ergebnisse wiederholen sich halt - das kann man aber dadurch konterkarieren dass man die Anzahl ermittelter Werte mitzählt und nach durchlaufen der Liste einen anderen Seed als Start nimmt. Wenn nun noch eine Tastaturabfrage o.ä. als Startpunkt für den nächsten Seed dient erhält man sehr gute Ergebnisse.
    Der Algo lässt sich auch problemlos auf größere Folgen erweitern und damit steigt auch die Anzahl valider Seeds exponentiell, schon bei einem 16-bit PRNG hat man 2048 verschiedene Folgen, die man durchhecheln kann.

    PRNGs aber die will man fuer vieles nicht ;-)
    Ein 8 bit PRNG hat im Idealfall 256 verschiedene Werte aber keinen Doppelt natuerlich.
    Es haengt eh immer vom Einsatz-Zweck ab.
    Der Wuerfeltest bestaetigt ausschliesslich, dass das BASIC RND nicht komplett kaputt ist.
    Aber ueber die Nutzbarkeit und Qualitaet sagt das nichts aus.
    Bei fast allen PRNGs die so einfach sind, sind auch nicht alle bits gleich 'zufaellig'. Meist eher die oberen.
    Der BASIC RND ist glaube ich wirklich relativ brauchbar, so ein Test ist aber keinesfalls geeignet das zu bestaetigen.
    Eine Reihe (i%6+1) waere demnach perfekt ;-)