Как использовать таблицы перемещения с MTD (f)
Я пишу AI для карточной игры и после некоторого тестирования, я обнаружил, что с помощью MTD (f) на моем альфа-бета алгоритме - ряд поисков нулевого окна - быстрее, чем просто использование альфы - беты отдельно.
MTD (f) алгоритм описан хорошо здесь http://people.csail.mit.edu/plaat/mtdf.html
Проблема, которую я имею, состоит в том, что для каждой передачи в MTD (f) поиск (для каждого предположения) я не снова использую ни одного из предыдущих положений, которые я сохранил даже при том, что запись на ссылке предлагает, чтобы я был должен (на самом деле очистка таблицы между повторениями ускоряет алгоритм).
Моя проблема состоит в том, что, когда я храню положение и значение в моей таблице перемещения, я также храню альфу и коэффициенты бета, для которых это допустимо. Поэтому вторая передача через дерево с другим предположением (и поэтому альфа и бета) не может возможно снова использовать информацию. Это то, что должно ожидаться, или я пропускаю что-то фундаментальное здесь?
Например, если для alpha=3 beta=4 мы приходим к результату 7 (очевидно, сокращение), я должен сохранить это в таблице как допустимое для alpha=3 к beta=6? Или beta=7?
1 ответ
Ваша проблема сводится к концептуальному пониманию того, как использовать таблицу транспонирования наряду с альфа-бета-поиском. Это была огромная проблема, с которой я тоже столкнулся, и, осмотревшись, я нашел это обсуждение , которое объясняло мне концепцию более естественно, чем любая статья, которую я читал по этой теме.
По сути, вы не можете обрабатывать все результаты альфа-бета одинаково, потому что, когда происходит отсечка, результат представляет только границу, а не истинное минимаксное значение. Было доказано, что использование границ всегда будет давать вам то же самое лучшее следующее состояние, но, возможно, без точного результата. Когда вы сохраняете состояние от отсечки, вам нужно рассматривать его как границу и пытаться улучшить его на следующем проходе. Это часто будет оценивать один и тот же узел несколько раз, но при необходимости будет постоянно улучшаться фактическая оценка.
Вот хороший пример более полной реализации концепций, перечисленных в ранее связанной статье. Прокрутите до страницы 14.