Building Boa Checker, a Rust-Based Bot for Battlesnakes

Hey all, I'm Back! And today I'll be writing a postmortem on an event I participated in a couple of weeks back. At the beginning of November, a colleague from the startup accelerator I'm a part of asked if I wanted to join a local Battlesnake tournament. I had heard of Battlesnake before but never gave it much thought and didn't fully understand what all went into it.

For those who aren't familiar, Battlesnake is essentially a competitive game of Snake where developers program their own bots (snakes) to compete for victory. There are countless resources you can use, but a good understanding of algorithms and probability is a must!

The event was held on December 6th and hosted by Hack Regina, a local developer community. Hack Regina organizes various developer events in our city to foster development and networking among developers.

So when I was invited to take part in the tournament I thought that this would be a fun little project and I could use this opportunity to learn a new language! The language I chose is Rust, which has consistently ranked as the #1 most desired programming language to learn. It's been on my backlog to find a project for Rust, and with Battlesnake's emphasis on quick response times, I thought it would be a perfect fit.

Day 0 - The Initial Plan

Before I even got started on implementing the project I had to do some research: how the heck do I even play this game?!

Thankfully there are countless resources online with all kinds of tips and tricks

After my initial research, I had a rough outline for my development process:

1. Setup the rust development environment and get the local battlesnake client running
2. Learn some core algorithms (A*, Flood fill, BFS, etc.) and gradually incorporate them into my bot. For this, my bot will have to be built with a that is modular.
3. Continue researching and refining my bot.
4. Deploy to cloud infrastructure.
5. Test against other bots in the global leaderboards
6. ???
7. Hopefully win the tournament! 🎉

Day 1- Rust, the borrow checker, and me

I'm not going to lie, the first 100 lines of code were very overwhelming – especially since I'm more familiar with languages like TypeScript and Dart. While I'm not averse to lower-level languages and actually prefer them, I was a little rusty with the low-level mental model.

To start I generated a project using the official Battlesnake rust starter template. This template automatically creates all the required files and API entry points I'll need for my project.

Morning

I came across a great resource by Thomas Weitzel. I liked the movement system Weitzel described in the blog post, where there is a set of available moves with varying probability that the bot can use to intelligently make the next decision. I used that as a starting point for my bot, and with this movement system in place, my goal of building a modular bot was on its way!

After the movement system was in place I spent some time researching how to implement A* path-finding so my bot would intelligently know where the food is located. But

Afternoon

As the afternoon rolled in, I dove deeper into enhancing my bot's intelligence. One critical aspect was wall avoidance, an essential skill for survival in Battlesnake. The rust start template already had this implemented but the default implementation didn't work with my upgraded movement system.

fn avoid_out_of_bounds(width: &i32, height: &i32, set: &mut WeightedMovementSet) {
    for future_move in set.moves.clone() {
        if future_move.position.x < 0 || future_move.position.x >= *width || future_move.position.y < 0 || future_move.position.y >= *height {
            println!("OOB - Removing {}", future_move.movement.to_string());
            set.remove(&future_move.movement);
        }
    }
}

Next up was body avoidance. I programmed the bot to recognize and steer clear of its own body and those of its competitors. This was trickier than I anticipated, requiring a nuanced approach to anticipate and react to rapidly changing scenarios on the board.

Dealing with competitor snakes was another hurdle. I implemented a system for competitor snake avoidance, ensuring my bot maintained a safe distance from others, particularly in crowded situations.

However, my attempt to avoid moves towards an enemy's head was somewhat flawed. While the idea was to prevent head-on collisions, the implementation wasn't as effective as I'd hoped.

Finally, I integrated the A* algorithm for food finding, setting a hunger threshold for my bot. This meant that it would prioritize food collection more aggressively when its health was low, a strategy crucial for sustaining itself in longer games.

I wanted to ensure that my bot wasn't always on the hunt for food as that would cause the snake to get too big too fast.

Evening

The evening was all about optimization and strategic thinking. I implemented a flood fill algorithm to prevent my bot from moving towards smaller spaces, reducing the risk of trapping itself.

