A Google software engineer named Tom Murphy recently created a program that learns how to beat various classic video games like Super Mario Bros. and Tetris. He explains his work, which he submitted as a paper entitled “The First Level of Super Mario Bros. Is Easy With Lexicographic Orderings and Ti’me Travel … After That It Gets a Little Tricky”, in this video, His work is a great example of using artificial intelligence techniques to enable a computer to adapt to changing situations in pursuit of a goal.
Murphy’s program consists of two phases, Learnfun and Playfun. In the Learnfun stage, the program tries to learn what it means to win a game. This phase takes a recording of a human playing the game for a minute or two and then analyzes it to identify moves that advance the player closer to the goal. It makes these observations at a very detailed level, looking not just at the score or the player’s position, but at a lot of less obvious cues, such as distances from enemies or proximity to powerups. It even identifies movements that lead the protagonist to a place where it can make the best progress in a future frame of animation. These aren’t predictions or guesses at this stage. Instead, the software considers hundreds or even thousands of scenarios on how the next few frames of animation will play out, and it chooses the courses of action that lead to the best outcomes. Based on these choices, Learnfun draws conclusions that are the rules by which it will play the game so that it has the best shot at winning.
That’s where the second phase, Playfun, comes in. Once it has made its observations and drawn conclusions about the best way to play the game, it then goes to work controlling the protagonist as it attempts to win the game. For example, it might move Mario left to right from screen to screen, or it might try to navigate Tetris pieces into place. It will do whatever its rules tell it to do to avoid losing and, preferably, to win. Sometimes the moves it makes are strange and take advantage of bugs in the game code. For example, in Super Mario Bros, it discovered in Learnfun that it is possible to kill Goomba’s from below, and so it employs this trick whenever it needs to. In Tetris, it quickly builds a tower from the bottom of the screen to the top, because that racks up points faster than any other strategy. It then it quickly triggers the pause button to avoid losing. That’s not exactly winning, of course, but at least it didn’t lose. For the machine, that’s good enough.
Murphy’s work provides a fun and interesting example of the power of artificial intelligence. Artificial intelligence is all about data collection, pattern recognition, and inference generation. Apparently, so is gaming.