игровое дерево с минимаксной глубиной первого поиска
Вопрос
Я хочу построить игровое дерево для игры nine men's morris.Я хочу применить минимаксный алгоритм к дереву для выполнения оценок узлов.Minimax использует DFS для оценки узлов.Итак, должен ли я сначала построить дерево до заданной глубины, а затем применить минимакс, или процесс построения дерева и оценки может происходить вместе в рекурсивном минимаксном DFS?
Спасибо Арвинд
Решение
Вы могли бы взглянуть на итеративное углубление первый поиск глубины.
Другие советы
Да, вы можете создавать и оценивать одновременно в рекурсивном минимаксе.
Это хороший подход, поскольку он позволит сэкономить место в памяти.
На самом деле, вы даже можете подать заявку альфа-бета обрезка в одно и то же время.
Редактировать: вот псевдокод из wiki Минимаксный:
function integer minimax(node, depth)
if node is a terminal node or depth == 0:
return the heuristic value of node
α = -∞
for child in node: # evaluation is identical for both players
α = max(α, -minimax(child, depth-1))
return α
Поскольку мы (вероятно) храним состояние игры / доски в каждом узле, мы могли бы встроить
создание состояний игры
в минимаксном алгоритме, т. е.
function integer play_minimax(node, depth)
if node is a terminal node or depth == 0:
return the heuristic value of node
α = -∞
LOOP: # try all possible movements for this node/game state
player = depth mod 2
move = make_game_move(node, player)
break if not any move
α = max(α, -play_minimax(move, depth-1))
return α