Randomizer Theory

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

  1. "Drought" is a bit fuzzy (e.g., Should we use the properties of 7 Bag as an indicator and consider the minimum condition for an I-piece drought to be >12 pieces before seeing that piece dealt? Should we consider anything beyond the expected value of 1/7?), but "sequence" I think we can get a better handle on.

    The length of the game before reaching the more-or-less unsustainable Level 29 is 230~290 lines depending on starting level. At 2.5 pieces per line, that makes the bare minimum piece count 575~725. If we allow for some play into Level 29+, you could start seeing piece counts around 750~850, but we have not seen much more than that. "A sequence" long enough to constitute an entire game for a human at current standards of play is certainly less than 1000, so we can use that as a very generous upper-bound.
     
  2. Droughts are always a bit context sensitive, aren't they? I don't know what metric they use at the NES tournaments, but certainly anything longer than 12 pieces starts to feel like a proper drought. We may as well throw down a (somewhat) arbitrary marker there. When I have time to go back thru this whole thread, I can probably work out the solution myself, but I was hoping someone already knew the answer, even if it's just intuitively from a deeper well of experience.
     
  3. zid

    zid

    Why arbitrarily rebase them onto an offset from 12?

    Just the number of pieces since you last saw that piece is a perfectly acceptable metric. It'll probably be about 7, 12 is slightly unusual, more is painful.

    It's more like an "x hours since coffee pot was changed" sign than a metric you want to keep as low as possible, so maybe it's just the word 'drought' that needs fixing.
     
  4. Because the question I'm asking is "How many droughts will I have in an average maxout run of NES Tetris?"

    That's a question whose answer has direct implications for stacking strategy.
     
  5. In NES Tetris, the sum of the probability of droughts size 1 through 12 is slightly less than 86%. So if you consider 1000 pieces, your expected I-drought count is roughly (1 - 0.86) * (1000 / 7) = 20. Or put differently, once every 50 pieces.
     
    JBroms, GyRo and Kitaru like this.
  6. Actually, for this purpose, maybe >10 pieces might be more applicable?
    Theoretically (like if you can make the pieces fit), if at least every 10th piece is an I-piece, you'll be able to keep your stack stable infinitely without the need to "burn" lines (ie. clear lines without making a Tetris) for a "perfect transition".

    Of course, if your stack is low enough, you can afford to wait 20+ pieces for an I-piece without burning, but once that happens you probably can't afford the same wait again, so on average you probably still want around one in every 10?
     
    Kitaru likes this.
  7. I now have yet another metric by which we can evaluate randomisers, through considering correlations between consecutive pairs of droughts. For example, due to the design of the bag randomiser, pairs of droughts have a high negative correlation - if the interval between two appearances of an I is very short, the next appearance will be long. In fact, calculating the correlation coefficient gives -0.5, which is a significant negative relationship. Conversely, in memoryless there is no correlation at all. Most randomisers will fall between one of these two extremes.
     
    colour_thief likes this.
  8. I had a similar thought, but instead of looking at correlation I've been looking at entropy. While high correlations will have low entropy, hypothetically some low correlations could as well. So it can reveal when things are going on that might otherwise be hidden.

    Just to clarify your idea. Are you looking at the sequence of droughts for a certain piece type? Or a sequence of droughts in general (eg. as the randomizer sequence is progressing)? Because they are both different in distribution and I haven't convinced myself one is more important to consider than the other.
     
  9. I'm looking at consecutive droughts for the same piece (not sure how a sequence of droughts in general would work). I was inspired by someone complaining about how bag "forces droughts" - if we have two Is in a row we know that the next I must be at least 7 pieces after that. I've already written code for recording the empirical joint distribution in my current simulation code, and added in calculations for the expected drought given the last drought interval.

    I was also considering attempting to calculate the auto-correlation function, but I'm not sure how useful the extra info would be.
     
  10. I've come up with a new randomizer that behaves much like Ti's when used to generate tetrominoes, but is usable for any number of piece types, such as with pentominoes. It has no manually enforced restrictions on its behavior (such as a fixed bag size), yet it seems to have "TGM randomizer" behavior, rarely behaving badly, but usually producing sequences that are appropriate for Tetris games.

    Python 3 version:
    Code:
    import random
    
    # Generic implementation, without special handling for the first piece.
    def Randomizer(pieceTypes):
      droughtLengths = [1 for piece in range(pieceTypes)]
      while True:
        i = random.randrange(sum(droughtLengths))
        end = 0
        for genPiece in range(pieceTypes):
          start = end
          end += droughtLengths[genPiece]
          if i >= start and i < end:
            for checkPiece in range(pieceTypes):
              if checkPiece != genPiece:
                droughtLengths[checkPiece] += 1
              else:
                droughtLengths[checkPiece] = 1
            yield genPiece
            break
    
    if __name__ == '__main__':
      r = Randomizer(7)
      pieceNames = { 0 : 'j', 1 : 'i', 2 : 'z', 3 : 'l', 4 : 'o', 5 : 't', 6 : 's' }
      print(''.join(pieceNames[next(r)] for i in range(70)))
    
    The attached archive contains a Windows program, C source code for that Windows program (the source is portable C, with nothing Windows-specific), the Python 3 source code shown above, and a readme describing how to use the Windows program. If you're doing tests of really large sequences, I'd suggest using the Windows program or the C source code.

    From what little analysis that I've done, the maximum drought length seems to scale proportionally to the number of piece types, and as the generated sequence gets longer the maximum drought length slowly grows.

    I've also found that the average drought length might be about 5 (exactly 5, as the sequence length approaches infinity?) when generating tetrominoes, so maybe the average drought length is some constant for each number of piece types.
     

    Attached Files:

    colour_thief likes this.
  11. The maximum drought size is technically unbounded with that algorithm, and the average drought size has to equal to 7 (or however many distinct piece types there are).

    I'm not sure who made the first version of that but I've seen it before. A natural extension is to weight pieces by the drought size raised to some floating point exponent greater than 1.
     
  12. NullpoMino has linear distance weight, quadratic distance weight and exponential distance weight already implemented. Having played around with it a bit, I've obtained interesting results from functions such as (1.2^d - 0.8), which eliminates both droughts and floods quite nicely.
     
    Last edited: 1 Nov 2019
    colour_thief likes this.
  13. I think that's where I saw it! Thanks for sharing.
     

Share This Page