МТД(ж)

MTD(f) — это альфа-бета- алгоритм поиска в дереве игры, модифицированный для использования начальных границ поиска «нулевого окна» и памяти (обычно таблицы транспонирования ) для повторного использования промежуточных результатов поиска. MTD(f) — это сокращенная форма MTD(n,f), которая обозначает тестовый драйвер с расширенной памятью с узлом «n» и значением «f». ^[1] Эффективность этой парадигмы зависит от хорошего начального предположения и предположения, что окончательное минимаксное значение находится в узком окне вокруг предположения (которое становится верхней/нижней границей для поиска от корня). Структура памяти используется для сохранения первоначального предположения, определенного в другом месте.

MTD(f) был представлен в 1994 году и в значительной степени вытеснил NegaScout (PVS), ранее доминирующую парадигму поиска для шахмат , шашек , отелло и других игровых автоматов. ^{[ нужна ссылка ]}

Источник

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

Название MTD(f) расшифровывается как Test Driver с расширенной памятью, отсылая к Judea Pearl . алгоритму тестирования ^{[ нужна ссылка ]} который выполняет поиск с нулевым окном. MTD(f) подробно описан в докторской диссертации Аске Плаат 1996 года. ^{[ нужна ссылка ]}

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

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

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

Псевдокод

function MTDF(root, f, d) is
    g := f
    upperBound := +∞
    lowerBound := −∞

    while lowerBound < upperBound do
        β := max(g, lowerBound + 1)
        g := AlphaBetaWithMemory(root, β − 1, β, d)
        if g < β then
            upperBound := g 
        else
            lowerBound := g

    return g

f: Сначала угадайте лучшее соотношение цены и качества. Чем лучше, тем быстрее сходится алгоритм. Может быть 0 для первого звонка.
d: Глубина для цикла. Итеративный поиск в глубину с углублением можно выполнить, вызвав MTDF() несколько раз с возрастанием d и обеспечивая лучший предыдущий результат в f. ^[5]

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

Описание

MTD(f) вызывает поиск с нулевым окном из корня дерева. Эффективность работы MTD(f) зависит от таблицы транспонирования. ^[6]

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

В тестах с программами турнирного качества, такими как Chinook (шашки), Phoenix (шахматы) и Keyano (Отелло), алгоритм MTD(f) превзошел все другие алгоритмы поиска. ^[4] последние алгоритмы, такие как Best Node Search, Предполагается, что превосходят MTD(f).

Ссылки

^ Йоханнес Фюрнкранц; Мирослав Кубат (2001). Машины, которые учатся играть в игры . Издательство Нова. стр. 95–. ISBN 978-1-59033-021-0 .
^ «Адаптивные стратегии MTD-f для реальных игр» . Токийский университет сельского хозяйства и технологий. К. ШИБАХАРА и др.
^ Теофило Гонсалес; Хорхе Диас-Эррера; Аллен Такер (7 мая 2014 г.). Справочник по вычислительной технике, третье издание: Информатика и разработка программного обеспечения . ЦРК Пресс. стр. 38–. ISBN 978-1-4398-9853-6 .
^ Jump up to: ^а ^б Плаат, Аске; Джонатан Шеффер; Вим Пейлс; Арье де Брюэн (ноябрь 1996 г.). «Минимаксные алгоритмы с фиксированной глубиной и лучшими первыми» . Искусственный интеллект . 87 (1–2): 255–293. дои : 10.1016/0004-3702(95)00126-3 .
^ «Аске Плаат: MTD(f), новый шахматный алгоритм» .
^ При использовании MTD(f) в программах, страдающих выраженным нечетно-четным эффектом, где оценка в корне выше для четных глубин поиска и ниже для нечетных глубин поиска, желательно использовать отдельные значения для f для запуска ищите как можно ближе к минимаксному значению. В противном случае для поиска минимаксного значения потребуется больше итераций, особенно для функций мелкозернистой оценки.

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

Описание алгоритма MTD(f)

[FürnkranzKubat2001-1] Йоханнес Фюрнкранц; Мирослав Кубат (2001). Машины, которые учатся играть в игры . Издательство Нова. стр. 95–. ISBN 978-1-59033-021-0 .

[2] «Адаптивные стратегии MTD-f для реальных игр» . Токийский университет сельского хозяйства и технологий. К. ШИБАХАРА и др.

[GonzalezDiaz-Herrera2014-3] Теофило Гонсалес; Хорхе Диас-Эррера; Аллен Такер (7 мая 2014 г.). Справочник по вычислительной технике, третье издание: Информатика и разработка программного обеспечения . ЦРК Пресс. стр. 38–. ISBN 978-1-4398-9853-6 .

[ai-4] Jump up to: ^а ^б Плаат, Аске; Джонатан Шеффер; Вим Пейлс; Арье де Брюэн (ноябрь 1996 г.). «Минимаксные алгоритмы с фиксированной глубиной и лучшими первыми» . Искусственный интеллект . 87 (1–2): 255–293. дои : 10.1016/0004-3702(95)00126-3 .

[5] «Аске Плаат: MTD(f), новый шахматный алгоритм» .

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

[1]

[2]

[3]

[4]

[5]

[6]