极小极大深度优先搜索游戏树

Question

我希望为“九子棋”游戏构建一棵博弈树。我想在树上应用极小化极大算法进行节点评估。极小化极大算法使用深度优先搜索来评估节点。因此，我是先构建树到给定深度，然后再应用极小化极大算法呢？还是可以同时进行递归极小化极大深度优先搜索的树的构建和评估过程？

谢谢 阿尔温德

- Arvind

Answer 1

在递归的极小化最大化算法中，您可以同时构建和评估。
这是一个好方法，因为它可以节省内存空间。

实际上，您甚至可以同时应用alpha-beta剪枝。

编辑：这里是维基百科极小化最大化算法的伪代码:

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 α

- Nick Dandoulakis

---

谢谢。有没有Java实现或伪代码可以参考的地方？ - Arvind

Answer 2

你可以看一下迭代加深深度优先搜索。

- Mark Byers