Mastering Tetris: Create an AI using Genetic Algorithms

Table of Contents:

1. Introduction
2. The Game of Tetris
3. Strategies for Playing Tetris
4. Introducing Genetic Algorithms
5. Applying Genetic Algorithms to Tetris
6. Building the Genetic Agent
   1. Initializing the Weights
   2. Calculating Fitness Score
   3. Creating Offspring
7. Training and Running the Genetic Agent
8. Conclusion

🧩 Introduction

Welcome to the Second workshop on creating an AI that can play Tetris using heuristics and genetic algorithms. In this workshop, we will take a look at the final product and delve into the detailed agenda. This workshop is divided into three parts: understanding how humans play Tetris, introducing the basics of genetic algorithms, and writing the code for the genetic agent together.

🎮 The Game of Tetris

Before we begin building our AI, let's first understand how humans play Tetris. Tetris is a game where randomly generated quad tiles, known as tetraminos, fall from the sky. Our goal as players is to arrange these tiles in such a way that they don't reach the top of the screen, causing the game to end. We can move the tiles left and right, rotate them, and sometimes swap the current tile with the next one. However, knowing just the controls is not enough to excel at the game. There are certain strategies we tend to follow in order to play efficiently.

🔀 Strategies for Playing Tetris

In order to Translate the strategies humans use into heuristics for our AI, we need to understand the objectives of the game. The main objective is to prevent the blocks from reaching the top of the screen. Therefore, an agent that simply stacks all the blocks on top of each other is not going to perform well. Making holes in the structure is also counterproductive, as the tiles will keep stacking up and limit our options. To incentivize our AI, we can assign a score each time it clears a line. This score will motivate the agent to clear lines more efficiently.

One strategy that many Tetris players follow is to keep their board as smooth as possible. The smoother the board, the easier it is to arrange the tiles. For example, a bumpy board with gaps makes it difficult to fill in the spaces. Let's teach our AI to aim for a smooth board as well.

🧬 Introducing Genetic Algorithms

In this workshop, we will be using genetic algorithms to create our AI. Genetic algorithms are inspired by natural selection, where the fittest individuals have a higher chance of survival. In the context of Tetris, we can measure the strength of an agent using heuristics like fitness value, survival time, and scores. By applying these heuristics, we can filter out the top-performing agents and focus on their genes to breed the next generation.

⚙️ Applying Genetic Algorithms to Tetris

Once we have identified the top agents, the next step is to evolve them. We pair up the agents and randomly mix their genes to create a pool of offspring. The hope is that these offspring will perform better than their parents. To maintain biodiversity in the gene pool, we also introduce random mutations. This ensures that the future generations are not confined strictly to the genes of the parents.

🤖 Building the Genetic Agent

Now that we understand the concepts of genetic algorithms and the objective of Tetris, let's dive into the implementation. We will be coding the genetic agent step by step, making necessary adjustments along the way.

1. Initializing the Weights

The first step is to initialize the weights of the four heuristic values. These weights are crucial for evaluating the fitness of the agent. Note that the random weights are only used in the first generation. In subsequent generations, the weights will be inherited from the parents.

2. Calculating Fitness Score

The fitness score of an agent is determined by evaluating the four heuristics separately and applying the weights from the agent's genes. The final fitness score is the weighted sum of these heuristics. Various utility functions, such as calculating bumpiness and counting holes, are used to evaluate these heuristics. Check the "tetris_util.py" file for more information.

3. Creating Offspring

After evaluating and filtering out the top agents, we create new child agents by randomly assigning genes from the parents. Each gene is chosen based on a random boolean value, which determines whether the gene is inherited from the first or second parent. Once all four genes have been assigned, we introduce random mutations with a certain mutation chance. This adds diversity to the gene pool and allows for potential improvements in future generations.

📊 Training and Running the Genetic Agent

Before we begin training the genetic agent, let's review the Parallel training settings in the "tetris_parallel.py" file. These settings include the game count, which determines the number of agents running simultaneously, and the mutation rate, which affects the speed of changes in the gene pool.

During training, green boxes will indicate the current best agents, and red boxes will appear when hovering over a Tetris board to show the agent's weight. On the right side, statistics regarding the score, fitness, generation, and agent information will be displayed.

👋 Conclusion

Thank you for joining this workshop on creating an AI for playing Tetris using heuristics and genetic algorithms. We covered the basics of Tetris, the strategies humans employ to excel at the game, and how genetic algorithms can be applied to build an AI agent. By following the step-by-step process, we implemented the genetic agent, trained it, and observed its performance. I hope you found this workshop useful, and if you have any lingering questions or simply want to chat, feel free to message us on our Discord server.