Entering the Battlesnake arena

Entering the Battlesnake arena

August 22, 2021 15 minutes reading time Development rust

A short time ago I started learning to program in Rust. Therefore, I’m looking for new toy projects to train my Rust programming skills. I first heard about Battlesnake in the podcast Go Time with Jon Calhoun, Brad van Vugt, and Mat Ryer. This blog post uses Rust as a programming language, but only as an example to explain the implementation of strategies. The information can be useful if you use other programming languages, too.

What is the aim of this post?

I started programming my first own snake Fairy Rust a couple of weeks ago. Up to now, I’ve invested about a working day of my spare time into this project. During that time, I learned some lessons to make my snake better. I want to share them with you. If you start programming your own snake, maybe they can make your snake better as well.

In the future, I plan to write more articles about how I got my snake to improve - if I’m able to make it better. I have some ideas that I will mention at the end of this article, so stay tuned.

How does the game look like?

Battlesnake can be thought of as the evolution of the classic game Snake from Nokia, that appeared for the first time in 1998 on the Nokia 6110. The game idea is even older, but Nokia made it known to a broad audience. The following game features four snakes fighting against each other. The animation stops after 3 repetitions in order to minimize distraction.

Example game in Global Arena

What is it?

Battlesnake is an online game where programs - and thus their programmers - play against each other. You only need a running web server that implements four endpoint, a.k.a. the Battlesnake API.

The most important one is the move endpoint that handles the requests for your next move. A request contains the description of the entire board prior to your move, for example:

  • the height and width of the board, e.g. 11 by 11 squares; each square is an address in a Cartesian coordinate system (X- and Y-axis)
  • the positions of all snakes on the board, where their heads and the rest of their body parts are
  • the current positions of food; eating food restores your health to 100 health points
  • where dangerous zones are (named hazard sauce); moving your head in it costs you not 1 health point but 15 per move

Your move endpoint responds with a direction for moving the head of your snake. It’s either Right, Up, Left, or Down. If your snake’s head is on point (2, 3), then Right will move it to (3, 3) and the rest of its body will follow. Responding with Down would move it from (2, 3) to (2, 2).

The lower left square of the board is point (0, 0), the upper right square is (width-1, height-1).

Developing your own snake

As a starting point, you can find starter snakes that implement a basic framework for handling requests for many programming languages on the GitHub BattlesnakeOfficial account. They do not include any useful logic for letting your snake survive, but enable you to start with your own logic without spending too much time setting up your own framework for handling requests:

Your snake has only one primary goal: to survive (not die) by moving correctly. So what lets your snake die:

  • leaving the board (running into the wall)
  • running into another snake, head-on collisions are a special case
  • head-on collision with a snake at least as long as your snake
  • starving (running out of health; one move normally costs you 1 health point, but 15 with your head in the hazard sauce)

When your snake is asked to make a move, it has to pick one of the four directions. So an initial strategy should check all points that can be reached by following the respective direction, if they result in death.

Strategies and how to implement them

If a new game starts, you only see the head of your snake, but it already has a length of 3. That’s because all other body parts are stacked beneath your head - all are at the same point. Thus, you can freely move in any of the four directions, because there is nothing that would kill you. But what is the best direction?

Whenever you have to chose from more than one possibility, not all of them might be equally good. So I’ve chosen to create a set of WeightedMovement with all four possible movements and a probability of success attached to each movement. How to calculate the probability is where we later spend most of the time. But what’s already clear: we should pick the movement with the highest probability of success:

pub enum Movement {
    Right,
    Left,
    Up,
    Down,
}

pub struct WeightedMovement {
    pub movement: Movement, // the movement
    pub probability: f32,   // probability of success
}

pub struct WeightedMovementSet {
    // will be initialized with all four movements,
    // all having a default/starting probability
    pub moves: HashSet<WeightedMovement>,
}

