This essay is about a self-learning system I created for Blue Planet Software, owner of the Tetris brand. It assumes familiarity with the Tetris game, but extensive information about the game can be found on Wikipedia.
One day, Henk Rogers (CEO of Blue Planet Software) came to me with what sounded like a fairly simple request: to make it easier to play the Tetris game on smartphones. He suggested something to do with selecting a play with a single mouse-click, rather than directing the piece to its spot through shifting and rotating the piece.
Traditionally, Tetris was being played using a keyboard or a game-pad and it required both keyboard dexterity and quick strategic thinking where to put the ever-faster falling blocks. But smartphones with their touch-screens don’t have tactile keyboards and every solution they had come up with until then proved to be so cumbersome to play, that for the first time in its 25 year existence Tetris was waning in popularity.
The first thing I did was make a program to calculate all the possible places a Tetris piece could be placed in the playing field. And display them below the game so they could be picked using a single mouse-click. Not entirely trivial, but also not too hard to accomplish. This way I found out that generally there are between 9 and 33 possible places to place a Tetris piece, depending on its symmetry.
Giving a player the choice of 33 possibilities on a smartphone is obviously not practical. So this would need to be cut down to a much smaller number, say 3 or 4. But which 3? In order for the system to be accepted by Tetris die-hards, at the very least the best possible move would have to be part of the selection. How would the program know what would consist as ‘best’? At this point I could probably have dug in and created an Artificial Intelligence (AI) algorithm that used a combination of heuristics and combinatorial search to try to compute the best move. But there are many variations on the Tetris game, all with different scoring rules and slightly different game mechanics. So for each of these variations the AI would need to be tweaked to account for those differences.
Instead of making a custom AI for each variation I decided to do something completely different. I developed an AI that didn’t know any of the rules of the game. Instead it used a simple pattern matcher that looked for good and bad patterns. It would look at the play-field for all the occurrences of the patterns and add to the score for the good patterns and subtract from the score for the bad patterns. All the program would have at its disposal was one good pattern consisting of a single empty point. And one bad pattern consisting of a single occupied point. This referred to the notion that the general object of Tetris is to keep the play-field free from blocks as long as possible. Empty points are good, occupied points are bad. It’s obvious though that these two patterns are next to useless. When this algorithm was used to play the game, blocks would just be placed at random places and the game would be finished in seconds with no score. Sometimes some points would be scored by pure chance.
Now you’d probably wonder what good it did to make an AI like that. Well, the good thing about it is that it lends itself very well for genetic programming. What I did next was make 8 copies of this program and give each of them the two simple starting patterns. And then I would let each of them play a game of Tetris. The program with the lowest score would be deleted. The top two scoring programs would ‘breed’ and its offspring would replace the deleted one. Breeding consisted of taking half of the patterns of the one program and half of the other. And then apply some small random additions and mutations to the patterns. Letting them play, round after round, each time removing the poorest one and replace it with a combination of the best two.
At first, all you’d see was random games that would finish in a fraction of a second and a new round would start. After a few minutes however, you’d start to see some order appear in the game-play. After maybe 15-30 minutes, it would actually start to look like somebody playing Tetris. Let it run for a full day or more, and all 8 programs would play like a top-class Tetris player.
All this without implicitly programming a single game-rule into the AI. If a different set of rules needed to be used in the game, all that was needed was to start again with the two simple initial patterns and let the programs breed for a day or so to get an expert player.
Given this AI, it became relatively easy to use it to assist in playing Tetris. The game would show an outline of the top 3 non-overlapping plays and all the player needs to do is touch which one he/she wants to play. And if you touch a spot not outlined, the AI would pick the play that would best match where the user touched the play-field. Now an important question was: doesn’t this make the game too easy? That turned out to be not the case. Maybe surprisingly, extensive tests showed that the same player would score in the same range using this “AI-assisted input method” (patent pending) as when they used a keyboard to play the game. This proves that the game is actually much more about strategy than about dexterity.
Apart from accomplishing what it was originally set out to do, there turned out to be an added benefit to this genetic algorithm. Because it can breed top-level players regardless of the rules, it also turned out to be a great testing tool. Before, any proposed change to the scoring or the game-mechanics would risk the game to become unbalanced. There was always a risk that there turned out to be a very simple but unforeseen strategy that would always result in the maximum score. So with every proposed change, countless hours were required of QA staff playing the game to check for this possibility. Now this can be accomplished by simply letting this AI run for a day, unsupervised.
Electronic Arts, the largest Tetris licensee, adopted a slightly modified version of this method in their Tetris for iOS app and called it OneTouch mode. Generally, reception of the OneTouch mode has been extremely positive by customers and it allows owners of smartphones to enjoy playing one of the greatest video games of all time once again.