fn flood_fill_bfs(start: &Coord, board: &Board, snake: &Battlesnake) -> usize {
    let mut visited = HashSet::new();
    let mut queue = VecDeque::new();
    let directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]; // Up, Down, Left, Right

    queue.push_back(start.clone());
    visited.insert(start.clone());

    let mut accessible_area = 0;

    while let Some(coord) = queue.pop_front() {
        accessible_area += 1;
        if accessible_area as u32 > snake.length + (snake.length / 2) {
            break;
        }
        for (dx, dy) in directions { // Up, Down, Left, Right
            let next_coord = Coord {
                x: coord.x + dx,
                y: coord.y + dy,
            };

            if pathfinding_is_valid(board, &next_coord) && !visited.contains(&next_coord) {
                visited.insert(next_coord.clone());
                queue.push_back(next_coord);
            }
        }
    }

    accessible_area
}

A significant portion of my time went into refactoring the code to speed up processing time. In a game like Battlesnake, every millisecond counts, and more efficient code could mean the difference between victory and defeat.

I then altered the decision-making process of my bot. Each rule now considered the decisions made previously. For instance, if one rule determined that a left move was impossible, the subsequent rule wouldn't even consider that as an option. This sequential filtering of decisions greatly enhanced the efficiency of the bot's movement strategy.

Day 1.5 - Deployment Hurdles

Figuring out the best deployment strategy for my bot without breaking the bank was challenging.

Originally I wanted to deploy the bot to AWS using API Gateway and Lambda. After some research, I found some concerns that there could be an issue with cold starts and the maximum response time of 500ms.

I settled on using an EC2 instance hosted in us-west-2, the same region the tournament was being held in– although the tournament was hosted on Google Cloud instead of AWS. I chose a t4g.small instance as it was under the free tier during the development of my bot.

I used Terraform to define the infrastructure as code, which helped automate deployment, setup, and port forwarding. Some manual work was required for server setup and running. Using Terraform also allowed me to dismantle the infrastructure overnight when the bot wasn't in use.

Code freeze

Once I got the bot hosted in EC2 I stopped my development. At this point, I've already logged over 1 full day of work on my bot and I thought that was enough for this tournament.

Leaderboard Matches

On the Battlesnake website, you can register your bot for daily tournaments in various game modes. I registered my bot in the daily dual and battle tournaments just to see where it stacked up.

After the first day my bot was winning a solid 60% of matches so I was pretty pleased with how everything came together. Unfortunately as of writing this, I can't show you screenshot proof because my bot has been offline for over a week so all my stats for game wins are wiped out ... you'll just have to trust me on this.

I noticed a few matches where my bot was timing out with some calls exceeding the 500ms response time limit. I suspect that the Battlesnake system uses several different regions when running the daily games, so the games that took place in regions like Asia or Europe were more likely to timeout.

Bug Fixes That Lead to More Bugs...

I made a change the night before the tournament to fix a bug related to my bot checking the position of the nearest head of the competitor's snakes. The way it was implemented originally was it was going through the snakes array in the game state and it compared the distance of that snake's head to my snake's head... the only problem is that my snake was also in this array. Which meant this check always made my snake think that it was super close to another snake, thus devaluing all move probabilities.

I fixed the bug but it actually borked the check altogether and ended up being the major weakness for my bot. I would show you some of the death cases here but as mentioned previously all the replays were wiped out.

Tournament Day!

I wasn't able to make it to the event in person due to some prior commitments, but I was able to watch a livestream of the event.

Little Boa Checker was able to make it to the semi-finals in both the rookie and the combined tournaments. Unfortunately, it didn't win the tournament but it still won in my heart :)

Overall it was a fun experience and I'm glad I could take part in the competition. I've always wanted to learn rust and this was a great opportunity to do so.

One recommendation I would give to the event organizers is to have a separate tournament for people who built their bots from scratch from those who used existing championship-winning snakes uploaded to GitHub.

The cool thing about the architecture of Boa Checker is that you could easily continue developing the bot to implement Minmax and Alpha pruning algorithms without much refactoring (thanks to the movement system Weitzel suggested).

Thank you so much for reading my Battlesnake adventures!

You can check out the code for my bot here:
GitHub – squaredx/boa-checker-snek