RND-Zahlen von 0-10 in ASM

Bei meiner Recherche ist mir eine schwacher Algorithmus mit viel Speed untergekommen. Typischer LFSR

Dieser Schieberegister koppelt die Bits 10+12+13+15 rück. Kombiniert man ihn beispielsweise per EOR mit dem selben Algorithmus, der an Bit 13+14 abgreift, erreicht man eine Periodenfolge von 65535*32767=2147385345, da beide Shiftregister in ihrer Periode teilerfremd sind.

Seedet man die beiden Register vorher schön mittels der Hardware-Randomwerte, müsste das eigentlich ganz brauchbare Generatoren geben. Natürlich nicht für Kryptographie geeignet und ich zweifel daran, dass es für einen Kartenmischer für Blackjack reichen würde. Erscheint mir zu abzählbar.

Zitat

Solche wertvollen Codeschnipsel sollte man auf keden Fall wiederauffindbar dokumentieren.

darum gibt es ja das: http://codebase64.org

Apropos Codeschnipsel. Gute Idee, das aufzunehmen. Also der Algorithmus ist natürlich recherchiert, also stammt nicht von mir. Die Umsetzung auf 6502 hab ich kurzerhand hingehackt. Bevor das aufgenommen wird, wäre es gut, wenn es nochmal jemand gegenprüft. Genauso den zweiten Algorithmus mit der Abnahme an zwei Stellen sowie die Kombination auf rand1 EOR rand2 mit der daraus resultierenden langen Periode.

Außerdem kann der AND #$04 wohl weg. Überflüssig, wie ich mir gerade überlege. Und damit geht der möglichen Optimierung auch langsam die Luft an überflüssigen Befehlen aus.

Nachtrag: ich habs mal kurz gemacht, hab beide Algorithmen fertig und kurz überflogen getestet. Scheint zu gehen.

Wer es prüfen möchte, hier ein Basic-Test:

Ich würde aber empfehlen, die Highbytes nicht mit ins Ergebnis aufzunehmen, sondern als unsichtbaren Seed zu belassen, sprich mit 20 PRINT PEEK(780)/256 bekäme man einen netten Wert zwischen 0..1)
Eine Verbesserung des Randomgenerators wäre allerdings, wenn man das eine Schieberegister nach links bewegt, das andere aber nach rechts. Sprich die Logik von random32k einfach umdreht. Der Vorteil liegt auf der Hand: die Random-Zahlen sind nicht immer die alte Zahl * 2 + Randombit, sondern die beiden Schieberegister arbeiten sozusagen "gegeneinander". Das Ergbnis müsste daher etwas lustiger werden und unvoraussagbarer. Wer wirklich gute Zufallszahlen will, braucht aber einen besseren Algorithmus als ein Schieberegister. Klar. Mersenne-Twister, sag ich.

Hier die vorgeschlagene Änderung, man achte auf das ROR sr2 statt oben ROL sr2 in Zeile 9. Der eigentliche Algorithmus ändert sich genausowenig wie die Periode. Nur die Zahlen werden etwas netter und unvorhersagbarer.

Noch eine Anmerkung, für alle, die es noch nicht gesehen haben: natürlich dürfen weder der gesamte Seed vom ersten noch vom zweiten Algorithmus 0 sein. Denn auf die 0 folgt in beiden Schieberegistern immer zwangsläufig nur die 0. Deshalb ist die Periode dieser beiden Register auch 2^x-1. Also sie laufen durch alle Zahlen außer der 0. Durch die Kombination der beiden Schieberegister erhält man tatsächlich auf relativ billige Art und Weise einen 32 Bit-Zufallsgenerator mit 2^31-1 als Periode. Benutzt werden sollten als Zahl meiner Meinung nach aber nur die unteren Bytes, also immer nur der Wert des Accus.

