Halite III Bot Development Kit in Rust

I don’t recall the first time I found out about Halite. It was probably years ago. I do remember thinking a lot about the idea of writing your own bot that plays the game and hopefully wins. I thought about doing it in Python for a week or so, but then I gave up and forgot about it.

Fast forward a few years, and here I am rediscovering Halite again. This time it was much more entertaining to play with. I combined it with my enthusiasm for Rust and spent a couple of days writing what I like to call a BDK, bot development kit.

halite game screenshot

Table of Contents

Game mechanics

Halite III is a resource management game in which players build and command ships that explore the ocean and collect halite. Ships use halite as an energy source, and the player with the most stored halite at the end of the game is the winner.

The map is two dimensional and is usually 32 by 32 cells in size. If your ship navigates off the map the wraparound will move it to the opposite side.

You start with a shipyard and some amount of stored halite. The default starting halite is 4000, but that might be configurable. I haven’t yet explored all the options the halite server exposes.

A ship costs 1000 halite to construct. Moving it will deplete 10% of the halite stored in it. Not moving for a turn will transfer 10% of the halite stored in the cell to a ship that’s parked on it. The cells have a cap and can’t contain more than 1000 halite. They will regenerate a small amount of halite on every turn.

If you deplete halite around your shipyard, you can convert a ship to a drop-off. That has the potential to decrease the distance ships need to travel, therefore reducing the halite loss.

Writing the BDK

It took me quite a while to find the Halite III starter kits. For some reason, their documentation seems to be broken in places. On the other hand, Halite II documentation still has working links for downloads and is much better overall. After some searching, I found this repo that contained instructions on how to compile the Halite III engine and starter kits in many languages.

I also came across this starter kit in Rust. I tried it, but it was hard for me to figure out the API and the game data you can get. I went through the code and figured I can probably write something similar. I wanted it to be a library to make it easily embeddable into any project.

The hardest part for me was figuring out how the communication protocol works. Halite server uses it to send data and receive commands from bots. For context, this is how a game of Halite is ran:

halite \
  --width 32 \
  --height 32 \
  "./bot1 --name borg" \
  "./bot2 --intelligence superhuman"

The server runs the bots as separate commands and uses their stdin and stdout pipes to communicate. The data flows into a bot through stdin in the form of a simple space and newline delimited protocol. I couldn’t find any materials that describe this protocol, so I’ll cover it here.

The protocol

// This is a comment and is not a part of the protocol

// This protocol does not use empty lines, they are
// here only for the formatting purposes

// First line is a JSON blob that contains the
// configuration / parameters for this specific game
{"CAPTURE_ENABLED":false,"CAPTURE_RADIUS":3,"DEFAULT_MAP_HEIGHT":32,"DEFAULT_MAP_WIDTH":32,"DROPOFF_COST":4000,"DROPOFF_PENALTY_RATIO":4,"E        XTRACT_RATIO":4,"FACTOR_EXP_1":2.0,"FACTOR_EXP_2":2.0,"INITIAL_ENERGY":5000,"INSPIRATION_ENABLED":true,"INSPIRATION_RADIUS":4,"INSPIRATION_SHIP_COUNT":2,"INSPIRED_BON        US_MULTIPLIER":2.0,"INSPIRED_EXTRACT_RATIO":4,"INSPIRED_MOVE_COST_RATIO":10,"MAX_CELL_PRODUCTION":1000,"MAX_ENERGY":1000,"MAX_PLAYERS":16,"MAX_TURNS":400,"MAX_TURN_TH        RESHOLD":64,"MIN_CELL_PRODUCTION":900,"MIN_TURNS":400,"MIN_TURN_THRESHOLD":32,"MOVE_COST_RATIO":10,"NEW_ENTITY_ENERGY_COST":1000,"PERSISTENCE":0.7,"SHIPS_ABOVE_FOR_CA        PTURE":3,"STRICT_ERRORS":false,"game_seed":1403861864,"map_height":32,"map_width":32}

// Next line contains the number of players and your
// player id
2 0

// Now we get the positions of shipyards for every
// player in this format -> player_id pos_x pos_y
0 8 16
1 23 16

// We get the map dimensions, we'll use something small
4 4

// Now we get the starting amount of halite for every cell
34 128 552 18
261 4 377 854
423 119 268 111
932 21 76 341

// The setup phase is now over, now we start getting
// turn data

// The turn number
3

// For every player we get data about ships, drop-offs,
// and halite stored:
// player_id num_ships num_dropoffs halite
// then for every ship -> ship_id pos_x pos_y halite
// then for every drop-off -> dropoff_id pos_x pos_y
0 3 0 2314
13 7 28 417
14 27 3 13
17 11 11 957
1 4 1 3829
7 30 23 333
9 21 1 591
10 15 11 5
14 22 11 122
1 24 31

Sending commands is really simple. I used print! and println! macros to implement that. Here are the text representations of the commands:

  • spawn ship g
  • move ship m {ship_id} {direction} (direction can be one of n, e, s, w, even o which means stay still)
  • convert a ship to drop-off c {ship_id}

When you’re ready to finish your turn, you need to write these commands to stdout with a \n at the end. Here’s an example:

g c 8 m 3 n m 15 w\n

A remark about Rust

The details about the development and the libraries I used won’t be covered here. That might be material for a future post. I just want to say that I’m amazed that I was able to write almost the whole thing without running it once. After it was probably 90% finished, I tried running it and quickly debugged a few protocol issues I had. It was working. 😯

There were a few problems with data ownership and lifetimes. I’m still far from comfortable when it comes to lifetimes. After I abandoned the “no clone no copy” idea, I was able to simplify the API.

