Different Tetris Algorithms

I am currently writing my Master’s thesis and using Tetris as a game of reference.  In a pre-test I needed a quick version of Tetris, that records a lot of the interaction and tests different algorithms for choosing blocks.  Before I present the resulting implementation (Pytris), I want to briefly talk about algorithms that choose blocks in Tetris.  Part of this post is in the draft of my written thesis as well.

But lets get into the heart of Tetris: how to choose blocks! Next to obvious solutions like a random choosing of all available blocks, there have also been propositions of using Tetris games as means of communication by encoding information in how the blocks are chosen. This selection of blocks is then still supposed to appear random or at least semi-random to an unknowing player of such a game (see for an example Ou, 2011).

In this post, the five algorithms implemented are presented with the general idea behind how the blocks are chosen. An exemplary implementation of each algorithm is provided in Python.

Nicetris

In order to offer players an algorithm that helps them learn the game and play it with a minimum amount of challenge, the Nicetris algorithm has been designed specifically for this work, but with the inverted principles of the Bust Head (see below) algorithm. By analysing the situation of the current game board and especially, how the contour looks like.situation[4] in the code example refers to an array containing all shapes, that are fitting the current built-up. If the current built up is really not fitting for any piece (which is theoretically impossible), the choice is made from the set of generally well fitting blocks (O, I, and L-blocks).


nice_bag = []
for element in bag:
  if element in situation[4]:
    nice_bag.append(element)
if len(nice_bag) > 1:
  return choice(nice_bag)()
else:
  return choice([I,O,L])()

This approach was designed to ensure that the player always has an edge-fitting option to place the current tetromino and, hence, enable them to clear rows fast.

Grab Bag

According to the Tetris Wiki, this is the original Tetris algorithm. Essentially, all possible tetrominoes are put in a bag and drawn randomly one after the other without replacement, which means, until the bag is empty. Then, another bag is started for the next seven pieces.


if len(ungrabbed_bag) == 0:
  ungrabbed_bag = [ O, I, S, Z, L, J, T ]
block = choice( ungrabbed_bag )
ungrabbed_bag.remove(block)
return block()

This is assumed to create a fair random game. The properties of this algorithm are, that there are at most 12 pieces between two I tetrominoes and a maximum of four ß pieces can come in a row. Hence, the chances of encountering a run of the same (bad) pieces are eliminated.

True Random

The most basic algorithm for choosing blocks in a game of Tetris is the True Random version.

return choice( O,I,L,J,T,S,Z )()

This algorithm is equal to drawing from an urn of tetrominoes with replacement. Very fortunate and very unfortunate series of blocks are likely in an equal way. However, this algorithm might actually sometimes show stronger patterns than the others.

Skewed Random

In order to increase the likelihood for a kill sequence as described by Burgiel, 1997, Skewed Random assigns a 50% chance to either of the ß (S or Z) pieces instead of the usual likelihood of 2/7 = 28.57%.


if random.randint(0,1) == 0:
  return choice([S,Z])()
else:
  return choice([O,I,L,J,T])()

Mild Skewed Random

A milder version of this algorithm adapts Skewed Random as such, that the likelihood for ß pieces are at about 39%. This version is expected to still be more difficult than the previously described algorithms (Nicetris, Grab Bag and True Random) while being less harsh than the 50% version.

Bust Head

This algorithm is inspired by the Bastet game developed by Frederico Poloni. While his version relies on a well analysis, the version used in this research is based on a contour analysis, but with a similar idea. First, the algorithm checks, which pieces do not fit the contour (fitting pieces are recorded in an array in situation[4] in the code example). Then, a bag of these pieces plus the O piece is used to randomly choose the next tetromino. If every possible tetromino could fit the contour, the undesirable combination of O and ß pieces is used as a bag for the next elements.


tiny_bag = [O]
for element in bag:
  if element not in situation[4]:
    tiny_bag.append(element)
if random.randint(0,2) > 0:
  if len(tiny_bag) == 1:
    return choice([O,S,Z])()
  else:
    return choice(tiny_bag)()
else:
  return choice(bag)()

While Bastet and Bust Head share the same core idea, which is to create a really difficult game of Tetris, their methods of achievement differ. Hence, the algorithm used here is named differently, but phonetically similar in order to keep the roots of the idea in mind.

I hope this helped a bit in understanding that randomness can be achieved in different ways and how the choosing block algorithm in Tetris can be manipulated.  This helps then in understanding the soon to come implementation description for Pytris.

Join the Conversation

1 Comment

Leave a comment

Your email address will not be published. Required fields are marked *

twelve + 1 =

This site uses Akismet to reduce spam. Learn how your comment data is processed.