Wenn man den Wert vom Accu auf den erwünschten Wertebereich anpasst mittels Accu/256*Wertebereich, kann man jeden normalen Würfelwurf damit reproduzieren. Statt durch 256 zu teilen macht man an dieser Stelle natürlich am besten eine 8 Bit*8 Bit=16 Bit Multiplikation und benutzt als Randomwert immer nur das Highbyte. Also als Beispiel für einen 6-Seitigen Würfel Highbyte(Accu*6)+1.

Statt einer vollen Multiplikation kann man als Geschwindigkeitssteigerung natürlich mit gezielten Additionen arbeiten. Mit 6 multipliziert bedeutet ja genau genommen A<<1 + A<<2, also Accu*4+Accu*2, mit 10 multipliziert wäre A<<1+A<<3

Wenn man die hier erhaltenen Zufallswerte als Index nimmt, um aus einer Tabelle Werte abzugreifen anstatt wie vorgeschlagen mit "Division" und Wertemultiplikation zu arbeiten, erhält man einen unschönen Nebeneffekt; die Werte sind nicht mehr gleichverteilt, also fair.

Beispiel: da 256 nicht durch 10 teilbar ist, wären in diesem Block einige Zahlen häufiger vertreten als andere. Daher verzerrt sich das Ergebnis zugunsten dieser Zahlen. Je größer der Rest ist, desto heftiger ist dieses Ungleichgewicht. Manchmal sind solche Ungleichgewichte erwünscht, aber in der Regel nicht. Sagen wir, wir nehmen die unteren 3 Bits unserer Zufallszahl, um in einem Spiel zu entscheiden, ob dem Spieler ein Monster oder eine Münze begegnet und wir wollen ihm mehr Münzen als Monster schicken (ist also ein Spiel, das nach 1989 geschrieben wurde*) und ein Monster steht für 1, eine Münze für 2, dann wäre unser Array etwa mit:

1,1,2,2,2,2,2,2

in 6/8 Fällen für die Münze. Faire Verhältnisse können wir nach dieser Methode jedoch nur bekommen, wenn unsere Ereignisse ein vielfaches von 2 sind. Bei 10, 6 oder sowas ist das nicht der Fall. Sagen wir, unsere unteren 4 Bits sind unser Zufallswert, dann bekommen wir:

1,2,3,4,5,6,7,8,9,10,x1,x2,x3,x4,x5,x6

Wobei wir bei x1-x6 gezwungen sind, unfaire Verteilungen einzufügen, sprich sechs unserer zehn Zahlen treten doppelt so häufig auf wie die anderen. Man könnte natürlich einfach bestimmen, dass so lange gewürfelt wird, bis ein valides Ergebnis kommt, aber das könnte im ungünstigens Falle an zeitkritischen Stellen zu unerwünschten Hakern führen. Daher ist die oben vorgeschlagene vereinfachte Divisions- und Multiplikationsmethode vorzuziehen.

Natürlich läßt sich durch das immer größer machen der Tabelle die Ungleichmäßigkeit unseres Zufallsergebnisses vertuschen, beseitigen läßt sie sich jedoch nie. Wenn man ganz genau sein möchte, muss man auch anmerken, dass unser Schieberegister per se nicht ganz fair ist. Es fehlt nämlich die Gesamt 0 in ihrem Seed. Und damit haben wir eine leichte Unwucht im Generator zulasten der kleinsten Zahl.

Man kann aber ganz allgemein annehmen, dass die von diesem Generator erzeugten Zahlen für viel Zwecke völlig ausreichend sein werden. Wie gesagt zweifel ich ein wenig an der Nützlichkeit des Generators für den Zweck der Kartenmischung, aber es gibt Standard-Randomverfahren in verbreiteten Sprachbibliotheken, die schlechter sind als der vorgestellte.

Fußnote ältere Spiele hatten das klare Ziel, den Spieler in die Verzweiflung zu treiben und in den möglichst grausamen und quälenden Tod. Und falls er der martialischen Vernichtung dennoch entkommen sein sollte, wurde es immer schwerer und schwerer. Save gab es nicht. Es gab eine Erinnerung in der Highscore, wenn du schließlich gestorben bist. Manchmal gab es ein paar zusätzliche Leben als milde Gabe von den Programmierern wie ein abgenagter Knochen einem bettelnden Hund zugeworfen wird. Heute jedoch ist der Spieler der "Kunde" und muss zufriedengestellt werden statt vernichtet und demoralisiert. Man versucht ihn am Leben zu halten, egal wie dämlich er sich anstellt und so ist es selbst den unfähigsten Spielern möglich, die modernen Spiele durchzuspielen und nicht nur einem von einer Million.

