Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Происхождение [ править ]

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

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

Поиск в нулевом окне [ править ]

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

Псевдокод [ править ]

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

AlphaBetaWithMemory это вариант альфа-бета-поиска, в котором кэшируются предыдущие результаты.

Производительность [ править ]

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

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

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

Ссылки [ править ]

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

Внешние ссылки [ править ]

  • Описание алгоритма МПД (f)
  • Описание массово-параллельной шахматной программы Силкчесс в Массачусетском технологическом институте