Implementing a Bitwise Simulation
For making a simulation that's really fast and near incomprehensible

06 January 2019

I’ve written a several articles at this point about my Entelect Challenge bot. The Entelect Challenge is an annual AI programming competition, and this year competitors had to write the best tower defence playing bot that they could.

The algorithm that I used, the Monte Carlo Tree Search, was based on playing out many random games. You can read more about it in my previous article, but for the sake of this article it’s enough to know that a key component was a simulation of the game rules that ran as fast as possible. The more I could get done in the two second timeframe imposed by the Entelect Challenge rules, the better the moves my bot would choose.

The implementation I ended up with made heavy use of bitwise operations. I haven’t used bitwise operations in many situations, in fact they’ve barely appeared at all in my programming since university, so it was interesting to see them come up here.

What are the steps that I needed to simulate?

Each tower defence game is a one-on-one battle between two programs that have been written by two competitors. In each round, the programs need to start up, read the state of the game board and make a move - all within a strict two second time limit.

Like a board game, the competition came with a set of rules explaining what moves a bot could make and the results a given move would have. The moves that the bots could choose from all revolve around building various towers on their side of the board:

  • Energy towers produce energy for you to build other towers,
  • Attack towers shoot missiles at your opponent and
  • Defence towers block opponent missiles.

You can see how these towers come together by watching the recording of the competition’s finals!

Let’s focus in on how to simulate a round of the game, assuming that you know the moves that the two players have chosen to make.

  1. Each player’s move is processed first. This usually results in a tower in an unconstructed state, with a countdown until it is fully built.
  2. Next you need to look at any unconstructed buildings and decrease their countdown. If any have reached zero, this is when they’re transformed into a fully functioning tower.
  3. Any missile towers that are ready to fire then add their missiles to the board. Any missile towers that are not ready to fire will have their cooldown updated, so they will eventually have their own turn to add missiles to the board.
  4. Missiles on the board are then moved forward by two blocks. After each move, they need to check if they’ve collided with any of their opponent’s towers, and destroy the towers if they have.
  5. The energy towers for each player then need to be counted, and the energy they generate is added to the player’s total.

This is a lot to do each round, especially if you only have two seconds to as many of them as possible.

What is a bitwise operation and why is it fast?

Several years back now, I took a course on digital electronics. The course mostly consisted of the different ways of connecting up these electronic blocks that they called ‘logic gates’.

A logic gate is an interesting circuit component in that we think of it as performing a logical operation on a signal. If you take a wire that either has a voltage on it or not (logically on or off, also represented as 1 or 0), and connect it to the input of a “not gate”, then the output of the not gate will produce the opposite signal. An “and gate” has two inputs and will only produce an output if both inputs are on. An “or gate” has two inputs and will produce an output if either of the inputs are on.

/assets/posts/bitwise/logic-gates-and.svg /assets/posts/bitwise/logic-gates-or.svg /assets/posts/bitwise/logic-gates-not.svg

Operations like these “ands” “ors” and “nots” are the fundamental building blocks of modern computers. It goes without saying that computers are very good at them.

By the time you’re dealing with a programming language, you’re not connecting logic gates together to work on single bits anymore. The CPU has a bunch of gates lined up in a row to act on many bits at once. This lets you do things like line up the bits of two 64 bit integers and run each pair of bits through an “and” gate. This is what I’m talking about doing when I talk about bitwise operations.

I’m not going to draw out an example of a 64 bit bitwise And, but this 8-bit bitwise And circuit should give you the general idea.

/assets/posts/bitwise/logic-gates-8-bit-and.svg

If you use them right, bitwise operations can let you do 64 logical operations in a single CPU instruction.

How would you represent that as bitwise operations?

It’s not nearly as complicated as it may seem. First you need to consider how we’re going to represent as much of our map as possible using bitfields.

Very conveniently, each side of the map is 8x8 block. This means that you can fit the whole map into a single 64 bit integer, with one bit for each block on the board.

If you want to represent just a single point on the map, then you can also store the index of the point you’re referring to. When you need to combine it with the other bitfields, then you can use one of the bitwise operations, the left shift, to convert the index of a bit into a bitfield where just that bit is set.

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Point {
    pub index: u8
}

impl Point {
    pub fn to_bitfield(self) -> u64 {
        1u64 << self.index
    }
}

/assets/posts/bitwise/positioning.svg

