БлогNot. Формат .B32 - компактная запись шахматной позиции в 32 байта

Формат .B32 - компактная запись шахматной позиции в 32 байта

От нечего делать решал эту задачку в уме в междугороднем автобусе ещё 14 января. Собрался всё же записать, маловероятно, что пригодится, но мало ли…

Итак, мы хотим максимально компактно в смысле использованных бит информации записать в двоичном коде шахматную позицию, сохранив при этом данных о позиции не меньше, чем в стандартной нотации Форсайта-Эдвардса (в последней, кстати, как минимум не хватает информации о времени, затраченном к этому моменту белыми и чёрными).

Если идти от сохранения фигур вместе с координатами полей, которые они занимают, получаем следующее: для 64 полей нужно 6 бит (64 = 26 или 3 бита на горизонталь, 3 бита на вертикаль), при этом достаточно сохранять координаты полей, только занятых пешками или фигурами. Имеем по 5 различных фигур + по пешке двух цветов, всего 12 вариантов занятого поля, на что требуется 4 бита. Итого – запись об одной фигуре десятибитовая, а расстановка фигур может занимать от 20 бит при "голых королях" до 320 бит (40 байт), когда все фигуры и пешки живы. Это уже много, тем более, хотелось бы иметь формат, как-то выравненный на границы хотя бы полубайтов, а общий размер записи – как степень двойки, чтоб можно было обрабатывать запись целиком, например, в регистре специализированного процессора.

Подойдём к задаче по-другому. Информацию о 64 полях можно разместить в 32 байта, раз у поля всего по 13 состояний (включая пустое). Один байт, таким образом, будет хранить данные о двух полях доски. Ясно, что при этом незачем задавать в формате координаты полей, можно считать, что поля хранятся последовательно a8, b8, …, h8, a7, b7, … и т.д. (раз уж доска по умолчанию обычно рисуется так, что чёрные вверху). Если поля пусты (а пусто всегда не менее половины доски), хранить нули как часть формата тоже незачем, в оставшееся место хотелось бы втиснуть всю остальную информацию.

Сначала определимся с набором состояний. У нас 12 различных состояний занятости поля пешкой или фигурой одного из двух цветов, если в полубайте нет ни одного из них, значит, он используется для других целей. Попробуем удобно закодировать 4-битовыми записями пешки и фигуры.

Белые Чёрные Фигура
0001 1001 Пешка
0010 1010 Король
0100 1100 Конь
0101 1101 Слон
0110 1110 Ладья
0111 1111 Ферзь

Такой выбор не случаен. Старший бит показывает ещё и цвет фигуры (0 – белые, 1 – чёрные). 3 младших бита – это вид фигуры, кроме того, трёхбитовые числа, кодирующие вид фигуры, увеличиваются по мере возрастания силы этих фигур (двоичное 1 – пешка, 2 – король, 4 – конь, 5 – слон, 6 – ладья, 7 – ферзь).

У нас осталось 4 "особых" четырёхбитовых комбинации: 0000, 0011, 1000, 1011. Будем считать, что если полубайт, кодирующий очередное поле доски, относится к одной из этих 4 комбинаций, то его нужно рассматривать как отдельный бит дополнительной информации со значением 0 или 1 (достаточно 00 интерпретировать как 0, остальные двухбитовые комбинации как 1). 8 таких записей, последовательно "собранных" с 8 не занятых фигурами полей, образуют дополнительный байт информации. Всего таких байтов с первых 32 свободных полей (а может и не быть больше 32 свободных) мы соберём 4. Попробуем в эти жалкие байты поместить всю остальную информацию. Ясно, что порядок её считывания будет определён порядком перечисления в формате, а условные "поля", хранящие эту информацию, могут быть любыми свободными полями доски.

Итак, 4 байта = 32 бита всего.

Очередность хода: 1 бит;

Возможность короткой и длинной рокировок для белых и для чёрных: 2 бита (4 состояния);

Проходимое поле (возможность взятия на проходе): всего таких полей возможно 16, значит имеем 4 бита… но состояний-то здесь 17, ведь нужно хранить и информацию о том, что проходимого поля нет, значит, увы, нужно 5 бит;

Счётчик полуходов до 50 (число полуходов, прошедших с последнего хода пешки или взятия. Используется для определения применения правила 50 ходов): он потребует 6 бит;

Номер хода: мне сложно сказать, какое ограничение здесь нужно, попробуем 1024, тогда имеем 10 бит. Где-то видел правило насчёт максимум 1600 ходов, тогда просто используем 11 бит, а не 10.

На этом нотация Форсайта-Эдвардса исчерпана, а мы заняли пока 24 (25) бит из 32.

К сожалению, при первом расчёте в уме я ошибся в числе свободных бит, полагая уместить в них ещё и информацию о времени, затраченном обоими игроками. Оставшиеся 7 бит позволят нам хранить не более 128 различных состояний, чего не хватит даже на время, оставшееся до конца контроля. Кстати, для минутного блица нужно всего 6 бит :)

Теоретически для времени, затраченного белыми и чёрными с точностью до секунды, хватило бы по 16 бит на сторону: секунды – 6 бит, минуты – 6 бит, часы – 4 бит (15 часов на партию, думаю, достаточно). Но это лишние 32 бита, а взять их негде.

Нельзя ли как-то ужаться? Смысла хранить время в секундах нет, 5 часов – это 18000 секунд, то есть, те же 16 бит.

Не попробовать ли объединить достоинства обоих подходов? Во-первых, хранить фигуры можно тоже всегда в определённом порядке (сначала позиция чёрной ладьи a8 или пусто, затем – позиция чёрного коня b8 или пусто и т.д.). Получается, не храня кодов самих фигур, мы имеем по 6 бит на хранение горизонтали и вертикали + "пустое" состояние, когда фигуры нет… опять лишний бит. А при 7-битовых записях о полях сохранённых в определённом порядке фигур нам нужно 224 бита из имеющихся 256. Свободно опять лишь 32 бита, но мы лишились удобного формата фигур-"полубайтов".

5 бит на фигуру нам нужно лишь потому, что не хватает одного состояния из 65. А что если кроме позиции упорядоченных в формате фигур (теперь 6-битовой, так что всего нужно 192 бита) ввести поле с "масками", отдельные биты которого показывают, взята или активна фигура? Это поле потребует ещё 32 бита (по общему числу фигур), в итоге имеем те же 224 бита, перебор.

Так что, по-видимому, задача в изначальной постановке не решена и нотация будет сохранена без времени. Тем не менее, для изучающих языки программирования низкого и среднего уровня (в особенности Си с его побитовыми операциями) было бы интересным упражнением написать чтение и запись нотаций в этом формате. По сути дела, произвольные 32 байта с этой точки зрения могут быть интерпретированы как запись шахматной позиции, и двоичный мир состоит из огромного числа таких позиций, скрытых в любом тексте, в том числе и этом.

02.02.2010, 14:59 [11823 просмотра]


теги: программирование шахматы форматы

К этой статье пока нет комментариев, Ваш будет первым