МПД-ф - MTD-f

MTD (f) это минимакс алгоритм поиска, разработанный в 1994 г. Aske Plaat, Джонатан Шеффер, Вим Пейлс, и Арье де Брюин. Эксперименты с турнирным качеством шахматы, шашки, и Отелло программы показывают, что это очень эффективный минимаксный алгоритм. Название MTD (f) является сокращением от MTD (n, f) (тестовый драйвер с расширенной памятью с узлом п и ценность ж). Это альтернатива альфа-бета обрезка алгоритм.[1]

Происхождение

MTD (f) впервые был описан в техническом отчете Университета Альберты, составленном Аске Плаатом, Джонатаном Шеффером, Вимом Пейлсом и Ари де Брюин,[2] который позже получил награду ICCA Novag Best Computer Chess Publication за 1994/1995 гг. Алгоритм MTD (f) был создан в результате исследовательских усилий по пониманию SSS * алгоритм, алгоритм поиска лучшего первого, изобретенный Джордж Стокман в 1979 г.[3] Было обнаружено, что SSS * эквивалентен серии альфа-бета звонки при условии, что используется хранилище альфа-бета, например, хорошо функционирующее таблица транспонирования.

Название MTD (f) означает тестовый драйвер с расширенной памятью, что означает Жемчужина Иудеи Алгоритм тестирования, который выполняет поиск в нулевом окне. MTD (f) подробно описана в докторской диссертации Аске Плаата 1996 года.

Поиск в нулевом окне

MTD (f) получает свою эффективность только за счет выполнения альфа-бета-поисков с нулевым окном с «хорошей» границей (переменная бета). В NegaScout, поиск вызывается с широким окном поиска, как в AlphaBeta (корень, -INFINITY, + INFINITY, глубина), поэтому возвращаемое значение лежит между значением альфа и бета за один вызов. В MTD (f) AlphaBeta не работает на высоком или низком уровне, возвращая нижнюю или верхнюю границу минимаксного значения, соответственно. Вызовы с нулевым окном вызывают больше отсечок, но возвращают меньше информации - только ограничение минимаксного значения. Чтобы найти минимаксное значение, MTD (f) несколько раз вызывает AlphaBeta, приближаясь к нему и в конечном итоге находя точное значение. А таблица транспонирования сохраняет и извлекает ранее найденные части дерева в памяти, чтобы уменьшить накладные расходы на повторное исследование частей дерева поиска.[4]

Псевдокод

функция MTDF (корень; f; d) является    g: = f upperBound: = + ∞ lowerBound: = −∞ в то время как lowerBound делать        β: = max (g, lowerBound + 1) g: = AlphaBetaWithMemory (корень, β - 1, β, d) если g <β тогда            upperBound: = g еще            lowerBound: = g вернуть г
ж
Первое предположение по лучшей цене. Чем лучше, тем быстрее сходится алгоритм. Может быть 0 для первого звонка.
d
Глубина петли. An итеративный поиск в глубину с углублением можно сделать, позвонив MTDF () несколько раз с увеличением d и обеспечивая лучший предыдущий результат в ж.[5]

Спектакль

NegaScout вызывает поиск с нулевым окном рекурсивно. MTD (f) вызывает поиск с нулевым окном из корня дерева. Реализация алгоритма MTD (f) на практике более эффективна (поиск меньшего числа узлов), чем другие алгоритмы поиска (например, NegaScout) в таких играх, как шахматы. [1], шашки и Отелло. Чтобы алгоритмы поиска, такие как NegaScout или MTD (f), работали эффективно, таблица транспонирования должен хорошо работать. В противном случае, например, при возникновении хеш-коллизии, поддерево будет повторно развернуто. Когда MTD (f) используется в программах, страдающих выраженным эффектом нечетного-четного, где оценка в корне выше для четных глубин поиска и ниже для нечетных глубин поиска, рекомендуется использовать отдельные значения для f, чтобы начать поиск. как можно ближе к минимаксному значению. В противном случае поиску потребовалось бы больше итераций, чтобы сойтись на минимаксном значении, особенно для точных функций оценки.

Поиск с нулевым окном обрывается раньше, чем поиск с широким окном. Следовательно, они более эффективны, но в некотором смысле также менее щадящие, чем поиск в широком окне. Поскольку MTD (f) использует только поиск с нулевым окном, а Альфа-Бета и NegaScout также используют поиск в широком окне, MTD (f) более эффективен. Однако более широкие окна поиска более снисходительны для машин с большими колебаниями нечетности / четности и детализированными функциями оценки. По этой причине некоторые шахматные движки не перешли на MTD (f) .В тестах с программами турнирного качества, такими как Чинук (шашки), Феникс (шахматы) и Keyano (Отелло) алгоритм MTD (f) превзошел все другие алгоритмы поиска.[4][6]

Недавние алгоритмы, такие как Поиск лучшего узла предлагается превзойти MTD (f).

Рекомендации

  1. ^ Йоханнес Фюрнкранц; Мирослав Кубат (2001). Машины, которые учатся играть в игры. Nova Publishers. С. 95–. ISBN  978-1-59033-021-0.
  2. ^ «Адаптивные стратегии МПД-ф для актуальных игр». Токийский университет сельского хозяйства и технологий. К. ШИБАХАРА и др.
  3. ^ Теофило Гонсалес; Хорхе Диас-Эррера; Аллен Такер (7 мая 2014 г.). Справочник по вычислениям, третье издание: компьютерные науки и программная инженерия. CRC Press. С. 38–. ISBN  978-1-4398-9853-6.
  4. ^ а б Plaat, Aske; Джонатан Шеффер; Вим Пейлс; Арье де Брюэн (ноябрь 1996 г.). «Лучшие первые минимаксные алгоритмы с фиксированной глубиной». Искусственный интеллект. 87 (1–2): 255–293. Дои:10.1016/0004-3702(95)00126-3.
  5. ^ https://people.csail.mit.edu/plaat/mtdf.html
  6. ^ Plaat, Aske; Джонатан Шеффер; Вим Пейлс; Арье де Брюэн (ноябрь 1996 г.). «Лучшие первые минимаксные алгоритмы с фиксированной глубиной». Искусственный интеллект. 87 (1–2): 255–293. Дои:10.1016/0004-3702(95)00126-3.

внешние ссылки