This page describes a TETRIS Artificial Intelligence based on Google's Pagerank Algorithm.
As it turns out, “PageRank” is actually a fairly decent Tetris player.
The PageRank algorithm was originally designed to rank webpages on the Internet, and works by treating each backlink to a webpage as if it were a vote of support for that page, and by giving extra weight to a vote if it comes from a webpage that itself has a high rank. In order to know the rank of the voting page to begin with, the PageRank algorithm must be run iteratively until votes in all directions have had a chance to propagate.
This same basic algorithm can also be applied to the game of TETRIS. Instead of ranking webpages, our objective now is to rank each possible stack surface on a scale from least accomodating to most accomodating. We consider surface "B" to be a vote of support for surface "A" if "B" can be formed from "A" via the placement of an additional piece. The vote for "A" is given extra weight if "B" itself has a high rank. In order to know the rank of "B" to begin with, the algorithm must be run iteratively until votes in all directions have had a chance to progagate.
Once the rank of each stack surface has been computed, a game is played by taking each new random piece and placing it in whatever position gives the highest rank for the new surface that is produced.
In this AI, we are interested in TETRIS Stacking where pieces are stacked in the left 9 columns and cleared via the 10th column. The goal is to maintain a "perfect" Tetris stack (i.e. no holes) for as many consecutive pieces as possible.
To do any sort of large-scale computation for this problem, we must begin with an efficient data representation. First of all, we are interested only in the contour of the surface along the top of the stack, not in anything that is below the surface. For example, we put both of the following stacks into the same equivalence class:
| is equivalent to |
Each stack surface is represented by 8 numbers between -4 and 4, specifying the relative difference in height between one column and the next. The example stack above is represented by the list 0,1,-2,0,0,-1,0,1.
With this representation, the entire stack space is made up of 98 = 43046721 different stack surfaces.
We will also need to a way to efficiently store and index ranks for the 43046721 different stack surfaces. For this purpose, we will use a more efficient representation of a stack surface that is a base 9 number with each digit corresponding to an element from the list plus 4. Using the above example again, its base 9 stack number is 45244345.
Rank is computed iteratively by the following functions:
| rank(iteration, stack) | Returns the average rankPiece(iteration, stack, piece) of all 7 pieces. |
| rankPiece(iteration, stack, piece) | Returns the best rankOrientation(iteration, stack, piece, orientation) of all 4 orientations of a piece. |
|
rankOrientation(iteration, stack, piece, orientation)
|
Attempts to place the given piece in the given orientation on the given stack, in all possible locations on the stack where it can fit without creating holes beneath the stack's surface. A set of new stack surfaces is generated from these placements. This function returns the highest previously computed rank(iteration-1, new_stack_surface) of all of the new stack surfaces. |
In a naive implementation, we might compute and store the ranks for all of the individual iterations into separate arrays. In practice, however, one iteration will depend only on the results of the previous iteration, and so it suffices to allocate just enough memory to hold two iterations. The following Java code illustrates the process:
int[][] ranks = new int[2][num_of_stacks];
for (int iteration = 0; iteration < num_of_iterations; iteration++)
{
for (int stack = 0; stack < num_of_stacks; stack++)
{
ranks[iteration%2][stack] = rank(iteration, stack)
}
}
You may notice this is a bit simpler than the original PageRank algorithm in that we do not make any use of a "damping factor", and we do not factor in the number of links that a page has.
Once all surfaces have been ranked, a game can be simulated by taking each new random piece and placing it in whatever position forms a surface with the highest rank. Occasionally, of course, we must clear lines via a "Tetris" or else the stack will only get higher and higher. We use a threshold to decide how high the stack is allowed to get before a Tetris is forced. The sequence of random pieces that is given to the player is determined by a randomiser. In our simulation we used the TGM randomiser which keeps a history of the 4 most recently generated pieces and tries not to generate one of those as the next piece. This randomiser is a little more reasonable than a memoryless randomiser which can often deal the same piece several times in a row.
There are two improvements that we can make at the simulation level without making any change to the generated ranking table. First of all, it can happen that a game plays itself into stack surfaces with steps steeper than 4 rows. Normally, such stacks cannot be ranked. However, it is possible to rank these stacks by automatically truncating steep steps to be within the range of -4 to 4. For example, if the stack on the left is encountered during the game, we can effectively consider its rank to be the same as that of the stack on the right:
| has the same rank as |
A second improvement can be made by implementing "lookahead", whereby the simulator will look at the next "N" random pieces in the queue, will test all possible arrangements of them, and will then choose whichever placement leads to the best-ranked stack surface after N placements. Lookahead can be implemented rather efficiently since the each rank can be obtained by a fast table lookup.
Under the TGM Randomiser, and using a ranking table produced from 15 iterations, this AI will maintain a perfect Tetris stack for the following number of consecutive pieces on average:
| lookahead | # of consecutive pieces | |
| 0 | 153 | |
| 1 | 823 | |
| 2 | 9,458 | |
| 3 | 154,645 | |
| 4 | 1,783,670 |
My motivation was to develop an Artifical Intelligence that could give insights to Human players about optimal stacking strategies. You can read about the strategies I reverse-engineered from this program on this page.
I have plans to do the following: