Как эффективно хранить шахматную партию?

Каков наиболее эффективный способ хранения всей шахматной партии в базе данных? учитывая, что средняя длина игры составляет 50-70 ходов (1 ход означает, что 2 игрока делают один ход), я надеюсь, что это займет менее 800 бит.

Начальное место фигуры могло храниться в 6 битах, а ход мог занимать 2-4 бита. есть ли способ хранить его меньше, чем это?

можете ли вы поделиться одной «средней» игровой записью, чтобы люди могли проверить на реальных данных ... Я потерял все свои несколько десятилетий назад ...

Spektre 08.06.2023 08:52

@DavidEisenstat интересная ссылка, предполагающая, что их наивная кодировка 47,5 бит / ход - это ASCII с некоторыми маркерами, такими как шахматы, гард или что-то еще, также объясняют дополнительные биты в двоичном коде.

Spektre 08.06.2023 19:44
ReactJs | Supabase | Добавление данных в базу данных
ReactJs | Supabase | Добавление данных в базу данных
Это и есть ваш редактор таблиц в supabase.👇
4
4
141
5
Перейти к ответу Данный вопрос помечен как решенный

Ответы 5

шахматы с наивным кодированием требуют 2*6 бит на ход:

number_of_moves(7 bits)
start_position (6bits) - target_position (6bits)
start_position (6bits) - target_position (6bits)
...

например:

70
E2 - E4
D7 - D5
...

3 бита для буквы A..H и 3 для цифры 1..8, и каждый ход имеет 2 позиции.

70 moves * 12 bits + 7 bits = 847 bits = 106 Bytes

Это уже около желаемых 800 бит. Теперь просто примените сжатие либо Huffman, либо LZW.

Теперь вы можете использовать 10-битное кодирование на ход, используя только 16 (0..15 -> 4 бит) шахматных фигур на каждой стороне. Каждая игра начинается с белого (поэтому нечетные ходы белые, а четные черные), поэтому измените кодировку на:

number_of_moves(7 bits)
white_piece_ix (4bits) - target_position (6bits)
black_piece_ix (4bits) - target_position (6bits)
...

это ведет к:

70 moves * 10 bits + 7 bits = 707 bits = 89 bytes

Что ниже ваших 800 бит уже

Если этого недостаточно, вы можете использовать переменную таблицу индексов шахматных фигур. Таким образом, каждый раз, когда какая-то фигура «удаляется» с доски, вы сдвигаете значение индексов, поэтому неиспользуемая шахматная фигура будет использоваться следующим индексом, а пробел будет в конечных значениях (так что, если фигура 13 удалена, то фигуры 14,15 будут стать 13,14). Таким образом, когда на одной стороне меньше 8 фигур, вы можете использовать 3 бита на ее индекс, меньше 4 использовать 2 бита и так далее, вы получите 7 .. 10 бит на ход.

Теперь вы также можете применить сжатие (LZW или Hufman). Я бы выбрал LZW, поскольку Хаффману необходимо передать также таблицу вероятностного распределения, которая будет:

16 * ceil(log2(2*70)) bits = ~ 128 bits

Что является относительно большой частью данных по сравнению с ограничением в 800 бит, в то время как LZW строит свой словарь на ходу, и его размер может быть выбран произвольно (поэтому, даже если есть небольшая оперативная память, это не должно быть большой проблемой).

Вам нужно будет описать кодировку для продвижения по службе.

trincot 08.06.2023 08:57

@trincot ваш способ интересен +1, но для предварительного вычисления потребуется относительно большой LUT ... кстати, у меня была ошибка в моих вычислениях: 10 бит на ход, а не 11 ... мне действительно нужно выпить утренний чай :)

Spektre 08.06.2023 09:15

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

vlad_tepesch 09.06.2023 17:15
Ответ принят как подходящий

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

(Теоретическая) позиция, найденная с наибольшим количеством разрешенных ходов, имеет 218 разрешенных ходов. Мы можем быть уверены, что нет позиции с более чем 256 допустимыми ходами, поэтому 8 бит достаточно для кодирования одного хода.

При таком кодировании для игры в 70 ходов потребуется 560 бит.

Динамическое количество бит

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

Поскольку в начальной позиции всего 20 ходов, первый ход белых будет закодирован всего 5 битами; то же самое для первого хода черных. По мере продолжения игры скоро появится позиция, в которой разрешено более 32 ходов, поэтому будут использоваться 6 бит. Например, после

1. e3 e5
2. Qg4 d6

... у белых 46 допустимых ходов, поэтому их ход будет закодирован с использованием 6 бит. Мы уже сэкономили 3 x 4 = 12 бит (по сравнению с 8 битами на ход) для кодирования этих первых четырех ходов.

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

Я не знаю, какой будет наихудшая игра с 70 ходами с точки зрения количества необходимых битов (невозможно вычислить за разумное время), но она будет намного меньше 500 битов.

