There was a thread on Reddit that caught my interest the other day. A Software Engineer at Google mentioned his favorite interview question for potential candidates was to have them write an algorithm to determine if a tic-tac-toe game had a winner. Thinking about the question inspired me to solve the algorithm.

To make the task more challenging, I decided to write the algorithm in Rust (a language I am learning but not competent in).

There are various strategies a developer might take in implementing an algorithm to determine the state of a tic-tac-toe board. Most approaches revolve around matching winning combinations (to which there are only 8) to player positions (X's and O's). The trick is determining the best way to evaluate the board state.

In this post, I'm going to walk through my thought process and implementations for two similar strategies for implementing this algorithm. You can skip all the prose and visit the actual code if you want: https://github.com/rclayton-the-terrible/solve-tic-tac-toe-rust

Model and Setup

Let's first start by establishing a simple domain model for a tic-tac-toe game:

// Represents a value at a specific position on the
// game board.
pub enum PlaceValue {
    X,
    O,
    E // Empty
}

// Represents the game board
pub struct Board {
    row1: [PlaceValue;3],
    row2: [PlaceValue;3],
    row3: [PlaceValue;3],
}

impl Board {
    // A simple method for building
    // a game board from an array of place values.
    pub fn from(positions: [PlaceValue;9]) -> Board {
        Board {
            row1: [positions[0], positions[1], positions[2]],
            row2: [positions[3], positions[4], positions[5]],
            row3: [positions[6], positions[7], positions[8]],
        }
    }
}

Our implementations (just functions) will have the following signature:

fn (board: &Board) -> Option<PlaceValue>

I have a battery of unit tests and benchmarks that will evaluate the validity of each implementation, so if you want to try your own, you will register it in src/tests.rs:

#[cfg(test)]
mod tests {
    use crate::*;
    use crate::PlaceValue::*;
    use super::test::Bencher;

    fn run_compliance_tests(eval_winner: fn (board: &Board) -> Option<PlaceValue>) {
        //... Test impl
    }

    #[test]
    fn test_bit_wise_eval_winner() {
        run_compliance_tests(bit_strategy::eval_winner);
    }

    #[bench]
    fn bench_bit_wise_eval_winner(b: &mut Bencher) {
        b.iter(|| run_compliance_tests(bit_strategy::eval_winner));
    }

    #[test]
    fn test_loop_eval_winner() {
        run_compliance_tests(loop_strategy::eval_winner);
    }

    #[bench]
    fn bench_loop_eval_winner(b: &mut Bencher) {
        b.iter(|| run_compliance_tests(loop_strategy::eval_winner));
    }
}

Loop Strategy

My first thought was to take the most direct approach, a nested loop strategy, that iterated over winning combinations and checked if the gameboard had any of those combinations for either player.

In (my sort of) pseudo-code, it would look like this:

for each winning combo [C]:
  for each value in the combo [c]:
    if current value at position is X:
      increment X matches
    if current value at position is O:
      increment O matches
  if X matches == 3
    return X as winner
  if O matches == 3
    return O as winner
default: return no winner

In the loop strategy, we define a winning combo as an array of "1"s and "0"s, where "1"s represent a required place value for that combo. I defined all winning combos like this:

const WINNING_POSITIONS: [[u8;9];8] = [
    [1, 1, 1, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 1, 1, 1, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 1, 1, 1],
    [1, 0, 0, 1, 0, 0, 1, 0, 0],
    [0, 1, 0, 0, 1, 0, 0, 1, 0],
    [0, 0, 1, 0, 0, 1, 0, 0, 1],
    [1, 0, 0, 0, 1, 0, 0, 0, 1],
    [0, 0, 1, 0, 1, 0, 1, 0, 0]
];

The implementation matches pretty closely to the pseudo code:

pub fn eval_winner(board: &Board) -> Option<PlaceValue> {
    for combo in &WINNING_POSITIONS {
        let mut x_matches = 0;
        let mut o_matches = 0;
        for i in 0..combo.len() {
            if combo[i] == 0 {
                continue;
            }
            // value_on_board just gets the value at position
            // "i", which is just the left-to-right, top-down
            // places on the 3x3 grid.
            match value_on_board(&board, i) {
                X => x_matches += 1,
                O => o_matches += 1,
                _ => ()
            }
        }
        if x_matches == 3 {
            return Some(X)
        }
        if o_matches == 3 {
            return Some(O)
        }
    }
    None
}

The loop strategy is not bad. It solves the problem directly and is not costly from a performance perspective, given that the algorithm will only experience 72 loop iterations (8 combos x 9 positions) at most.

However, with some additional complexity, we can optimize this algorithm a little bit.

Bitwise Strategy

Instead of using arrays and nested loops, we could model both winning combos and player selections as bit arrays (actually, unsigned integers).

The winning combos are now modelled in binary:

const WINNING_POSITIONS: [u16;8] = [
    0b_111_000_000,
    0b_000_111_000,
    0b_000_000_111,
    0b_100_100_100,
    0b_010_010_010,
    0b_001_001_001,
    0b_100_010_001,
    0b_001_010_100
];

