I created and developed an algorithm that masters the game of snake.
SnakeSoul always achieves the maximum length of the snake and performs up to 96% faster than other algorithms.
- Pygame
This library can be installed on Windows, Ubuntu and macOS via pip:
pip install pygame
You can test that you have correctly installed the app by running the following command:
python snake_ai.py
SnakeSoul provides a starting menu that enables the user to choose the way he wants to play the game of snake.
The next menu enables the player to choose the difficulty. A harder difficulty means that the size of each cell of the snake is smaller.
Before the game starts, another menu makes sure that the player knows the instructions he can use.
A delightful design of the game of snake.
Based on the game mode and on the outcome of the game, SnakeSoul will provide a customized final menu.
In order to always achieve the maximum length and win, I calculate a hamiltonian cycle of the grid that the snake will follow. I do this fast: O(nr) for generating a certain hamiltonian cycle and O(nr * log(nr)) for generating a random hamiltonian cycle, where nr is the number of cells in the grid.
To be more interesting, I generate a random hamiltonian cycle whenever it is possible. To generate a random hamiltonian cycle I use Prim's algorithm for finding the Minimum Spanning Tree of a random-weighted grid and then I use a cool trick to create the hamiltonian cycle based on the outline of the maze determined by the MST.
In order to lower drastically the overall time complexity of every step, I store the snake in a deque(because only the head or the tail can be added or removed) and I always update only the pixels that changed instead of the whole screen.
But the algorithm could be still improved, because just following the hamiltonian cycle isn't the fastest strategy to win.
So I programmed the snake to take shortcuts. The only shortcuts that guarantee that the snake won't die are the ones that are going to positions that aren't between the head and the tail in the hamiltonian cycle in its traversal direction, because otherwise there exists a tiny chance that the snake will hit its own body.
Another observation I made that speeds up the performance of the AI is that from a certain moment in the game the shortcut-making strategy isn't the best anymore and another strategy that moves the snake in a more compact manner would be better. So after a certain moment in the game I switch from the shortcut-making strategy to the strategy that followed blindly the hamiltonian cycle.
I made some statistics and measurements regarding the improvement of AI, and all the results that I got resembled this one:
I determined the time it took 2 different algorithm's to win the game on maximum speed and same difficulty:
My final version of the AI -> 7 seconds
Average versions of my AI -> 225 seconds
This demonstrates that SnakeSoul's final version of the AI performs 96.88% faster than other algorithms.