Encoding tic-tac-toe in 15 bits

[0] TicTacToe-base3.md

Test cases for the blog post Encoding tic-tac-toe in 15 bits.

Run like this:

# Base4 test
$ cc base4.c && ./a.out

# Base3 test
$ cc base3.c && ./a.out

Try changing the typedef for state from uint32_t to uint16_t. Notice that the base4 test fails, but the base3 test continues to succeed.

[1] base4.c

#include "main.h"

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

void set_cell(state *s, int i, cell val) {
    int pos = 2 * i;    // Bit offset of cell i.
    *s &= ~(3 << pos);  // Clear the old value.
    *s |= val << pos;   // Set the new value.
}

[2] base3.c

#include "main.h"

// 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 number and read the cell.
}

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

[3] main.h

#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

typedef enum cell {
    EMPTY = 0,
    CROSS = 1,
    CIRCLE = 2,
} cell;

// Try setting this to uint16_t. The tests will fail for base4 but not base3.
typedef uint32_t state;

cell get_cell(state s, int i);
void set_cell(state *s, int i, cell val);

void test(state *s, int i, cell val) {
    state start = *s;
    set_cell(s, i, val);
    cell got = get_cell(*s, i);

    if (val != got) {
        printf("Failed:\n");
        printf("Pos:   %d\n", i);
        printf("Val:   %d\n", val);
        printf("Got:   %d\n", got);
        printf("Start: 0x%06X\n", start);
        printf("State: 0x%06X\n", *s);
        exit(1);
    }
}

int main(int argc, char *argv[]) {
    state s = 0;

    // Randomly generated test table.
    test(&s, 6, EMPTY);
    test(&s, 3, CIRCLE);
    test(&s, 1, EMPTY);
    test(&s, 5, CIRCLE);
    test(&s, 7, EMPTY);
    test(&s, 2, EMPTY);
    test(&s, 4, CIRCLE);
    test(&s, 4, CROSS);
    test(&s, 5, CIRCLE);
    test(&s, 0, CIRCLE);
    test(&s, 8, CIRCLE);
    test(&s, 5, CROSS);
    test(&s, 6, EMPTY);
    test(&s, 0, CROSS);
    test(&s, 6, CIRCLE);
    test(&s, 2, EMPTY);
    test(&s, 4, EMPTY);
    test(&s, 8, CROSS);
    test(&s, 7, CIRCLE);
    test(&s, 5, CROSS);
    test(&s, 1, CROSS);
    test(&s, 8, CIRCLE);
    test(&s, 2, CROSS);
    test(&s, 1, EMPTY);
    test(&s, 7, CIRCLE);
    test(&s, 4, CROSS);
    test(&s, 6, CIRCLE);
    test(&s, 3, CROSS);
    test(&s, 6, EMPTY);
    test(&s, 5, EMPTY);
    test(&s, 4, EMPTY);
    test(&s, 8, EMPTY);
    test(&s, 2, CIRCLE);
    test(&s, 1, EMPTY);
    test(&s, 8, CIRCLE);
    test(&s, 1, CIRCLE);
    test(&s, 7, CIRCLE);
    test(&s, 6, CROSS);
    test(&s, 3, EMPTY);
    test(&s, 3, CIRCLE);
    test(&s, 1, EMPTY);
    test(&s, 1, CIRCLE);
    test(&s, 8, EMPTY);
    test(&s, 5, EMPTY);
    test(&s, 5, EMPTY);
    test(&s, 7, CROSS);
    test(&s, 3, EMPTY);
    test(&s, 1, CROSS);
    test(&s, 4, CIRCLE);
    test(&s, 0, CIRCLE);
    test(&s, 5, CIRCLE);
    test(&s, 3, CROSS);
    test(&s, 8, EMPTY);
    test(&s, 6, CROSS);
    test(&s, 0, CROSS);
    test(&s, 7, CIRCLE);
    test(&s, 8, CIRCLE);
    test(&s, 7, CROSS);
    test(&s, 0, CROSS);
    test(&s, 1, CROSS);
    test(&s, 4, CROSS);
    test(&s, 3, EMPTY);
    test(&s, 6, EMPTY);
    test(&s, 8, CROSS);
    test(&s, 2, CROSS);
    test(&s, 3, EMPTY);
    test(&s, 4, EMPTY);
    test(&s, 6, CIRCLE);
    test(&s, 0, EMPTY);
    test(&s, 7, EMPTY);
    test(&s, 6, CROSS);
    test(&s, 4, CIRCLE);
    test(&s, 5, CROSS);
    test(&s, 6, CIRCLE);
    test(&s, 8, EMPTY);
    test(&s, 7, EMPTY);
    test(&s, 1, CIRCLE);
    test(&s, 4, CROSS);
    test(&s, 0, EMPTY);
    test(&s, 0, CROSS);
    test(&s, 8, CROSS);
    test(&s, 5, CROSS);
    test(&s, 3, CROSS);
    test(&s, 2, CIRCLE);
    test(&s, 2, CROSS);
    test(&s, 2, EMPTY);
    test(&s, 2, EMPTY);
    test(&s, 0, CIRCLE);
    test(&s, 7, EMPTY);
    test(&s, 5, EMPTY);
    test(&s, 5, CIRCLE);
    test(&s, 0, CIRCLE);
    test(&s, 8, CROSS);
    test(&s, 4, EMPTY);
    test(&s, 7, CROSS);
    test(&s, 3, CIRCLE);
    test(&s, 2, CROSS);
    test(&s, 3, CROSS);
    test(&s, 0, EMPTY);
    test(&s, 1, CROSS);
    test(&s, 2, CIRCLE);
    test(&s, 3, CIRCLE);
    test(&s, 6, CROSS);
    test(&s, 1, CIRCLE);
    test(&s, 0, EMPTY);
    test(&s, 4, CIRCLE);
    test(&s, 7, CROSS);
    test(&s, 2, CIRCLE);
}

The entire game history (all possible moves / state) from the first move to the 9th move can be encoded into 18 bits. This also allows reconstruction of the game state after every move. The trick is to use the encoding logic for video compressors, start with a keyframe and encode delta frames. In this case, a delta frame would be to determine the number of available spaces, and store the next move. The number of available spaces decrements after every move, so you need less bits. A further space optimisation can be to reuse unused bit values from subsequent moves. Eg. for the 3rd move, there are 7 available fields. This can be packed into 3 bits, with one value spare. The spare can be borrowed to move 1, which has 9 fields. This allows the following optimisation:

1st / 9 / 3 bits (-1)
2nd / 8 / 3 bits (0)
3rd / 7 / 3 bits (+1) (used to complete 1st)
4th / 6 / 3 bits (+2)
5th / 5 / 2 bits (-1) (use 4th extra)
6th / 4 / 2 bits (0)
7th / 3 / 1 bit (-1) use 4th extra
8th / 2 / 1 bit (0)
9th / 1 / 0 bits

Total = 18 bits. This is for the entire game history, from the first to last move, and every board state in between. Decoding this 18 bit mask is not really that challenging, since there are only 3 special cases, and the 9th move requires no bits to store the move (since there is only one possible move). To reconstruct the state at any given time, you need to start from the keyframe and move forward.

18 bits for entire game history.