A fair, unpredictable, Random Number Generator.
in The Brewery
Hi all,
- user
Edit: typo correction
Cheers!
This is the second task to achieve on my process of learning NES
and 6502 Assembly programming.
You will forgive my lacks in English, it is not my first language.
And you will forgive my lacks of jargon and correct terminologies,
I'm not a programmer, neither a mathematician.
Let see this
"tiny, fast, 8-bit pseudo-random number generator in 6502 assembly"
from White Flame you can find here.
lda seed
beq doEor ; $00, force the EOR
asl
beq noEor ; $80, skip the EOR
bcc noEor
doEor: eor #$1d ; constant value
noEor: sta seed
There are 4 cases: $00 : (shift and) perform EOR
$80 : just shift
%1xxxxxxx : shift and perform EOR
%0xxxxxxx : just shift
Citing the author:
" This yields a chain of all 256 8-bit values in pseudo-random,
repeating order. The 256 different possible seeds you can give
it will simply start the chain at a different point.
To get a different chain (essentially a different PRNG
altogether), the value of the EOR would have to be changed.
I ran a loop to test what values would create a chain of all
256 numbers and found 16 of them:
$1d (29) $2b (43) $2d (45) $4d (77)
$5f (95) $63 (99) $65 (101) $69 (105)
$71 (113) $87 (135) $8d (141) $a9 (169)
$c3 (195) $cf (207) $e7 (231) $f5 (245)
This gives 16 possible PRNGs, each with 256 possible starting
seed points. "
Of course, this is not the kind of randomness (whatever this could
mean) needed for RPGs or gambling games.
" Any one who considers arithmetical methods of producing random
digits is, of course, in a state of sin. For, as has been pointed
out several times, there is no such thing as a random number -
there are only methods to produce random numbers, and a strict
arithmetic procedure of course is not such a method. "
John von Neumann
I say 5! It is a number. It is that a random one?
I roll a dice, I roll a 5! It is a number. It is that a random one?
What does take to make a number, a random one?
A number itself, a value, does not have an "I'm random" attribute.
Let's define a satisfying random number generator method:
- Each number generated must be arithmetically unpredictable.
- Each possible output, from 0 to 255 both included, must be equally
likely, and have exactly 1 chance out of 256 to be generated.
- Each number generated must be statistically independent, which
means that after a "1" is generated, there is still, exactly, 1
chance out of 256 to generate a "1" again the next time.
- The method must be able to run infinitely without being forced to
repeat a specific sequence of outputs.
- The output sequence must not be locked into a predictable series of
numbers artificially generated imposing to each possible output the
same frequency (it must be unlikely but possible to generate the
same specific output infinite consecutive times), which means that
the output cannot be generated relying only on an algorithm which
operates applying an arithmetic procedure on the seed.
In few words, it must simulate an infinite number of rolls of a die.
Mission impossible? Luckily, perhaps not.
Let's adapt the routine above to achieve these goals.
This method will use all the 16 constant values, essentially it will
use sixteen (16) independent parallel random generators.
Let's store into the ZeroPage these constants and some seeds:
$00: $** $** $** $** $** $** $** $** $** $** $** $** $** $** $** $**
$10: $1d $2b $2d $4d $5f $63 $65 $69 $71 $87 $8d $a9 $c3 $cf $e7 $f5
so, the seeds are from $00 to $0f, the constants are from $10 to $1f.
Each seed ($**) can be any number from 00 to ff, it doesn't matter.
Finally, let's assign the hex value 00 (0 dec) to the address $20.
So, this method uses the first 33 bytes into the ZeroPage.
Let's write some code:
; ZeroPage address $21 is reserved to store the prev button pushed
; ZeroPage address $22 is reserved to store the last button pushed
; ZeroPage address $23 is reserved to store the __ random number __
rnd:
lda $00,x
beq do
asl
beq no
bcc no
do: eor $10,x
no: sta $00,x
rts
shf: ; execute every generator
ldx #$00
nx: jsr rnd
inx
cpx #$10
bne nx
rts
skp: ; increase by 3 the value in $20
ldx #$03
lp: inc $20
lda $20
cmp #$10
bne go
lda #$00
sta $20 ; if 16 (10 in hex) restart from 00
go: dex
bne lp
rts
reset:
; ... reset routine, 2 wait for vblank, set up stack, clear memory
; ... set sprite 0 in a visible position, all others out of screen
; ... load palettes, background all black, load sprites patterns
; ... ppu stuff, start transfer ...
loop: ; wait for nmi (non maskable interrupt)
jmp loop
nmi: ; on non maskable interrupt
jsr skp ; increase by 3 the value in $20
lda #$01
sta $4016
lda #$00
sta $4016 ; joyspads latch buttons
joy: ; check buttons
ldx #$09
ck: dex beq bN
lda $4016
and #$01
beq ck ; joypad input (08 A; 07 B; 06 S; 05 ST;
; 00 None 04 U; 03 D; 02 L; 01 R).
bY: stx $22 ; store the last button pushed
ldx $20 ; whenever a button is pushed
jsr rnd ; execute only one of the generators (defined by $20)
lda $22 ; load the last button pushed
cmp $21 ; compare it with the previous button pushed
beq bZ ; skip if is the same button
cmp #$08 ; compare it with the A button value
bne bZ ; skip if is another button
lda $00,x ; load the __ random number __
sta $23 ; store the __ random number __
sta $0201 ; set the pattern of sprite 0 == __ random number __
lda $22 ; load the last button pushed again
bZ: sta $21 ; store last button as previous button pushed
jmp ppu ; done
bN: stx $22 ; whenever no buttons are pushed
stx $21 ; store 00 in both previous and last button pushed
jsr shf ; execute all generators
ppu: ; PPU (picture processor unit) routine
lda #$00
sta $2003
lda #$02
sta $4014 ; start transfer
; ... then clean up the PPU
rti ; return (to loop) from interrupt
So, for each not maskable interrupt, which happens 60 times/second
on NTSC systems, and 50 times/second on PAL systems:
- The value stored in the ZeroPage address $20 increases by 3,
following the path:
hex: 00 03 06 09 0c 0f 02 05 08 0b 0e 01 04 07 0a 0d -> 00
dec: 0 3 6 9 12 15 2 5 8 11 14 1 4 7 10 13 -> 0
- Every time all the buttons are not pushed, all the generators are
executed once, shifting to their next seed.
- Every time any button is pushed, a single generator (which one is
determined by the value stored at $20), is executed once, shifting
to its next seed, breaking the syinchrony between the generators.
- Every time the player pushes the A button, the currently generated
random number is saved. Where does this random number come from?
It is the seed of the ( value stored at $20 )th generator.
[If more than a single random number is needed, for each one extra
needed, it is enough to increase by 1 the value stored at $20 (and
set it to 0 when reaching 10 hex, i.e. 16 dec), store this value in
the register x, and call the subroutine rnd once again; up to 16
statistically independent numbers can be generated in a single nmi
(the 17th generated will forcefully be different from the first)].
For each nmi, no matter what the player does, or abstains to do, it
will influence the next output; and it is highly unlikely to be able
to manipulate this method timing up actions to get specific outputs.
I guess this is enough entropy.
I think this method meets the requirements listed above.
Good enough to claim it better than Mersenne Twister like algorithms
for RPGs and gambling games? I guess so. Let me know your opinion.
Note: please, let me know about any bug you find.
.nes file attached; the gph.txt file attached is the .chr file used.
- user
Edit: typo correction
Comments
Originally posted by: Mario's Right Nut
Have you run this a few bazillion times and seen the actual results? Like store the values it spits out and see if it is a uniform distribution?
Not on a statistical meaningful way, of course.
Since it depends on the player interactions (or lack of them), bizillion times is not pratical.
But if anytime you can get twice the same series of four numbers let me know, you are very lucky!
Cheers!
Originally posted by: Mario's Right Nut
Have you run this a few bazillion times and seen the actual results? Like store the values it spits out and see if it is a uniform distribution?
Also, the goal of this program, it is to simulate an infinite number of rolls of a die.
A series of 1'000'000 of "1" must be ___extremely___ (1/256^1000000) unlikely, but (in theory) possible!
I'm not a mathematician, so, I'm asking you: if "an infinite numbers of rolls of a die" meets forcefully the definition of "uniform distribution", then that's the goal; if not, then it's not the goal to always output values under "uniform distribution". I hope this makes sense in English.
Again, sorry for my lack of correct terminologies. And as said, this is mostly a learning experiment.
Thanks for the interest and the reply.
Cheers!
Originally posted by: Vectrex280996
Not bad, seems to be fairly random.
Thanks.
Originally posted by: user
Originally posted by: Mario's Right Nut
Have you run this a few bazillion times and seen the actual results? Like store the values it spits out and see if it is a uniform distribution?
Also, the goal of this program, it is to simulate an infinite number of rolls of a die.
A series of 1'000'000 of "1" must be ___extremely___ (1/256^1000000) unlikely, but (in theory) possible!
I'm not a mathematician, so, I'm asking you: if "an infinite numbers of rolls of a die" meets forcefully the definition of "uniform distribution", then that's the goal; if not, then it's not the goal to always output values under "uniform distribution". I hope this makes sense in English.
It's a question of what your distribution looks like over a given sample size.
if your sample size is 1,000,000 rolls of the die and they ALL roll a "1", then no reasonable person would assume that the die was random and unbiased.
If you sample size is 10^100 AND you had a uniform distribution of outcomes, getting "1" a million times in a row might not actually be a deal-breaker, despite being extremely unlikely.
If you want to exercise it, figure out how to get an emulator to dump output to a CSV file for you to do data reduction on later, and set up some method for automatically stimulating the inputs... then let it run all weekend. That will give you a huge sample of outputs to check.
I don't think folks would get too up-in-arms about RNG accuracy on an 8-bit cart though.
Originally posted by: arch_8ngel
If you sample size is 10^100 AND you had a uniform distribution of outcomes, getting "1" a million times in a row might not actually be a deal-breaker, despite being extremely unlikely.
Good point! Thanks for the reply and this lesson!
Originally posted by: arch_8ngel
If you want to exercise it, figure out how to get an emulator to dump output to a CSV file for you to do data reduction on later, and set up some method for automatically stimulating the inputs... then let it run all weekend. That will give you a huge sample of outputs to check.
This is fair request. I'm claiming this does something, so it's up to me to prove it.
But, honestly, I lack both knowledge and tools (I guess) to do what you request.
You can see in the debugger: the 16 "jars" (addresses $00 to $0f) shuffling numbers each nmi, and the "arrow" (stored in $20) pointing toward a different jar each nmi. And what happens when you interact. This is all I can offer. I wouldn't bet all my money on this not being somehow rigged, of course.
So yeah, you are right of course; let just say it is a silly experiment then, and leave Mersenne alone maybe.
Cheers!
Originally posted by: cirellio
You know, I've often wondered if devs haven't ever made RNG functions that are glitchy on purpose (include a series of known glitches for unpredictable behavior).
I don't think folks would get too up-in-arms about RNG accuracy on an 8-bit cart though.
To complete a low level game in FFI, most players would leverage the weaknesses of the PRNG a lot.
Originally posted by: Shiru
Any PRNG gives the same sequence of values from the same seed, no matter how many PRNGs you'll combine. Only length of the sequence changes. To make a PRNG more random, you just need to introduce user interaction on the seed and sometimes on the generation (but not too often). The first thing is usually achieved by a (preferably high resolution) counter on the title screen that sets up the PRNG seed when user press a button. The second thing can be simply a dummy call of the rand function on some action, like jump button.
What you describe works with common PRNGs algorithms. I was trying a different approach: this method has the numbers shuffling each nmi (like in a lotto machine) and let the player interaction (pushing the button) output the next one. The fact that it uses also an arithmetic algorithm is just for convenience, but it is NOT the arithmetic algorithm itself that generates the next output, it just shuffles numbers; it is the timing of the player pushing the button to determinate the next output (one fraction of second later, would generate a totally different output).
I hope this makes sense.
Edit: and there are 16 "pots" also to be able to have up to 16 statistically independent random outputs to use within the same single specific nmi routine, if needed.
Edit: or perhaps, simply, for some reason this is not a good idea, after all; in which case, never mind, I apologize for wasting your time guys. Still, it was a good learning task for me to produce it.
Originally posted by: arch_8ngel
If you want to exercise it, figure out how to get an emulator to dump output to a CSV file for you to do data reduction on later, and set up some method for automatically stimulating the inputs... then let it run all weekend. That will give you a huge sample of outputs to check.
@all
I attach a brief sample of the output, just the first 100 numbers an human player generated randomly pushing (or not pushing) buttons running the rom attached in the first post, if someone wishes to check it out.
I know it is way too short to have any statistical purpose, but it is all I can offer, and I can't think of better ways to produce a sample of the output. Please remember I'm the ignorant newcomer in here.
Also, I attach a graphical demo rom:
The way it changes is unpredictable and unlikely to replicate a second time, since it doesn't depend on what the user does, but it depends on when the action (of pushing a button) is performed.if you don't do anything, you'll see a graphical pattern repeating on your screen.
every time you push a button, the pattern will change.
The more the buttons are pushed, the more the pattern will change, every time, in an unpredictable way.
When stopping pushing buttons, the last pattern will start repeating itself.
N-joy (uhm... not too much to enjoy, however).
Cheers!
Edit: typo corrections
Originally posted by: Shiru
A simple test of distribution of a RNG is to just put a point at 'random' coords, many thousands of points, and see if it produces an evenly filled noise field, or some artifacts (very bad RNG output: http://wellington.pm.org/archive/...). As you can't really display separate points on the NES, at least in an easy way, you'll need to recreate your RNG algorithm on the PC to test it.
Thank you for your feedback. I really appreciate you are spending your time to read what I write. You are a cheerful person, and I honestly know you have way more know how than I do programming wise. So maximum respect from me.
But still, I doubt what you propose is doable here.
I can be wrong, in which case please correct me.
This method is based on the idea that players actions are unpredictable: even if it is going to jump on that platform at that point in the game, you can't tell if the button will be pushed a couple of nmi earlier or later, you can't tell in which nmi it will be released, you can't tell exactly when (fractions of second wise) he will get there, you can't tell that even if a single jump is enough the player will instead jump twice, or will get there jumping just for the sake of it, or if instead of going left all the time, it releases the button and stops for a bit, or goes right then left again because it was confused on the direction to take; moreover, you don't know if it will unpredictably leave the controls for a fraction of second to scratch its nose, if the game will be paused sometimes and when, and so on...
All the above is what generates "randomness", or "pseudo-randomness" (whatever this means, I'm not a philosopher), not the two arithmetic algorithms which:
and one or the other of these behaviors happens only if and when the player interaction "says" so.one just shuffles the 256 values from 00 to ff in 16 ZP addresses;
and the other goes: 0>3>6>9>12>15>2>5>8>11>14>1>4>7>10>13> 0>3> ... ;
This is why even setting the same seeds in the beginning, after few minutes of play you will not (how many chances they are to time up every input the same twice?) get twice the same sequence of outputs: even the seeds of the shuffling algorithms will be different then (by the way: yes, you can test those two shuffling algorithms them self of course, and they work).
As I said in a post above, I'm not even too sure this approach is actually a good idea altogether (it was also about the concept proposed and its implementation that I wished to get some opinions from experts). But still, this is the idea.
So, I wonder:
Thanks again for your interest and your reply; but honestly, I admit my ignorance here: for all the above I can't figure out a reasonable way to test if this method meets the benchmarks required for PRNGs (besides, this is for me just a single step on the path, a learning task, not a final goal; and finishing (it is going to be very soon, I hope) with the actual programming of my first complete Nes game is way more fun to do in my free-time! ).how to test the output of this method without a player generating it?
how to produce a large sample of outputs without a player generating them?
how to simulate the "randomness" of in-game human actions to avoid having a player generating it?
in few words: how to perform any test on this without having a human hitting (or not hitting) buttons?
So, to all, my bad for proposing a confrontation with PRNGs in the first post; please let's forget about that, and maybe just take this for what it is, a simple learning experiment. What do you guys think about it, code wise?
Cheers!
Edit: text formatting, typo corrections.
Edit II: also, to all, my apologies for the first post of this thread entirely in bold, I know is not an elegant thing to do, it sounds like screaming; my intention was to put in bold only the code to highlight it, but I obviously messed up the formatting and I didn't realize it then.
Another thing to consider is that in an actual game you may need quite some of random numbers per frame, like a hundred, and in this area you still have the same problems as with a normal PRNG.
Originally posted by: Shiru
As you rely on the user input as the main source of randomness, there is obviously no way to test it without actual user input, and it'll take quite some time to get some statistics (like, thousands of key presses). Actually there is no way to ensure the RNG quality either, as an actual game will force player for certain input patterns in certain situations, so while random button mashing in a test can yield nice distribution, conscious input in a game could have completely different output.
Another thing to consider is that in an actual game you may need quite some of random numbers per frame, like a hundred, and in this area you still have the same problems as with a normal PRNG.
I 100% agree on those limits and the possibility of those eventualities!
Those are exactly my concerns! Are you able to read minds?
That's why I'm affirming I'm not too sure about this approach, and I wished people with more know how to give an opinion about it.
Thanks, really appreciated.
Cheers!