But how does the data structure work out for an actual player looking at their side of the board? Well, here is the code for that. For those not familiar with the Rust programming language, u64 is an unsigned 64 bit integer. For these, the 64 bit part of that is more important than the unsigned integer part.

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Player {
    pub energy: u16,
    pub health: u8,
    pub unconstructed: ArrayVec<[UnconstructedBuilding; MAX_CONCURRENT_CONSTRUCTION]>,
    pub buildings: [u64; DEFENCE_HEALTH],
    pub occupied: u64,
    
    pub energy_towers: u64,

    pub missile_towers: [u64; MISSILE_COOLDOWN_STATES],
    pub firing_tower: usize,
    
    pub missiles: [(u64, u64); MISSILE_MAX_SINGLE_CELL]
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct UnconstructedBuilding {
    pub pos: Point,
    pub construction_time_left: u8,
    pub building_type: BuildingType
}

Some parts of this data structure may feel familiar, like an array to hold the list of buildings that are currently under construction. The interesting part is all of the 64 bit integers.

Look at the energy towers for example. If I had 2 energy towers, located at positions 8 and 26, the bitfield would look like the decimal number 67109120. If you draw it out in binary however, it looks more like this:

/assets/posts/bitwise/energy.svg

occupied indicates whether or not a spot is available to build on. If there is any building standing on a spot, even a building that’s currently under construction, a bit will be set of it in that number.

Some values need a few bitfields to represent fully. buildings, for example, is the health value for each building. For most buildings, they only get a bit set in the first element in the array, because they can be destroyed with a single missile. Defence towers, on the other hand, start with 4 bits set: one for each missile that a defence tower can withstand before it is destroyed. Each time a missile hits the tower, a bit is knocked off. When all of the bits for a spot in buildings are set to 0, then that tower is destroyed. If you’re careful about the order that you remove those bits, you can check just the first element in an array to see when a tower has been destroyed.

Some buildings you need to keep track of the individual building types. For example, you need to know how many energy towers you have. You also need to know where they are, so that you know when they’ve been destroyed by your opponent. Another bit field is perfect for this.

For missile towers, you need to keep track of their cooldown. The missile_towers array of bitfields has a bitfield for each batch of missile towers that shoot at the same time. This is paired with firing_tower, an index pointing at which one is going to fire next.

The missiles are the only thing that you need to keep track of on both sides of the board.

And, Or and Not

There are a few techniques that are useful to know about when you work with bitfields.

The And operation works well for masking. That is, setting up one field with the bits that you’re interested in inspecting set, and then Anding it with the value that you’re working with. This is also a convenient way of checking if a single bit is set. The And operation pairs well with the Not operation, if you want to mask to include everything except the set bits.

The Or operation is useful if you want to add new data into an existing bitfield. If you take a value set up with just the data you want to set, and a target bitfield with a range of zeroes, you can add the data into the empty region with an Or. Something to keep in mind is that the Or operation can’s unset bits, only set new ones. You can use an And mask to reset a region to zero if you want to clear it out first.

To get anything useful out, we usually need to chain a whole bunch of these together.

Let’s put it together

Example 1: Missile Towers Shoot Missiles

One fairly neat example of how this all comes together is when the missile towers fire. I’m already keeping the missile towers in bitfields, grouped by which ones fire together, so I have a bitfield of the towers that fire together.

Conveniently, the bitfield for the missiles I need to add is identical to the bitfield of towers that are firing.

If you could guarantee that there can only be one missile on a block at a time, then you could just use a bitwise or to add the new missiles to the game, but unfortunately this isn’t the case. Based on the size of the board and the rate that the towers can fire, it’s possible to have up to 4 missiles on a single block. I handled this by using 4 tiers of bitfields for missiles.

For each tier, you can use an And mask to see which missiles you can add to that tier. Then you use Or to put the missiles that there is space for into that tier. Finally, you use And to remove the missiles that you just added from the bitfield of missiles that you still need to add. Repeat this for each tier, and by the time you get to the end the bitfield of missiles that you still need to add should be empty.

Putting it all together in code looks like this:

fn add_missiles(&mut self) {
    // find the set of missiles that need to be added
    let mut missiles = self.missile_towers[self.firing_tower];
  
    for mut tier in &mut self.missiles {
        // use an And mask to see what fits in this tier
        let setting = !tier.0 & missiles;
        // use Or to put those missiles into the tier
        tier.0 |= setting;
        // clear the missiles that have been added to the tier from
        // the set you missiles that need to be added
        missiles &= !setting;
    }
    // next round, you'll be firing from the next set of missile towers
    self.firing_tower = (self.firing_tower + 1) % MISSILE_COOLDOWN_STATES;
}

Something important to notice here is that even though I might be adding many missiles to the board, shot by many towers, the actual number of CPU operations that I need to do is constant. I iterate through the different tiers of missiles, which will depend on the size of the board which is a constant. It’s a very compact representation of adding missiles to the board, both in terms of memory used by the missiles and the number of CPU operations used to put them there.

Example 2: Missiles Move and Hit Towers

A more complicated example is moving all of the missiles and having them collide with buildings.

// If you convert these masks from hex to binary, you'll see that they
// each have a bits set down the left or right column of the
// game board. Very useful for filtering those columns out from the
// rest of the board.
const LEFT_COL_MASK: u64 = 0x0101_0101_0101_0101;
const RIGHT_COL_MASK: u64 = 0x8080_8080_8080_8080;

fn move_and_collide_missiles(opponent: &mut Player,
                             player_missiles: &mut [(u64, u64); MISSILE_MAX_SINGLE_CELL]) {
    let mut destroyed = 0;
    let mut damaging = 0;

    // Missiles move 2 blocks at a time, but they might hit something
    // after only moving one block
    for _ in 0..MISSILE_SPEED {
        // As in the previous examples, our missiles are in a list of
        // bitfields because there might be more than one missile on a
        // single block. We need to move all of them.
        for missile in player_missiles.iter_mut() {
            // The missiles are actually in a tuple of two bitfields:
            // one for missiles on your side of the board and one for
            // missiles that have crossed over the middle into your
            // opponent's territory.

            // If they're in the right hand column of the left
            // bitfield, then the missiles need to move from the left
            // bitfield into the right one.
            let swapping_sides = missile.0 & RIGHT_COL_MASK;

            // Similarly, there is a column of missiles that about to
            // hit the opponent and do damage.
            let about_to_hit_opponent = missile.1 & LEFT_COL_MASK;

            // When you move the missiles that aren't swapping sides
            // or hitting the opponent, you need to use an And mask to
            // ignore the ones that are swapping sides, otherwise they
            // might affect other rows.
            missile.0 = (missile.0 & !RIGHT_COL_MASK) << 1;
            // The missiles that moved from left to right are added in
            // here using Or. We know that there is space for them on
            // the right because we Or them in after moving all of the
            // missiles left.
            missile.1 = ((missile.1 & !LEFT_COL_MASK) >> 1) | swapping_sides;

            // As a trick to optimize counting up the number of hits
            // from all the tiers of missiles, all of the missiles
            // that hit an opponent are combined into one bitfield,
            // using Or and shifting the bitfield on by one each time
            // you want to use it.
            damaging = (damaging << 1) | about_to_hit_opponent;


            let mut hits = 0;
            // Building health is structured as a series of
            // bitfields. Most towers, which are destroyed by one
            // missile, only write a bit into the first tier. The
            // defence building writes into all four tiers.

            // Missiles need to check from the highest tier, to ensure
            // that the health bar is knocked off in the right order.
            for health_tier in (0..DEFENCE_HEALTH).rev() {
                // First use an And mask to identify which missiles will actually hit.
                hits = opponent.buildings[health_tier] & missile.1;
                // Next update the building health, and remove the
                // missiles that just hit buildings from the group
                // that might still hit the next health tier.
                missile.1 &= !hits;
                opponent.buildings[health_tier] &= !hits;
            }
            // The last tier checked is the last hit the building can
            // take. When we leave the loop, the last bitfield of hits
            // can show us which buildings were destroyed.
            destroyed |= hits;
        }
    }

    // There's an efficient algorithm in the Rust standard library for
    // counting the number of set bits in a bitfield
    let damage = damaging.count_ones() as u8 * MISSILE_DAMAGE;
    opponent.health = opponent.health.saturating_sub(damage);

    // After you've moved the missiles, there's some housekeeping to
    // do with the other bitfields. All of the ones tracking specific
    // buildings need to be updated if their buildings have been
    // destroyed. Luckily, we have a bitfield at the end of this
    // showing all of the buildings that were destroyed this round.
    BitwiseGameState::destroy_buildings(opponent, destroyed);
}

Bitwise operations: useful for high performance, not so good for readability

So that’s bitwise operations. They are one of the fundamental operations that a CPU can perform, and so if you manage to shape your problem to fit them your execution time can be very fast.

How much faster?

  • Before implementing the bitwise version of the game rules, I was able to simulate 80 000 full random games.
  • At the end of the tournament, I had this up to 400 000.

That’s a 5x speed increase!

On the other hand, as I transitioned from my initial implementation of the game rules into the bitwise version, I found the code was harder to figure out what it was doing just by reading it. This made the code less maintainable in the long term.

Luckily I don’t need to maintain this code, the tournament is over, but that’s the trade off you need to be aware of.