Как использовать таблицы транспонирования с MTD (f)

Question

Я пишу ИИ для карточной игры, и после некоторого тестирования я обнаружил, что использование MTD (f) в моем алгоритме альфа-бета - серии поисков с нулевым окном - быстрее, чем просто использование альфа-беты сам по себе.

Алгоритм MTD (f) хорошо описан здесь http://people.csail.mit.edu/plaat/mtdf.html

Проблема, с которой я столкнулся, заключается в том, что для каждого прохода в поиске MTD (f) (для каждого предположения) я не использую ни одну из предыдущих позиций, которые я сохранил, даже несмотря на то, что запись по ссылке предполагает, что я должен фактически очистка таблицы между итерациями ускоряет алгоритм).

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

Например, если для альфа = 3 бета = 4 мы получим результат 7 (очевидно, отсечение), я должен сохранить это в таблице как действительное для альфа = 3 до бета = 6? Или бета = 7?

Answer 1

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

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

Вот хороший пример более полной реализации концепций, перечисленных в ранее связанной статье. Прокрутите до страницы 14.