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

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

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

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

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

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

Ответ 1

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

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

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