我想为九人莫里斯游戏建立一个游戏树。我想在树上应用 minimax 算法来进行节点评估。Minimax 使用 DFS 来评估节点。那么我应该先将树构建到给定的深度,然后再应用 minimax,还是可以在递归 minimax DFS 中同时进行构建树和评估的过程?
谢谢阿文德
是的,您可以在递归 minimax 中同时构建和评估。
这是一个很好的方法,因为它可以节省内存空间。
实际上,您甚至可以同时应用alpha-beta 修剪。
编辑:这是来自 wiki 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 α
由于我们(可能)在每个节点中存储游戏/棋盘状态,我们可以将游戏状态的创建嵌入到
极小极大算法中,即
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 α
你可以看看迭代加深深度优先搜索。