Finding the optimal solution for solving the classic game of Snake with pathfinding and heuristics

An exploration into finding the most optimal programmatic solution for completing the classic game of snake.

13 Apr 2020

The classic game of Snake is a simple concept but it has some interesting problems when it comes to creating a programmatic solution. When I came across the notorious gif of 'the perfect game', it made me curious how a programmatic solution would work.

Pathfinding

The concept of Snake is to guide the snake across the map to the point, avoiding collisions with itself or the walls. This general problem of finding a path from a starting point to an endpoint can be applied to lots of other applications like satellite navigation, routing packets across the internet, game AIs, OS file system search, distribution/utility networks and many more.
The domain of all of these problems, including the game of snake, can be solved with graph theory. Each of the places that can be visited and their connections to other places can be represented as nodes and edges/links on a mathematical structure called a graph, similar to that shown in Fig 1.
Fig 1. A graph representation, nodes visualised as circles and links as lines between them.
Graph search algorithms are used to determine the path from node to node, usually looking for a single specific node as the end goal. We'll be looking at two algorithms for the Snake solution, 'Breadth-First Search' and 'Best-First Search'.
Breadth-First Search
Fig 2. Breadth-First Search frontier ring.
The Breadth-First Search algorithm uses a queueing system for exploring all of the nodes depth by depth (the queued cells are sometimes referred to as the frontier ring). It takes the node at the front of the queue and then pushes all of the connecting nodes onto the end of the queue. This ensures that the nodes with the closest links to the starting node are explored first and makes it ideal for finding an endpoint where the direction is unknown or if there are a lot of obstacles.
Best-First Search
The Best-First Search algorithm explores a single path by prioritising the next node using a heuristic evaluation. This heuristic usually guides the path towards a known endpoint, though this will depend on what the heuristic function is.
We'll be using a Best-First search as the main searching algorithm and the solutions below will be focused around writing a heuristic function to help decide on the path for the snake.

Analysing optimality

To determine the optimality of the solution we need a way to analyse them, and for that we can track a couple of metrics and create a scoring system, for example:
  • Points: The number of points that the snake collects is an indication to how successful the solution is. The more points, the longer the snake lasted, and so the better the solution is at avoiding crashes while also collecting points.
  • Cumulative moving average: Tracking the number of moves from point to point helps to see the efficiency of the solution throughout the game. As the snake gets longer from collecting points, there are less available spaces on the grid for the next point to generate, so the efficiency of the solution is less important towards the end then it is at the beginning. We can use a cumulative moving average here to smooth out the variability that comes from the randomness of the point positioning.
The scoring system will be a cumulative score of the current point weighted by the moving average, the current path length and progress into completing the game. The weight of the progress is less impactful towards the end.

Solutions

The solutions below are all heuristic functions that will be run for each cell on the map. Whichever node around the head of the snake has the lowest value, will be the node the snake will move to next. This will continue to happen until either the snake has crashed or the game is complete.
A live runner with each solution can be used to play out the game of snake with that solution, and is taken from my interactive developer game of writing your own heuristic (in Javascript).
Manhattan Distance
The Manhattan Distance is a taxicab metric of Taxicab geometry. The name comes from the grid layout of streets on the island of Manhattan, and the function is the absolute distance between two points.
Fig 3. Snake runner: Manhattan Distance.
The Manhattan Distance is a direct solution but it's completely unaware of the environment so this leads to a low average numbers of moves but also a low number of points collected, as it crashes into itself quite early into the game.
Euclidean Distance
The Euclidean Distance is the straight-line distance between two points in Euclidean space and is given by the Pythagorean formula (a² + b² = c², or in Javascript we can use Math.hypot).
Fig 4. Snake runner: Euclidean Distance.
This ultimately leads to just an alternative path of the Manhattan Distance, but a more diagonal route. The analysis is almost identical to the solution shown in Fig 3, because likewise it does nothing to handle the environment, and simply just knows about moving towards the point.
Hamiltonian Cycle
A Hamiltonian Path is a path that visits each node of a graph exactly once, and a Hamiltonian Cycle is where the final node visited connects back to the first node and allows the exact same path to be repeated continuously.
Fig 5. Snake runner: Hamiltonian Cycle.
This is a methodical solution but has very poor efficiency towards the start of the game due to the unnecessary number of moves that are not weighted to moving towards the direction of the point.
On an even sided grid this has the consistent behaviour of getting 100% completion, however on an odd sided grid it is almost impossible due to the cycle needing to alternate it's direction (see Fig 5) and ultimately crashing into itself.
Note: This is not a true Hamiltonian Path or Cycle because of the need to alternate the path and visiting some nodes for a second time before getting back to the start.
Tail Escape
Some observations we can make from the previous solutions is that the ideal solution needs to have some awareness of the current environment to prevent crashes, like the cells occupied by the snake and the bounds of the map. It also needs to be weighted to move in the direction of the point to keep the number of moves down to a minimum.
This solution focuses on the idea that as long as the head of the snake has a path back to the tail (similar to the Hamiltonian Cycle), then it can avoid crashing into itself by following the tail.
Fig 6. Snake runner: Tail Escape.
The randomly positioned points and the positioning of the snake means there will not always be a direct path to the point, so this solution has a few conditions.
  1. If there is a direct path to the point check that the hypothetical position of the snake once collecting the point has a path back to the end of the tail, then it's a favourable option.
  2. If there isn't a path to the point but has a path to the tail, then it's still an option, but just less favourable.
  3. If in both situations there are no paths back to the tail, then the cell is not an option.
A Breadth First Search is ideal for searching for the point and tail because of the snake's body providing an obstacle and thus the path to the point will likely not be a direct one.
However, there are still times where this solution does not complete the game 100%. Towards the end of the game, it is likely that single empty cells are available but cannot be manoeuvered into and when a point gets generated into that available cell the snake gets stuck in an endless loop.

Summary

The four heuristic solutions above all range in complexity and approach. The Manhattan and Euclidean distance use a simple distance evaluation to determine which next cell is the closest, while the Hamiltonian Cycle is methodical and aims to get a greater level of completion over efficiency. The Tail Escape is the most complicated and tactful, and also most resembles 'the perfect game' gif.
When plotting the solutions moving averages and scores for better comparison against one another, some observations can be made. The Hamiltonian Cycle, as expected, does initially have a lot of variability in the high average number of moves because the number of moves rests entirely on the random position of the point. But overtime, the average does decrease due to the reducing number of cells that the point can generate in.
The Tail Escape solution starts to follow a similar line to the Manhattan and Euclidean distance solutions, which are as direct as possible. This is a good indication that despite not actually using a distance evaluation, the Tail Escape still moves as direct as possible using a breadth first search.
As pointed out above, the Tail Escape solution is still not consistently perfect, and I suspect there is an optimisation to be made that ensures no unmaneuverable cells are left.