Минимизация для разумных игр

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

Используйте детерминированный шахматный движок, который выдает счет за каждый допустимый ход, и используйте счет как вероятность того, что этот ход действительно сыгран. Важно, чтобы он всегда давал один и тот же счет за один и тот же ход в одном и том же игровом состоянии. Используйте кодировку Хаффмана для соответствующего кодирования движения. Это будет означать, что хорошие ходы займут меньше битов, чем плохие. Например, если ферзя можно взять, это может даже стать ходом всего с одним битом. Для глупых ходов потребуется больше битов, чем в среднем, может быть, даже больше, чем 8 бит (когда допустимых ходов много, и среди них есть очень хорошие и очень плохие ходы). Игра из 70 ходов, в которой почти все ходы плохие, может занять больше битов, чем с алгоритмом кодирования без Хаффмана, но разумные игры будут использовать меньше.

Могли бы даже выполнить арифметическое кодирование — с вероятностями, оцениваемыми на основе оценки каждого допустимого хода некоторым детерминистическим шахматным движком. Игра опытных игроков, вероятно, будет менее 100 бит.

Sneftel 08.06.2023 11:12

Вы можете переключить это на допустимое назначение вместо допустимого перемещения, которое обычно можно закодировать в <+ 5 бит, с дополнительными битами для устранения неоднозначности источника, когда это необходимо (может быть, 1 бит в среднем.

Dave 08.06.2023 15:31

@ Дэйв, это не помогает. Когда есть n допустимых ходов, вы не можете использовать менее log(n) битов, чтобы получить уникальный ключ для хода, если только вы не принимаете диапазон наилучшего/худшего случая, где иногда вам потребуется больше, чем n бит. В своем ответе я хочу сосредоточиться на худшем случае, а затем минимизировать объем памяти.

trincot 08.06.2023 15:56

@trincot Есть 20 допустимых начальных ходов, которые приземлятся на одну из 16 клеток. Вашему методу всегда требуется 5 бит для кодирования этого. Моему всегда нужно 4 для кодирования квадрата, плюс пятый бит для 4 квадратов, доступных коням. Так что по крайней мере в некоторых случаях мой подход использует меньше битов. Я не уверен, верно ли обратное.

Dave 08.06.2023 17:42

Вы можете посмотреть на мой ответ, но вот резюме. 1. Все квадраты пронумерованы от 0 до 63. 2. Определить, сколько возможно посадочных квадратов (в данном случае 16). 3. Биты потолка(log_2(количество возможных клеток)) будут использоваться для кодирования того, на какую клетку назначения вы приземлитесь. 4. Определите, сколько возможных исходных клеток может переместиться в эту конечную клетку. 5. Если > 1, используйте биты log_2(количество(возможные исходные квадраты)) для кодирования исходного квадрата.

Dave 08.06.2023 18:10

@Dave, эта система будет работать для этого примера, но когда в игре есть 32 допустимых хода, например, после 1. d4 e5 2. f4, вашему методу в некоторых случаях потребуется 6 бит, в то время как мое решение (во втором разделе моего ответа) понадобится 5. Так что это работает в обе стороны. Кроме того, может стать еще хуже, когда до квадрата можно дотянуться 5 частями, что потребует 3 дополнительных бита. Кроме того, вы читали третий раздел моего ответа?

trincot 08.06.2023 18:11

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

Dave 08.06.2023 18:11

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

Dave 08.06.2023 20:08

Хороший. Лучший анализ и самая компактная кодировка, если не самый практичный ответ :)

Matt Timmermans 09.06.2023 05:05

Недостатком такого решения является невозможность поиска в такой закодированной базе данных ходов или игровых состояний (конечно, OP не указывает это как требование). Даже декодирование довольно интенсивно обрабатывается, потому что вам нужно запустить игровой движок (для варианта с вероятностным кодированием), но хорошая идея

vlad_tepesch 09.06.2023 16:36

Пронумеруйте квадраты 0-63. Подсчитайте количество квадратов, достижимых текущей стороной. Используйте минимальное количество битов, чтобы представить, в какой из достижимых квадратов было перемещено значение потолка (log_2 (количество достижимых квадратов)) бит.

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

Вот пример с использованием первых нескольких ходов из «Каспаров против Топалова» 13.04.13. Я нумерую 0 в левом нижнем углу (белая ферзевая ладья начинается с 0, белый ферзевый конь - с 1 и так далее).

  1. e4d6 1100 кодирует, что это 12-й из 16 возможных квадратов (с индексом 0, поэтому 0000 будет записывать e3); никаких дополнительных битов не требуется, так как здесь может двигаться только одна деталь.

  2. d4Nf6 1011 кодирует, что это 11-е из 16 возможных полей; опять же, никаких дополнительных битов не требуется.

  3. Nc3g6 01101 кодирует, что это 13-е из 25 возможных полей; опять же, никаких дополнительных битов не требуется.

  4. Be3Bg7 10001 означает, что это 14-е из 17 возможных полей. Здесь ход мог быть сделан с двух полей (конем или пешкой), поэтому нам нужен 1 бит, чтобы отличить какое, для окончательного кодирования 100011.

