The Perfect Game of Snake: Algorithms to Master the Classic

Few YouTubers explain algorithms and artificial intelligence as well as Code Bullet. Their videos have it all: successes, failures, insults, emotional breakdowns, and simple challenges that turn gigantic. Their most recent video is a continuation of a project published months ago, in which they struggled to get an AI to learn to play Snake via Q-learning. This time, they're back for revenge, and although "perfection" in Code Bullet videos should be taken with a grain of salt, the final result is far superior to the previous one.

AI and Games: A Growing Bond

This isn't the first time we talk about AIs trained to dominate games. Google's Deep-Q has been trained with Atari 2600 titles, and especially with nightmares like Montezuma's Revenge. Facebook already participated with its bots in StarCraft tournaments, and OpenAI scored high-profile victories in Dota 2.

The Challenge of Snake

The link between videogames and artificial intelligences will only grow stronger, but regardless of the quality of the matches, it's not a bad idea to learn a bit about what happens in the background. Let's take the case of Snake: a game that's more than simple if a human plays it, but what would an AI need to conquer it completely?

Code Bullet on YouTube decided to answer that question... and I think they're a bit regretful. After suffering with Q-learning in their first video in mid-July, they returned, throwing all previous work in the trash and starting from scratch. Snake has four basic commands: up, down, left, and right. There's a wall around the perimeter of the map, but the snake's own body acts as an internal wall, with the extra difficulty that it moves. When calculating the number of possible paths, the approximate number is 295 trillion possibilities... so it needs something different.

A* and Its Pitfalls

The first idea was to prioritize paths that let the snake get closer to the food instead of moving away, using the A* algorithm, one of the most popular in pathfinding... but it didn't work. When trapped, the snake simply stopped moving. The solution was to turn A* upside down: instead of looking for the shortest path, the snake takes the longest, which is in some way what all Snake players should do when the snake gets very long. To that, they added another condition: the snake must always be able to access 80% of the empty blocks...

The Hamiltonian Solution

... and they almost made it. Another restart, and then they arrived at the so-called "Hamiltonian Cycle", which interprets the Snake map as a circuit full of nodes that must be visited only once, returning to the beginning. All the new algorithm had to do was generate Hamiltonian cycles and follow each one to the letter... but that's boring for Code Bullet, so they made a small adjustment so the snake could take occasional shortcuts. Results? The first was a success, with a perfect game of Snake. The second ended in failure by just two blocks... although the map was enormous.