Как реализовать итеративное углубление с альфа-бета-обрезкой

Я пишу программу для игры в точки и квадраты и хочу повысить эффективность своего времени, упорядочивая ходы, которые я рассматриваю в alphaBeta, на основе их эвристических значений в итеративной схеме углубления. По сути, я хочу войти в дерево поиска, увеличивая глубину с каждой итерацией, и оценивать каждый узел с помощью alphaBeta. В каждой последующей итерации порядок, в котором я рассматриваю узлы, будет определяться эвристическими значениями узлов из предыдущей итерации. Однако у меня возникли проблемы с пониманием того, как это будет реализовано. Может ли кто-нибудь предоставить псевдокод того, как стандартная программа alphaBeta будет адаптирована для поиска с использованием итеративного углубления? Спасибо!


java minimax alpha-beta-pruning iterative-deepening
person A. Romer    schedule 20.01.2017    source источник

Ответы (2)


arrow_upward
7
arrow_downward

Ну, Итеративное углубление реализовать несложно. Если у вас уже есть функция для выполнения поиска, назовем ее alphaBetaAtRoot, которая выполняет поиск с фиксированным расстоянием, вы просто вызываете ее повторно, начиная с расстояния 1:

for(int distance = 1; distance < MAX_DISTANCE && !outOfTime(); distance++) {
  bestmove = alphaBetaAtRoot(position, distance);
}
play(bestmove);

Однако важно, чтобы вы внедрили таблицу транспонирования. В противном случае вы не получите выгоды от лучшего порядка ходов, так как каждый поиск будет начинаться с нулевого знания.

person Philipp Claßen    schedule 21.01.2017
comment
Спасибо! Я не понимал необходимости таблицы транспонирования. Я сделал еще немного чтения, и это очень помогло. - person A. Romer; 24.01.2017
comment
Я не уверен, насколько хорошо это работает, потому что при каждом увеличении расстояния вы будете снова искать предыдущую глубину. Например, после поиска всего на расстоянии 1 вам придется исследовать все на расстоянии один снова перед поиском на глубине 2. - person David Chopin; 15.10.2020
comment
@DavidChopin Это комбинация двух наблюдений: во-первых, порядок ходов очень важен. Начиная с лучшего хода, можно сохранить значительную часть дерева поиска. Во-вторых, поскольку дерево поиска экспоненциально растет с глубиной поиска, поиск, как кажется, требует меньше накладных расходов. В конце концов, деревья, которые вам нужно искать снова, экспоненциально меньше, чем дерево на самом высоком уровне. - person Philipp Claßen; 15.10.2020
comment
Ах, хороший момент. Я полагаю, что после поиска на заданной глубине мы можем обрезать гораздо больше родственных узлов для любых последующих поисков на большей глубине. - person David Chopin; 15.10.2020

arrow_upward
2
arrow_downward

Я нашел следующую ссылку: https://github.com/nealyoung/CS171/blob/master/AI.java Надеюсь, это вам поможет.

person Iaido42    schedule 27.01.2017
comment
Добро пожаловать в СО. Обратите внимание, что ответы, содержащие только ссылки, не соответствуют стандартам этого сайта. См. stackoverflow.com/help/how-to-answer. - person Uwe Allner; 27.01.2017
comment
Вау! Большое спасибо! - person A. Romer; 29.01.2017