minimax深度第一搜索游戏树

Question

我想为九个男人的莫里斯游戏构建一个游戏树。我想在树上应用minimax算法来做节点评估。 Minimax使用DFS来评估节点。那么我应该首先将树建立到给定深度，然后应用minimax，或者可以将树和评估的构建过程一起发生在递归极小极小DFS中？

谢谢 阿文德

Answer 1

你可以看看iterative deepening depth first search。

Answer 2

是的，你可以建立并在递归极小，同时评估。
这是一个很好的方法，因为它会节省内存空间。

事实上，你甚至可以在同一时间申请alpha-beta pruning。

编辑：这里是从维基Minimax伪代码：

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 α 

因为我们（可能）存储在每个节点的游戏/板的状态，我们可以嵌入 创建游戏状态的
在minimax算法，即

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 α