English version | Русская версия

Кветка

Программа для анализа шахматных партий

Описание формата дебютных книг от Chessbase.

Это неофициальная спецификация формата CTG. Поэтому в ней многие детали реализации остались неясными. Также в последующих версиях Chessbase этот формат может измениться.

Общая структура

Каждая дебютная книга от Chessbase состоит из четырёх файлов:

.INI файл --- содержит некоторую вспомогательную информацию. Представляет из себя обычный текстовый файл и по большей части все его записи говорят сами за себя. Здесь мы его описывать не будем.
.CTG файл --- основной файл книги. Все данные из неё хранятся здесь.
.CTB файл --- назначение этого файла в основном неизвестно. Есть предположение, что в нём хранится что-то вроде битовой карты свободных страниц в CTG файле. (что бы это ни значило). Мы коснёмся этого файла очень кратко.
.CTO файл --- содержит своего рода таблицу индексов для быстрого поиска в CTG файле. Формат этого файла известен очень поверхностно.

Все целочисленные данные, если не оговорено обратное, записаны в формате big-endian (от старшего бита к младшему). Они могут иметь длину в 2, 3 и 4 байта.

Если записывается длина какого-либо блока данных, то в неё включаются сами эти байты с длиной.

Файл CTG

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

Заглавная страница

Первая страница является заглавной и содержит общую информацию обо всей книге:

Смещение 28, длина 4 б --- общее число партий, на основе которых составлена дебютная книга. В первых 32-х байтах хранится также и какая-то другая информация, назначение которой неизвестно.
Смещение 1024, длина 32 б --- хранятся неизвестные данные.
Смещение 2048, длина 32 б --- хранятся неизвестные данные.

Остальные байты в заголовочном файле не используются.

Страницы с данными

Все остальные страницы после заглавной хранят шахматные позиции. Первой странице с данными (начинающейся со смещения 4096) присваивается нулевой номер, следующей странице - первый и т.д. Номера страниц используются в CTO файле.

Каждая страница хранит данные об одной или нескольких позициях в случайном порядке. Не до конца понятно, каким образом Chessbase решает, какую позицию в какую страницу сохранять. Скорее всего, сортировка позиций идёт по их хэш значениям.

Каждая страница начинается с небольшого заголовка.

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

Со смещения 4 начинают идти записи позиций. Они следуют непосредственно одна за другой без промежутков до конца страницы (то есть до конца полезной информации на странице).

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

Кодирование позиции

Для каждой позиции кодируется информация о расположении фигур на доске, о возможных рокировках и взятии на проходе.

Подготовка доски

Каждая позиция сохраняется в таком виде, как если бы сейчас был ход белых. Если на самом деле в позиции должен быть ход чёрных, то необходимо предварительно инвертировать цвета фигур и симметрично отразить доску по вертикали (то есть, a1 < - > a8, a2 < - > a7 и т.д.). Информацию о возможных рокировках чёрного и белого королей тоже необходимо поменять местами.

Далее с позицией необходимо провести ещё одно преобразование. Если ни один из игроков больше не может сделать рокировку (сдвинулись либо король, либо ладьи) и белый король расположен в левой части доски (столбцы 1 - 4), то необходимо симметрично отобразить доску по вертикали (то есть, a1 < - > h1, a2 < - > h2 и т.д.) При этом информацию о продвижении пешки тоже нужно соответствующим образом поменять.

Вследствие симметричности доски, исходная и конечная позиции будут идентичными с точки зрения выигрышности.

Кодирование

Каждая запись начинается с заголовочного байта позиции:

Первые 5 бит (& 0x1f) описывают длину позиции вместе с заголовочным байтом (только шахматной позиции, не всей записи).
Если установлен 6-й бит (& 0x20), то позиция содержит информацию о возможном взятии на проходе. Здесь необходимо проверить выполнение двух условий. Во-первых, на предыдущем ходе соперник должен был продвинуть пешку на две клетки вперёд. Во-вторых, на соседней от продвинувшейся пешки клетке слева или справа должна стоять пешка соперника, теоретически способная к взятию на проходе. Если хотя бы одно из условий не выполнено, то позиция не будет содержать информации о взятии на проходе.
Примечание. Не имеет значения, будет ли взятие на проходе легальным (например, если после такого взятия открывается шах королю). При выполнении вышеуказанных условий 6-й бит будет установлен.
Если установлен 7-й бит (& 0x40), то в позиции хранится информация о возможных рокировках. В противном случае рокировки в позиции невозможны ни с чьей стороны.
8-й бит не используется.

