Я бы попробовал использовать кодировку Хаффмана . Теория, лежащая в основе этого, заключается в том, что в каждой шахматной игре будут фигуры, которые будут много перемещаться, а некоторые, которые мало двигаются или рано выбрасываются. Если в стартовой позиции уже есть несколько фигур, тем лучше. То же самое касается квадратов - некоторые квадраты видят все действия, в то время как другие не сильно касаются.
Таким образом, у меня будет два стола Хаффмана - один для фигур, другой для квадратов. Они будут сгенерированы, глядя на саму игру. У меня могла бы быть одна большая таблица для каждой пары кусок-квадрат, но я думаю, что это было бы довольно неэффективно, потому что не так много экземпляров одного и того же элемента, движущихся по тому же квадрату снова.
Каждому предмету будет присвоен присвоенный идентификатор. Поскольку существует 32 разных элемента, мне понадобится всего 5 бит для идентификатора элемента. Идентификаторы фигур не меняются от игры к игре. То же самое касается квадратных идентификаторов, для которых мне потребуется 6 бит.
Деревья Хаффмана будут кодироваться путем записи каждого узла по мере его прохождения в порядке (т. Е. Сначала выводится узел, затем его дочерние элементы слева направо). Для каждого узла будет один бит, указывающий, является ли это листовым узлом или узлом ветвления. Если это листовой узел, за ним следуют биты, дающие идентификатор.
Начальная позиция будет просто задана серией пар кусочек-локация. После этого для каждого хода будет одна пара кусочек-локация. Вы можете найти конец дескриптора начальной позиции (и начало дескриптора ходов), просто найдя первый фрагмент, который упоминается дважды. В случае, если пешка получит повышение, будет 2 дополнительных бита, определяющих, чем она станет, но идентификатор фигуры не изменится.
Чтобы учесть вероятность продвижения пешки в начале игры, между деревьями Хаффмана и данными также будет «таблица продвижения». Сначала будет 4 бита, указывающих, сколько пешек модернизируется. Затем для каждой пешки будет свой код, закодированный Хаффманом, и 2 бита, указывающих, кем он стал.
Деревья Хаффмана будут генерироваться с учетом всех данных (как начальной позиции, так и ходов) и таблицы повышения. Хотя обычно таблица продвижения будет пустой или содержит всего несколько записей.
Подводя итог в графическом выражении:
<Game> := <Pieces huffman tree> <squares huffman tree> <promotion table> <initial position> (<moves> | <1 bit for next move - see Added 2 below>)
<Pieces huffman tree> := <pieces entry 1> <pieces entry 2> ... <pieces entry N>
<pieces entry> := "0" | "1" <5 bits with piece ID>
<squares huffman tree> := <squares entry 1> <squares entry 2> ... <squares entry N>
<Squares entry> := "0" | "1" <6 bits with square ID>
<promotion table> := <4 bits with count of promotions> <promotion 1> <promotion 2> ... <promotion N>
<promotion> := <huffman-encoded piece ID> <2 bits with what it becomes>
<initial position> := <position entry 1> <position entry 2> ... <position entry N>
<moves> := <position entry 1> <position entry 2> ... <position entry N>
<position entry> := <huffman-encoded piece ID> <huffman-encoded squre ID> (<2 bits specifying the upgrade - optional>)
Добавлено: Это все еще можно оптимизировать. Каждая часть имеет только несколько законных ходов. Вместо простого кодирования целевого квадрата можно указать идентификаторы на основе 0 для возможных ходов каждой фигуры. Одни и те же идентификаторы будут повторно использоваться для каждой фигуры, поэтому в общей сложности будет не более 21 разных идентификаторов (у королевы может быть не более 21 различных возможных вариантов перемещения). Поместите это в таблицу Хаффмана вместо полей.
Однако это затруднит представление исходного состояния. Можно создать серию ходов, чтобы поставить каждый кусок на свое место. В этом случае необходимо как-то отметить конец начального состояния и начало ходов.
В качестве альтернативы они могут быть размещены с использованием несжатых 6-битных квадратных идентификаторов.
Представит ли это общее уменьшение в размере - я не знаю. Возможно, но стоит немного поэкспериментировать.
Добавлено 2: Еще один особый случай. Если в игровом состоянии НЕТ ходов, становится важно различать, кто движется следующим. Добавьте еще один бит в конце для этого. :)