illayyy / snake_ai

Snake AI which utilizes Prim's Minimum Spanning Tree algorithm and Hamiltonian Cycles in order to find an optimal path around the game grid.

Snake AI

An algorithm for the game of snake which utilizes Prim's Minimum Spanning Tree algorithm and Hamiltonian Cycles in order to find an optimal path around the game grid, while avoiding crashing into itself.

Prim's Algorithm

Prim's algorithm is a greedy algorithm that finds a Minimum Spanning Tree (MST) in a weighted undirected graph. However in this instance, we use randomized weights in order to generate an MST that is half the dimensions of our desired game grid, using the tiles of the grid as nodes in the tree.
It should be noted that due to the fact that the MST needs to be half the dimensions of the game grid, the dimensions of the game grid cannot be odd.

The process of generating the tree is as follows:

1. Choose a random vertex on the graph to be the origin of the tree.
2. Find all vertices that currently border the tree. We will refer to these nodes as the "frontier".
3. Randomly choose a vertex from within the frontier to connect to a vertex on the tree. If there are multiple tree vertices that border the frontier vertex, randomly pick one of the tree vertices to connect to the frontier vertex.
   (This step simulates the randomized edge weights of the tree)
4. Repeat steps 2 and 3 until tree includes all vertices on the graph.

Finally, we should be left with something that looks a little bit like this:

Hamiltonian Cycle

A Hamiltonian Cycle is a path in a graph that visits each vertex exactly once, and ends at the same vertex that it begins at.

It's quite simple to visualize how, using Hamiltonian Cycles, we are essentially guaranteed to beat game of snake, every time.
We simply need to generate a Hamiltonian Cycle for the given game grid, and follow it for the entirety of the game. This way the snake visits each tile exactly once in each "cycle" until it has grown to the size of the entire game grid, and has hit its' own tail.

However, generating a Hamiltonian Cycle for a given graph has a staggering time complexity of O((2^n)*(n^2)).
For this reason, we have opted to use a shortcut which takes advantage of our previously generated Minimum Spanning Tree.

All we need in order to transform our MST into a Hamiltonian Cycle with double the dimensions, is to follow the tree's path like the walls of a maze, making sure to stick to the same wall for the entire process. This process can be visualized like this:

Shortcuts

At this point we should already be set to finish the game of snake.
However, the approach of following the Hamiltonian Cycle throughout, is extremely boring and makes completing the game take ages, due to the fact that on average, it would take the snake half a cycle to eat a single piece of food.

The solution to this problem is to take shortcuts that bring us closer to the food, without ruining the safety net that is the Hamiltonian Cycle.

To achieve this, we first have to make one key realization:
By playing the game using the Hamiltonian Cycle, we have essentially reduced the game of Snake from a 2D game, to a 1D game. Where the one dimension is the one dimensional array of coordinates on the game grid, ordered using our Hamiltonian Cycle.

Using this realization we can also infer that as long as our snake's body remains "ordered" (tail>body>head), within the 1D array of coordinates, it would never crash into itself.
This allows us to begin skipping parts of the cycle which do not contribute to us getting closer to the food.

At long last, we can start taking shortcuts around the game grid, seeing as our only restriction now is for our snake to remain ordered.

To find the optimal shortcut we will first look at all adjacent tiles to the tile that contains the snake's head.

We will then check which of these adjacent tiles will allow or snake to remain ordered, if we were to move into them. We will refer to these tiles as "legal".

Finally, for each of these "legal" tiles we will calculate their distance to the food in the Hamiltonian Cycle's 1D array. In other words, how many steps it would take us if we were to follow the Hamiltonian Cycle from that tile until we arrive at the food.

And at last, we can pick the "legal" tile that is closest in the cycle to the food, and use it as a shortcut.

In the example above, our next tile in the Hamiltonian Cycle is tile #5, which will result in us arriving at the food in 5 additional moves.
However, tile #9 is also a "legal" tile, since it allows our snake to remain ordered. Furthermore, moving to tile #9 will result in us arriving at the food in 1 additional move.
Therefore, our algorithm will pick tile #9 as the next move.

It is important to note that this is a greedy search, as we are not checking every possible path to the food, but only the first available move towards it. Therefore the snake won't always take the most efficient path to the food.

Finally, the algorithm doesn't take into consideration the fact that eating food extends the snake's body, which can lead the snake to occasionally crash into itself in the later stages of the game.

Because of that, we would want the snake to stop taking shortcuts once it has achieved a certain length, which I have chosen to set at 85% of the game's grid size. Beyond this certain length, the snake will simply follow the Hamiltonian Cycle.
Keep in mind that even with this bound the snake may on very rare occasions crash into itself, however these events are few and far in between, and occur even less frequently the larger the game grid is.

And at long last, we have our Snake AI:

SNAKE_COMP.mp4

References

https://github.com/CheranMahalingam/Snake_Hamiltonian_Cycle_Solver
https://johnflux.com/2015/05/02/nokia-6110-part-3-algorithms/
https://medium.com/@pascal.sommer.ch/generating-hamiltonian-cycles-in-rectangular-grid-graphs-316c94ecefe0
https://github.com/BrianHaidet/AlphaPhoenix/tree/master/Snake_AI_(2020a)_DHCR_with_strategy