Encoding tic-tac-toe in 15 bits

I just lately stumbled upon a blog post by Alejandra González (a.okay.a @blyxyas) that seeks to compress a tic-tac-toe recreation state into as few bits as potential. She arrived at an answer in 18 bits. This bought me pondering, can we do higher?

As Alejandra factors out, there are 765 potential recreation states^{. We might merely assign a quantity to all the sates, which might take up 10 bits. However in Alejandra’s phrases, that’s “boring.” Extra particularly, there’s not a lot we are able to do with a illustration like that. Whether or not we need to learn the worth of a given cell or replace from one state to a different, in observe we’re going to wish a lookup desk to map every quantity to a bigger, extra structured illustration, which defeats the entire concept behind a compressed illustration.}

An 18 bit answer

Alejandra got here up with a greater answer, the place every cell is represented by a pair of bits, and the grid is represented as a concatenation of 9 of those bit pairs. Inside a bit pair, one bit represents a circle and the opposite represents a cross; at most one little bit of the pair might be set.

// The illustration of a single cell.
typedef enum cell {
    EMPTY  = 0, // Binary 00
    CROSS  = 1, // Binary 01
    CIRCLE = 2, // Binary 10
} cell;

// The concatenation of 9 cells. We solely care in regards to the decrease 18 bits.
typedef uint32_t state;

The core strategies that we wish to have on our state kind are getting and setting cell values at a given index. That is fairly simple to implement with some fast bit-twiddling.

cell get_cell(state s, int i) {
    int pos = 2 * i;        // Bit offset of cell i.
    return (s >> pos) % 4;  // Learn the cell.
}

void set_cell(state *s, int i, cell val) = val << pos;   // Set the brand new worth.

This can be a improbable, environment friendly answer.

Getting smaller with base-3

In observe, the variety of bits in an integer must be an influence of two. Within the code above, we used a 32 bit integer to carry our state, once we actually solely wanted 18 bits. If we might save simply two extra bits, we might minimize our reminiscence utilization in half through the use of a 16 bit integer for the sport state.

Within the code above, we’ve conceived the sport state because the concatenation of 9 cell states. This can be a good concept as a result of it makes it easy to implement our core strategies. We are able to consider this as a base-4 quantity the place every cell state is a base-4 digit having values 0 (empty), 1 (cross), 2 (circle), and three (invalid). This conception exhibits up within the code too, the place we convert our base-4 index right into a base-2 index by multiplying it by 2, in order that we are able to use bitwise operations to entry the info.

The issue is that pesky invalid cell state. What if we as a substitute conceive the sport state as a base-3 quantity and a cell state as a base-3 digit? On this case we want 9 base-3 digits, which maxes out at (3^9-1) or 19,682. Representing this in binary will price us… 15 bits^!

So we are able to use a base-3 illustration to hit our 16 bit goal. However how will we implement our strategies?

The trick is to generalize our bit-twiddling to arbitrary bases. In binary, the left-shift operation x << i is equal to (x cdot 2^i), and likewise the right-shift operation x >> i is equal to (x div 2^i ). To generalize these operations from base-2 to base-n, simply substitute 2 with n. For the opposite bitwise operations, we are able to use a mixture of addition and subtraction.

The brand new code appears like this:

// The illustration of a single cell.
typedef enum cell {
    EMPTY  = 0,
    CROSS  = 1,
    CIRCLE = 2,
} cell;

// Consider the sport sate as a base-3 quantity with 9 digits.
typedef uint16_t state;

// A helper to compute pow(3, i), when 0 <= i < 9.
static int pow3(int i) {
    if (i < 0 || 9 <= i) return 1;
    static int p[] = {1, 3, 9, 27, 81, 243, 729, 2187, 6561};
    return p[i];
}

cell get_cell(state s, int i) {
    int div = pow3(i);     // Get the base-3 offset of the cell.
    return (s / div) % 3;  // "Shift" the base-3 quantity and browse the cell.
}

void set_cell(state *s, int i, cell val) {
    int div = pow3(i);         // Get the base-3 offset of the cell.
    int previous = (*s / div) % 3;  // Learn the previous worth of the cell.
    *s -= previous * div;           // Reset the cell to empty.
    *s += val * div;           // Set the cell worth.
}

Conclusion

Is that this any higher? It relies upon, however most likely not.

See Also

Month-to-month Information – October 2023 – The Linux Mint Weblog

In the event you had a really massive variety of recreation states that you simply wanted to retailer, you may pack them tightly utilizing 18 bits for the base-4 illustration or 15 bits for the base-3 illustration. That’s a financial savings of 16%, which can or is probably not price it.

And in the event you’re chosing a illustration for CPU efficiency, then the base-4 illustration wins palms down. The bottom-3 illustration has a lof of multiplication and division that may’t be simply optimized away.

However in the event you had some wild software the place you wanted to maintain trillions of recreation states unpacked in reminiscence, then positive, use base-3.

This can be a wild case of untimely optimization that no one requested for. 😅

You will discover test cases on GitHub.