Random Number Generation?

Are you new to 6502, NES, or even programming in general? Post any of your questions here. Remember - the only dumb question is the question that remains unasked.

Moderator: Moderators

tepples
Posts: 21982
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Post by tepples » Fri Aug 06, 2010 6:26 pm

Kasumi wrote:Seven pieces. He used 3 bits. Seven of the possibilities deal the piece it corresponds to. (1= I, 2 = O, etc.) When the eighth possibility comes up he increments (or decrements) and wraps around a variable and deals the piece that corresponds to the current value of the variable.
I used this method, which I called "possession arrow", to simulate a uniform randomizer in versions of LJ65 (then called tetramino) prior to 0.33. In that version, I switched to the LRU system to reduce repetition, following Arika's TGM games that use a conceptually similar system.

User avatar
neilbaldwin
Posts: 481
Joined: Tue Apr 28, 2009 4:12 am
Contact:

Post by neilbaldwin » Sat Aug 07, 2010 12:51 am

@Tetris randomiser : just ace! I wish I could think like that :D

bogax
Posts: 34
Joined: Wed Jul 30, 2008 12:03 am

Post by bogax » Sat Aug 07, 2010 2:25 am

This question comes up a lot, so I've thought about it some.
I'm not sure I'm analyzing it correctly (and I haven't actually
tested it so take this with agrain of salt ;) )

My thought is to take a random number MOD your range and then
accumulate and hope that the bias accumulates and distributes
itself over the range. (or the bias ends up "diluted" in the
accumulation, depending on how you look at it)

Choose a range of random numbers that's easy to MOD to your target
range.

So eg if you random number generator returns numbers 0-FF,
and you want random numbers in the range 0-1B mask off the lower
five bits (the next higher power of two, and if you start with
a range that's a power of two and MOD for a range thats a power
of two that shouldn't introduce any bias)

MOD that to your target range

Add it to your random number accumulator

MOD that to your target range.

something like this:

Code: Select all

 ; return a number in the range 0-1B 
 ; start with a random number 0-FF in a
 ; myrand needs to be intialized to be in range

 ; MOD to an easier power of two
 and #$1F           ; the assumption is if a is random in a range
                    ; that's a power of two this result should be random

 ; MOD that to the target range
 cmp #$1C
 bcs ACCUMULATE 
 sbc #$1B           ; biased to account for carry clear 

ACCUMULATE
 clc
 adc myrand

 ; MOD to the target range
 cmp #$1C
 bcs SAVE_MYRAND 
 sbc #$1B           ; biased to account for carry clear 

SAVE_MYRAND
 sta myrand
 rts
Edit:

I forgot to mention you could use the next lesser power of two
to start and save some MODing.

My gut says that the larger the range you start with the better
off you'll be distribution wise.
So it becomes something of a trade off between the size of the range
and the effort spent doing the MOD.

I'd guess that using the next lesser power of two probably
wouldn't make a lot of difference especially if it's close to
your target range.
Last edited by bogax on Sat Aug 07, 2010 11:52 am, edited 1 time in total.

User avatar
blargg
Posts: 3715
Joined: Mon Sep 27, 2004 8:33 am
Location: Central Texas, USA
Contact:

Post by blargg » Sat Aug 07, 2010 4:46 am

Here's one I came up with for use to generate a random value between 0-79, with uniform distribution (for use in Litewall, which has a 10x8 grid it wants to generate random coordinates into):

Code: Select all

random_80:
@retry:
    jsr random_256 ; A = random 8-bit value
    sec
    sbc #80
    bcc @done
    sbc #80
    bcc @done
    sbc #80
    bcs @retry
@done:
    adc #80
    rts
It divides by 80 and takes the modulus. This takes care of the first 240 values, leaving 16 extra. In that case, it gets a new random value and tries again. The probability of retrying the first time is 16 in 256, or 1 in 16. The probability of it retrying two times in a row is 1 in 16*16 = 1 in 256, and so on. This means that on average, it takes only slightly longer than random_256, but worst-case, it could take forever, assuming random_256 has an infinite period. If random_256 is a simple 8-bit LFSR, this routine will always terminate, since random_256 would then generate each value every 256 calls.

tepples
Posts: 21982
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Post by tepples » Sat Aug 07, 2010 6:46 am

Or in C:

Code: Select all

unsigned char rand80() {
  unsigned char raw;
  do {
    raw = random_256();
  } while (raw >= 240);
  return raw % 80;
}
blargg wrote:If random_256 is a simple 8-bit LFSR, this routine will always terminate
In a video game or a real-time demo, you want the RNG to terminate within a guaranteed amount of cycles so that you don't overflow frame time. In this case, I'd recommend something similar to possession arrow logic for cases where the base RNG returns 240-255: increment a counter by 16 (mod 80) and then combine that with the low bits of the remainder. Or 3 bits for Y and 3 bits plus an LRU unit for X.

User avatar
Dafydd
Posts: 114
Joined: Sun Mar 16, 2008 1:45 am
Location: Uppsala, Sweden

Re: Random Number Generation?

Post by Dafydd » Tue Mar 05, 2013 4:08 pm

Sorry for the necro post, but I didn't see another thread on the topic.

I want to produce a large number of random sequences of the numbers 0-15 where each number must occur exactly once. A 4-bit LSFR would make the sequence predictable very quickly, and an 8-bit LSFR (which would be much less predictable) doesn't guarantee that any 4 bits I choose (the last 4 out of 8, for example) do not have the same combination of values in a 16 values long sequence, as far as I know.

One solution could be to run fisher-yates on an array of the numbers I want, where the random number (i.e. the index) is taken from the last 4 bits of an 8-bit LSFR (picking the next value or truncating it should it be out of range) that is periodically seeded by the unknowing player by counting the number of frames passed between certain actions (in this case, pulling the trigger on the Zapper). That should give pretty good randomness, but I could be wrong, and I don't even know whether there's a way I could prove myself right or wrong.

Another solution could be to keep a table of sequences that are chosen from by the aforementioned frame counter, but that seems like a pretty bad idea considering, uh, [grabs a calculator] there are nearly 21 trillion different possible sequences and each sequence would need 8 bytes of memory for storage. So yeah, very bad idea.

So... does anyone feel right away that the 8-bit LSFR + Fisher-Yates solution is also a bad idea, for any reason? In particular, is anyone good enough at math to tell me whether or the sequences that are produced by this method are equally likely to happen, or whether there's a tendency to prefer a particular set of sequences? The delay between trigger pulls is likely to have some kind of normal distribution around 60 frames or so, but other than that... not sure whether I should investigate further or just try it and see how well it works. It's going to be in silico either way.
Last edited by Dafydd on Wed Mar 06, 2013 11:25 am, edited 2 times in total.

tepples
Posts: 21982
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Random Number Generation?

Post by tepples » Tue Mar 05, 2013 4:42 pm

What I'd use is a 16-bit LFSR (use Greg Cook's CRC16 from 6502.org) feeding Fisher-Yates.

