GATetris

Elad Shahar and Ross West
December 10, 2010

Overview

The aim of this project is the application of genetic algorithms to the video game Tetris. In the game Tetris, pieces named tetrominoes (made up of four unit squares arranged into predetermined shapes) fall from the top of the screen until they collide with something (the bottom of the board or a tetromino already on the board). By filling in a full horizontal row, the row is cleared and the player is awarded with points. If the pieces reach the top of the screen, the game ends. Tetris is an interesting game to play with because it combines both luck and skill (obviously required because there is a professional gaming league for Tetris players). Additionally, Tetris has been a common topic in artificial intelligence, and has been solved using other AI techniques such as reinforcement learning and state space search. Tetris has also been used as a test-case for machine learning algorithms. Using genetic algorithms exploits the fact that we don’t need a Tetris grand master to train a tetris bot, and using an evolutionary technique allows "smart" solutions to develop naturally.

Screenshot

Concepts Demonstrated

Genetic Algorithms are used to evolve the features for a heuristic function for evaluating a given Tetris board state.
A State Space Search is used to find the optimal piece placement based on a heuristic function based on feature detectors for given features.

Innovation

While creating an AI that can only play Tetris results in a very specialized solution, the solution can be extended to solve other problems that may require genetic algorithms. Additionally, as stated above, Tetris has been used as a test-case for machine learning algorithms, which are then used in important real-world scenarios such as developing artificially intelligent robots, solving complex problems, and performing intelligent data mining.

Technology Used Block Diagram

Generated using Gliffy

Evaluation of Results

We chose to run three separate and distinct tests.

100 Line Limit (Force game end after 100 lines cleared) - This was used to ensure that games did not last too long and a lot of evolution could occur. We found that due to the line limit, the bot learned to get larger line clears and combos (2, 3, or 4 line clears at once, rather than single line clears) which reward more points. Within 100 evolutions, the bot was clearing about 75% of the lines with a Tetris (4 lines at once).
1000 Line Limit (Force game end after 1000 lines cleared) - Similar to the last one, the bot learned to get multiple line clears and combos.
Unlimited (No forced game end, other than hitting the top) - This one was arguably the most interesting. The bot tends to focus on keeping as much of the game area clean as it can, to minimize the chance of it losing the game. The problem with this is that the games started lasting an incredibly long time. While each move took at most 5ms, a single game would take as long as 3.5 hours on generation 2! Considering a population size of 50, this means an average population will take 175 hours to complete -- that's over a week's worth of time! While we would like to keep running it in unlimited and see how it does, doing so is outside the time scope of this project.

Additional Remarks

Genetic Algorithms simulate the process of natural evolution. In real life, we are all made up of chromosomes, each of which have many genes, each of which has an allele. Through fitness tests ("survival of the fitness"), a certain percentage of the population reproduces and moves their genes to the next generation. During'reproduction, crossover and duplication occur of genes. Additionally, genes can mutate randomly causing unexpected behavior. In this case, each "Tetris Player" bot is made up of one chromosome. The feature detectors are the genes of the chromosome, and the values (features) are the alleles. Three things happen during evolution:

Reproduction - The most successful chromosomes (best Tetris scores) are duplicated and passed on to the next generation.
Crossover - Alleles from two chromosomes are swapped from a certain point onwards, and both are passed on to the next generation.
Mutation - Alleles can randomly mutate to a random value