Comments 32
Таки достаточно же одного uint64. Шашки раз мещаются только на половине клеток, так что спокойно два бита на каждое поле есть и так.
Хотя если помнить, что надо только 3 положения на клетку, то все состояние впихивается в 51 бит в лоб, без необходимости учитывать что шашек ограниченное число
Там же дамки ещё, так что 5 положений на клетку. И количество ходов дамками надо записывать, чтобы знать, когда объявить ничью.
Погодите-ка. Как одного? На доске 64 клетки, но используется только половина, т.е. 32. Каждая клетка может иметь 5 состояний: пустая, белая шашка, белая дамка, чёрная шашка, чёрная дамка. На 5 состояний нужно не менее 3 бит. Получаем 1*32*3 = 96 бит. А вот 2 * 32 * 2 = 128 бит можно получить либо если хранить отдельно белые и отдельно чёрные шашки, либо если для простоты "округлить" 3 бита до ниббла (4 бита).
Поскольку состояния клеток теоретически можно хранить совместно, то необязательно округлять 5 состояний до 3 битов, а точная верхняя оценка составит ceil (log2(5)*32), то есть 75 битов. Но это без учёта того, что шашек ограниченное количество, поэтому не все комбинации состояний клеток реализуемы, следовательно ещё несколько битов можно откинуть.
Насколько эффективна для обработки будет такая упаковка – другой вопрос.
Да просто используем uint64 для того чтобы описать "номер возможной комбинации", их оценивают в 10^20 что меньше чем 2^60. Правда очередность кода и подсчет количества ходов в эндшпиле без взятия уже не впихнуть, похоже.
Не то чтоб я считал это сколько-либо рациональным для любого применения :)
У меня получилось 2308487698984342680192 (2.31*10^21) = 71 бит для всех позиций. Считал так: https://carc.in/#/r/f1we
Это правда без учета того что не все позиции возможны в реальной игре (не могут обе стороны провести все свои фишки в дамки) - но ведь в движке может потребоваться и невозможные в реальности позиции представлять.
Можно еще меньше, если первый бит декодирующий: 0b0 - это пустая клетка, 0b100~0b111 - занятая клетка. 72 бита на занятые клетки, и 8 бит пустых. Итого 80 бит в начале игры, и до минимум 35 (остаться должен только один) или 38 (ничья) в конце. Остальные 48+ бит можно потратить на счетчики ходов.
Ужать меньше наверно не получится из-за оверхеда. Не знаю как @datacompboy получил 51 бит.
Как у вас получилось 72 и 80? Ровно 64 бита же. 16*3=48 для занятых и 16*1=16 для пустых чёрных клеток доски.
А 51 бит он получил, не учтя дамки, по вашему способу тогда получается 48.
У меня получилось что-то вроде:
00 - пустая
01 - Наша шашка
10 - враг
110 - наша дамка
111 - чужая дамка
В лучшем случае 64 бита, в случае с дамками начинает расти.
Наверное, алгебраическое кодирование даст больше, но вероятности все съедят :(
Какие вероятности? Хотя кажется понял.
ошибся, «арифметическое», не алгебраическое шифрование. Оно использует вероятности чтобы кодировать наиболее часто встречаемые последовательности (скажем, у нас довольно быстро будет пустых ячеек больше, чем не пустых), но ручками в полночь сделать его я не смогу, а так же, очевидно, нам для декодирования нам нужно гдето хранить эту самую вероятность.
PS Хотя шахматы, вон, Хаффманом кодируют.
Когда-то портировал под j2me опенсорсный шахматный движок от https://www.java-chess.de/java-chess/ - там все поле с фигурами хранится в массиве из 4х long. И вся обработка ходов идет через битовые операции. Весьма мозговыносяще было)
Достаточно 3 битовых масок, где каждая - 32 бита (количество полей). Одна маска - белые фигуры, вторая маска - черные фигуры, третья маска - дамки. Это самое эффективное представление.
Если вдруг интересно использовать наработки эндшпильной базы от Тундры, обращайтесь в личку. Параметры сжатия такие: в 4ГБ хранится 400 млрд позиций.
400 млрд в 4ГБ это по 100 позиций на байт. Без серьезных сжатий тут не обошлось. Могу предположить что разреженность поля, пустота большую часть времени игры (пустот сильно больше чем фишек), и значительная репетативность позволяют применить те же кодирования Хоффмана на большом масштабе.
А мне интересно (если не жалко), имеет ли свертка значение или не особо? (Под сверкой я имею ввиду порядок обхода поля -- слева направо сверху вниз или по диагонали или еще какой-то хитрой фигурой, как в JPEG)
Что-то мне подсказывает, что это 3 байта на позицию а потом 7zip или xz поверх
Для каждой позиции хранится не только результат Выигрыш/Ничья/Проигрыш (что можно упаковать 5 в один байт), но и то как в ней ходить. Ведь если в дамочном окончании выигрыш где-то очень далеко, то просчет не добивает, а знание результата не позволяет достичь выигрыша без просчета/перебора.
Отвечая на ваш вопрос, порядок полей скорее всего не имеет значения. Важно то, что "соседние позиции" повторяют результат. Хорошо, если соседние поля имеют близкий индекс - это позволяет усилить сжатие, но например в окончаниях важно владение большаком (диагональю a1-h8), а кодировать такие аспекты - вряд ли эффективно.
Отличная идея с тремя масками. Можно попробовать переделать мой код и сравнить.
За базы спасибо 🙏
Так же нужно не забывать что нужно не только эффективно представлять позиции, но и получать информацию тоже. Поэтому чтение по простой маске являются наиболее предпочтительными
Есть довольно простой способ сравнения. Сравнить скорость генерации ходов. С представлением 12 байт на позицию (3 маски по 32 бита) мой генератор ходов выдавал 10 миллионов генераций в секунду (когда частота процессоров была 2-3 ГГц; само собой - на одно ядро). Ваш генератор (посмотрел в исходники) способен на сотни тысяч в секунду, не больше.
Что-то мне кажется что нам для расчёта хода не важно белая это дамка или чёрная. Думаю эффективнее было бы 0b001 - белая шашка, 0b010 - чёрная. Признак дамки вынести в старший бит. 0b101 - белая, 0b110 - чёрная. Если больше 3, то дамка, меньше 4 обычная шашка.
Русские шашки: представление доски с помощью двух uint64