Randomizer Theory

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

  1. Muf

    Muf

    Right. Does that actually make a difference to my point though? NEStris has been broken (in TAS terms) for a while now, I don't think a new faster TAS is going to come out of this new information.
     
    Qlex likes this.
  2. 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.
     
    Qlex likes this.
  3. I'm still working out NES randomizer stuff but I think I have some interesting partial results to share. Try a little experiment! :D

    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.
     
    Qlex likes this.
  4. 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.
     
    colour_thief likes this.
  5. Nice to see it reflected in real data, nice job daleb!
     
  6. 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
     
  7. 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) :p
     
    Omio9999 likes this.
  8. 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.
     
    Last edited: 25 Dec 2016
    colour_thief likes this.
  9. 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.
     
    simonlc, xyrnq and Kitaru like this.
  10. 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?
     
    colour_thief likes this.
  11. 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.
     
  12. FeV

    FeV

    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.
     
    Last edited: 2 Aug 2017
  13. 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!
     
    FeV likes this.

Share This Page