Сразу после заголовочного байта следует информация о позиции. Она кодируется с использованием кодов Хаффмана, а потому вся информация представлена потоком битов. Упорядочены они стандартным образом: 1-й бит потока - это старший бит 1-го байта, за младшим битом байта следует старший бит следующего байта. Все лишние биты (если таковые останутся) должны быть равны нулю.

Все клетки доски кодируются в следующем порядке:

	a1, a2, ..., a8, b1, ..., b8, ..., h8.

Каждая клетка кодируется следующим образом:

0 - Пустая клетка
11c - пешка (c = 1 означает чёрную пешку, c = 0 - белую).
1011c - ладья.
1010c - слон.
1001c - конь.
10001c - ферзь.
10000c - король.

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

В противном случае, определим сначала параметр N, который будет зависеть от возможности хотя бы одной рокировки (С=1, в противном случае С=0) и от возможности взятия на проходе (E=1, в противном случае E=0):

E=0, C=0: N=8

E=0, C=1: N=4

E=1, C=0: N=3

E=1, C=1: N=7

Теперь правило такое: если до конца байта осталось меньше N бит, то добавляем в поток столько нулевых бит, пока это условие не выполнится.

Кодирование продвижения пешки

Теперь, если возможно взятие на проходе, то информация о нём кодируется в следующих трёх битах. В них записывается номер столбца, на который произойдёт взятие на проходе: 000=a, 001=b, 010=c, 011=d, 100=e, 101=f, 110=g, 111=h.

Далее, если возможны рокировки, то информация о них кодируется в следующих четырёх битах. Порядок кодирования такой: сначала кодируется возможность короткой рокировки чёрных (1 - рокировка возможна, 0 - нет), затем возможность длинной рокировки чёрных, короткой рокировки белых и длинной рокировки белых.

С этого момента кодирование позиции заканчивается. Как было сказано раньше, это должно произойти ровно в конце байта.

Продолжения из книги

Сразу после описания позиции хранится список ходов из неё. Предваряет их заголовочный байт, в котором хранится число байт, требующееся на все ходы (включая сам этот байт). Каждый ход кодируется двумя байтами, так что значение заголовочного байта всегда равно (2 * <число ходов>)+1.

Первый байт каждого хода содержит описание самого хода, а второй - аннотацию к нему.

Описание хода задаётся фигурой и её относительном перемещением. Фигура характеризуется её видом и порядковым номером (например, 2-й конь, 1-й слон, 4-я пешка). Для определения номера фигуры производится поиск на доске белой фигуры соответствующего вида в том же порядке, что и кодирование доски (a1, ..., a8, ..., h8). Например, в начальной позиции конь на b1 будет записываться как "1-й конь", а конь на g1 - как "2-й конь".

Относительное перемещение будет записываться двумя координатами. Они означают, на сколько клеток вправо и вверх перемещается фигура. При этом у доски верхняя и нижняя, а также правая и левая границы "склеены". То есть, перемещение фигуры на 7 клеток вправо означает то же самое, что и перемещение на одну клетку влево.

Определение хода по его коду производится с помощью следующей таблицы:

0xEC: 1-я пешка, y+1
0xDB: 1-я пешка, y+2
0x8B: 1-я пешка, x+1, y+1
0x0C: 1-я пешка, x+7, y+1
0x04: 2-я пешка, y+1
0x62: 2-я пешка, y+2
0x96: 2-я пешка, x+1, y+1
0xD1: 2-я пешка, x+7, y+1
0x55: 3-я пешка, y+1
0x9B: 3-я пешка, y+2
0x7C: 3-я пешка, x+1, y+1
0x27: 3-я пешка, x+7, y+1
0xCF: 4-я пешка, y+1
0xE6: 4-я пешка, y+2
0xEB: 4-я пешка, x+1, y+1
0x06: 4-я пешка, x+7, y+1
0xBB: 5-я пешка, y+1
0x5F: 5-я пешка, y+2
0x00: 5-я пешка, x+1, y+1
0xDE: 5-я пешка, x+7, y+1
0xCB: 6-я пешка, y+1
0xB1: 6-я пешка, y+2
0x2D: 6-я пешка, x+1, y+1
0x82: 6-я пешка, x+7, y+1
0x18: 7-я пешка, y+1
0xC8: 7-я пешка, y+2
0x5C: 7-я пешка, x+1, y+1
0xC7: 7-я пешка, x+7, y+1
0xA3: 8-я пешка, y+1
0x4A: 8-я пешка, y+2
0x14: 8-я пешка, x+1, y+1
0x24: 8-я пешка, x+7, y+1

