игровое дерево с минимаксной глубиной первого поиска

Question

Я хочу построить игровое дерево для игры nine men's morris.Я хочу применить минимаксный алгоритм к дереву для выполнения оценок узлов.Minimax использует DFS для оценки узлов.Итак, должен ли я сначала построить дерево до заданной глубины, а затем применить минимакс, или процесс построения дерева и оценки может происходить вместе в рекурсивном минимаксном DFS?

Спасибо Арвинд

Answer 1

Вы могли бы взглянуть на итеративное углубление первый поиск глубины.

Answer 2

Да, вы можете создавать и оценивать одновременно в рекурсивном минимаксе.
Это хороший подход, поскольку он позволит сэкономить место в памяти.

На самом деле, вы даже можете подать заявку альфа-бета обрезка в одно и то же время.

Редактировать: вот псевдокод из 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 α