Comments 34
Интересно, а если эти три картинки - это одно и то же положение, развёрнутое на 90 градусов, то может можно ещё пооптимизировать?
Конкретно эту реализацию - нет, нельзя.
А вот таблицу поиска со всеми допустимыми комбинациями таким образом оптимизировать можно, и именно так из ~9000 позиций получается таблица в 765 штук.
Ждал какой-то логики поверх сжатого состояния, а тут всего лишь чтение и запись.
Я как-то давно делал бота для 3-match с битовым состоянием поля, по которому прогонялись битовые маски для быстрого поиска наиболее оптимального хода.
нам придётся использовать таблицу поиска, сопоставляющую каждое число с
более крупным и структурированным описанием, что делает бессмысленным
саму идею сжатого описания
Не надо хранить таблицу поиска, надо написать две функции encode : СостояниеТаблицы -> Integer, и decode : Integer -> СостояниеТаблицы. Да эти функции каждый раз будут высчитывать таблицу поиска заново, пока не найдут требуемое состояние таблицы, не запоминая результатов расчёта. Будет работать медлено, зато какая грандиозная экономия памяти! ))
А какая "большая" логика в крестиках-ноликах? Тот кто делает первый ход, он либо выигрывает, либо сводит в ничью. Вся логика игры: "либо 1-й в центр, 2-й по вертикали-горизонтали, 3-й по диагонали. либо по любым 3-м углам". Все остальное это вариации с поворотом на 90 градусов.
Но есть нюанс, Детерминированая реализация машины на битовых формулах была реализована в 1950-ых. В книге "Искусство программирования, том 4a" "The Art of Computer Programming, volume 4a", есть описание реализация и задание для таких крестиков ноликов.
Section 7.1.2 of the Volume 4 pre-fascicle 0A of Donald Knuth's The Art of Computer Programming is titled “Boolean Evaluation.” In it, Knuth considers the construction of a set of nine boolean functions telling the correct next move in an optimal game of tic-tac-toe. In a footnote, Knuth tells this story:
This setup is based on an exhibit from the early 1950s at the Museum of Science and Industry in Chicago, where the author was first introduced to the magic of switching circuits. The machine in Chicago, designed by researchers at Bell Telephone Laboratories, allowed me to go first; yet I soon discovered there was no way to defeat it. Therefore I decided to move as stupidly as possible, hoping that the designers had not anticipated such bizarre behavior. In fact I allowed the machine to reach a position where it had two winning moves; and it seized both of them! Moving twice is of course a flagrant violation of the rules, so I had won a moral victory even though the machine had announced that I had lost.
Теперь, благодаря этой оптимизации, можно статически сохранить все 765 возможных состояний игры в 1435 байтах. А текущее состояние уже "удобно" хранить в 10 битах. (шутка)
18битное решение без толку замороченное. Символы одного игрока на одной строке представляют собой биты. Для строки нужно 3 бита. 3 бита * 3 строки * 2 игрока = те же 18бит.
Я нифига не понял, зачем хранить состояние «недопустимо».
Дальше на правах под пиво: Чтобы передать состояние первого игрока флагами, нужно девять бит. Но при этом мы кое‑что про него знаем. Ни при каких обстоятельствах не может быть больше пяти знаков у первого игрока, а у второго — больше, чем у первого. Можем мы этим воспользоваться?
Пишем первые девять бит. Затем пишем девять бит для второго игрока. 18 бит.
Поскольку знаки второго игрока не могут стоять там, где стоят знаки первого, то мы при записи второго пропускаем биты, соотвествующие знакам первого. Получаем плавающую длину записи 13–18 бит, причём мы можем получить длину из самой записи, так что никаких доп. данных не нужно.
Длина 18бит — худший случай — будет, только если у первого игрока 0 знаков — но тогда и у второго будет ноль. Смело отбрасываем с хвоста один бит. Если у первого игрока поле пустое, то дальше не читаем.
Длина 17 бит будет только если у первого игрока 1 знак, а у второго — ноль или один. Мы можем инвертировать биты первого игрока и чётко видеть, что они инвертированы, потому что 8 знаков у него быть никак не может. Отбрасываем с хвоста ещё один бит. Если он был ноль — просто отбрасываем, а если один — инвертируем первого игрока.
Длина 16 бит будет, если у первого игрока 2 знака. И у второго до двух, из 7 бит, отведённых под него. Значит, мы всё ещё можем определить, что поле второго игрока инвертировано. Отбрасывам с хвоста ещё один бит, и используем инвертированность полей обоих игроков в роли двух последних бит.
15 БИТ!
В 15 бит кодируется вообще любое состояние поля, а не только то, которое может быть получено по правилам игры. Достаточно перевести девятизначное троичное число в двоичное, т.е. в другую систему счисления.
Чтобы сокращать дальше, нужно договориться, что именно мы кодируем - важны ли повороты/симметрия, важны ли правила игры, нужны любые состояния или только конечные состояния сыгранной партии.
0 - пусто, 1 - крест, 10 - ноль. 8 бит на нули, 5 на кресты при полной загрузке. Остается из индекса состояния вычислить сколько бит анализировать. Часть в байт уложится и в среднем результат будет лучше 18
В функции set_cell ошибка, там сигнатура должна быть `void set_cell(state* s, .....)`
1 клетка принимает 3 состояния и влезает в 2 разряда.
2 клетки - 3^2 = 9 состояний, 4 разряда.
3 клетки - 3^3 = 27 состояний, 5 разрядов.
Это значит, мы можем построить функции
using table = unsigned short; // 15 bit
using row = unsigned char; // 5 bit
using cell = unsigned char; // 2 bit
row encode_row(cell c0, cell c1, cell c2) {
return c0 + (c1 + c1*2) + (c2 + c2*8);
// на сдвигах, если хочется умножения экономить
}
const cell decode_row[27][3] = {
{0,0,0},{1,0,0},{2,0,0},
{0,1,0},...............,
...............,{2,2,2},
};
// что-то сходу лень думать, можно ли арифметическим колдовством
// обойтись без деления и при этом - без таблицыВ общем, дальше лень писать :)
Что будет быстрее работать, - деления или нудная работа с таблицами, - хз. Бенчмарки тоже лень писать.
я сперва подумал что они всю ИГРУ уместили в 18 бит, а тут только рабочее поле. все эти битовые приключения как то уже напоминает алгоритмы сжатия. В масштабе 9 ячеек больше потеряешь на коде чем выиграешь. Другое дело когда гигабайты
Другое дело когда гигабайты
Ну это состояние одной игры 18 бит. Смасштабировать можно и до гигабайтов.
Может у нас волшебно-квантовый компьютер, где CPU бесплатен, а вот память ограничена и миллионы людей(ботов) играют одновременно в крестики-нолики зачем-то.
Но на практике вы правы, конечно, это скорее решается как будет храниться база данных с правильным deduplication.
Маленькие проги можно делать без exe/elf хедеров, то есть сразу писать код на асме как в досе. Пример крестиков ноликов до 256 байт: https://www.pouet.net/prod.php?which=87163
Как говорит Алехандра, существует 765 возможных состояний игры1. Мы можем просто назначить число каждому состоянию, что займёт 10 битов2. Но, по словам Алехандры, это «скучно». С таким описанием игры мы практически ничего не сможем сделать. Когда будет нужно считать значение из конкретной ячейки или перейти из одного состояния в другое, на практике нам придётся использовать таблицу поиска, сопоставляющую каждое число с более крупным и структурированным описанием, что делает бессмысленным саму идею сжатого описания.
Строить поле для определения хода совершенно излишне. Каждое состояние игры имеет какой-то ответный ход, который выберет наша программа, и этот ход сам по себе представляет состояние, то есть такое же число. Поэтому можно действовать, как клуб любителей анекдотов, ведя диалоги типа “5-13-703” и т.д. Строить само поле нужно только для визуализации неопытному человеку.
Какое практическое применение может иметь такое кодирование? Например, два программиста, сидя в одиночных камерах, играют в крестики-нолики перестукиванием. Тогда они могут затратить неограниченное количество ресурсов на кодирование и декодирование, но стремятся сократить количество стуков.
В ситуации реальной игры, правда, можно ещё изрядно сэкономить, потому что только очень небольшое количество позиций являются возможными ходами в каждой конкретной ситуации.
"15 бит хватит всем" © ;)
Ждал определения поворота в первых 4 или дополнительно симметрии еще в 1 бите в зависимости от первых ходов. Ну или чего-нибудь подобного, а не просто "как перевести троичную систему в двоичную"
Ну или вместо всех состояний на каждый ход хранить какие-нибудь смещения и вычислять по ходам. получится явно эффективнее, чем по 15 бит на каждый ход партии (минимум 5 раз).
Типа первый ход - 3.25 бита, второй - 3 бита, 3й - 2.75 и т.п... и всё плотно упаковать
Прочитал заголовок. На калькуляторе посчитал 3**9. Ага, как раз в 15 бит лезет. Остальную статью быстро просмотрел: ага, то же самое.
IO логика займет в тысячи раз больше
Я как-то раз что-то подобное проворачивал на блюпринтах в unreal engine. Было забавно.
Не совсем про кодирование состояния, но может будет интересно - There are Exactly 14 Different Games of Tic-Tac-Toe
У одной строчки - 27 состояний, лезет а 5 бит. Делаем табличку на 27 значений, пихаем в 3 числа по 5 бит, получаем 15 бит.
Извиняюсь, я кое-что не учел(отредактировал). Сейчас перепроверю свою идею
Спасибо большое автору, мне было интересно!
Можно использовать 4 бита на кодирование последующего числа числа бит (все число вплоть до 15 бит при максимальном значении, но если оно например равно 1, отсечь все кроме первого бита)
Тогда сумарный минимум будет 5 бит, максимум 19: в среднем 12
Ещё немного можно отсечь комбинаций, из тех что следуют уже после победных, но я не использовал это
Партия состоит из 4х ходов максимум, после которого заканчивается победой крестиков или ноликов (1 бит)
Итого в лучшем случае 41 бит на партию (5 * 4 * 2 + 1), 153 бита максимум (19 * 4 * 2 + 1)
В среднем 97, против 120 на всю партию константно
Вероятно есть неточности, но я думаю что есть возможность хранить в среднем в меньшем пространстве чем 120 бит. И в чем я не уверен, но возможно можно задавать базисы, которые будут склонять запись партии к минимальному числу бит. Не уверен, что повороты точно помогут, но как одна из идей
Кодируем крестики-нолики в 15 битах