How to install

The BDK is available on crates.io. You can check out the source code in the GitHub repository.

If you use the great cargo-edit, you only need to run cargo add halite3bdk inside your Rust project.

Writing your first Halite bot

The first step is to make sure the halite engine is available in your $PATH. I couldn’t find an executable on the site, so I compiled it from the source. You’ll need to clone a repo and follow short instructions here.

My primary concern was to have a simple API. I think I’ve achieved that as the minimal example is only 8 lines long (not counting the blanks).

use halite3bdk::game::Game;

fn main() {
  let game = Game::init("botman");

  loop {
    game.next_turn();
    game.end_turn();
  }
}

You import the BDK, initialize the game, then loop until the game is finished.

If you compile this and run the game, you’ll see your bot is not doing anything.

Because Halite uses stdin and stdout to communicate with the bots, they can’t print anything, not even for debugging purposes. That’s why I’ve exported a logger utility, which will log into a file.

use halite3bdk::game::Game;
use halite3bdk::logger;

fn main() {
  let game = Game::init("botman");

  // Logger can be used after the game is initialized
  logger::info("Hello world");
  logger::error("This is weird");
  logger::abort("Could not initialize warp drive");
}

Now is the right time to add some behavior.

It moves

The most basic behavior we can implement is moving all the ships in the same direction. The shipyard will now spawn ships if possible, so we have something to move.

// import direction
use halite3bdk::direction::Direction;
...

game.next_turn();

let mut cmds = vec![];
let halite = game.my_halite();
let shipyard = game.my_shipyard();
let ships = game.my_ships();

// We spawn some ships
let shipyard_occupied = game.map.is_occupied(&shipyard.position);
if halite > 1000 && !shipyard_occupied {
  let cmd = shipyard.spawn();
  cmds.push(cmd);
}

// We move all ships to the north, why not
ships.iter().for_each(|ship| {
  // I need to change the method name as `move` is a
  // reserved keyword and needs to be invoked like
  // this, for now
  let cmd = ship.r#move(Direction::North);
  cmds.push(cmd);
});

game.register_commands(cmds);
game.end_turn();

It eats

It would be much more beneficial for this civilization to mine halite and move when there’s nothing left to mine. Let’s make them move in random directions until they find a valuable tile.

// import random dice throw
use halite3bdk::random::dice_usize;
...

ships.iter().for_each(|ship| {
  let tile_halite = game.map.get_cell(&ship.position).halite;
  let tile_is_worth = tile_halite > 1000 / 10;

  if !tile_is_worth {
    let directions = Direction::all();
    let chosen_dir = directions[dice_usize(4)];

    let cmd = ship.r#move(chosen_dir);
    cmds.push(cmd);
  }

  // we don't do anything if the tile is worth it, we keep mining 
});

It avoids death

It’s visible from the videos that our ships don’t really care much about their lives. They’ll move in any direction, even if it means certain death. Now they’ll start avoiding collisions.

if !tile_is_worth {
  let directions = Direction::all();
  let chosen_dir = directions[dice_usize(4)];

  let future_position = &ship.position.with_direction(&chosen_dir);
  let is_safe = !game.map.is_occupied(future_position);

  if is_safe {
    let cmd = ship.r#move(chosen_dir);
    cmds.push(cmd);
  }
}

The ships are a little more careful now about their movement, but they still die. The problem is that some of them might decide to move to the same tile next turn. We need to fix that.

...
if is_safe {
  // Set this tile to occupied for next ships to know not to
  // navigate there
  game.map.set_occupied(future_position);
  let cmd = ship.r#move(chosen_dir);
  ...

It’s alive

The only behavior left to implement is dropping off the halite when the ship is full. We’ll need some sort of container to keep track of ship states. An ordinary HashMap should do it.

...
enum ShipState {
  Mining,
  Returning
}

fn main() {
  let game = Game::init("botman");

  let mut ship_state: HashMap<u32, ShipState> = HashMap::new();

  loop {
  ...

And now we check the state for every ship.

ships.iter().for_each(|ship| {
  // the hashmap will not contain any states as first, so we
  // use ShipState::Mining as default
  match ship_state.get(&ship.id).unwrap_or(&ShipState::Mining) {
    ShipState::Mining => {
      if ship.halite < 1000 {
        // do what we did above, pick a random direction and
        // move if it's safe
        ...
      } else {
        // ship is full, start returning
        ship_state.insert(ship.id, ShipState::Returning);
      }
    }
    ShipState::Returning => {
      let destination = &shipyard.position;

      if &ship.position != destination {
        let next_directions = game.map.direction_to(&ship.position, destination);
        let direction = next_directions.first();

        match direction {
          Some(dir) => {
            let future_position = &ship.position.with_direction(&dir);
            let is_safe = !game.map.is_occupied(future_position);

            if is_safe {
              game.map.set_occupied(future_position);
              let cmd = ship.r#move(*dir);
              cmds.push(cmd);
            }
          }
          None => (),
        }
      } else {
        // ship is home, now go back to mining
        ship_state.insert(ship.id, ShipState::Mining);
      }
    }
  }
});

Future

At this point, I’m not sure if I will continue working on the BDK. This was only a “weekend” project for me. I’ll probably play with it for a couple more days, potentially improve the API. If people try and keep using this for their own bots, I might invest some more time in it.

Dijkstra maps

There’s one thing I’d like to explore for programming ship behavior, and that’s building Dijkstra maps for the environment. I came across these two posts that describe what they are and how can they be effectively used for all sorts of different behavior. It seems there aren’t any Rust libraries that expose something like this, so I might publish it as a separate crate.