Хеширование состояния поля в игре Nine Men's Morris (мельница)

Не уверен, что в тот раздел. Подскажите, если что

Итак, есть поле для игры на 24 ячейки, есть 2 игрока с девятью фишками на руках.
Фаза 1: каждый игрок поочередно выставляет на свободную ячейку фишки
Фаза 2: игроки перемещают фишки по линиям на поле
Фаза 3: игрок с 3 оставшимися фишками получает возможность переставлять свою фишку на любое свободное поле

Если игрок собрал мельницу (3 фишки в ряд), то он забирает любую фишку соперника. Дальше уточнять правила не буду, только приведу ссылку на англоязычную статью: http://library.msri.org/books/... gasser.pdf

Там описываются идеи, заложенные в основу вычисления хеш-функции, и приводятся правила игры.

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

Немного моих выкладок (в терминах памяти): итак, если 24 клетки могут иметь три состояния (свободна либо занята игроком), то грубая оценка сверху дает 3^24 состояний доски. Допустим, состояние 5 клеток мы поместим в один байт (241 из 256 значений, почти полностью займем место), тогда на всю доску у нас уйдет 5 байт. При количестве состояний 3^24 (282 млрд) мы можем хранить их, используя всего лишь 282*5 Гб дискового пространства. На руках сейчас имеется 700 гб, и очень не хотелось бы использовать их все. Вот так как-то.

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

0

Сообщение от Ksardas_178 При количестве состояний 3^24 (282 млрд)

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

Состояние, кроме расположения фишек должно включать фазу и чей ход.
Можно отдельно хранить (и кодировать) состояния для фазы 1 и состояния для фаз 2/3.

Добавлено через 21 минуту
Заглянул в статью. Там всё это написано. И даже приводится алгоритм для вычисления цены всех состояний. В чём вопрос?

0

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

Добавлено через 2 минуты
И да, надеюсь, вариант вроде "перебирать что есть, выкидывая лишнее, и пересчитывать новый индекс для реально существующих состояний" мы не рассматриваем. Неприемлемо по времени.

0

В статье описан алгоритм, который работает на десктопе 1990-го года. Полагаю, проблем по времени быть не должно.

0

А ты действительно хочешь делать ИИ в виде гигабайт данных вида (состояние -> ход) ?
Почему бы не реализовать что-то наподобие шахматного ИИ? Например, для каждого хода - дерево возможных будущих событий с отсеченем плохих веток.

Сообщение от Ksardas_178 но вопрос в том, как построить алгоритм перевода состояния поля в число.

Ячейки доски имеют 3 состояния, 24 ячеек - следовательно у тебя число из 24 цифр по основанию 3.
А перевести число из одной системы счисления в другое - не должно составить проблем.
Там получается 39 бит. Записываем ответ в буфер uint64 и выдергиваем из него эти 5 байт информации, и также в обратную сторону.

0

Сообщение от wingblack Почему бы не реализовать что-то наподобие шахматного ИИ?

Фактически эта часть уже реализована и худо-бедно работает через минимакс. Хранить для нее поле вообще бессмысленно. Есть операции makeTurn(t) и reverseTurn(t), рекурсивный алгоритм просто копает на n шагов вглубь, потом оценивает доску и выбирает лучший ход из возможных, затем откатывает ходы, сделанные для анализа. Все на этом. На глубине 7 ему предсказуемо становится плохо. Играть играет, но зачастую тупит.

Сообщение от wingblack Ячейки доски имеют 3 состояния, 24 ячеек - следовательно у тебя число из 24 цифр по основанию 3.

Это было написано уже в первом посте, только я округлил 39 бит до 5 байт информации. Сейчас с битами никто и не работает. Если писать в int64, получим вместо 5 байт 8.

На вопрос о том, как закодировать поле не функцией с 2^34 состояниями мне, видимо, никто ответить не сможет.

0

Нужно хранить оценки для фаз 2/3 и считать минимаксом фазу 1.

0

Сообщение от Ksardas_178 Сейчас с битами никто и не работает. Если писать в int64, получим вместо 5 байт 8.

uint64 удобно использовать как буфер где ты будешь создавать это число по основанию 3. Иначе тебе нужно несколько переменных поменьше и для них реализовывать мини-длинную арифметику.
Да, оно будет занимать 8 байт памяти, но значимыми тут являются только крайние 5 (остальное всегда нули), вот их и хранить.
Ты во время своей рекурсии как хранишь состояние доски - как 24 байта, или кратковременно развертываешь в 24 байта, а перед стартом новой вложенной рекурсии сворачиваешь ее до 5 байт, предварительно освободив память?
А ты учел момент что тебе не нужно сворачивать все ветки, а только после хода противника откидывать "не сработавшие" и расширять ту которая соответствует новому ходу?
Еще можно состояние доски обрабатывать в виде 48 бит, по 2 бита на ячейку, где единица это флаг где какого цвета камень сидит. А для хранения все также в 5 байт сворачивать.