Damit ein LFSR eine lange Periode bekommt, braucht man auch ein gutes Feedbackpolynom. Da würde ich einfach eins nehmen, welches bei CRC32 benutzt wird (ist ja der selbe Algorithmus, nur eine Eingabe weniger).

Für 32 Bit wird da oft $04C11DB7 verwendet. Bei 16 Bit ist's häufig $1021 oder $8005.

Der 16 Bit Algo sieht in Assembler dann so aus:

Der Startwert von "random" sollte dabei ungleich 0 sein.

Will man das ganze noch zufälliger machen, dann ist ein EOR mit irgendwelchen schwer vorhersagbaren Quellen immer gut. Es bieten sich hierfür vor allem folgende Hardwareregister an: $DC04, $DC05, $D012 und $D800.

Das Farbram auf dem C128 ist 8bit breit. Daher würde ich von $d800 abraten.

EDIT: stimmt nicht. Die benutzen tatsächlich nur 4 bits.

Hat der Mactron, der das Thema Random aufgerissen hat, hier überhaupt nochmal reingesehen?

Ich denke nicht. Das scheint mein Schicksal zu sein, dass alles, was ich schreibe am Ende mit Null Downloads im Forum liegenbleibt. *schnüff*

Dabei kam am Ende meiner Recherche zu Randomisierern folgendes heraus: das Verfahren im C=64 ist denkbar schlecht. Das hält nichtmal eine Überprüfung in zwei Dimensionen stand. Mein Randomisierer ist da schon etwas besser. Aber eigentlich vor allem schneller. Man könnte das selbe Prinzip auf 32 Bit ausweiten, aber das scheint mir für den geforderten Zweck einerseits sinnlos zu sein, andererseits bleibt bei den Shiftregistern das Problem, dass sie nur im untersten (oder obersten) Bit zulegen, der Rest bleibt stabil immer *2 oder /2.

Dagegen habe ich ein wenig Abhilfe geschaffen, indem ich einen zweiten Randomisierer drübergelegt habe. Das sollte eigentlich helfen.

Wer es für wissenschaftliche Zwecke braucht, der kommt um einen Mersenne Twister nicht herum, für kryptographische Zwecke wäre allerdings der Yamal oder Fortuna besser. Fortuna wäre ein interessanter Ansatz, wenn ich als Zufallsbox einen AES-Chiffre nehme. Der ist schnell und elegant und würde auf dem C=64 noch in angemessener Zeit durchlaufen und ein wirklich klasse Ergebnis liefern. Aber ohne weiteren Bedarf setze ich jetzt keine Arbeit mehr da rein.

ob das wohl daran lag das sein problem gelöst war lange bevor das thema hier ins absurde gedriftet ist?

Da waren Lösungen? Ich glaube nicht, dass irgendwer vor mir einen kleinen Registershifter oder auch nur einen Ansatz gepostet hätte. Oder einen Link. Wenn es ihm genügt, das ganze mittels des wirklich lahmarschigen und schlechten C=64 RND() zu machen, dann verstehe ich das nicht. Mir würd das nicht reichen. Der RND() war schon in den 80ern als hoffnungslos veraltet abgeschrieben. Da hätten sie genauso gut einen Neumannschen "Quadrat-Mittel" nehmen können. Und auch die Initialisierung mittels RND(0) ist inakzeptabel vom Ergebnis. Vor allem, weil die Zahlen am Ende als Floating Point kommen und damit viel zu langsam sind.

Mit dem Rechenaufwand mach ich dir einen Fortuna.

Ach übrigens, anpassen von 256 auf 10:

