极小深度优先搜索博弈树

Question

我想建立一个游戏树九名男子的莫里斯游戏。我想在树上申请极大极小算法做节点的评估。极小使用DFS评估节点。所以，我应该先建树高达一个给定的深度，然后应用极大极小或建造树和评估的过程中，可能会发生一起递归极小DFS？

感谢您 Arvind的

Answer 1

您可以看看迭代加深深度优先搜索。

Answer 2

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

实际上，甚至可以应用α-β在同一时间修剪。

修改这里是从伪代码维基极小 ：

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 α