Требуемое количество битов на ход будет зависеть от игры. Для пункта назначения никогда не может потребоваться более 6 бит, и я считаю, что для большинства ходов в большинстве игр потребуется только 5. Я не думаю, что нам следует ожидать <= 4, за исключением начальных ходов и некоторых ситуаций в эндшпиле.

Шаг устранения неоднозначности (какой из нескольких квадратов перемещается к месту назначения) будет возникать довольно часто. Я предполагаю, что для большинства ходов это не требуется, но некоторые ходы с 1-2 битами и редко с 3 встречаются в большинстве игр.

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

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

Dave 08.06.2023 15:23

Также ранжируйте фигуры (0 = пешка, 1 = конь, ...) для повышения.

Dave 08.06.2023 15:32

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

Jim Mischel 08.06.2023 16:51

Добавлю, что при записи битов мы должны пропускать биты, имеющие только одно возможное значение. Например, если мы кодируем число, которое может находиться в диапазоне от 0 до 4, то нам обычно требуется 3 бита: 000, 001, 010, 011, 100. Однако, если первый бит равен 1, мы знаем это. кодирует место 4 и что никакие другие установленные биты невозможны, поэтому не кодируйте оставшиеся нули.

Dave 08.06.2023 21:29

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

vlad_tepesch 09.06.2023 17:11

Есть 32 штуки и 64 квадрата. Таким образом, для хранения фигуры и ее положения требуется 11 бит: 5 бит для фигуры и 6 бит для позиции.

Исходное положение фиксировано, поэтому нет необходимости его сохранять. После этого вам нужно только сохранить позиции движущихся фигур: 11 бит на фигуру. То есть ваша сохраненная игра просто записывает ходы отдельных фигур. Вы знаете, где произведение началось, поэтому все, что вам нужно запомнить, это то, где оно закончилось.

Таким образом, большинство ходов можно хранить в 11 битах (ходы одной фигуры). Как ни странно, захват можно закодировать, обновив только позицию захватываемой фигуры. Логика игры может увидеть, что две фигуры занимают одно и то же место, и удалить захваченную фигуру с доски. Что хорошо, потому что нет 65-го места (то есть «не на доске»), чтобы поместить его: у вас нет битов для этого. Почти так же можно закодировать en passant: пусть это понимает игровая логика. Первоначально я думал, что для рокировки потребуется кодировать ходы двух фигур, но на самом деле это не так. Король всегда ходит на две клетки, что в любой другой ситуации было бы недопустимым ходом. Ваша логика могла бы легко определить «незаконный» ход и поступить правильно.

Продвижение пешек - проблема. Ход не проблема, но вам нужен какой-то способ сослаться на только что созданную фигуру. Битов на штуки всего 5 и они уже израсходованы. Подумайте о том, чтобы переместить пешку королевского рыцаря с G7 на G8. Обычно вы сохраняете [14,62] (т. е. фигура номер 14 перемещается на позицию 62). Вам нужен какой-то способ показать, что фигура номер 14 теперь ферзь, а не пешка. Это можно сделать, но это потребует дополнительных битов.

Таким образом, лучший случай в игре с 70 ходами — это 11 битов на ход или 770 битов. В игре с 50 ходами это 550 бит.

Это было бы жестко, но я думаю, что то, о чем вы просите, может быть возможно даже без добавления любого типа сжатия или сложной логики. Конечно, вы могли бы получить в среднем 800 битов за игру для игр из 50–70 ходов.

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

Это 4 бита на фигуру и 5 битов на ход — 9 бит на ход. Очень просто.

Другие вопросы по теме

Похожие вопросы

Как написать SQL-запрос в Azure Cosmos DB, чтобы найти шаблон поиска любого пользователя
Данные из столбца образа Sybase усекаются до 32 КиБ при получении через pyodbc
Пользовательское значение первичного ключа отображается неправильно
Как преобразовать дату и время моей живой базы данных в местное время пользователя?
Как расставить приоритеты в поиске подобия векторов Redis?
Почему мой код Python не вставляет данные в базу данных PostgreSQL из файла JSON?
Какой смысл в драйверах MongoDB, если их нельзя безопасно использовать для прямого подключения мобильного приложения к базе данных для производства?
Хранение пользовательских данных в сеансе пользователя и сохранение данных после успешного выхода из системы
Как найти индексы/строки, где комбинация столбцов равна столбцам другого фрейма данных
Какую функцию использовать при связывании нескольких таблиц с помощью Eloquent (Laravel)?