From TetrisWiki
Jump to navigation Jump to search

One issue with the history function: How do you pre-program history, as done in the actual TGM Randomizer?

And also, having a program that can process a randomizer specification string, and then output a list that would be produced by it. I'm guessing that this will happen as part of the development process, though :-) --Lardarse 13:55, 27 December 2006 (EST)

Things that seem impossible with the current specification so far:

  • Pre-population of history
  • Looping through arbitrarily defined strings (eg. Recreating the Sega Tetris power-on pattern or TGM3's Sakura pattern)
  • Checking from multiple histories flushed at independent timings (Panel de Pon/Puzzle League uses multiple histories to avoid pieces clearing immediately upon entry)
  • Arbitrary sequence of random choices from multiple predefined groups (Puyo Pop Fever has a fixed sequence of piece shapes in random colors - If the sequence was domino domino tromino domino domino tetromino, for instance, the shapes would always come in that order, but in different colors every time)
  • Reusability via XML


"Pre-population of history"? Granted. I'll just hardcode Z,S,... in the first public implementation until we find a better way. Does with Z,S,Z,S history look OK?

"Looping through arbitrarily defined strings"? In theory, this pathological case could be expressed in Blackjack as a a 65536-piece deck with 65535 history, but at least my first implementation of Blackjack won't support decks that big.

"Multiple histories"? PDP != Tetris. Still, as I understand it, PDP actually checks the bottom line of the playfield as it exists, not as it was generated. Still, you could just run six Blackjack objects in parallel.

"Arbitrary sequence of random choices from multiple predefined groups"? Puyo != Tetris. Still, this would be easy. Run two Blackjack objects, one set to I2,I2,L3,I2,I2,O with 5 history and the other set to R,Y,G,C,B.

"Reusability via XML"? XML is often thought of as an overrated serialization. In fact, editors of Ward Cunningham's design pattern wiki have called XML a poor copy of Lisp's S-expressions. A lot of AJAX sites use JSON or other custom notations that are smaller across the wire than XML. If you insist on XML for some odd reason, is it really that hard to do?

  <history rolls="6">

What seems difficult to me is that the generality of Blackjack brings in more computational and RAM overhead than fixed-function randomizers. I'll probably include Blackjack as an option in Lockjaw for PC (where even my 6-year-old machine is 866 MHz with 128 MB of RAM) but not in Lockjaw for GBA (where every machine is 16.8 MHz with about 0.3 MB of RAM). The current randomizer has about 20 bytes of state; Blackjack's increased generality needs about 160 bytes.--Tepples 22:55, 27 December 2006 (EST)

As for Panel de Pon and Puyo, I fail to see the reason this needs to be limited to Tetris and not for piece-dealing games in general (Chiral, Pipe Dream, Hexic, ...). The criteria between including a feature in the language specs and excluding it to outside handling seems pretty arbitrary at this point.
As for XML, just looking at the success BulletML has enjoyed in generalizing and reusing shmup barrage patterns. I guess a personal bias toward lower-powered hardware takes that down.


"Pre-population of history"? Granted. I'll just hardcode Z,S,... in the first public implementation until we find a better way. Does with Z,S,Z,S history look OK? - Sounds good, as long as we specify that "card" names can't start with a number. That will likely make your job easier.

I also see a use for Blackjack in multiple piece-dealing/block-dropping games, even if it means that we need multiple Blackjack machines running. To that end, it would be nice if we could have the entire state in 1 array/string/struct.

Is there any chance we could document the piece order for each character in Puyo Pop Fever, and have more infomation about the PdP randomization system (including frequency of "shock blocks")?

XML does feel like overkill for this. And keeping it all one one line means that we could store it in lj.ini, for example.

There is one other thing that this doesn't support, but I'm not sure you want to be thinking about it just yet... --Lardarse 08:40, 28 December 2006 (EST)

"I fail to see the reason this needs to be limited to Tetris" I didn't intend to limit it to Tetris. I just didn't want scope creep to destroy my will to get an 0.1 implementation out. Randomizers in Columns, classic Puyo Pop, and classic Lumines appear to resemble Dr. Mario's R,Y,B repeated once for each block in the piece.

"The criteria between including a feature in the language specs and excluding it to outside handling seems pretty arbitrary" - My criterion is the analogy to a single deck of playing cards. Bag and History style randomizers can be described in terms of physical operations on cards. The whole original proposal (n bag of list) was based on my observation that the randomizers in card games work almost exactly like Random Generator, prompted by Lardarse's suggestion of a cut point.

As for multiple objects vs. one object determining multiple attributes: In Monopoly, Community Chest and Chance would be represented as separate Blackjack objects because they are obviously separate decks. If the color and shape of a piece are determined together, as the suit and number on playing cards (H4, S9, CJ), then the analogy holds. Likewise, the 3D orientation of a snake or gun tetromino is determined with its shape by splitting S and Z into separate elements. But if the color and shape of a piece are determined separately, you need two randomizers. If you're making random fast food meals, you'll want one randomizer involving BigMac,QuarterPounder,FiletOFish, one involving Fries,OnionRings,OrangeSlices,Applesauce,SideSalad, and one involving Coca-Cola,DietCoke,Sprite,ChocolateShake,Coffee. --Tepples 13:31, 28 December 2006 (EST)

There are a fe other things that I would like to add to the specification at a later date, but I am unable to find a way to explain it in words, and I am willing to wait for a while if it will allow development to proceed more efficiently. --Lardarse 20:32, 29 December 2006 (EST)


There are now two options for first:

spec first list
Follow spec, except choose the first piece from list.
spec first sequence of list
Follow spec, except use list as the first length(list) pieces.

Also added an option to specify the initial history list:

list with len history past history_list
list with len history number rolls past history_list

Sample implementation in Python

Use regular expressions for now, a C implementation will be more complicated.

The beginning of a Blackjack expression has two optional choices: [n] bag of or sequence of. Followed by the actual list: list History has several optional parameters tacked onto the end of it: with len history [number rolls]? [past history_list]? And finally 'first' or 'first sequence of': first[ sequence of]? list

 def bj_regex():
   nbag_regex    = r'(?:(?:(\d*)\s+)?(bag\s+of))'
   seq_regex     = r'(:?sequence\s+of)'
   bors_regex    = r'(:?' + nbag_regex + r'|' + seq_regex + r')?'
   past_regex    = r'(?:\s+past\s+(\S*))?'
   roll_regex    = r'(?:\s+(\d*)\s+rolls)?'
   history_regex = r'(?:\s+with\s+(\d*)\s+history' + \
                   roll_regex + past_regex + r')?'
   first_regex   = r'(?:\s+first\s+(sequence\s+of)?\s*(\S*))?'
   final_regex   = r'\s*' + bors_regex + r'\s*(\S*)' + \
                   history_regex + first_regex + r'\s*'
   return final_regex

Next, use the regular expression to parse a string. The results should be cleaned up to convert string to integers and the piece list string to an an actual list.

 def parse_rule(rule):
   import re
   (ignore, nbag, is_bag, is_seq, _list, hlen,
    rolls, past, is_first_seq, first) = \
     re.match(bj_regex(), rule).groups()
   nbag         = (nbag != None and int(nbag) or 0)
   is_bag       = (is_bag == 'bag of')
   is_seq       = (is_seq == 'sequence of')
   _list        = _list.split(',')
   hlen         = (hlen  != None and int(hlen)  or 0)
   rolls        = (rolls != None and int(rolls) or 0)
   past         = (past  != None and past.split(',') or [])
   is_first_seq = (is_first_seq == 'sequence of')
   first        = (first != None and first.split(',') or [])
   if(is_bag and nbag == 0): nbag = len(_list)
   return (nbag, is_bag, is_seq, _list, hlen, rolls,
           past, is_first_seq, first)

Sanity check results:

 >>> TGM2_rule = 'I,J,L,O,S,T,Z with 4 history 6 rolls past Z,S,Z,S first I,J,L,T'
 >>> parse_rule(TGM2_rule)
 (0, False, False, ['I', 'J', 'L', 'O', 'S', 'T', 'Z'], 4, 6, ['Z', 'S', 'Z', 'S'], False, ['I', 'J', 'L', 'T'])

The actual piece generator needs some extra values aside from the rules. A move number, so it can handle first and first sequence of, the history, and for bags, it needs what is remaining in the bag, and how many items left to select before refilling the bag.

 class struct:
   def __init__(s, **e): s.__dict__.update(e)
 generator = struct(
   rules          = parse_rule("S,Z with 1 history"),
   nbag_remaining = 0,
   current_list   = [],
   history        = [])

A quick utility function to randomly select a single item from a bag:

 def rand_from(l):
   from random import randint
   length  = len(l)
   random  = randint(0,length-1)
   return l[random]

The outer function which handles history:

 def gen_piece(generator, move_number):
   (nbag,  is_bag, is_seq,       _list, hlen,
    rolls, past,   is_first_seq, first) = generator.rules
   if(move_number == 0):
       generator.history = past
       while(len(generator.history) < hlen):
   piece = gen_piece1(generator, move_number)
   generator.history = generator.history[1:]
   return piece

And the inner logic which actually generates a piece:

 def gen_piece1(generator, move_number):
   (nbag,  is_bag, is_seq,       _list, hlen,
    rolls, past,   is_first_seq, first) = generator.rules
   if(is_first_seq and move_number < len(first)):
       return first[move_number]
   if(first != []  and move_number == 0):
       return rand_from(first)
   if  (is_first_seq): move_number -= len(first)
   elif(first !=  []): move_number -= 1
       return _list[move_number % len(_list)]
       if(generator.nbag_remaining == 0):
           generator.current_list   = _list[:]
           generator.nbag_remaining = nbag
       piece = rand_from(generator.current_list)
       generator.nbag_remaining -= 1
       return piece
   if (hlen == 0):
       return rand_from(_list)
   elif (rolls > 0):
       for i in range(rolls):
           piece = rand_from(_list)
           if(piece not in generator.history):
               return piece
       return piece
       local_list = _list[:]
       for piece in generator.history:
           if(piece in local_list):
       return rand_from(local_list)

Some examples and some notes:

 def test_generator(rule, count):
   generator = struct(
       rules          = parse_rule(rule),
       nbag_remaining = 0,
       current_list   = [],
       history        = [])
   print "".join([gen_piece(generator, i) for i in xrange(count)])
 test_generator("sequence of D,E,F,G first sequence of A,B,C", 8)
 # Outputs: ABC..DEFG..D, not ABC..G..DEFG..
 test_generator("S,Z history 1", 6)
 # Outputs: SZSZSZ or ZSZSZS as expected.
 test_generator("bag of I,J,L,O,S,T,Z", 7*10)

Code released under the public domain. -- Lambda