../battlesnake

The World's best Snake AI

Battlesnake is a competitive AI programming platform for a multiplayer variant of the classic game snake. It looks like this.

A random game of Battlesnake

What you see are 4 players playing a game of snake. The only difference here is that each snake is controlled by a different AI, each likely developed by a different developer. Mine is the controlling the red snake, it's called Shapeshifter. In 2022, Shapeshifter was arguably the strongest snake AI in the world, winning more than 50% of all official competitions that year. This article will be a small postmortem on how Shapeshifter was built, focusing mostly on a few key innovations.

The Basics

Shapeshifter is similar in concept to many modern chess engines like Stockfish, in that it performs minimax treesearch to find the best move. I will not re-iterate that algorithm and most of the many optimizations I implemented here, but for anyone wanting to read up on them, here is a list of my favourite resources on the topic:

Search Frameworks

One thing I would like to shed some light on here, even though it is nothing new, are minimax search frameworks. Conceptually, we can call our alpha beta pruning minimax function directly and it will find the best move at the target depth. But we can go a lot faster, by utilising this function more cleverly, in a search framework that makes multiple smaller calls to it. What do I mean by "smaller calls"? - Good question! The key idea here is that we don't need to call the function with the maximum search window for our parameters alpha and beta. Instead we can call it with a smaller window, even a minimal one, where alpha and beta are right next to each other. This is called a null window search [3] . A null window search is essentially the same as asking "Is the true minimax value for this move at least this high?". The cool thing about this is that a null window search is extremely fast, because almost every branch in the tree gets pruned by the alpha beta algorithm.

Now, a search framework can make repeated null window searches to find the actual minimax value, or the best move. The most popular one of these is MTD(f) [2] . It is the fastest algorithm (afaik) for finding the true minimax value of any move. But we can in fact do better. If we are willing to sacrifice knowing the exact evaluation score of our best move, we can use Best Node Search (a.k.a Fuzzied Game Tree Search [1] ). This essentially performs a binary search over our evaluation score range, to find a cut-off point at which only one move is better than the probed score. Intuitively, this can be faster than MTD(f) (or any other algorithm that computes the exact MiniMax value), since we are fundamentally computing less information. We only want to know which move is best, not how good or bad that move is exactly.

Shapeshifter has implementations of both BNS and MTD(f), and at least in self-play, BNS wins by a landslide.

Bitboards

To represent the game state while traversing the minimax tree, bitboards are a popular option in chess engines, but before Shapeshifter, they had not been used in Battlesnake, at least to my knowledge. This makes sense, as they are a lot more tricky to implement in this domain. For one thing, a battlesnake board is not sized 8x8, fitting neatly into a 64 Bit integer. Instead the standard board is 11x11, requiring 121 Bits. Because of this, my initial implementation used Rust's u128 integer type for the bitboards. But Battlesnake does not only play on 11x11 boards, oh no. The largest board size that is common is actually 25x25, which does not fit neatly into even the widest SIMD registers on existing hardware today. I still expanded my implementation to any arbitrary board size, by using low-overhead bitsets as the underlying datastructure instead of integers. At the time, Rust didn't have a bitset library that supported fast shift operations on compile-time sized bitsets (which is needed so they can be stored on the stack; Shapeshifter does actually not allocate any heap memory during processing). Naturally, I built my own really fast bitset implementation bitssset, to solve the issue.

Why go through the trouble of implementing bitboards?

So far everything was either completely known territory in the battlesnake world, or existing techniques from chess newly applied to battlesnake. However, there is one technique in Shapeshifter that does not appear in existing literature. That is what I call Minimum Combination Search or MCS.

The main problem in multiplayer minimax is that the high branching factor of the game tree makes it intractable to search it to deep enough to make good moves. The best known minimax algorithms for multiplayer games are Best Reply Search [4] , and its improved version BRS+ [5] . Both are fundamentally paranoid minimax versions that search a heavily reduced paranoid minimax tree. BRS+ uses a domain specific, efficient heuristic to choose one decent move per opponent, and then visits each move for each opponent once, letting the other opponents play their heuristic move at the same time. This assumes that in most game scenarios, we can choose one opponent to be the most important one and we need to deal with their move first and foremost. That assumption mostly holds in Battlesnake. The issue with this very clever algorithm is that the branching factor of the tree we are searching still grows with the number of players. If we have 3 opponents and each has 3 moves, that is a branching factor of 7. With 7 opponents it becomes 15, with 15 opponents it is 31, and so on. So with a growing number of players the treesearch still becomes intractable, because remember, trees grow with O(n^x) where x is the branching factor and n is the depth.

Minimum Combination Search follows the same principle as BRS+, searching each move for each opponent at least once. The difference is that it does not select a default move for all other opponents in each search branch. Instead it searches the tree in a way that uses the minimum number of opponent move combinations possible, to still cover all individual opponent moves. Assuming still 3 moves per opponent, we get a branching factor of 3, no matter if we are playing against 3 or 7 or even 100 opponents. Isn't that amazing?!

Let's illustrate: Assume you have three opponents, each with the moves A, B, C available to them. Assuming the default move heuristic always picks move A, BRS+ would search the seven move combinations [A, A, A], [B, A, A], [C, A, A], [A, B, A], [A, C, A], [A, A, B], [A, A, C]. In this notation, [A, B, C] denotes that simultaneously opponent 1 makes move A, opponents 2 makes move B and opponent 3 makes move C.

MCS on the other hand only searches the combinations [A, A, A], [C, B, B], [B, C, C] (or any other set of combinations that covers all individual moves). In this algorithm, it is even more important than in other minimax variants, to have a good move ordering heuristc. This can be used to order the individual opponent moves in a way that the best ones are probably searched together, leading to an earlier pruning of the tree and to a more realistic game state during search.

During my (non-scientific) evaluation of MCS, I noticed, that this performed extremely well in play against real opponents. In fact, as expected, the advantage grows with the number of players, to the point that Shapeshifter at one point boasted a 60% win rate both in 4 player games, as well as in 8 player games. You would expect to win half as many games with twice the number of players. In self-play however, BRS+ actually beats MCS, even though it performs worse against real opponents. This suggests that there might be some sort of rock-paper-sissors situation going on with these algorithms.

The advantages and disadvantages of the MCS can be summed up like this:

What have I learned?

Shapeshifter was the most complex and longest running project I had worked on until then. Among other things it taught me: