Головоломка программиста: кодирование состояния шахматной доски на протяжении всей игры

Question

Не совсем вопрос, скорее загадка ...

На протяжении многих лет я участвовал в нескольких технических интервью с новыми сотрудниками. Кроме того, что я задавал стандартные вопросы «Знаете ли вы X технологии», я также пытался понять, как они решают проблемы. Обычно я отправляю им вопрос по электронной почте за день до собеседования и ожидаю, что они примут решение к следующему дню.

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

Так что я решил написать один из своих вопросов для аудитории Stack Overflow.

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

Код не требуется для ответа, просто описание алгоритма, который вы бы использовали.

РЕДАКТИРОВАТЬ: Как указал один из плакатов, я не учел временной интервал между ходами. Не стесняйтесь учитывать это также в качестве дополнительной опции:)

EDIT2: просто для дополнительного пояснения ... Помните, кодер / декодер осведомлен о правилах. Единственные вещи, которые действительно должны быть сохранены, - это выбор игрока - предполагается, что кодировщик / декодер может знать все остальное.

РЕДАКТИРОВАТЬ3: Будет трудно выбрать победителя здесь :) Много хороших ответов!

Answer 1

Так я бы кодировал игровые шаги. Для игры с 40 шагами это займет около 180 бит или около того.

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