As a consequence, these are the functions I’ve implemented for the WeightedMovementSet. Alternatively, I could have chosen to not implement the remove function, but set the probability of a move to a small value if it leads to immediate death.

impl WeightedMovementSet {
    // initializes the set with the four movements, each having a default probability
    pub fn new() -> WeightedMovementSet { /* … */ }

    // removes a movement from the set, because it's not a viable option
    pub fn remove(&mut self, movement: &Movement) { /* … */ }

    // changes the probability of a movement, because we gained some insight
    pub fn change_probability(&mut self, movement: &Movement, new_probability: i32) { /* … */}

   // picks the best movement - if there is one
    pub fn pick_movement(&self) -> Option<Movement> { /* … */ }
}

Start with the four movements

You should remove all movements that would immediately kill your snake from the set of possible movements and only look at the remaining ones. There might be scenarios where you only can make a move that results in the death of your snake (leaving your set of possible movements empty), so you should always have a default move that you make (like Up) if you have no viable option left. Your snake will die anyway - sorry!

Starting from the point where your snake’s head is, you should identify and then check the points on the game board that you can reach with your next move. These points should not be points where some sort of problem occurs - I will explain shortly. To make life easier for me, I have attached the corresponding movement information to these checkpoints, i.e. in which direction the head of my snake has to move to reach this point:

pub struct CheckPoint {
    point: Point,
    movement: Movement,
}

The following function will return a collection of points that my snake’s head can reach in the next move. I have to pass the position of my snake’s head (reference point) as an argument. These checkpoints are the basis for further investigation:

pub fn make_check_points(ref_point: &Point) -> Vec<CheckPoint> {
    vec![
        CheckPoint { point: Point { x: ref_point.x + 1, y: ref_point.y     }, movement: Movement::Right },
        CheckPoint { point: Point { x: ref_point.x,     y: ref_point.y + 1 }, movement: Movement::Up    },
        CheckPoint { point: Point { x: ref_point.x - 1, y: ref_point.y     }, movement: Movement::Left  },
        CheckPoint { point: Point { x: ref_point.x,     y: ref_point.y - 1 }, movement: Movement::Down  },
    ]
}

Eliminate movements leading to immediate death

The first obvious reasons for the immediate death of your snake are, if it moves its head to a point that …

  • is outside the board
  • does belong to the body of a snake, either another one or your own snake

As an example, I’ll show you how to eliminate all movements that will make your snake run off the board. A battlesnake in JSON format looks like this, so you can retrieve the point where the head is directly from this:

{
  "id": "totally-unique-snake-id",
  "name": "Sneky McSnek Face",
  "health": 54,
  "body": [
    { "x": 0, "y": 0 },
    { "x": 1, "y": 0 },
    { "x": 2, "y": 0 }
  ],
  "latency": "123",
  "head": { "x": 0, "y": 0 },
  "length": 3,
  "shout": "why are we shouting??",
  "squad": "1"
}

The function needs the size (width and height) of the board, as well as the head position of your snake. I have decided to let it directly remove all deadly movements from the set of possible movements, as it doesn’t make sense to look at them from this point on. We already know that our snake has no future with any of these movements.

It first calculates all the points (checkpoints) that can be reached by our snake’s head with its next move, and then looks if a checkpoint is outside the board. These points are not considered any further:

pub fn avoid_wall(width: i32, height: i32, you: &Battlesnake, set: &mut WeightedMovementSet) {
    let head = &you.head;
    let check_points = make_check_points(head);
    for check_point in &check_points {
        if check_point.point.x < 0 || check_point.point.x >= width || check_point.point.y < 0 || check_point.point.y >= height {
            // remove this movement from the set of possible movements
            set.remove(&check_point.movement);
        }
    }
}

You can now go ahead and implement a function that avoids movement into the body parts of your and all other snakes (exercise left to the reader).

Stacked snakes

As soon as I implemented the function that avoids moving into a snake’s body, I realized that it’s normally safe to move into the position of a snakes tail, because it will have moved on by the time my snake makes that move. But there is an exception to that rule: if a snake has eaten food during the prior move, its tail will stay in the same position for another move.

