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

Question

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

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

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

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

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

Answer 1

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

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

Here is a good example более полной реализации концепций, перечисленных в ранее связанной статье. Прокрутите к странице 14.