# Randomizer Theory

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

1. ### colour_thief

Yeah deep bag concepts are neat, I should explore them more than I have. I have a framework where even for highly experimental randomizers I can automatically calculate exact drought curves, entropy, conditional entropy, perplexity etc. I keep meaning to properly write up the stuff I've discovered but have been perpetually side tracked.

I don't think I've posted this here but this is probably as close as I'll get to a proper exposition for a while:
twitch.tv/videos/1085579617
When you internalize my methods a bit you start getting pretty nice intuitions about how these different randomizers will play out.

I'm definitely eternally passionate about this stuff so if you check it out and have questions hit me up!

2. ### Arcorann

I dug up the link I got from you a couple of years back and read through the stuff there; I see you've added some things since then.

Speaking of things from a couple of years back, another thing I talked about on Discord back then but never publicly was Tetris with Cardcaptor Sakura's randomiser in Easy. Based on my notes, they tried to do a 3-history 4-roll randomiser with biased piece probabilities, but the reroll code was bugged so the history was effectively ignored. Unfortunately I seem to have forgotten to write down the exact probabilities of each piece type...

3. ### colour_thief

That's pretty neat that they experimented with a couple different randomizers in there. Hopefully someone digs into it again at some point.

4. ### Arcorann

I tried to implement what I'm calling (as a temporary name) the (1,6) bag stack (using the principle I described the other day with two bags of size 1 and size 6, with the 1 on the bottom) and it appears to have exposed a flaw in your entropy calculation -- running the calculation gave me an entropy of 0.00%, which is obviously wrong (exercise: show that this bag stack is equivalent to a strict 1 history randomiser). Are you interested in having a look to see whether you get the same result?

5. ### colour_thief

Sure I'll give it a shot. Like post #260 yeah? What's the setup exactly (what bag sizes)? Just a single piece in the bottom layer? I must be missing something because that's sounds equivalent to pure random with forbidden repeats.

6. ### Arcorann

It looks to me like you have the right model in mind. I picked a simple case for testing (the (2,5) and (3,4) cases are more interesting, as are those where we have 14 or more pieces in the system) and the fact that it's equivalent to strict 1 history makes it really easy to derive the correct values for everything. However, it also has the property that given the state the next piece is known exactly, which seems to be tripping up your entropy calculation.

7. ### colour_thief

I tried to implement it today and I think I see the issue. To use my tools you have to represent a randomizer as a digraph with a finite number of states. To give a practical test to figure out when this is the case:

If you know the current state and the piece dealt, and can deduce with certainty what the next state is, then these methods work. (example: NES, TGM1, TAP, 7-bag etc.)

If, even if you know the current state and piece dealt, the next state is ambiguous, then these methods don't work. (example: TGM3 has not-player-visible rerolls that change the probabilities of piece types by weighting them differently in the bag of 35) But if you can express the same randomizer with unambiguous states then you're good.

If you're familiar with some finite automata theory you'll know that automata with multi-digraph structures can be transformed into equivalent simple digraph structures using a "powerset construction"). eg. if your automata has n states, then you can simply create a new automata with 2^n states for the powerset of states.

The issue with the powerset approach with our case (stochastic automata) is that instead of a powerset of all states (each a simple binary 1 or 0 for set inclusion), we have probabilities. And if you work out some examples by hand you'll see that there are actually infinite states when you try to represent the multidigraph this way. This doesn't mean there's no way to take a multidigraph and transform it into an equivalent digraph but this is a very hard general problem and I don't have a function that can do it yet.

To go in specific detail about your deepbag example... You're getting 0 entropy because (I'm assuming) you programmed it in a way that implies you always know what's in the front bag. If you do, then (1,6) truly has 0 entropy. In reality even if you knew your current state, after seeing a piece dealt you would only know 6 possible next states each of probability 1/6. But you could go arbitrarily long without, say, moving the I piece into the front bag. And with each piece dealt the probability of the I piece is in the front bag can only stay the same or increase, getting arbitrarily closer to 100%. So we have an infinite state explosion problem when you try to represent the randomizer in graph form using a "stochastic power set" vector.

This stuff is pretty interesting to me and I'd like to handle these cases more elegantly but it is a little over my head and I'm not even entirely certain that it's not an unsolved problem in theoretical computer science.

8. ### Zaphod77Resident Misinformer

Interestingly Heboris U.E. has an odd family of randomizers called hebo2 through hebo7 that aren't used by default (it usually uses 4 history 6 rerolls)

These randomizers draw the listed number of pieces from the bag, but will put the piece back in the bag and reroll if it matches the previous one.

Additionally, they never start you with O S or Z by default.

so hebo7 is even kinder than 7 bag, because it never gives a direct repeat ever. it can't give you ss or zz, or even szz or ssz or zzs or zss. it can still give you SZSZ and ZSZS, though. It makes tetris tetris tetris combo even harder though.

hebo6 will never give you a repeat either, but it can starve you of a piece longer than bag can. so it's more unpredictable. with the lower numbers capable of starving you of more pieces at once.

9. ### Zaphod77Resident Misinformer

I have finally sussed out Bloxeed's piece randomizer precisely.

It's a variant of sega tetris, which has been reversed already.

Instead of generating a 1k sequence, it runs the main generator once (identical to sega except that the seed is one higher), and stores all 32 bits of the result as the seed for the piece generator.

Instead of taking the lower 6 bits of the result, and doing a modulo 7 to pick a piece it takes the lower SEVEN bits of the result. This introduces a slight bias towards I and Z, compared to the original sega slight bias for I.

If the upper three bits of the result and 0X7f are all set (if ((result & 0x70)==0x70) ) then a flag is set to turn s and z into I for that roll.

This means that compared to sega tetris, which had a slight bias for I and I only (10 in 64 chance, vs 9 in 64 chance for the others), Bloxeed has a bigger bias towards I, and hands out less S and Z. Piece probabilities are

I:3/16
S:1/8
Z:1/8
J:9/64
L:9/64
O:9/64
T:9/64

those last four are same as sega tetris.

While this isn't an exact translation of the assembly code, it produces identical results, and replicates the poweron pattern exactly.

This is to make up for the advancing garbage. Only correcting a roll of 127 was required to ring the results inline with original sega tetris, but this additional adjustment was clearly intended to make it not give out as many stupid snake sequences (and there are some really stupid ones in sega's poweron pattern).

It also doesn't loop. it instead backs up the piece seed so it can turn back the clock when you continue.

This is of course now in my Hebo U.E. fork.

10. ### Arcorann

Anyone have any randomizer algorithms they're interested in simulating? I managed to code up the Master of Blocks 4 algorithm and it seems to be going well (it's an interesting mix of bag and history).