Hm, do I then have to remember if there was food in the position where a snake’s head has moved? I would have to store the information from the previous request, thereby creating global state. Thankfully no! Whenever a snake eats food, it will grow and get another body part in a position where it has one already. This part of its body becomes stacked. And a stacked snake’s tail does not move. A naive implementation to find out can look like this - checking if there’s more than one body part in a position:

pub fn is_stacked(snake: &Battlesnake) -> bool {
    for i in 0..snake.body.len() - 1 {
        for j in i + 1..snake.body.len() {
            // snake.body[n] is a point with X- and Y-coordinate 
            if snake.body[i] == snake.body[j] {
                return true;
            }
        }
    }
    false
}

So whenever a snake is stacked - either your own snake or another one - it’s not wise to move into the position of its tail. If it’s not stacked, you can consider moving there. You should still evaluate if another nearby snake can move into that spot, too. If it’s at least as long as your snake, you might die in a head-on collision. I’m therefore recommending downgrading the probability of success for such a move.

The tail of a snake is the last element of its body:

pub fn get_tail(snake: &Battlesnake) -> &Point {
    // there cannot be an empty snake body
    snake.body.last().unwrap()
}

Dead ends

As soon as your snake survives for more than just a couple of moves you start realizing that it does lots of stupid things. It makes bad decisions, like moving into an area where there is not much room and no way out. Sometimes it curls up, eventually running into itself.

How to solve these kinds of problems? You need a strategy for looking ahead for more than just what does not immediately kill you in your next move.

The flood-fill algorithm comes to the rescue. I will not explain it here, but will mention that it can help you identify areas that are too small, where you shouldn’t go.

The implementation and use of the flood-fill algorithm is probably the single most important thing to do, as it will improve your snake beyond the majority of all other snakes. And it has the potential for even further improvement:

  • helps in finding the shortest path to food
  • helps in finding the shortest path out of the hazard sauce
  • assists in decision-making (which area contains how many heads, tails, food, and how far are they away)

Sudden death by latency

To participate in battlesnake games, your battlesnake’s API must be reachable over the Internet. Since I have my own server, I decided to deploy my first battlesnake to it and run it from there. The server is located in Strasbourg, France. Currently, the Battlesnake Game Engine is hosted in AWS US-WEST-2. That’s nearly 6,000 miles apart.

Latency was below 200 ms for most parts of the games, but with sudden and unpredictable spikes. Most spikes where above 500 ms, outside the time cap for the request. Whenever this happens, the game engine repeats the last move for your battlesnake. If your snake is head against the wall, it will be dead afterwards. It was especially bad in the Global Royale game mode, where my snake was running into the wall after only a couple of moves every time.

To reduce latency, I looked for a cloud provider who had servers nearby the Battlesnake Game Engine. Other requirements were that it was easy to use and affordable. Linode offered:

  • a region nearby: Fremont, CA
  • a promotion: $100 free for 60 days
  • low cost small instance: Nanode, 1 GB RAM, 25 GB storage, approx. $5/month
  • 1 TB of un-throttled network traffic
  • Ubuntu 20.04 LTS image, my preferred distro right now

The Nanode instance is more than enough for my Rust implementation (stand-alone executable), that runs as a Linux service. The entire system uses approx. 15 % of the available RAM, and CPU usage never goes above 10 %, below 1 % on average. Estimated network traffic is less than 2 GB per month, well below the 1 TB high-speed limit. Running my battlesnake on Linode gives me less than 50 ms latency consistently. I’ve run into some timeouts as well, so they are not gone completely. But the number of timeouts is so low, I barely recognize them anymore.

Deployment to Linode

In this section I will explain how to set up a Linux service for your battlesnake on a Linode instance, how to start and stop it (even remotely), and how to deploy new versions of your snake with the push a button - sort of.

SSH key and easy access

