Tetris Workshop

🎮 Every Programmer Should Write Tetris! 🚀

JavaScript, Beam Search and Python w/ AI

Alex Avdiushenko
May, 2025

Step 1: Look for some implementation of Tetris on the Inrenet

Source: Javascript Tetris, how it works

Features for Heuristic Agent

Now let's talk about creating an AI that can play Tetris. To build a heuristic agent, we need to define features that help evaluate how "good" a particular board state is. The image shows four critical features we'll use: aggregate height (the sum of the heights of each column), complete lines (how many rows are filled), holes (empty cells with filled cells above them), and bumpiness (the sum of differences between adjacent column heights). These features capture important aspects of a Tetris board state that influence gameplay decisions. A good Tetris AI needs to balance these factors—minimizing height, holes number, and bumpiness while maximizing completed lines.

Heuristic Agent

Combine features into a heuristic score:

(-0.51 * aggHeight + 0.76 * completeLines - 0.36 * holes - 0.18 * bumpiness) $\to\max$

Here's where we combine those features into a single heuristic score that our agent will try to maximize. The formula shown here has been derived through experimentation and optimization. Notice the coefficients: we heavily penalize aggregate height (-0.51) because tall stacks are dangerous. We give a large positive weight to complete lines (0.76) as that's the goal of the game. We also penalize holes (-0.36) quite heavily since they make it harder to clear lines. Finally, we give a smaller penalty to bumpiness (-0.18). This weighted combination guides our agent to make decisions that result in better game states. The agent will consider all possible moves and rotations, calculate this score for each resulting board state, and choose the action that maximizes it.

The first result

Fixed bug in Possible Moves

Fixed Height calculation, including null-bug

Heuristic Agent Results

(-0.51 * aggHeight + 0.76 * completeLines - 0.36 * holes - 0.18 * bumpiness) $\to\max$

Case	Rows	Score
Heuristic with bugs	0	222
Fixed Possible Moves	5	1 036
Fixed Heigh calculation	612	78 268

Ok, looks good, but what about Beam Search?

What is Beam Search?

An approximate search algorithm commonly used in natural language processing tasks like machine translation and speech recognition
It is a variation of greedy search that explores multiple paths simultaneously, keeping track of the $k$ most promising paths at each step
Beam search striking a compromise between the efficiency of greedy search and the optimality of exhaustive search

Full Search based on the next piece

Heuristic Agent Results

(-0.51 * aggHeight + 0.76 * completeLines - 0.36 * holes - 0.18 * bumpiness) $\to\max$

Case	Rows	Score
Heuristic with bugs	0	222
Fixed Possible Moves	5	1 036
Fixed Heigh calculation	612	78 268
Full Search w\ Next Piece	44 301	5 623 130

Time to rewrite it in Python!

Let's trust Junie to do the hard work:

Prompt 1: Look at the javascript tetris project and come up with the plan of rewriting it in Python. Write all the details in the `python-tetris/plan.md` file.

Prompt 2: Implement the tetris in Python according to the `python-tetris/plan.md`, but replace the texture.jpg background to the simple gray grid.

Prompt 3: The game in Python works, but there is no AI mode, only flag for it.

It took about 30 min to get

Possible Future Steps

Fix a Python implementation
Join our programs at NUP or CUB 😎
Rewrite Tetris in C++ or Kotlin
Implement true Beam Search or MCTS
Switch to other game 🙂

🎮 Every Programmer Should Write Tetris! 🚀

JavaScript, Beam Search and Python w/ AI

Step 1: Look for some implementation of Tetris on the Inrenet

Features for Heuristic Agent

Heuristic Agent

The first result

Fixed bug in Possible Moves

Fixed Height calculation, including null-bug

Heuristic Agent Results

What is Beam Search?

Full Search based on the next piece

Heuristic Agent Results

It took about 30 min to get

Possible Future Steps

Good luck and have fun!