1. Перечислите все фигуры, которые можно переместить (в начале белые могут переместить 8 пешек и 2 коня, всего 10.
2. Сохраните как количество возможных вариантов, так и сам выбор.
3. Перечислите все возможные позиции движения. (когда пешка была выбрана в начале, вы можете переместиться на 1 или 2 поля вперед, поэтому у вас есть 2 возможных варианта.
4. Опять сохраните количество возможных вариантов и сам выбор.

Это даст вам такой список:

[[10, 3], # choose white pawn at index #3
 [2, 0],  # move it one step forward
 [10, 2], # choose black pawn #2 
 [2, 1],  # move it two steps forward
 ...
]

И так далее. Чтобы его закодировать, вам просто нужно сохранить выбор, а не количество возможных ходов. Один из способов сохранить это - узнать, сколько битов требуется для каждого выбора:

[[10, 3], # 10 choices => 4 bits
 [2, 0],  # 2 choices => 1 bit
 [10, 2], # 10 choices => 4 bits
 [2, 1],  # 2 choices => 1 bit
 ...
]

Итого 4+1+4+1=10 бит за первые два хода. Но несколько битов потрачены впустую, используя 4 бита для 10 вариантов выбора. Потери 6 возможных вариантов.

Можно сделать лучше: перевернуть список и рассчитать число на основе возможных вариантов и сделанного выбора:

n = 0         # last position
n = n*2 + 1   # from [2, 1]   n=1
n = n*10 + 2  # from [10, 2]  n=12
n = n*2 + 0   # from [2, 0]   n=24
n = n*10 + 3  # from [10, 3]  n=243

Теперь у нас есть число 243, двоичное 11110011, которое кодирует все вышеперечисленные шаги всего в 8 битах.

Для декодирования мы знаем, что начальная позиция открытия имеет 10 возможных вариантов. Подсчитайте

n = 243
choice = n % 10  # we know there are 10 moveable pieces. => choice=3
n /= 10          # n=24
choice = n % 2   # we know 2 possible moves for selected pawn => choice=0
n /= 2           # n=12
choice = n % 10  # 10 moveable pieces for black player. => choice=2
n /= 10          # n=1
choice = n % 2   # 2 possible moves for pawn => choice=1
n /= 2           # n=0, finished decoding

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

Answer 2

В базовом случае начальной доски плюс последующие ходы рассмотрим следующее.

Используйте шахматную программу, чтобы назначить вероятности для всех возможных ходов. Например, 40% для e2-e4, 20% для d2-d4 и так далее. Если некоторые ходы законны, но не учитываются этой программой, дайте им небольшую вероятность. Используйте арифметическое кодирование, чтобы сохранить выбранный выбор, который будет некоторым числом от 0 до 0,4 для первого хода, от 0,4 до 0,6 для второго и т. Д.

Сделайте то же самое для другой стороны. Например, если существует вероятность 50% для e7-e5 в качестве ответа на e2-e4, то закодированное число будет между 0 и 0,2. Повторяйте, пока игра не закончится. Результатом является потенциально очень маленький диапазон. Найдите бинарную дробь с наименьшим основанием, которое соответствует этому диапазону. Это арифметическое кодирование.

Это лучше, чем Хаффман, потому что его можно рассматривать как дробное битовое кодирование (плюс некоторые в конце игры для округления до целого бита).

Результат должен быть более компактным, чем у Хаффмана, и не существует особых случаев для повышения по службе, en passant, хода 50 правил и других деталей, поскольку они обрабатываются программой оценки шахмат.

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

Если ваша шахматная программа достаточно хороша, вы можете получить лучшее сжатие с помощью кодера с двумя состояниями, где вероятности определяются на основе ходов как для черного, так и для белого. В самом крайнем случае из примерно 200+ состояний это кодирует весь набор всех возможных шахматных игр и поэтому неосуществимо.

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

Answer 3

Каждая фигура может быть представлена ​​4 битами (пешка к королю, 6 типов), черный / белый = 12 значений

Каждый квадрат на доске может быть представлен 6 битами (координаты х, координаты у).

Начальные позиции требуют максимум 320 бит (32 штуки, 4 + 6 бит)

Каждое последующее движение может быть представлено 16 битами (из позиции в позицию, часть).

Рокировка потребует дополнительных 16 битов, поскольку это двойной ход.

Королевские пешки могут быть представлены одним из 4-х резервных значений из 4 битов.

Если не выполнять подробные математические расчеты, это начинает экономить место после первого хода по сравнению с сохранением 32 * 7 битов (предопределенный массив элементов) или 64 * 4 битов (предопределенное назначение квадратов)

После 10 ходов с обеих сторон максимальное требуемое пространство составляет 640 бит

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

Исходные позиции = максимум 384 бита (32 штуки, 6 + 6 бит) Каждый ход = 12 бит (в позицию, идентификатор части)

Затем после 10 ходов на каждой стороне максимальное требуемое пространство составляет 624 бита

Answer 4

Сохранение состояния платы

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

Далее представьте каждую шахматную фигуру в порядке ее расположения. Используя 4 бита на штуку, это занимает 32 * 4 бита (всего 128). Что действительно очень расточительно.

Используя бинарное дерево, мы можем представить пешку в одном байте, рыцаря и ладью и слона в 3 и короля и королеву в 4. Поскольку нам также нужно сохранить цвет фигуры, который занимает дополнительный байт в конечном итоге это выглядит так (извините, если это не так, я никогда раньше не рассматривал кодирование Хаффмана в деталях):

• Пешка: 2
• Ладья: 4
• Рыцарь: 4
• Епископ: 4
• Король: 5
• Королева: 5

С учетом итогов:

2*16 + 4*4 + 4*4 + 4*4 + 2*5 + 2*5 = 100

Что бьет, используя набор битов фиксированного размера на 28 бит.

Итак, лучший метод, который я нашел, это сохранить его в массиве 8 ² + 100 бит

8*8 + 100 = 164

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

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

Так что для каждого нормального хода у нас есть необходимые 1 + 5 = 6 биты. (1 битный тип, 5 бит на штуку)

После того, как номер фигуры был декодирован, мы затем узнаем тип фигуры, и каждая фигура должна представлять свой ход наиболее эффективным способом. Например, (если мои шахматные правила до нуля), пешка имеет в общей сложности 4 возможных хода (сделать левый, правый, один шаг вперед, два вперед).
Таким образом, чтобы представить ход пешки, нам нужно 6 + 2 = 8 битов. (6 бит для начального заголовка перемещения, 2 бита для какого перемещения)

Перемещение для королевы было бы более сложным, так как было бы лучше иметь направление (8 возможных направлений, таким образом, 3 бита) и в общей сложности 8 возможных квадратов для перемещения в каждом направлении (таким образом, еще 3 бита) , Таким образом, чтобы представить перемещение королевы, потребуется 6 + 3 + 3 = 12 битов.

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

Результирующий формат
Таким образом, формат файла будет выглядеть примерно так

[64 бита] Местоположения начальных частей
[100 бит максимум] Начальные части [1 бит] Ход игрока
[n бит] ходов

Где ход
[1 бит] Тип перемещения (специальный или обычный)
[n бит] Переместить деталь

Если Движение - это нормальное движение, Детализация Движения выглядит примерно так:
[5 бит] шт
[n битов] конкретная часть движения (обычно в диапазоне от 2 до 6 битов)

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

Answer 5

Алгоритм должен детерминистически перечислять все возможные пункты назначения при каждом движении. Количество пунктов назначения:

• 2 епископа, 13 направлений каждый = 26
• 2 ладьи, 14 пунктов назначения каждый = 28
• 2 рыцаря, 8 направлений каждый = 16
• королева, 27 направлений
• король, 8 направлений

8 лап могут стать королевами в худшем (с учетом перечисления) случае, что делает наибольшее количество возможных направлений 9 * 27 + 26 + 28 + 16 + 8 = 321. Таким образом, все пункты назначения для любого перемещения могут быть перечислены 9-разрядным числом.

Максимальное количество ходов обеих сторон составляет 100 (если я не ошибаюсь, не шахматист). Таким образом, любая игра может быть записана в 900 битах. Плюс начальная позиция каждого куска может быть записана с использованием 6-битных чисел, что составляет 32 * 6 = 192 бит Плюс один бит для записи «кто двигается первым». Таким образом, любая игра может быть записана с использованием 900 + 192 + 1 = 1093 бита.

Answer 6

Доска имеет 64 квадрата и может быть представлена ​​64 битами, показывающими, является ли квадрат пустым или нет. Нам нужна только информация о фигуре, если у квадрата есть фигура. Поскольку игрок + фигура занимает 4 бита (как показано ранее), мы можем получить текущее состояние в 64 + 4 * 32 = 192 бита. Добавьте текущий ход, и у вас будет 193 бита.

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

Пешка: Вперед, первый ход два вперед, en passant * 2, повышение = 7 бит. Вы можете объединить первый поворот вперед и повышение в один бит, поскольку они не могут происходить с одной и той же позиции, поэтому у вас есть 6. Ладья: 7 вертикальных квадратов, 7 горизонтальных квадратов = 14 бит Рыцарь: 8 квадратов = 8 бит Епископ: 2 диагонали * 7 = 14 бит Королева: 7 вертикальных, 7 горизонтальных, 7 диагональных, 7 диагональных = 28 бит Король: 8 окружающих квадратов

Это по-прежнему означает, что вам необходимо отобразить целевые квадраты на основе текущей позиции, но это (должно быть) простой расчет.

Так как у нас 16 пешек, 4 ладьи / рыцари / слоны и 2 королевы / короли, это 16 * 6 + 4 * 14 + 4 * 8 + 4 * 14 + 2 * 28 + 2 * 8 = еще 312 бит, доводя общее количество до 505 бит.

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

Короче говоря: храните дополнительные данные (фигуры и т. Д.) Только в том случае, если квадрат занят, и храните только минимальное количество битов для каждой фигуры, чтобы представить его законные ходы.

РЕДАКТИРОВАТЬ1: Забыл про продвижение рокировки и пешки на любую фигуру. Это может привести к сумме с явными позициями до 557 ходов (еще 3 бита для пешек, 2 для королей)

Answer 7

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

Таким образом, мы получаем 164 бита для фигур, 4 бита для информации о замке (при условии, что мы храним фрагмент игры, в противном случае его можно восстановить), 3 бита для полной информации о праве на участие - просто сохраните столбец, в котором произошло перемещение (если en passant невозможно, сохраните столбец там, где это невозможно - такие столбцы должны существовать) и 1 для того, кто должен перемещаться.

Ходы обычно занимают 5 или 6 битов, но могут варьироваться от 1 до 8.

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

Answer 8

На доске 32 фигуры. У каждой фигуры есть позиция (одна на 64 квадрата). Так что вам просто нужно 32 натуральных числа.

Я знаю, что 64 позиции сохраняются в 6 битах, но я бы не стал этого делать. Я бы оставил последние биты для нескольких флагов (выпавший кусок, пешка ферзя)

Answer 9

Как уже упоминали несколько других, вы могли бы для каждого из 32 предметов, которые вы могли бы хранить, на каком квадрате они находятся, и если они на доске или нет, это дает 32 * (log2 (64) + 1) = 224 бит.

Однако епископы могут занимать только черные или белые квадраты, поэтому для них вам нужно всего лишь log2 (32) бита для позиции, что дает 28 * 7 + 4 * 6 = 220 бит.

И поскольку пешки не начинаются сзади и могут двигаться только вперед, они могут быть только на 56, поэтому можно использовать это ограничение для уменьшения количества битов, необходимых для пешек.

Answer 10

Как и Роберт Дж, я бы предпочел использовать PGN, поскольку он является стандартным и может использоваться широким спектром инструментов.

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

ходы не должны записывать состояние; декодер может отслеживать состояние, а также то, какие шаги допустимы в любой заданный момент. Все ходы, которые необходимо зафиксировать, - это то, какая из различных правовых альтернатив выбрана. Поскольку игроки чередуются, ход не должен записывать цвет игрока. Поскольку игрок может перемещать только свои цветные фигуры, первым выбором является то, какую фигуру игрок перемещает (я вернусь к альтернативе, которая использует другой выбор позже). Максимум 16 штук требует максимум 4 бита. Когда игрок теряет фигуры, количество вариантов уменьшается. Кроме того, конкретное игровое состояние может ограничивать выбор фигур. Если король не может двигаться, не ставя себя под контроль, количество вариантов уменьшается на один. Если король находится под контролем, любая фигура, которая не может вытащить короля, не является жизнеспособным выбором. Пронумеруйте фигуры в главном порядке строк, начиная с a1 (h1 следует перед a2).

Как только часть указана, у нее будет только определенное количество легальных мест назначения. Точное число сильно зависит от макета доски и истории игры, но мы можем определить некоторые максимальные и ожидаемые значения. Для всех, кроме рыцаря и во время рокировки, часть не может пройти через другую часть. Это будет большой источник ограничений хода, но его трудно определить количественно. Часть не может сдвинуться с доски, что также в значительной степени ограничит количество пунктов назначения.

Мы кодируем место назначения большинства фигур путем нумерации квадратов вдоль линий в следующем порядке: W, NW, N, NE (черная сторона - N). Линия начинается в самом дальнем в данном направлении квадрате, по которому можно двигаться, и продолжается в направлении. Для необремененного короля список ходов - W, E, NW, SE, N, S, NE, SW. Для рыцаря мы начнем с 2W1N и продолжим по часовой стрелке; пункт назначения 0 является первым действительным пунктом назначения в этом порядке.

• Пешки: у неподвижной пешки есть 2 варианта назначения, поэтому требуется 1 бит. Если пешка может захватить другую, либо обычную, либо пассивную (которую декодер может определить, так как она отслеживает состояние), она также имеет 2 или 3 варианта ходов. Кроме этого, у пешки может быть только 1 выбор, не требующий битов. Когда пешка находится на уровне 7 ^th , мы также выбираем промоушен. Поскольку пешки обычно превращаются в ферзей, а за ними следуют рыцари, мы кодируем варианты:
  • Королева: 0
  • Рыцарь: 10
  • епископ: 110
  • ладья: 111
• Епископ: не более 13 пунктов назначения при значении {d, e} {4,5} для 4 битов.
• Ладья: максимум 14 пунктов назначения, 4 бита.
• Рыцари: максимум 8 мест назначения, 3 бита.
• Короли: когда есть возможность рокировки, король возвращается к S и не может двигаться вниз; это дает в общей сложности 7 пунктов назначения. В остальное время король имеет максимум 8 ходов, что дает максимум 3 бита.
• Королева: То же, что и выбор слона или ладьи, всего 27 вариантов, что составляет 5 бит

Так как число вариантов не всегда является степенью двойки, приведенное выше все равно теряет биты. Предположим, что количество вариантов выбора C , а конкретный выбор пронумерован c и n = ceil (lg ( C )) ( количество битов, необходимых для кодирования выбора). Мы используем эти значения, потраченные впустую, изучая первый бит следующего выбора. Если это 0, ничего не делать. Если это 1 и c + C <2 <sup>n , то добавьте C к c . Декодирование числа переворачивает это: если получено c > = C , вычтите C и установите первый бит для следующего числа равным 1. Если c <2 <sup>n - C , затем установите первый бит для следующего числа равным 0. Если 2 ⁿ - C <= <em>c <<em> C , тогда ничего не делайте. Назовите эту схему "насыщенность".

Другим потенциальным типом выбора, который может сократить кодировку, является выбор фигуры противника для захвата. Это увеличивает количество вариантов для первой части хода, выбирая фигуру, но не более чем на дополнительный бит (точное число зависит от того, сколько фигур может переместить текущий игрок). Этот выбор сопровождается выбором фигуры захвата, которая, вероятно, намного меньше, чем число ходов для любой из данных фигур игрока. Часть может быть атакована только одной частью с любого кардинального направления, плюс рыцари, всего не более 10 атакующих фигур; это дает в общей сложности максимум 9 битов для движения захвата, хотя я бы ожидал в среднем 7 битов. Это было бы особенно выгодно для захвата королевой, так как у него часто будет довольно много легальных мест назначения.

С насыщением кодирование захвата, вероятно, не дает преимущества. Мы могли бы разрешить оба варианта, указав в исходном состоянии, которые используются. Если насыщенность не используется, кодировка игры также может использовать неиспользуемые числа выбора ( C <= <em>c <2 <sup>n ) для изменения параметров во время игры. В любое время C является степенью двойки, мы не можем изменить параметры.