Randomizer Theory

Muf has a point, the game is open to luck manipulation. But Qlex is also right, it all comes down to frame delays.

The sort of results I'm talking about are biases that exist assuming no luck manipulation. It describes the natural tendency of the game and is only useful for legit players. TASers have been using this knowledge for quite some time now. But even if they knew how this worked, there is new knowledge here in describing the natural bias of the algorithm.

 

I'm still working out NES randomizer stuff but I think I have some interesting partial results to share. Try a little experiment!

Test:
1. Power cycle the NES (not sure if reset will work)
2. Wait any number of frames (seed value doesn't matter)
3. Play 4 pieces

Result:
You will never, not once, receive TT, JJ, or ZZ duplicate sequences. It's impossible.

This specific test is easy to set up, but really it happens on an 8 piece cycle. So you can examine pieces 9-12 and find the same thing etc.
There are other patterns with other pieces, it'll be really interesting to see how this settles.

 

I used that script for the gameboy version of Tetris for a short time, here was the results: http://i.imgur.com/d7I6c3u.png

L 9.57%
T 17.38%
I 13.48%
O 18.44%
J 12.77%
Z 12.06%
S 16.31%

I think it fits the pattern described at the top of page 9 pretty well.
One way to look at it might be:
T, O and S being "high probability"
I, J and Z being "medium probability"
L being "low probability"
as the 3 categories for people to keep in mind when playing.

 

Nice to see it reflected in real data, nice job daleb!

 

Daleb, could you point me to the script you talked about? I want to add more pieces to the script, and present the info with larger numbers.

EDIT: My fingers bounced and mashed a "Post Reply" key combination by mishap, I think. xD

 

This one, from back on page 8: https://tetrisconcept.net/threads/randomizer-theory.512/page-8

I also posted example outputs from both of these (showing the bias quite well, I believe)

 

Correct me if I'm wrong but if the chosen piece is the same as the most droughted piece, would it not have the same effect wether it updated it or not? They are the same piece, so the end result is the same.

 

Sorry for the delay, been afk for most of the last month.

When the chosen piece is the most droughted piece, what *should* happen is that a new most droughted piece gets calculated and that new piece gets inserted into the bag slot that the chosen piece came from.

Instead there is no change to the bag of 35, which is a bug.

 

I've slowly been reading over all of this thread and trying to take it all in. To clarify further what CT last posted, the piece that is being placed into the bag should be calculated after the piece that is chosen is calculated. Instead what is happening is the piece that is being placed into the bag is being calculated before the piece that is chosen, so you can end up putting into the bag a piece that has a 0 drought. Is this correct?

 

I forget the specifics of the implementation but you could be right. The location receiving the 0 droughted piece already contains that piece so it doesn't do anything. So I may have simplified what was happening in my notes.

Not that you meant it but to clarify an ambiguity in what you wrote:
Each roll replaces the rolled bag index with a copy of the most droughted piece. This all happens as things are getting rolled, as opposed to all at once after the final roll. So if the final roll selects the most droughted piece, and assuming the above mentioned bug is not happening, then the last roll injects a "new" most droughted piece whereas all previous rolls injected the "old" most droughted (and selected) piece.

 

I did some looking into the TGM PRNG and TAP's piece sequences. As far as I can tell there is one master sequence of pieces, which has period 766,809,472 (in TGM1, the master sequence should be longer, in Ti not sure). The sequences you get when you play the game (starting at ZSSZ history) will converge on the master sequence after a small number of pieces.

It can be exactly zero (seed's sequence is just a starting point in the master sequence), which seems to be the case for a million or two seeds. I don't know an upper bound yet because I've been trying to work on other things, but I'm guessing it takes no more than 30 pieces for any seed to converge on the master sequence.

This is very much a consequence of the simple LCG rand() used in the games combined with history-reroll behavior. Over the course of the master sequence, for every piece you call rand() about 5.6 times. This is because although TAP tries 6 "rolls of the dice" or whatever, it in fact calls rand() /twice/ for the first 5 rolls, and zero times for the sixth roll (don't ask me why it works this way). So 1 roll is 1 rand(), 2 rolls is 3... , 6 is 10. Therefore on average it uses a little more than 3 rolls to determine each piece. Here's what the code looks like (in C):

Code:

for(i = 0; i < rerolls; i++) {
    t = read_rand() % 7;

    in_hist = 0;

    for(j = 0; j < hist_len; j++)
    {
        if(history[j] == t) in_hist = 1;
    }

    if(!in_hist)
        return t;

    t = read_rand() % 7;
}

return t;

After 2^32 rand() calls the sequence loops. Simple stuff but I haven't seen a lot of TGM specific PRNG discussion so I'm just putting it out there.

 

That's a really interesting analysts Fev. I'm curious if TGM3 has all seeds converging on a master sequence. Because the contents of the bag of 35 are always changing, the period might be crazy huge.

For sure let us know about an upper bound for convergence if you find one!

 

I decided to try reading Tetris DX's assembly again and I might finally be able to explain why the randomiser is so biased. Here's the code (from address 58B6, spoilered for length):

Spoiler

Code:

ld a,(AF84)
ld (AF85),a
ld a,(AF83)
inc a
cp a,07
jr c,58C5
xor a
ld (AF83),a
ld a,(ff00+04) ; divider register
and a,07
cp a,07
jr c,58D3
ld a,(AF83)
ld hl,AFB0
cp (hl)
jr nz,58E5
inc hl
ld a,(hl)
inc a
ld (hl),a
cp a,05
jr c,58E8
xor a
ld (hl),a
jr 58BC
ldi (hl),a
ld (hl),00
ld (AF84),a

It's not immediately obvious what this does, but based on my reading it can be translated roughly into this pseudocode:

Code:

currentPiece = nextPiece
pieceCount = (pieceCount + 1) % 7

// generate the piece
a = randInt(0..7)
if a == 7 {
    a = pieceCount
}
if a != lastPiece {
    lastPiece = a
    rerollCount = 0
} else {
    a = rerollCount
    a += 1
    rerollCount = a
    if rerollCount >= 5 {
        rerollCount = 0
        go back to the "generate the piece" comment
    }
}
nextPiece = a

Note the code executed when a == lastPiece: firstly, lastPiece isn't updated, and secondly, nextPiece is set equal to rerollCount. This code will be executed 1/7 of the time, and since the value 1 corresponds to the piece T this largely explains where the bias comes from.

Could someone confirm that I'm reading the assembly correctly?

Here's a sample piece sequence I just recorded, by the way (565 pieces, spoilered for length):

Spoiler

ZTOLSZOTTSOTJSIJOLOITJTJITJZSTLSTLOJLJSOJTSLOTLJTIJLTZLTLJZSTIOTZISTSOILSOLJZOTTLSZLIOJIJSJITSTZSOZLTOTSLIJISISOTJTOTZTOTOSLTOIJOTJTZTLZISTZOTSJIOJOTILSLOIJLSJTSLSTJOLOISZSTJLTZOJTISZIOSIZLSTZSTTOLIOSJTJTZSLSLJITJOSOSLTTZTLZTSZLTZTJTZSJSITZSTJZLJLZLZJZTLOJTZOTZTOZLTOILJZJSITZTTZSTTZSLSTOLJSITIJIOLJSZLTLSILTTZTLZJLTZTIOTTZTSOLILIOZSLJOTTOIOJTIZTZOZOJTOZLSITTOTJSZSTTJSLISTOTILTTTOJOLOLSOLTTOJIZIJIOZLOSILTJTISJOZLTJILTJZSZSJTLSTTOSLTJLJTZSLTZTJTIOZIZJSOJLOLIOIOSTSOSOSOTJLOIJTZITJTLOTZOLTZTLSIZSOITSLILOSZJLOZITOSTLIOLTZIOTZOTSJOIOLTJSOLSZZTTOTLOIJZOTTTZZTZLZIITZS

 

Code:

I: 61
J: 67
L: 77
O: 83
S: 76
T: 128
Z: 73

I made it an endpoint so you can query it to count pieces for you: https://piece-counter-m0u2ez0lasw9....ZIOTZOTSJOIOLTJSOLSZZTTOTLOIJZOTTTZZTZLZIITZS

 

@Arcorann I double checked your work and it looks accurate. A small thing I noticed is that when the reroll counter hits 5, it actually jumps slightly further back in the code and increments the piece counter a second time.

This is an extremely pedantic correction though, because I just played 500 lines and never triggered my breakpoint even once. I believe that if you maxed out the line counter (assuming that's 9999) you would expect to trigger this only once. Ain't nobody got time for that.

Another super minor correction is in the interpretation of expecting to branch on a == lastPiece 1/7 of the time. We know that 2 consecutive pieces determined by the piece counter are guaranteed to be different. So it's probably a bit worse than 1/7, something like 63/64 * 1/7 give or take weirdness in the DIV register. I swear the odds are even worse than that measuring it empirically.

Here's the piece mapping for reference:

0 = I
1 = T
2 = Z
3 = S
4 = J
5 = L
6 = O

This means that while T is still massively biased, to a lesser extent we should expect to see it with Z (and S and J but not I L O) if we looked at the stats of a long enough sequence.

Also because of the piece counter pieces, there are 7 piece pairs that are more common (similar to the a == lastPiece branching argument above). We would expect stuff like O -> I to be more common than I -> O even though both I and O are equally likely individually.

 

Thanks for the corrections. I'm almost certain they screwed up the rerollCount comparison, because if you make it the other way round the code makes a lot more sense (though not perfect sense), morphing into a slightly biased 5-reroll randomiser.

I haven't formally analysed a long sequence but I did notice some of those correlations in the short sequence I posted.

 

Figured I would dump this here because I recently found out about the drought bug independantly and had to go through the code with a fine toothed comb and update it:

Code:

#include <stdint.h>

typedef unsigned short piece_t;

enum PIECES
{
    PIECE_I,
    PIECE_Z,
    PIECE_S,
    PIECE_J,
    PIECE_L,
    PIECE_O,
    PIECE_T
};

struct rng_state
{
    piece_t  active_piece;
    uint16_t pad1;
    uint32_t field_4, field_8;
    uint8_t  rotation;
    uint8_t  lock1;
    uint8_t  lock2;
    uint8_t  pad2;
    uint32_t field_10;
    uint32_t seed;
    piece_t (*rand)(struct rng_state *);
    piece_t *sak_seq;
    uint16_t sequence;
    uint16_t held;
    piece_t preview[3];
    piece_t history[4];
    piece_t histogram[7];
    uint8_t bag[35];
    uint8_t field_63;
    uint32_t bone;
} __attribute__((packed));

unsigned short piece_rand(uint32_t *seed)
{
    uint32_t t;

    t = 0x41C64E6DUL * *seed + 12345;
    *seed = t;
    return (t >> 10) & 0x7FFF;
}

static int piece_in_history(struct rng_state *r, piece_t piece)
{
    if(r->history[0] == piece)
        return 1;
    if(r->history[1] == piece)
        return 1;
    if(r->history[2] == piece)
        return 1;
    if(r->history[3] == piece)
        return 1;

    return 0;
}

static void history_push(struct rng_state *r, piece_t piece)
{
    r->history[3] = r->history[2];
    r->history[2] = r->history[1];
    r->history[1] = r->history[0];
    r->history[0] = piece;
}

static void histogram_update(struct rng_state *r, piece_t piece)
{
    unsigned int i;

    /* Every piece has now not been seen for 1 more piece */
    for(i = 0; i < 7; i++)
        r->histogram[i]++;

    /* Except for the piece we just picked */
    r->histogram[piece] = 0;
}

static piece_t tgm3_rand(struct rng_state *r)
{
    piece_t piece, droughted_piece;
    unsigned int bagpos, i, j, highscore;

    highscore = 0;
    droughted_piece = 0;

    for(i = 0; i < 6; i++)
    {
        bagpos = piece_rand(&r->seed) % 35;
        piece = r->bag[bagpos];

        /* Piece is not in the history, this is fine */
        if(!piece_in_history(r, piece))
            break;

        /* Calculate least seen piece */
        for(j = 0; j < 7; j++)
        {
            if(highscore < r->histogram[j])
            {
                highscore = r->histogram[j];
                droughted_piece = j;
            }
        }

        /* Piece is already in the history, churn the bag a little and reroll */
        r->bag[bagpos] = droughted_piece;

        /* We might be about to fall out of the loop, pick something at random */
        bagpos = piece_rand(&r->seed) % 35;
        piece = r->bag[bagpos];
    }

    /* Make the pieces we didn't pick more likely in future, and this piece less */
    histogram_update(r, piece);

    /* ORIGINAL BUG: highscore = 0; missing */
    for(j = 0; j < 7; j++)
    {
        if(highscore < r->histogram[j])
        {
            highscore = r->histogram[j];
            droughted_piece = j;
        }
    }

    r->bag[bagpos] = droughted_piece;

    return piece;
}

void __cdecl init_randomizer(struct rng_state *r, uint32_t seed, char is_sakura)
{
    unsigned int i;
    piece_t piece;

    /* Initialze bag with 000001111122.. */
    for(i = 0; i < 35; i++)
        r->bag[i] = i/5;

    r->seed = seed;

    r->rand = tgm3_rand;
    /* Pick first piece, it can't be a Z S or O */
    while(1)
    {
        piece = piece_rand(&r->seed) % 7;

        if(piece != PIECE_Z && piece != PIECE_S && piece != PIECE_O)
            break;
    }

    /* Active/previews are offset by 2 for some reason */
    r->active_piece = 2;
    r->preview[0] = piece + 2;
    r->preview[1] = piece + 2;
    r->preview[2] = piece + 2;

    r->history[0] = piece;
    r->history[1] = PIECE_Z;
    r->history[2] = PIECE_S;
    r->history[3] = PIECE_S;

    r->histogram[PIECE_I] = 4;
    r->histogram[PIECE_Z] = 4;
    r->histogram[PIECE_S] = 4;
    r->histogram[PIECE_J] = 4;
    r->histogram[PIECE_L] = 4;
    r->histogram[PIECE_O] = 4;
    r->histogram[PIECE_T] = 4;

    r->field_63 = 1;
    r->bone = 0;
    r->held = 0;
}

piece_t piece_pop(struct rng_state *r)
{
    piece_t piece;

    piece = r->rand(r);
    history_push(r, piece);

    if(r->bone)
        piece |= 0x20;

    r->active_piece = r->preview[0];
    r->preview[0] = r->preview[1];
    r->preview[1] = r->preview[2];
    r->preview[2] = piece + 2;

    return piece + 2;
}

Too lazy to add the sakura stuff though.

 

I'm just skimming thru this thread again, but based on some of the true random piece distributions I saw, I've ballparked it at about 5-6 I block droughts expected in a given maxout run on NES Tetris. Does that sound right? The number you would expect (and also the variance, which I don't have a sense of) is relevant to optimal stacking methods.

 

What's your definition of a drought and how many pieces is a sequence?