Snake, math and a Hamiltonian circuit

November 2020

How to create an algorithm that always plays snake to maximum length, yet does not look utterly boring? It's very easy to just have the snake zigzag from topleft to bottom right, loop back and start over. Both images are examples of a Hamiltonian circuit. A closed loop visiting each cell or node in the playing field once.

When the game resets, a random Hamiltonian circuit is generated so each game and each path the snake follows will be different. But of course, simply following this circuit right from the start is not very efficient. So let's add some shortcuts.

When we display the indices of all cells in the circuit, it is easy to see how we can take shortcuts. Our snake just follows the numbers along the circuit. So on each move, it can look to the neighbouring squares and if the index of that square is less than the index of the food and less than the index of our last tail block, then it is safe to take a shortcut to that square.

In the above image, the snake is currently at 58. Normally it would move to 59 but cell 65 is better as it is closer along the circuit to the food on 41 and it would not overtake the food or tail. Next steps would be 66 67 90 91 94 95 96 97 6 ... If multiple directions give a valid shortcut, it will take the one with the index closest to the food along the path.

Note that this is not optimal yet. At 91 the move 94 is the closest to the food along the circuit but of course, going to 92 allows for a much better shortcut one step further by going to 7. So rather than just looking a single move ahead, one could look multiple moves ahead and take the best path where none of the intermediate cells overtake the tail or food.

At first, a lot of moves lead to a shortcut. The longer the snake becomes though, the more it follows the Hamiltonian circuit. And of course by doing so, it will never collide with itself.