0x34: 1-й конь, x+1, y+2
0x85: 1-й конь, x+7, y+2
0x36: 1-й конь, x+2, y+1
0xF7: 1-й конь, x+6, y+1
0xE9: 1-й конь, x+2, y+7
0x0F: 1-й конь, x+6, y+7
0x8A: 1-й конь, x+1, y+6
0xDA: 1-й конь, x+7, y+6
0x4C: 2-й конь, x+1, y+2
0xF3: 2-й конь, x+7, y+2
0xD2: 2-й конь, x+2, y+1
0xD3: 2-й конь, x+6, y+1
0xE0: 2-й конь, x+2, y+7
0x01: 2-й конь, x+6, y+7
0x2A: 2-й конь, x+1, y+6
0x30: 2-й конь, x+7, y+6

0x2E: 1-й слон, x+1, y+1
0xC1: 1-й слон, x+2, y+2
0x0D: 1-й слон, x+3, y+3
0x6A: 1-й слон, x+4, y+4
0x15: 1-й слон, x+5, y+5
0x3A: 1-й слон, x+6, y+6
0x12: 1-й слон, x+7, y+7
0x1B: 1-й слон, x+7, y+1
0xC3: 1-й слон, x+6, y+2
0x66: 1-й слон, x+5, y+3
0x3C: 1-й слон, x+3, y+5
0xB2: 1-й слон, x+2, y+6
0x26: 1-й слон, x+1, y+7
0xF5: 2-й слон, x+1, y+1
0xC2: 2-й слон, x+2, y+2
0xB9: 2-й слон, x+3, y+3
0x9F: 2-й слон, x+4, y+4
0x32: 2-й слон, x+5, y+5
0x09: 2-й слон, x+6, y+6
0x1D: 2-й слон, x+7, y+7
0x54: 2-й слон, x+7, y+1
0x22: 2-й слон, x+6, y+2
0xCA: 2-й слон, x+5, y+3
0xCC: 2-й слон, x+3, y+5
0x79: 2-й слон, x+2, y+6
0x72: 2-й слон, x+1, y+7

0x81: 1-я ладья, y+1
0xE8: 1-я ладья, y+2
0x7A: 1-я ладья, y+3
0x99: 1-я ладья, y+4
0x87: 1-я ладья, y+5
0x50: 1-я ладья, y+6
0xE1: 1-я ладья, y+7
0x7F: 1-я ладья, x+1
0xCD: 1-я ладья, x+2
0x98: 1-я ладья, x+3
0xEF: 1-я ладья, x+4
0x6E: 1-я ладья, x+5
0x52: 1-я ладья, x+6
0x86: 1-я ладья, x+7
0x7D: 2-я ладья, y+1
0xF4: 2-я ладья, y+2
0xE3: 2-я ладья, y+3
0xC5: 2-я ладья, y+4
0xA5: 2-я ладья, y+5
0x7B: 2-я ладья, y+6
0x69: 2-я ладья, y+7
0xC4: 2-я ладья, x+1
0xA9: 2-я ладья, x+2
0x0E: 2-я ладья, x+3
0xAD: 2-я ладья, x+4
0xB5: 2-я ладья, x+5
0xD8: 2-я ладья, x+6
0x21: 2-я ладья, x+7

