A while ago I made a clone of the game Tetris, and then followed it up with an AI that can play the game.
I’ve always thought this was pretty damn cool, so I want to go into how it actually works. To make a long story short, you don’t need to make an AI that’s good at Tetris – you need to make an AI that can learn to become good at it.
What we want to do is break the problem down into smaller, more easily approachable problems. When you think of the game Tetris, you’re really just solving one problem over and over again – Where should I place the current piece? The way I tackled this is to analyze every possible location where a given piece can be placed and assign that location a score.
Which leads us into another problem, which is – How do we assign these locations a score? The answer to that is that we look at several different attributes about a location, and assign each of those attributes a score. The final score for the location is the sum of all of its attribute scores.
For example, one attribute that we could use in determining the score would be to look at height of each of the blocks in the shape.
To get the score for this attribute, we can add up the height of every block.
Now the AI knows that, in terms of height, the shape on the right is better than the shape on the left.
We could go through similar processes for other aspects of that position in order to get the full score for a given position. For example, clearing a row is an essential aspect of the game, so we could add up how many lines we’ll clear when placed in a given position.
This is all well and good, but ideally we want to be able to specify whether one attribute should hold more importance than another attribute. What we actually end up doing is giving every attribute a value I’ll call a weight, and multiplying the result of that attribute by this weight value. In the height example above, if the weight for the height is -10, then the result for the left would be -30, and the shape on the right - 10.
I used 6 different attributes for determining a score. It doesn’t really matter what the attributes are, they can really be anything you think might play a role in determining whether or not something is a good position. For reference, though, I’m using
To get the final score, we add add every aspect up. The location with the highest score will be the location that we choose.
The only other question left to answer at this point is how to determine the weight values for each aspect. Should the height aspect be considered more important than whether or not we cover up a hole? Should touching the wall be considered positive or negative? I sure as hell don’t know. This is where the AI learning comes in.
It’s a process similar to natural selection. To start off we can randomly assign weights for the AI. We then run the game with these values and record the results of several games until we’re confident that we have the average final score it’s going to attain with these values. We then randomly modify a weight value (and occasionally randomly modify multiple weights at once) and repeat the process. If we see an improvement we can keep the changes, and if not, we revert to the better performing values and try another random mutation.
Now all you have to do is wait, and you’ll get an AI that improves before your eyes. I think the highest I’ve seen mine get is around 8,000 lines cleared, but that’s a rare occasion. It can usually do around 4,000 before dying off.
To end this off, I’ll show a screenshot of one of the first iterations of the AI.
Its pretty cool to see how far it’s come since then.
Copyright © - Daniel J. Petersen