I assume you have created a Linode instance and it’s ready for use. In order to work with your remote Linode server, you should create a private/public key pair locally and store the public key under SSH keys in your Linode account. Suppose you have created a key pair in your ~/.ssh directory with the name id_linode. You then upload the contents of the file id_linode.pub to Linode as your public SSH key. The other file id_linode contains your private key and should never be shared.

To easily connect to your Linode instance with ssh linode, add the following lines to your local ~/.ssh/config file:

Host linode
  # use IPv4 address from your Linode instance
  HostName 123.45.67.89
  Port 22
  User root
  IdentitiesOnly true
  IdentityFile ~/.ssh/id_linode
  ServerAliveInterval 15
  StrictHostKeyChecking no

Setup Linux service

Now it’s time to set up your service on your Linode instance. In this example, I will name the service battlesnake, but you can name it however you like. Your executable file (built with cargo build --release, or whatever language/tool you are using) is stored in the directory /opt/battlesnake on the server with the name battlesnake. If it’s not there yet, copy it to this location first. Make sure it’s executable, e.g. with sudo chmod +x /opt/battlesnake/battlesnake. Create the file /lib/systemd/system/battlesnake.service:

[Unit]
Description=battlesnake service
ConditionPathExists=/opt/battlesnake/battlesnake
After=network.target

[Service]
Type=simple
User=www-data
Group=www-data
LimitNOFILE=1024

Restart=on-failure
RestartSec=10
StartLimitInterval=60

WorkingDirectory=/opt/battlesnake
ExecStart=/opt/battlesnake/battlesnake

PermissionsStartOnly=true
StandardOutput=syslog
StandardError=syslog
SyslogIdentifier=battlesnake

# Set environment variables (optional)
Environment=LOG_LEVEL=WARN

[Install]
WantedBy=multi-user.target

You are now ready to work with your service:

  • enable the service with sudo systemctl enable battlesnake.service
  • start the service with sudo systemctl start battlesnake.service
  • check status with sudo systemctl status battlesnake.service

Checking the status of your service should give you something like this:

# sudo systemctl status battlesnake.service
● battlesnake.service - battlesnake service
     Loaded: loaded (/lib/systemd/system/battlesnake.service; enabled; vendor preset: enabled)
     Active: active (running) since Mon 2021-08-16 13:12:24 UTC; 1 day 22h ago
   Main PID: 571 (battlesnake)
      Tasks: 19 (limit: 1071)
     Memory: 4.0M
     CGroup: /system.slice/battlesnake.service
             └─571 /opt/battlesnake/battlesnake

Automatic deployment

If you use a SSH key as described above and have a SSH configuration for linode, then it’s easy to write a shell script - run on your development machine - that automates the deployment. Here I’m deploying the executable target/release/battlesnake to the server. You can even stop and start the service remotely:

#!/bin/bash

# uses SSH key from ~/.ssh directory and configuration from ~/.ssh/config

echo "stop service"
ssh -t root@linode "systemctl stop battlesnake"

echo "copy executable file"
scp target/release/battlesnake root@linode:/opt/battlesnake/battlesnake

echo "start service"
ssh -t root@linode "systemctl start battlesnake"

What’s coming next?

My snake is participating in all three global arenas, with mixed success. It’s not completely bad, but there’s definitely room for improvement. For example, it struggles to stay in the Platinum Level in the arenas Global Arena and Global Royale, oscillating between Gold Level and Platinum Level. I still have a lot to do to improve it.

Example game in Global Arena

I plan to write one or more follow-up posts. Some things I plan to implement and then write about are:

  • aggressive mode: go for head kills (or: don’t miss a chance to do it)
  • flood-fill algorithm in detail and further improvements

Do you have some other suggestions for me? I would like to hear them.

Attributions

The image used for this post’s card is taken from the Battlesnake’s Summer League 2021 banner. I reached out to the Battlesnake team, and they kindly allowed me to use it. Thank you!