0x05: 1-й ферзь, y+1
0x9D: 1-й ферзь, y+2
0x94: 1-й ферзь, y+3
0x37: 1-й ферзь, y+4
0xB7: 1-й ферзь, y+5
0x9A: 1-й ферзь, y+6
0xFD: 1-й ферзь, y+7
0x2F: 1-й ферзь, x+1
0x74: 1-й ферзь, x+2
0x31: 1-й ферзь, x+3
0xE5: 1-й ферзь, x+4
0x39: 1-й ферзь, x+5
0x29: 1-й ферзь, x+6
0x8F: 1-й ферзь, x+7
0xF1: 1-й ферзь, x+1, y+1
0xA2: 1-й ферзь, x+2, y+2
0x45: 1-й ферзь, x+3, y+3
0xE7: 1-й ферзь, x+4, y+4
0x28: 1-й ферзь, x+5, y+5
0x61: 1-й ферзь, x+6, y+6
0xED: 1-й ферзь, x+7, y+7
0xD7: 1-й ферзь, x+7, y+1
0xD9: 1-й ферзь, x+6, y+2
0x7E: 1-й ферзь, x+5, y+3
0x4B: 1-й ферзь, x+3, y+5
0x80: 1-й ферзь, x+2, y+6
0x42: 1-й ферзь, x+1, y+7
0x4D: 2-й ферзь, y+1
0xBD: 2-й ферзь, y+2
0xA0: 2-й ферзь, y+3
0xB0: 2-й ферзь, y+4
0xC6: 2-й ферзь, y+5
0x1A: 2-й ферзь, y+6 (возможно, его надо поменять на 0xF9, тут в первоисточнике опечатка.)
0xC9: 2-й ферзь, y+7
0xF8: 2-й ферзь, x+1
0x03: 2-й ферзь, x+2
0xFA: 2-й ферзь, x+3
0x08: 2-й ферзь, x+4
0xBC: 2-й ферзь, x+5
0xF9: 2-й ферзь, x+6 (Возможно, его надо поменять на 0x1A, тут в первоисточнике опечатка.)
0xF0: 2-й ферзь, x+7
0x92: 2-й ферзь, x+1, y+1
0xFB: 2-й ферзь, x+2, y+2
0xAE: 2-й ферзь, x+3, y+3
0x38: 2-й ферзь, x+4, y+4
0x41: 2-й ферзь, x+5, y+5
0x23: 2-й ферзь, x+6, y+6
0x6F: 2-й ферзь, x+7, y+7
0xEE: 2-й ферзь, x+7, y+1
0x8E: 2-й ферзь, x+6, y+2
0xFE: 2-й ферзь, x+5, y+3
0x3B: 2-й ферзь, x+3, y+5
0xAB: 2-й ферзь, x+2, y+6
0x63: 2-й ферзь, x+1, y+7

0x13: король, y+1
0x67: король, x+1, y+1
0xDF: король, x+7, y+1
0xBE: король, x+1
0x97: король, x+7
0x0A: король, y+7
0x44: король, x+1, y+7
0x8C: король, x+7, y+7
0x6B: король, O-O
0xF6: король, O-O-O.

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

Возможные значения для байта аннотации:


0x00: аннотация отсутствует
0x01: !
0x02: ?
0x03: !!
0x04: ??
0x05: !?
0x06: ?!
0x08: единственный ход
0x16: цугцванг

Большинство других аннотаций связаны с позицией, а не ходом. Они кодируются в соответствующем разделе.

Статистика

После кодирования всех ходов записывается статистика данной позиции:

Смещение 0, длина 3 б --- число всех партий, в которых встретилась эта позиция.
Смещение 3, длина 3 б --- число партий, в которых выиграли белые. Напомним, что все позиции рассматриваются с точки зрения, что сейчас ходят белые. Поэтому, если в реальности ходят чёрные, то это будет число проигрышных партий для белых.
Смещение 6, длина 3 б --- число партий, в которых выиграли чёрные.
Смещение 9, длина 3 б --- число ничейных партий.

После статистики хранится 4-х байтовое число неизвестного назначения. Оно практически всегда равно нулю, однако временами принимает другие маленькие значения.

Рейтинг

Далее хранится информация о рейтинге позиции. На каждую позицию приходится по два рейтинга:

Смещение 0, длина 3 б --- число партий для 1-го рейтинга.
Смещение 3, длина 4 б --- сумма рейтингов по каждой из партий для 1-го рейтинга.
Смещение 7, длина 3 б --- число партий для 2-го рейтинга.
Смещение 10, длина 4 б --- сумма рейтингов по каждой из партий для 2-го рейтинга.

В Chessbase значение performance rating вычисляется на основании этих значений и статистики позиции.

Комментарий к позиции

Далее записывается один байт, в котором хранится комментарий к текущей позиции. Возможные значения:


0x00: комментарий отсутствует
0x0B: =
0x0D: позиция неясна
0x0E: =+
0x0F: +=
0x10: -/+
0x11: +/-
0x13: +-
0x20: развитие преимущества
0x24: с инициативой
0x28: с атакой
0x2C: с компенсацией
0x84: контригра
0x8A: цейтнот
0x92: новинка

После комментария в записи страницы хранится ещё несколько байт неизвестного назначения.

Файл CTB

По большей части его формат неизвестен. Похоже, что он хранит некое битовое поле по страницам CTG файла. Однако два значения в этом файле известны, и для нас они имеют особый интерес:

