Как лучше всего обрезать дерево поиска в игре реверси?

Question

[ffff567]

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

Проблема в том, что программа работает на маленькой глубине 4-6 на финише до 12 может доходить при этом на глубине 6 программа иногда потребляет всю оперативную память компьютера 16 гигабайт.

Вопрос, как лучше всего обрезать дерево поиска?

Есть несколько идей:
Первая идея
Перебрать все комбинации на глубину 4 оценить минимаксом все ходы
начинаем обрезать.

На 1 глубине выбрать 5 лучших продолжений остальные удалить
перестроить дерево удлив первый ход и и оценить снова ходы
На 2 глубине то же выбрать 5 лучших продолжений остальные удалить
Итого мы удалили большую часть дерева.
Начинаем перебирать все комбинации дальше +2 глубины и снова обрезка дерева.

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

Может у вас есть какая-нибудь идея как обрезать лучше всего дерево поиска?

Comments

[alexalexes]

А вы как храните контекст одного узла дерева? Сохраняете позиции всех клеток?
Может в узел записывать только действие игрока, а позиции на доске восстанавливать по цепочке ходов от корня дерева (или держа в кэше последнюю расшаренную конфигурацию доски родителя узла + ход игрока для текущего узла. Узлы, у которых расшарены ходы всех ближайших детей - у них кэш досок удалять)?
Тогда памяти должно меньше уходить.

[ffff567]

alexalexes, храню в словаре индексы ходов например (65,54,32,11) Это означает 4 хода
У меня есть идея сократить количество вариаций таким способом
хранить не индексы а позицию на доске

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

Пока что хочу разобрать с этим уменьшением

[alexalexes]

А если в базу данных положить данные? Даже в классическом SQL можно хранить узел в виде node_id, parent_id, атрибуты узла. Если у вас не будет глубоких иерархических запросов, а просто хождение от родителя к ребенку, то индексы sql будут прекрасно отрабатывать обход.

[EDIsaev]

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

[ffff567]

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

[EDIsaev]

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