History of Tetris randomization algorithms

In 1985, Alexey Pajitnov and Vadim Gerasimov released Tetris. This fascinating and highly addictive game required players to connect randomly appearing pieces. Since then, more than 150 licensed versions of Tetris have been released. Differing in game modes, rules, and implementation, they all played slightly (or very) differently. The Tetris randomizer is a function that returns a randomly selected shape. Over the years, the rules for choosing shapes have evolved, influencing the gameplay and randomness itself. Some of these algorithms have been reverse engineered and documented. I have compiled a list of randomizers that I consider important, and I will show in the article how the internal structure of Tetris has changed over the years.

Tetris (c. 1985)

The first and original version of Tetris had a randomizer without bias. Nothing influenced the choice of the next figure, it was simply chosen and shown to the player.



When using a randomizer without displacement, situations arise in which the player receives a sequence of one figure (called a "flood", flood) or a sequence in which there is no certain figure (called a "drought", drought). We will see how designers of different versions of Tetris tried to slightly smooth out this problem.



Although a randomizer without bias creates the greatest puzzle complexity for players, it is unstable and can lead to an invincible sequence (PDF) . However, this does not happen in a real game, because computers do not have true random number generators. Pseudorandom number generators (PRNGs) try to simulate true randomness, but do not have properties that can generate in a row 70 thousand Z shapes.

True pseudo randomness

function* random() { const pieces = ['I', 'J', 'L', 'O', 'S', 'T', 'Z']; while (true) { yield pieces[Math.floor(Math.random() * pieces.length)]; } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Puzzle difficulty: 4/5



Flood Prevention: 0/5



Drought Prevention: 0/5

Tetris , Nintendo (1989)

Four years later, the unusually popular version of Tetris for NES was released .



To reduce the number of floods (repetitions) of figures, a history check was added to the randomizer. This simple check did the following:

1. choose a figure
2. checked if the figure matches the previous one,
3. if so, then the algorithm selected a new shape, but only once,
4. and whatever the result, the figure was given to the player.

Although the probability of getting one piece in a row was decreasing, nothing prevented the game from issuing two alternating pieces. In addition, in this version, drought over more than 30 figures was a frequent situation. Drought could occur for any type of tetramino, but figure I is important for scoring in this game, and its great drought could significantly affect the final score.

Memorizing a story 1 figure in depth and with 1 throw

 function* historyRandomizer() { const pieces = ['I', 'J', 'L', 'O', 'S', 'T', 'Z']; let history; while (true) { // First "roll" piece = pieces[Math.floor(Math.random() * pieces.length)]; // Roll is checked against the history if (piece === history) { piece = pieces[Math.floor(Math.random() * pieces.length)]; } history = piece; yield piece; } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Puzzle difficulty: 5/5



Flood Prevention: 2/5



Drought Prevention: 0/5

Tetris: The Grand Master (1998)

Although Tetris for NES improved the algorithm compared to randomization without bias, droughts in it were still frequent. Tetris: The Grand Master ( TGM ) essentially used the same system, but with a longer history and more throws.



Due to the increase in these values, not only the number of floods decreased, but the situation with droughts also improved. Four figures were preserved in history, and this meant that the probability of obtaining a figure that had not existed for a long time increased. Despite this, the game still lacked a strict rule to prevent droughts and they still occurred, albeit much less frequently than in Tetris for NES .

Memorizing a story with 4 pieces and 4 throws

 function* historyRandomizer() { const pieces = ['I', 'J', 'L', 'O', 'S', 'T', 'Z']; // First piece special conditions let piece = ['I', 'J', 'L', 'T'][Math.floor(Math.random() * 4)]; yield piece; let history = ['S', 'Z', 'S', piece]; while (true) { for (let roll = 0; roll < 4; ++roll) { piece = pieces[Math.floor(Math.random() * 7)]; if (history.includes(piece) === false) break; } history.shift(); history.push(piece); yield piece; } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Puzzle difficulty: 4/5



Flood Prevention: 4/5



Drought Prevention: 2/5

Tetris Worlds et on (2001)

Tetris Worlds introduced the masses to the random generator. He is now the official randomizer, in most official versions of the game after Tetris Worlds, and to this day he is used.



History-based randomizers helped get rid of the floods (or at least minimize them), but did not stop the drought. Under certain conditions, there was still the possibility of a deadly sequence of figures.



The random generator (Random Generator) solves these problems through the use of a new system of "bags" (bags). In this system, the list of figures is placed in a “bag”, after which the figures are randomly extracted from it one after another until the “bag” is empty. When it is empty, the pieces return to it and the process repeats. Random Generator has a “bag” of size 7 (7-bag), that is, a “bag” filled with each of 7 tetraminos. Other types of "bags" are possible, for example a 14-bag, in which two pieces of each type of tetramino are placed.



Due to the lack of history of the “bags”, floods of 2 figures and “snakes” of 4 figures may occur at their junctions ( , etc.). That is, in a sense, this is a step backward compared to traditional Tetris for NES .



The pieces drop out of the 7-bag stably, which makes it more predictable. It is easy to understand what part of the “bag” you are in, and when the figure you need can come. Due to the predictability of this randomness generator, the game can actually be played endlessly . In general, this is a very stupid system, and it is unclear how it generally became an official randomizer.

7-bag

 function* randomGenerator() { let bag = []; while (true) { if (bag.length === 0) { bag = ['I', 'J', 'L', 'O', 'S', 'T', 'Z']; bag = shuffle(bag); } yield bag.pop(); } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Puzzle difficulty: 3/5



Flood Prevention: 3/5



Drought Prevention: 4/5

Tetris: The Grand Master 3 - Terror-Instinct (2005)

TGM3 has greatly advanced the idea of ​​generating randomness. This is a unique system not found in any other version.



Instead of a bag or story, the TGM3 uses a pool of shapes. Initially, it has 5 figures of each type, that is, a total of 35 figures. When a figure is pulled, it is not removed from the pool, but is replaced by the figure with the largest drought (one that has not been removed for a long time). Gradually, the pool is more and more filled with this figure until it is finally pulled out. This solves the problems of “bag” systems, as well as systems with a history; she takes the best from both types of randomization.

Pool of 35 figures with 6 throws

 function* tgm3Randomizer() { let pieces = ['I', 'J', 'L', 'O', 'S', 'T', 'Z']; let order = []; // Create 35 pool. let pool = pieces.concat(pieces, pieces, pieces, pieces); // First piece special conditions const firstPiece = ['I', 'J', 'L', 'T'][Math.floor(Math.random() * 4)]; yield firstPiece; let history = ['S', 'Z', 'S', firstPiece]; while (true) { let roll; let i; let piece; // Roll For piece for (roll = 0; roll < 6; ++roll) { i = Math.floor(Math.random() * 35); piece = pool[i]; if (history.includes(piece) === false || roll === 5) { break; } if (order.length) pool[i] = order[0]; } // Update piece order if (order.includes(piece)) { order.splice(order.indexOf(piece), 1); } order.push(piece); pool[i] = order[0]; // Update history history.shift(); history[3] = piece; yield piece; } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Puzzle difficulty: 4/5



Flood Prevention: 4/5



Drought Prevention: 4/5

findings

It is difficult to draw any definite result. The TGM3 randomizer seems more predictable and less complex for the player. The clumsy 7-bag feels unnatural, but allows you to create many stably viable building strategies. An unfriendly randomizer, such as in Tetris for NES, can ruin your game, or, more likely, your mood to play.



Can we improve these systems by making them seem more random, and by placing severe restrictions on droughts and floods? Or are such severe restrictions just making the game more predictable?