Müsste funktionieren und verbrät nicht einen ganzen Block schlecht ausgewuchteter Tabellen. Ergebnis ist 0..9
Wie ich sagte ist eine echte Multiplikation nicht nötig.

Habs nochmal angehängt mit SYS9*4096 : PRINT PEEK(780)+1 kann man überprüfen, dass es hervorragend läuft.

Nachtrag: da ist noch ein Fehler drin, ich arbeite dran...

Zitat

Da waren Lösungen? Ich glaube nicht, dass irgendwer vor mir einen kleinen Registershifter oder auch nur einen Ansatz gepostet hätte.

wozu auch, er ist ja selber auf eine lösung gekommen die für seine zwecke vollkommen ausreichend ist.

So, ich hab das nochmal korrigiert. Jetzt läuft es sauber. Auf 10000 Durchläufe hatte ich
1: 1047
2: 995
3: 971
4: 1020
5: 979
6: 1015
7: 985
8: 951
9: 1066
10: 971

Das ist sauber. Bei 100000 Durchläufen immer noch, Statistik gleicht sich an. Gesamtlänge des Generators: 113 Bytes. Und damit deutlich kleiner als die andere Lösung. In der Zeropage würds noch kürzer und schneller gehen.

Hier der betreffende Codeteil:

Zitat

Original von sauhund
(wofür braucht man denn bei einem flipper grossartig zufallszahlen? *kratz*)

Ich hab da noch eine interessante Frage gefunden. Wozu braucht man Zufall in einem Spiel wie einem Flipper oder irgend etwas anderem, was eine physikalische Simulation darstellt?

Davids Midnight Magic ist ein gutes Beispiel. Da die reale Welt bei einem Zusammenstoß von zwei Gegenständen sich anders verhält als das idealisierte mathematisch-physikalische Modell springt die Kugel immer ein wenig anders ab und bringt in das Flipperspiel ein wenig Zufall hinein. Bei einer Simulation, sprich einem Spiel befinden wir uns komplett in einem deterministischen Modell ohne jede Art von natürlicher Unregelmäßigkeit und der Vielzahl von Variablen, die das Spiel beeinflussen. Deshalb addiert man zu jedem Ereignis einen gewissen Zufallsvektor. Bei Davids MM kann man das sehr deutlich sehen: die Kugel springt auf dem Paddel permanent hoch, auch wenn der Paddel still steht und sie eigentlich still liegen bleiben sollte.

Hier sieht man ganz deutlich, wie der Programmierer die fehlende Zufallsvariable in das Modell hinzugefügt hat. Das selbe kann man in fast allen anderen Modellen sehen. Zum Beispiel im aktuellen SecondLife; hat man einen physikalischen Gegenstand, beginnt er sich leicht zu bewegen, auch wenn keine Kräfte von außen wirken. (Woher sollten sie auch kommen?)

Es ist ja auch nicht nur die fehlende Diversität innerhalb eines vereinfachenden Modells, sondern auch der Spieler hat nur sehr wenige Vektoren, mit denen er auf das Spiel Einfluss hat. Beispielsweise bei einem Computer-Billard gegen ein echtes Billiard. Wo Haltung, Grad der Abnutzung und Kreide auf dem Kö, Qualität des Belages, Festigkeit und Präzision der Ränder, Filz und Ungleichmäßigkeiten in den Kugeln, Fingerfett und all das als Variablen hinzukommen. Diese Variablen gibt es einfach nicht im Computer, denn die Schnittstelle zwischen Spieler und Gerät ist äußerst simplifiziert durch einen Joystick oder etwas ähnliches. Deshalb der Zufall. Er macht das ganze "echter" und bringt es aus dem Bereich des deterministischen Modells zu etwas, mit dem man spielen kann, was einen immer wieder überraschen kann. Man darf den Einfluss des Zufalls natürlich nicht übertreiben und damit die Fähigkeit des Spielers reduzieren. Können muss sich trotzdem auszahlen. Aber immer Erfolg zu haben ist langweilig; so etwas gibt es nicht in der realen Welt. Jedenfalls sind solche Spiele ziemlich öde. Tick Tack Toe sag ich da nur.