The algorithm changes slightly. We don't need to loop through every position on the board multiple times to determine the winner:

convert board positions for X's and O's into bit arrays
for each winning combo (as int):
   if (X & combo) == combo:
     return X as winner
   if (O & combo) == combo:
     return O as winner
default: return no winner

The key to this approach is the bitwise & (AND) operator.

The bitwise AND operator is applied to two numbers (e.g. 402 & 163). All 1 bits shared at the same position between both numbers are retained. All other positions are filled with 0s:

We already have all the winning combo positions defined as integers. All we need to do is convert the board positions for X's and O's into integers as well:

struct XPosOPos(u16, u16);

fn board_to_bits(board: &Board) -> XPosOPos {
    let mut x_bits: u16 = 0;
    let mut o_bits: u16 = 0;
    for i in 0..9 {
        let row = get_row(&board, i);
        let position = get_row_pos(i);
        match row[position] {
            PlaceValue::X => x_bits |= 1 << i,
            PlaceValue::O => o_bits |= 1 << i,
            _ => (),
        }
    }
    XPosOPos(x_bits, o_bits)
}

The functions get_row and get_row_pos are just helpers that translate i (the index in our 9-bit array) to the 3x3 grid of tic-tac-toe. With that position, we determine whether the value is "X", "O", or "E" (empty). If it's X or O, we need to set the bit at position i in that integer to 1. We can set the bit using the bitwise | (OR) and the left shift << operators.

The bitwise OR operator is applied to two numbers (e.g. 402 & 163). For all bit positions, if a 1 occurs in either number, the value of that bit position becomes 1. All positions where both numbers have a 0 remain 0:

The left shift operator << is an operator that shifts all bits on the operator's left-hand side by N positions (specified by the value on the right-side). For example, 0b001 << 1 results in 0b010 or 2.

When the bitwise OR (|) and left-shift (<<) operators are combined, you can set the bit at a specific position in a number. To do this, we make a "mask" -- a bit array with the 1 in the correct position. We then perform a bitwise OR between the number whose bit we want to set and the mask. For example, say we want to set the 6th bit to 1:

let mut n = 22;
// move the 1 bit to the 6th position; 0b000_000_001 becomes 0b000_100_000
let mask = 1 << 6;
n = n | mask;
// Alternatively, Rust has |= operator similar to +=
n |= mask;

Now that we understand how the board state is translated into two integers (bit arrays) representing the X and O positions, let's look at the algorithm for determining the winner:

pub fn eval_winner(board: &Board) -> Option<PlaceValue> {
    let XPosOPos(x_bits, o_bits) = board_to_bits(&board);
    for pos in &WINNING_POSITIONS {
        if (pos & x_bits) == *pos {
            return Some(PlaceValue::X);
        }
        if (pos & o_bits) == *pos {
            return Some(PlaceValue::O);
        }
    }
    None
}

All we do now is iterate over combo positions and check to see if the combo matches the X and O positions ((pos & x_bits) == *pos).

It's easier to see what's happening with this expression by looking at an example:

(0b010 & 0b111) == 0b010
// simplifies to:
0b010 == 0b010

Comparison of Strategies

The loop and bitwise strategies are both effective. As I mentioned before, the worst-case scenario for the loop strategy is 72 loop iterations. The bitwise method accomplishes the same result with a maximum of 17 loop iterations (9 to create the X and O bit positions and 8 to loop through the combos). Of course, the body of the loops are also different - so perhaps not an apt comparison.

In terms of memory, the bitwise approach uses fewer resources. The loop approach has to store 72 integers (8, 9 element arrays) plus two integers for the intermediate state during iterations. The bitwise strategy uses eight integers for combo state and two integers for the X and O board state.

Both approaches use a minimal amount of memory and would be acceptable in a production system. The loop method is arguably easier to maintain. However, if you are interviewing or completing a Leetcode challenge, you will want to optimize for the fewest resources.

So what do the benchmarks look like?:

> cargo bench
    Finished bench [optimized] target(s) in 0.00s
     Running unittests (target/release/deps/solve_tic_tac_toe-2ba3cdb4b32fcc5e)

running 5 tests
test bit_strategy::tests::test_board_to_bits ... ignored
test tests::tests::test_bit_wise_eval_winner ... ignored
test tests::tests::test_loop_eval_winner ... ignored
test tests::tests::bench_bit_wise_eval_winner ... bench:          97 ns/iter (+/- 4)
test tests::tests::bench_loop_eval_winner     ... bench:         581 ns/iter (+/- 44)

test result: ok. 0 passed; 0 failed; 3 ignored; 2 measured; 0 filtered out; finished in 10.38s

The bitwise approach is nearly five times faster!

Conclusion

I thought this was an exciting project to apply Rust and optimization techniques like bitwise operators. Tic-tac-toe is not the most practical thing to optimize for, but the solutions demonstrate bitwise operators' potential if you need to eke out extra performance from some code.

If you thought the bitwise operators were neat, please check out this course on Educative: Master Solving Problems using Bit Manipulation.