14 Mar 2018

Heuristic Tetris Bot

A heuristic AI I wrote to beat my friends at tetris.

Motivation

I wrote this particular program back in sophomore year of high school. All my friends were playing Tetris Friends on facebook and bragging about how good they were. It was a pretty fun time, only I wasn’t very good. Given that I knew how to code quite well and that I had already worked on a number of botting projects before, the idea to make a tetris bot came pretty naturally.

What is a Heuristic AI?

A heurisitic AI is an artificial intelligence (AI) based on heuristics. Those heuristics are specifically coded concepts telling the AI what it should do in given situations. It seems the more I learn about AI, the less impressive my Tetris bot feels. We have companies like Deep Mind making algorithms that actually learn to do tasks instead of being programmed to do them. Sure, I had only the slightest awareness of neural networks when I coded this up, but ever since I finished this Tetris bot, I’ve wanted to rework it using machine learning.

In comparision, what my Tetris bot does isn’t “intelligent” at all. It simply compares scores for all possible placements of the currently available piece and picks the best one. The scoring is all hard-coded based on some rules (heuristics) I came up with while playing tetris myself. If you watch the video you can see the bot making the same sort of choices (and mistakes) that I would make. The difference, of course, is that the bot is way faster.


Video

Here is a video of my bot (on the right) playing againt me (on the left).


Tetris Friends

The video above shows the bot running in my Tetris environment. I ended up writing my own Tetris implementation and a sort of Tetris API so that the AI could move as fast as my CPU would allow.

However, the original goal was to get this bot to beat people on Tetris Friends. The bot did, in fact, play on Tetris Friends for me and it did pretty well (a lot better than anyone I knew). Still, other humans (bots?) at the very highest ranks did win against it. My bot had some problems with scanning the screen and identifying the board state. Its input system expected certain colors of pixels in a certain layout on screen. Unfortunately, Tetris Friends had all sorts of animations and visual effects that interfered with those assumptions. For example, when the opponent cleared rows and sent them over to the bot’s board, the sudden change in board state would delay the bot’s next actions. Making that delay worse, my bot also had to wait after each key it pressed to see if/when the key actually registered. This slow response checking loop combined with the interference from visual effects limited my bots ability to play quite a bit and allowed other players to beat it.


Code

All of the source code is available on my GitHub tetris-ai repository (link). I offer a pretty simple explanation of how it works in the repository’s readme, which I will reproduce here:

Algorithm

The algorithm is very simple, it uses a score-based approach with a small number of parameters. I designed it to play the way I do, which is apparently alright. The scoring code is in TetrisBot.calculateBoardScore(). In order to decide on the next move, the AI scores all valid placements of the current piece or the piece that can be swapped from the hold position.

Scoring is based on the following ideas:

  • Clearing lines is good
  • Clearing tetrises is even better (4 lines at once)
  • It is possible to eliminate the entire piece being placed by clearing lines, and that is a wonderful move if available
  • Pieces should be placed so that they share as many edges as possible with the current stack.
  • Placing pieces near walls is a good thing too
  • Piece placement should prefer lower positions on the stack
  • It is very bad to place a piece so that it creates a “shadow”
  • Likewise, it is bad to cover up bubbles in the stack below the newly placed piece. (Doing so makes it harder to access and break the lines containing these bubbles)
  • Leaving “cliffs” of greater than 1 tile next to the newly placed piece is bad, as it creates a need for an L, J, or I piece.

All of the above heuristics came from my own observations as I played. The numerical weights to each of these heuristics came from experimentation. The heuristics also adjust automatically between a few presets subject to a the following conditions.

Additional Conditions

  • If the stack is relatively short, the bot avoids placing pieces in the left-most column, this helps to build up possible tetrises.
  • If there are a large number of bubbles in the stack, shadows become even more penalized and row clears gain a great significance. This change allows the AI to try to clear some of the excessive number of bubbles.
  • If the stack height is too large and a tetris score is not coming soon (I piece in the next 5 pieces), then the AI stops prioritizing tetris scores and works to clear as many lines as possible.

Menu