Смещение 4, длина 4 б --- нижняя граница хранения данных (lower_bound)
Смещение 8, длина 4 б --- верхняя граница хранения данных (upper_bound)

Их назначение будет разъяснено в следующем разделе про CTO файл.

Файл CTO

Этот файл по сравнению с файлом CTG не настолько хорошо понятен. Некоторые приведенные здесь утверждения находятся на уровне предположений и могут оказаться неверными.

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

В начале файла записаны 16 заголовочных байт. Их формат:

Смещение 4, длина 4 б --- число записей в CTO файле. (Утверждается, что это число не может быть степенью двойки и простым числом.)
Назначение остальных байт неизвестно.

Далее хранятся сами записи, по 4 байта на запись.

При поиске позиции, сначала вычисляется её хэш значение, и затем оно уменьшается в соответствии с числом записей в этом файле. Далее на основании полученного значения ищется запись в CTO файле. Хранящееся в записи число - это номер страницы в CTG файле, на которой следует искать заданную позицию. Если в партии позиции не оказывается, то значит, в книге её нет. Значение записи 0xffffffff означает, что в книге нет ни одной позиции с таким (уменьшенным) хэшем. На одну и ту же страницу может указывать более одного хэша.

Вычисление хэш значения позиции

Здесь приводится код для вычисления 32-биттного хэша от заданной позиции. На вход gen_hash подаётся массив байт, закодированных из позиции по аналогичным правилам, как в CTG файле. В len подаётся длина полученного кода.


  unsigned int tbl[] = {
          0x3100d2bf, 0x3118e3de, 0x34ab1372, 0x2807a847,
          0x1633f566, 0x2143b359, 0x26d56488, 0x3b9e6f59,
          0x37755656, 0x3089ca7b, 0x18e92d85, 0x0cd0e9d8,
          0x1a9e3b54, 0x3eaa902f, 0x0d9bfaae, 0x2f32b45b,
          0x31ed6102, 0x3d3c8398, 0x146660e3, 0x0f8d4b76,
          0x02c77a5f, 0x146c8799, 0x1c47f51f, 0x249f8f36,
          0x24772043, 0x1fbc1e4d, 0x1e86b3fa, 0x37df36a6,
          0x16ed30e4, 0x02c3148e, 0x216e5929, 0x0636b34e,
          0x317f9f56, 0x15f09d70, 0x131026fb, 0x38c784b1,
          0x29ac3305, 0x2b485dc5, 0x3c049ddc, 0x35a9fbcd,
          0x31d5373b, 0x2b246799, 0x0a2923d3, 0x08a96e9d,
          0x30031a9f, 0x08f525b5, 0x33611c06, 0x2409db98,
          0x0ca4feb2, 0x1000b71e, 0x30566e32, 0x39447d31,
          0x194e3752, 0x08233a95, 0x0f38fe36, 0x29c7cd57,
          0x0f7b3a39, 0x328e8a16, 0x1e7d1388, 0x0fba78f5,
          0x274c7e7c, 0x1e8be65c, 0x2fa0b0bb, 0x1eb6c371
  };

  unsigned int gen_hash(signed char *ptr, unsigned len)
  {
          signed hash = 0;
          short tmp = 0;
          int i;

          for (i = 0; i < len; ++i) {
                  signed char ch = *ptr++;
                  tmp += ((0x0f - (ch & 0x0f)) << 2) + 1;
                  hash += tbl[tmp & 0x3f];
                  tmp += ((0xf0 - (ch & 0xf0)) >> 2) + 1;
                  hash += tbl[tmp & 0x3f];
          }
          return hash;
  }

Осторожно, приведенный здесь код будет некорректно работать на 64-биттных системах, так как он использует 32-биттное переполнение при сложении переменной hash.

Уменьшение хэш значения

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


  for (int n = 0; n < 0x7fffffff; n = 2*n + 1) {
        unsigned c = (hash & n) + n;

        if (c < lower_bound)
                continue;

        search_page(c);

        if (c >= upper_bound)
                break;
  }

Здесь переменные lower_bound и upper_bound - это те самые значения из CTB файла. Функция search_page() читает запись в CTO файле под соответствующим номером и далее на полученной странице ищет данную позицию.

Сам Chessbase, по всей видимости, производит поиск позиции каким-то более эффективным способом. Однако если вы не хотите самостоятельно создавать дебютные книги в формате CTG, то приведенный алгоритм вполне должен вас устроить.

Текст написан на основе описания формата CTG дебютных книг.
Автор перевода --- Бодягин Дмитрий

info@kvetka.org