User avatar
blargg
Posts: 3715
Joined: Mon Sep 27, 2004 8:33 am
Location: Central Texas, USA
Contact:

Re: Random Number Generation?

Post by blargg » Tue Mar 05, 2013 5:01 pm

Is there any reason you can't do a straightforward shuffle of 16 values in RAM? Write an array with 0-15, then step through each of the 16 entries and swap it with a random entry from the array.

User avatar
Dafydd
Posts: 114
Joined: Sun Mar 16, 2008 1:45 am
Location: Uppsala, Sweden

Re: Random Number Generation?

Post by Dafydd » Tue Mar 05, 2013 5:18 pm

How is a "straightforward" shuffle different from Fisher-Yates? It swaps with any value, not just the remaining ones? How does that ensure I don't get more than one of the same value in the sequence?

EDIT: Oh, wait. I'm stupid. Sorry.

User avatar
Dafydd
Posts: 114
Joined: Sun Mar 16, 2008 1:45 am
Location: Uppsala, Sweden

Re: Random Number Generation?

Post by Dafydd » Tue Mar 05, 2013 5:31 pm

Now I'm really confused. When swapping a with a[j] in an array of length N, what is the purpose of having 0 <= j <= i (as in Fisher-Yates) when it might as well be 0 <= j <= N-1 (as blargg suggests)? It should have something to do with breaking the (un-)bias, but I don't know for sure.

tepples
Posts: 21982
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Random Number Generation?

Post by tepples » Tue Mar 05, 2013 6:11 pm

In theory, there's a bias in the case of 0 <= j < N. Proof: There are N! distinct permutations after the algorithm. With 0 <= j <= i, there are also N! distinct paths to these permutations. But with 0 <= j < N, there are N^N equally distributed paths. Because N! does not generally divide N^N (example: N = 3; 3! = 6 does not divide 3^3 = 27), these states don't all have the same number of paths to them; therefore bias.

But in practice, I dare someone else to prove that this bias is any more noticeable than the limitation that a CRC16 can generate only 65536 of the 2.1×10¹³ distinct permutations.

User avatar
Dafydd
Posts: 114
Joined: Sun Mar 16, 2008 1:45 am
Location: Uppsala, Sweden

Re: Random Number Generation?

Post by Dafydd » Tue Mar 05, 2013 6:21 pm

I drew a trinary tree of possibilities for the array of [1, 2, 3] (i.e. length 3) and came up with 27 leaves, distributed like so:

123 x 4
132 x 5
213 x 5
231 x 5
312 x 4
321 x 4

I came up with a more elegant explanation, but tepples beat me to it.

Anyway, in this particular case, as tepples suggests, I think I'll run with blargg's version, because it's much easier to implement, and because the bias isn't going to matter, especially since the input will be shuffled from last time anyway.

Thanks, guys!

zzo38
Posts: 1064
Joined: Mon Feb 07, 2011 12:46 pm

Re: Random Number Generation?

Post by zzo38 » Sat Mar 09, 2013 1:03 am

I used ARCFOUR, running several times per frame when nothing else is doing, and including the microphone if it is available.
[url=gopher://zzo38computer.org/].[/url]

User avatar
TmEE
Posts: 747
Joined: Wed Feb 13, 2008 9:10 am
Location: Estonia, Rapla city (50 and 60Hz compatible :P)
Contact:

Re: Random Number Generation?

Post by TmEE » Tue Mar 12, 2013 5:36 am

This is not exactly NES stuff but in my MD game "Glass Breaker" I used this to create some garbage for random enemy business :

Code: Select all

MOVE.W (GARBAGE), D0
MOVE.W D0, D1
NOT.W  D1
ROR.W  #3, D0
EOR.W  D1, D2
ADD.W  D1, D0
ROL.W  #7, D1
ADD.W  D1, D0
EOR.W  D2, D0
MOVE.W D0, (GARBAGE)
It takes quite little time and provided me adequate enough output for the things I needed.
I did not really spend much time on, just arranged some instructions until I got satisfying result...

Post Reply