For the second year in a row, Redbrick was proud to sponsor BattleSnake, an artificial intelligence programming competition held every year in Victoria.

In BattleSnake, your task is to write a program that plays the classic arcade game Snake. Your “snake” will be placed on a board with other snakes, and the last snake slithering wins the round.

We had three snakes enter the tournament this year: Aleksiy’s Snake, by Aleksiy, written in C++ Matt Damon, by Conrad and Jon, written in PHP Better than Aleksiy’s Snake, by Tyler, Mark, Kevin, and Wayne, written in Python. Better than Aleksiy’s Snake ultimately went on to win the Advanced Division, much to our surprise (and delight!), netting $1000 to the team.

Matt Damon had a strong showing as well, winning its bracket in the quarterfinals and advancing to the semi-final round. I’ve asked each of our teams to share some information about their strategy and design process below:

Aleksiy’s Snake

I chose to use C++ so that I could get the most out of the 200ms execution time. For the web server, I selected Crow, a C++ web microframework that was inspired by Flask. Lightweight, fast, and simple to use, it was perfect for this project. For JSON parsing I went with JSON for Modern C++ which has a very familiar syntax.

The strategy was very simple. At every turn, a flood fill algorithm was used to find dead ends and fill them. BFS was used to find the nearest food. In the early game, it would eat the closest food until reaching a size of 10.

Then, a secondary strategy would kick in. If it was far away from food, it would BFS to the nearest food. Once close, it would A* back to two spaces from its tail, delaying until its health was low.

When its health is less than the size path to the nearest food added with a buffer value, it would execute the path found by the BFS to eat the food. This strategy had a major drawback – enemy snakes could steal food from it while it was low on health, causing it to starve.

The snake came 3rd in its first battle, dying to a flood fill bug which did not allow it to grab the food it needed to survive. In its next battle, it lost a one on one to the eventual winner aptly named Better than Aleksiy’s Snake. Next year’s snake will be improved by rewriting dead end detection, eating food that other snakes are trying to steal, and implementing alpha-beta/minimax to fully utilize the performance of C++.

Matt Damon

Matt Damon looked for food that was close to him, and looked farther away the more hungry he became. He would also target the closest piece of food if there was a clean line of sight. He didn’t do any path routing to find food because there seemed to be plenty of it respawning all over the board through the game.

Additionally, Matt looked for free areas on the board. Notably, he headed in directions where he wasn’t likely to get stuck without enough room to move and cause a collision death. He did this by checking for areas around him that were smaller than his current size by using (standard) flood fill and a heuristic directional weighted (by proximity) flood fill. This let him know how much room there was to move in each direction and how wide the paths were.

Each of the six functions used to find food and open spaces were weighted for each direction based on the particular situation and the best option is chosen. Unfortunately, Matt died by turning into a closed space, something that the flood fill is supposed to catch. It is likely that last-minute tweaks caused the failure in the tournament. At least Matt made it to the semifinals but he’s not the greatest that ever was by any stretch. RIP good sir.

Better Than Aleksiy’s Snake

Our strategy was to use a local search algorithm with everything we could think added in. It would start by choosing a general direction to move based on very simple information about the location of snakes and food (where they were, open space onboard, distance to food compared to other snakes, our health, other snakes length, etc.)

Once we picked a general direction we would look at all open spaces in that direction to evaluate how desirable they were (creating a list of rated spots). For each spot in this list we spawned a thread and ran a simple BFS to find the best path for each (pursuing the best).

If nothing returned a path then we were trapped so we would floodfill in each direction and pick the longest path. This was the basic concept, but there were a lot of overrides – We made some squares invalid to move into, such as the ones around enemy snakes heads when they were larger than us.

However, we also ignored that override if we were very hungry. Quick floodfill checks were also run on surrounding areas to make sure that we weren’t moving into a dead end.

The Bounty Snake

We also had a bounty snake, written by myself (Scott) using Lua. Bounty snakes are a little bit different – instead of competing in the tournament, your task is to build the best snake that you can, and to come up with a set of rules for defeating it, as well as one or more prizes (“bounties”) that can be won if the snake is defeated. Prior to the tournament, other teams can issue a challenge to a bounty snake, and if they win, they can claim your bounty.

Our bounty this year was the Board Game Prize Package, including: Risk Settlers of Catan Codenames Exploding Kittens Cards Against Humanity Apples to Apples Super Mario Uno Our bounty snake, “Robo”, finished the day with 42 wins and 3 losses.

This means of the seven prizes we had up for grabs, we only ended up giving away three (Risk, Catan, and CAH). The snakes that ultimately defeated Robo ended up going quite far in the tournament, and claiming victories against several bounty snakes – I’d be quite interested to hear their strategies!

Those snakes were: greedy-snek – won Risk bin-bot – won Cards against Humanity Your New Dad – won Settlers of Catan I will share more information about the design and strategy of our bounty snake in an upcoming blog post – there’s quite a lot to talk about! Big thanks to Sendwithus, Stembolt, and Workday for putting on such a great event! See you next year!