Winner of Battlesnake 2018 Advanced Division. This is a complete rewrite based on things learned from a first attempt of writing a C++ snake for Battlesnake 2017. This time the focus was on building a good base of data structures to keep the state of the game. In addition we wanted to be able to simulate games locally for testing and training. Finally, by providing a good base of data structures with well defined interfaces writing various algorithms becomes a much easier process, something that was much harder in the first version.
The snake uses the minimax with alpha-beta pruning to make all of its decisions. A heuristic function is used to evaluate every game state. The heuristic function takes multiple weights to balance the terms of the heuristic function which are tuned by a genetic algorithm and then were hand tuned based on perceived flaws.
The heuristic function is a points system used to score the current state of the board for a snake. Its range is the the maximum and minimum of the double type in C++. Right away we can return the minimum if we are dead in this state and the maximum if we are a winner. Otherwise, we used two main heuristics to evaluate a game state: how close we are to food in relation with our health and the number of squares we own.
Food is found by using Breadth first search. From there we can use the size of the path to get distance to this food. It is obvious that food and health is related. In principle we probably do not want to eat food when we have high health and do want to eat food when we are low health. We decided to simply minus the length to the closest food from our health and then use a arctan function with two weights to get a score. The final equation was score = a * arctan((h - l) / b) where h is the current health, l is the path to nearest food and a and b are constants chosen by the genetic algorithm. The final weights for the constants was a = 68.60914 and b=8.51774.
Voronoi is a concept that we read in a1k0n's post mortem for the Google AI lightbike challenge. Voronoi allows us to introduce a heuristic for maximizing the amount of points we can reach before anyone. It follows that we also minimize our opponents space which is extremely useful in lategame one on one, as well as surviving in multiopponent situations. A visualization from aik0n's blog post shows how it works.
Voronoi can easily implemented by doing BFS from the head of every snake one depth at a time. We score this heuristic by giving a point for every owned space and then multiplying by a constant as found by the genetic algorithm. In our case this constant was 7.60983.
By building a test arena in C++ we were able to test different heuristics for our snake. We had four hyper parameters in our heuristic, and to converge to a solution faster we chose a genetic algorithm approach. We found a promising library in the form of GALGO. Unfortunately, GALGO performed a fitness function on each candidate independently. We had to modify the library to perform perform the fitness function evaluation on the population as a whole. Each candidate solution in the population was initialized into a snake game of other candidates as well as some basic snakes. These basic snakes were snakes that moved randomly and snakes that always ate the nearest food. The candidates where initialized as snakes without alpha-beta look ahead, moving only based on their heuristic. Each population ran the game 10 times.
The fitness function was the average lifespan of each snake during the 10 games. There were many problems with this fitness. When running training the solution did not converge towards a single optimum. It would often regress in to a worse score over time. However, this is a flaw in the fitness function as time alive does not necessarily indicate the skill of a snake. For example, a snake that wins against its opponents extremely quickly would also have a low time alive in relation to other populations. A second approach based on rank was also tried. However, the problem with this approach is that it is very hard to understand if the genetic algorithm is converging to a global maximum. For example, a mid skill snake might dominate some low skill snakes a gain a high rank in its population, while a group high skill snake may have an average middle rank in a population of other high skill snakes. Even though our fitness function was flawed it still reduced the search space dramatically. We hand selected snakes that had high scores, observed their behaviour and analyzed their heuristic values before selecting the one used during the competition.
After pulling the repository the submodules need to be pulled. This includes the Crow C++ Micro webserver, JSON for Modern C++, and GALGO genetic algorithm library.
git submodule init
git submodule update
Next Crow header file needs to be created.
cd crow/amalgamate
python merge_all.py
This project uses the C++ Boost libraries and SDL2 for GUI.
sudo apt-get install libsdl2-dev
sudo apt-get install libsdl2-ttf-dev
sudo apt-get install libboost-all-dev
If you wish to be able to run the tests you will need googletest.
sudo apt-get install libgtest-dev
cd /usr/src/gtest
sudo cmake .
sudo make
sudo mv libg* /usr/lib/
There are three main ways to run the project.
Run a game with multiple snakes as defined in src/gui_main.cpp.
make gui
Run the genetic algorithm training as defined in src/training.cpp
make train
Finally run the server as defined in in src/server.cpp
make server