I recently discovered a super-cool online code-gaming platform and super talented coding community called Battlesnake. The architecture is particularly interesting: you can use any language to code up your snake’s brain. Then you host an HTTP endpoint that responds within a half-second with your move given the current state of the board.
It’s difficult. The space of possible moves is huge. No single strategy will be sufficient to win. Given the game has been around for a while, there are several established players. Some have even written very sophisticated research papers describing strategies.
Also, there’s no one standard library, there are lots of languages and strategies in use. Outside of the main resource page, the best way to learn what people are doing is the Discord channel. Finally, it’s difficult because luck is still involved in winning since food appears randomly on the board.
After around 50-60 hours of work, my nephew and I were able to get to 40th place in the recent summer tournament.
Coding up a snake brain required solving some well-trod (but still fun) computer science problems. A path-finding algorithm is necessary to compute the distance to food and competitors. A “fill” calculation is necessary to determine if the space you’re moving into is open or a dead end. Lastly, some form of “lookahead” (minmax or pruned tree search) will be necessary to choose the best move based on predicting what your competitor will do.
With my first tree search implementation, I found I could only look 3 moves deep (even when filtering to snakes within 3 moves away). To avoid the risk of a timeout, I abandoned this approach in favor of simple rules to avoid dying. I’m eager to retry this with a better pruning strategy (it sounds like some form of Monte Carlo random choice method would be just the ticket).
I also threw in a quick genetic algorithm to load up some coefficients, mutate them and then save them only if my snake won a match. It was useful in understanding which parts of my algorithm were important, but I haven’t rigorously evaluated if there were enough matches (generations of winning snakes) to matter.
My most successful strategy ended up being scoring each move based on a simple mathematical function for each consideration (eating, staying alive, etc). In other words, moving “left” is scored highly if I’m hungry and there’s food in that direction. On top of that, manual rules and strategies, like “be hungry for the first 50 moves” and “never move into a possible head position of a larger snake” were necessary to be competitive.
I’d love to read more about other players’ strategies using reinforcement learning (or other applications of machine learning). I’ve already started building a large set of test cases for future work.
Lastly, Replit is cool. I’ve used plenty of online code editors – but it was really useful to have a hosted server that restarted in real-time. What a time to be alive!
You can challenge one of my snakes via my Battlesnake profile.