Сообщение от Ksardas_178 На вопрос о том, как закодировать поле не функцией с 2^34 3^24 состояниями мне, видимо, никто ответить не сможет.

А ты думал что у доски есть 3 оси симметрии, что ее можно повернуть в 4 положения и зеркалить по осям?
С точки зрения стратегии все такие "картинки" будут абсолютно одинаковыми состояниями.

0

*4 оси симметрии.

А в что у тебя упирается рекурсия, в объем памяти или по времени перебора всех вариантов?

0

Сообщение от wingblack С точки зрения стратегии все такие "картинки" будут абсолютно одинаковыми состояниями.

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

Добавлено через 6 минут

Сообщение от wingblack Ты во время своей рекурсии как хранишь состояние доски - как 24 байта, или кратковременно развертываешь в 24 байта, а перед стартом новой вложенной рекурсии сворачиваешь ее до 5 байт, предварительно освободив память?

Я уже писал выше, что не храню новые доски. Лишь меняю состояние текущей, а после расчетов откатываю назад.

Сообщение от wingblack А ты учел момент что тебе не нужно сворачивать все ветки, а только после хода противника откидывать "не сработавшие" и расширять ту которая соответствует новому ходу?

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

0

Сообщение от Ksardas_178 даже пытаясь ее покрутить всеми предложенными способами, мы даже на треть не сократим максимальное возвращаемое значение функции

Сообщение от Ksardas_178 Энивей, в этой теме я хотел бы обсудить именно составление полной базы знаний.

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

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

Нужно посмотреть какая последовательность операций позволит перебирать все равносильные состояния доски без повторений.
Например, можно повернуть доску на 90 градусов 0,1,2,3 раза, потом 0,1 раз отзеркалить по вертикали, потом повернуть 0,1,2,3 раза, потом отзеркалить 0,1 раз по главной диагонали, потом повернуть 0,1,2,3 раз
Я не сильно в этом шарю, но предположу что это сокращает размер функции до (4 + 4*4 + 4*4*4) раз (впрочем, здесь будет много состояний которые имеют симметрию - они не будут давать такого большого сокращения функции)

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


P.S. Если делать не рекурсивно, а строить наподобие K-D дерева, то многие ветки будут переплетаться, экономя немного времени.
Кстати говоря, дерево... В программировании же извечный выбор между памятью и производительностью, очевидно что у тебя выбор в сторону уменьшения памяти, почему бы тогда не хранить доску по принципу дерева, но хранить не состояния, а только ходы обоих игроков? Тогда на одно состояние нужно только 5 бит.

Добавлено через 54 минуты
а если их еще не округлять до байта, а хранить пакетами по 8 штук - еще немного места сэкономим

0

ИМХО
Нужно взять фиксированное распределение - например, 3 белых и 3 чёрных фишки - и построить для него все варианты. Затем уменьшить в 16? раз (4 поворота и 2 оси симметрии). После чего, попробовать построить хеш-функцию для данного распределения.

0

Сообщение от Shamil1 Затем уменьшить в 16? раз (4 поворота и 2 оси симметрии).

У квадрата есть 4 оси симметрии - горизонталь, вертикаль и две диагонали. Одна из них вырожденная - любые три преобразования в сумме дают четвёртое. Поэтому можно выбрать из них любые три. Кроме того, у поля Мельницы есть ещё одна ось симметрии - внешний квадрат ничем не отличается от внутреннего. Итого 4 преобразования. Применением от 0 до 4 из них получаем 16 вариантов.

Преобразования можно описать массивами замен:
У нас есть массив из 24 элементов, каждый из которых может принимать 3 значения. Для фиксированного количества белых и чёрных фишек получаем перестановки с повторениями - "n элементов m различных типов, причем в каждом типе все элементы одинаковы". Количество перестановок равно мультиномиальному коэффициенту. Можно перебрать их все в лексикографическом порядке и пронумеровать те, которые являются лексикографически минимальными в своём классе из 16 вариантов.

Фактически, предыдущем абзаце описан алгоритм кэшфункции. Проблема в том, что для поиска элемента с индексом эн нужно перебрать все предшествующие (напоминает поиск в линейном списке). Для ускорения используем кэш - массив перестановок с их индексами. Методом деления пополам находим максимальную перестановку меньше/равно искомой и её индекс. Дальше запускаем алгоритм из предыдущего абзаца, но не с самого начала, а с найденного значения. Например, можно "закэшировать" каждую 10,000-ую перестановку (нужно найти баланс между скоростью вычисления нужного индекса и памятью под кэш).

1