# Randomizer Theory

Thread in 'Research & Development' started by colour_thief, 12 Jan 2007.

1. ### colour_thief

My results do assume that an unbiased pseudo-randomness is feeding the history/reroll algorithm. Do you have a way of logging each roll as well as each chosen piece? This would confirm if I messed up (rolls even out to 1/7 for all pieces) or if there is other weirdness at play.

If you wouldn't mind double-checking the bit patterns of the pieces I would appreciate it also.

L 000
J 001
I 010
O 011
Z 100
S 101
T 110

Last edited: 3 May 2013
2. ### Xkeeper

I should've saved the notes from last night, but if you can repost them here (specifically, to check where when what gets executed) I can dump that too.

Code:
L	000
J	001
I	010
O	011
Z	100
S	101
T	110
Hmm, my values are
Code:
[0x00]	= "L",
[0x04]	= "J",
[0x08]	= "I",
[0x0C]	= "O",
[0x10]	= "Z",
[0x14]	= "S",
[0x18]	= "T",

I would say that matches up.

Also, I let it run overnight.

Code:
T   784596   21.47%
J   552636   15.13%
I   542390   14.85%
O   516755   14.14%
S   506106   13.85%
Z   414194   11.34%
L   336876    9.22%
3653553
Good job, Nintendo.

3. ### Xkeeper

I'm really hoping this is an error on my part, but...

4. ### colour_thief

At \$2054 register D stores the piece roll value. Very curious to see if the basic rolls are biased.

Last edited: 8 May 2013
5. ### Pineapple

Hold on. That's Tetris DX, not Tetris (G. Are you saying that they're both as bad as each other?

Also, I seem to remember that TDX is easily to RNG manipulate, so your sampling method may be affecting things. In both games, now that I think about it...

Last edited: 3 May 2013
6. ### colour_thief

The method he's using is letting pieces drop while a script artificially clears the field. I'm not sure how the underlying RNG works but it could introduce bias that would only come from such unnatural consistency.

If the basic piece rolls show bias, my next request would be to play a couple hundred pieces manually and see if the pattern disappears.

7. ### Xkeeper

That's what I was starting to suspect too, so I re-ran it but disabled pushing buttons, and also made the pieces lock randomly across the board (in case it was taking playfield state into account for some bizarre reason):

So I tried playing a quick game up to 116 pieces:

Conclusive, no, but highly suggestive, yes. Also notice the glut of T-pieces in the playfield already in this screenshot (the green blocks all along the left + scattered about).

Not looking good.

8. ### Xkeeper

Tetris GB:
http://pastebin.com/vqmxV1gE

Tetris DX:
http://pastebin.com/tSxxdfHc

These scripts should count pieces dealt using vba-rr (google). It's not perfect but it does the job.

In the case of Tetris GB you'll have to push X to see (or change it to if true or inpt['X'] then)

9. ### Kitaru

Couldn't it just be that the timer register is not an appropriate source for randomness after all? Maybe we should also be keeping track of all the values the timer register takes on whenever we hit the line in the code from which it is polled.

10. ### Zaphod77Resident Misinformer

The problem with gathering entropy during gameplay is that it allows players to skew the randomness. this is known as "luck manipulation" and is commonly used in tool assisted speedruns. NES tetris, for example does this. I dunno about GB etris. also tetri DX may not have the same randomizer.

11. ### Xkeeper

That is correct, but if the randomizer is showing badly skewed results with no input or with real-player input then there is a severe problem.

In-game entropy should be sufficient, assuming that you cannot manipulate pieces as a human player (no savesates/rewinds).

12. ### Pineapple

I think that this is getting to the point where I'd rather have the actual sequence output, rather than just the count. It might help us to see what's going on.

13. ### Xkeeper

The scripts provided can provide it if you want to output it in some format (perhaps by printing it to the output window). Worst case I'll let it run for a while and log it myself.

14. ### colour_thief

Re-reading the assembly, I think I understand the general nature of the bias.

I can say that 100% of the source "random" numbers are taken from the Game Boy's divider register. This is an 8 bit (0-255) number that increments once for every 256 of the CPU's clock cycles, if I understand the specs properly. Input and the game field don't affect the randomness directly. Luck manipulation would happen as a result of causing more or less CPU cycles to elapse before the divider register is read for its "random" number.

Now for a given roll 0-255, the code that converts this to a piece 0-6 and checks for "duplicates" takes a completely predictable amount of CPU cycles. So rather than there being 256^3 possible sets of 3 rolls, if my gut instinct is right there's instead just 256. Each roll, if rejected, will be followed by the exact same next roll, every time. And mapping these out will reveal the bias we are seeing.

15. ### Pineapple

Output to text file would be far easier to use, especially for large amounts of data. One piece per character, no line breaks unless there's a new game, please.

16. ### Xkeeper

Just to sate my curiosity, how are you disassembling these games? I wasn't aware there was a particularly decent GB disassembler.

17. ### Kitaru

Personally, I just used BGB's built-in debugger.

18. ### colour_thief

I'm actually reading a text dump Kitaru gave me haha

19. ### Zaphod77Resident Misinformer

sure manipulation to the extent seen in a TAS isn't possible real time. But in my experience games that do collect entropy this way seem very fickle, and fairly often skew the results far from what probability should suggest.

20. ### colour_thief

Kindly state what that experience is or back out of this discussion, Mr. Misinformer.