Кодируем крестики-нолики в 15 битах

Недавно я наткнулся на пост Алехандры Гонсалес (@blyxyas), в котором рассказывается о попытке сжать игру крестики-нолики в минимальное количество битов. Она пришла к решению из 18 битов. Это заставило меня задуматься: а можно ли улучшить этот результат?

Как говорит Алехандра, существует 765 возможных состояний игры¹. Мы можем просто назначить число каждому состоянию, что займёт 10 битов². Но, по словам Алехандры, это «скучно». С таким описанием игры мы практически ничего не сможем сделать. Когда будет нужно считать значение из конкретной ячейки или перейти из одного состояния в другое, на практике нам придётся использовать таблицу поиска, сопоставляющую каждое число с более крупным и структурированным описанием, что делает бессмысленным саму идею сжатого описания.

18-битное решение

Алехандра придумала более умное решение, в котором каждая ячейка представлена в виде пары битов, а сетка описывается как конкатенация девяти этих битовых пар. Внутри битовой пары один бит обозначает нолик, а другой — крестик; в паре может быть задан максимум один бит.

// Описание одной ячейки.
typedef enum cell {
    EMPTY  = 0, // Binary 00
    CROSS  = 1, // Binary 01
    CIRCLE = 2, // Binary 10
} cell;

// Конкатенация 9 ячеек. Нам важны только нижние 18 битов.
typedef uint32_t state;

Базовые методы, которые нам бы хотелось использовать с нашим типом state — это получение и запись значений ячеек по заданному индексу. Их легко реализовать при помощи манипуляций с битами.

cell get_cell(state s, int i) {
    int pos = 2 * i;        // Битовое смещение ячейки i.
    return (s >> pos) % 4;  // Считывание ячейки.
}

void set_cell(state *s, int i, cell val) {
    int pos = 2 * i;    // Битовое смещение ячейки i.
    *s &= ~(3 << pos);  // Сброс старого значения.
    *s |= val << pos;   // Установка нового значения.
}

Это потрясающее, эффективное решение.

Снижаем размер при помощи троичного счисления

На практике количество битов в целом числе должно быть степенью двойки. В представленном выше коде мы использовали для хранения состояния 32-битный integer, хотя на самом деле нам нужно всего 18 битов. Если бы мы смогли сэкономить ещё два бита, то это бы снизило объём необходимой памяти вдвое и позволило использовать для хранения состояния игры 16-битный integer.

В представленном выше коде мы представили состояние игры как конкатенацию состояния девяти ячеек. Это хорошая идея, потому что она упрощает реализацию базовых методов. Мы можем воспринимать это как четверичное (по основанию 4) число, в котором состояние каждой ячейки — это четверичная цифра, имеющая значение 0 (пусто), 1 (крестик), 2 (нолик) или 3 (недопустимо). Эта концепция проявляется и в коде, когда мы преобразуем четверичный индекс в двоичный индекс, умножая его на 2, чтобы можно было использовать побитовые операции для доступа к данным.

Проблема заключается в этом неудобном состоянии ячейки «недопустимо». Что, если вместо этого представим состояние игры как троичное число, а состояние ячейки — как троичную цифру? В таком случае нам понадобится девять троичных цифр, исчерпывающиеся при значении 3⁹−1 или 19682. Для представления этого значения в двоичном виде нам понадобится… 15 битов³!

То есть мы можем использовать троичное описание, чтобы уместиться в 16 битов. Но как тогда реализовать методы?

Трюк заключается в том, чтобы обобщить наши манипуляции с битами до произвольных оснований. В двоичном счислении операция сдвига влево x << i эквивалентна x * 2ⁱ, а операция сдвига вправо x >> i эквивалентна x ÷ 2ⁱ. Чтобы обобщить эти операции с основания 2 до основания n, достаточно просто заменить 2 на n. Для других побитовых операций мы можем использовать сочетание сложения и вычитания.

Новый код выглядит так:

// Описание отдельной ячейки.
typedef enum cell {
    EMPTY  = 0,
    CROSS  = 1,
    CIRCLE = 2,
} cell;

// Представим состояние игры как троичное число с 9 цифрами.
typedef uint16_t state;

// Вспомогательная функция для вычисления pow(3, i) при 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);     // Получаем троичное смещение ячейки.
    return (s / div) % 3;  // "Сдвигаем" троичное число и считываем ячейку.
}

void set_cell(state s, int i, cell val) {
    int div = pow3(i);         // Получаем троичное смещение ячейки.
    int old = (*s / div) % 3;  // Считываем старое значение ячейки.
    *s -= old * div;           // Сбрасываем значение ячейки, делая её пустой.
    *s += val * div;           // Задаём значение ячейки.
}

Заключение

Стало ли лучше? Это зависит от условий, но, вероятно, нет.

Если бы у нас было очень большое количество игровых состояний, которое нужно хранить, то можно было бы их тесно упаковать, используя 18 битов для четверичного описания или 15 битов для троичного описания. Мы сэкономим 16%, и непонятно, стоит ли оно того.

А если выбирать описание с целью повышения производительности CPU, то четверичное описание абсолютно точно лучше. В троичном описании есть много умножений и делений, которые нелегко оптимизировать.

Но если бы у вас было какое-то безумное приложение, в котором нужно было бы хранить в памяти триллионы распакованных игровых состояний, то определённо стоит использовать троичное счисление.

Мой код — это дурацкий пример оптимизации, о которой никто не просил.

Тестовые случаи можно найти в GitHub.

1. https://www.egr.msu.edu/~kdeb/papers/k2007002.pdf

2. Строго говоря, нам нужно log₂⁡(765)≈9,58 бита, но последнюю часть бита невозможно использовать.

3. Опять же, строго говоря, нам нужно всего need log₂⁡(3⁹)≈14,26 бита.