Im 64er sind die Modelle in der Regel sehr einfach gehalten. Während in späteren Rechnergenerationen in der Regel die physikalischen Modelle auf die Grafik abgebildet werden, ist beim 64er meistens die Grafik das Modell. Also bewegt sich die Kugel nicht bei Davids MM, steht auch das Modell. Die Addition von Zufallswerten wird also direkt in graphische Bewegungen umgesetzt. Ob diese grobe Vereinfachung wirklich nötig ist, ist zu bezweifeln.

Aber die Vereinfachung reduziert auf jeden Fall die nötigen Rechenschritte, also die Feinheit der Auflösung der Simulationsschritte. Und das ist wahrscheinlich der Grund.

Tatsächlich ist selbst beim Urvater der Computerspiele "Pong" eine Zufallsvariable mit von der Partie. Wenn man es schafft die beiden Paddel so zu positionieren, dass der Ball zwischen ihnen eigentlich endlos hin und herfliegen müsste, stellt man fest, dass er plötzlich dennoch in eine unvorgesehene Richtung fliegt. Das selbe bei Breakout. Und bei jedem anderen Spiel, das mir einfällt und wo der Programmierer seine Hausaufgaben gemacht hat.

Deshalb Zufall in Spielen wie einem Flipper.

den "zufallsvektor" addiert man bei physikalischen simulationen auch aus einem anderen grund dazu (und er muss auch nicht wirklich zufällig sein). aber das spare ich mir zu erklären, wenn man sowas mal programmiert kommt man eh von selber drauf warum man das braucht.

Zitat

Original von enthusi
junge, junge...
GENERIERST Du Deine Texte?

Nein, eigentlich nicht. Aber ich habe in den frühen 90ern mal mit Textgenerierung gespielt. Das ist ein Spinnoff meiner Beschäftigung mit Buchstabenwahrscheinlichkeiten gewesen und mit Kryptographie. Das Programm heißt APE und geht der Idee nach, wie es aussehen würde, wenn Affen willenlos auf Tasten hämmern aber immerhin wissen, mit welcher Wahrscheinlichkeit ein Zeichen auf das vorherige folgt. Ich nenne das "zweite Ordnung", hier ein Beispiel für einen Zufallstext dritter Ordnung mit Eingabe von meinem letzten Posting:

Zitat

APE.c
Paddells, mit von das sind Kräfte Fähigkeinem
Flipperminis einem and, bezweilig; so direkt in
dern auchtung, Grad das ein da noch wennoch wenight
nur sie Addie einheit und wo die Fähnlich kommer
Präfte von Zufalls selbe kann machungerfett in
gibt es Beispielen kann, auf jedem Zufall in Secondenerhalb
das äußers reduzierten Spiele mationiertrein der
Und bringen er Auflösung wie Grund da noch die
Art von Variablender Paddel Einfachung des Billard.
Tatsächlich andenn müssteht man die Grafik abgebildet
wahrschen spät dem ande auch nich nich in eineinein
eine Rich anden Welt und dass eignist über reduzierten
Geräfte von Variable in das MM kann, all. Aber
Simulationiereiben und brauch die Frage graphischer
Unregendlos hinzukommenstätereiben and, bei Das
ganze "echen: die Kugelmäßigkeiten in er meist
ja auf da nur. Da die Simulatischene physikalität
in einem man echnitte. Ungleiben ble mit den, diertreiben
SecondLifeln, mir einem Zufallsvariablen Gegel
die Feinein ganze "Pon

Alles anzeigen

Unterschied erkennbar?

Zitat

Original von sauhund
den "zufallsvektor" addiert man bei physikalischen simulationen auch aus einem anderen grund dazu (und er muss auch nicht wirklich zufällig sein). aber das spare ich mir zu erklären, wenn man sowas mal programmiert kommt man eh von selber drauf warum man das braucht.

Wenn du das weisst, warum fragst du das dann?