Tic-Tac-Toe is a cool game when talking about Game Theory. It’s an adversarial game (where both players have opposite goals), in which a decision from each player influences the whole game state.

Today, we’re going to learn how to encode a match of Tic-Tac-Toe in a single number by using Bitwise operations. Our requirements are:

The number of game states that Tic-Tac-Toe has is $ 765 $1, we could assign a unique number to each one of those states only using a 9.58-bit unsigned integer. But that’s boring, doesn’t meet our requirements and the worst of all: Memory intensive

We don’t want to use much memory here; not because of real concerns, but because of imaginary ones.

So, we need a way to indicate how does the game look, using a very limited number of bits, $\leq 128$, so that it can fit in a single Rust u128.

Note that we don’t know yet the number of bits we need (we only know that it needs to be less than 128), so we’ll define $“n”$ as the number of bits necessary.

A cluster inside a cluster inside a…

Nobody said that we need to think of our bytes as a single number (well, I kinda did). So we’re going to split our bits into two $\frac{n}{2}$-bit clusters. The first cluster will contain positions for Player 1, and the second cluster will contain positions for Player 2.

Diagram with a 128-bit binary number with two clusters

Now, we can create more clusters inside those clusters! We’ll make 9 more clusters inside each one of those clusters to store each one of the squares. We’ll use 2 bits to represent a single square. Doesn’t trigger your programmer built-alarms? Using 4 possible values to represent 3 possibilites?

Getting to the real deal

Let’s imagine we have this board:

Diagram with a 128-bit binary number with two clusters

Having the following distribution:


This would be the translation into our new format:

So now we know, the ID for this specific board is ✨ 18696 ✨ But… this data isn’t compressed, we would use 18 total bits, innacceptable!

Or… is it?

I just made some benchmark using the Rust’s std::mem::size_of function. And so, checking the following simple struct:

struct Board {
    pub board: [State; 9]

Turns out it uses 9 bytes! That’s 4 times larger than our required 18-bit encoded number. I guess it was compressed after all.

use std::mem::size_of;

enum State {

struct Board {
    pub board: [State; 9]

impl Board {
    pub fn is_tied(&self) -> bool {
        for state in &self.board {
            if matches!(state, State::Empty) {
                return false;

fn main() {
    println!("{}", size_of::<Board>());