根据我的理解,您的主要问题如下:您已经知道了如何在max/min循环的情况下使用minimax,但现在您的游戏有时一个玩家可以连续做多个动作。
我将向您解释适用于基本任何游戏的一般方法,然后再补充几件为曼卡拉不同的事情。
一般方法如下:
标准minimax是这样进行的:
function minimax(node, depth, maximizingPlayer)
if depth = 0 or node is a terminal node
return the heuristic value of node
if maximizingPlayer
bestValue := -∞
for each child of node
val := minimax(child, depth - 1, FALSE)
bestValue := max(bestValue, val)
return bestValue
else
bestValue := +∞
for each child of node
val := minimax(child, depth - 1, TRUE)
bestValue := min(bestValue, val)
return bestValue
在你初始化极大/极小minimax调用时,它会不断变化。在你的情况下,你只需要添加一个微小的检查。
function minimax(node, depth, maximizingPlayer)
if depth = 0 or node is a terminal node
return the heuristic value of node
if maximizingPlayer
bestValue := -∞
for each child of node
if freeTurn(child):
isMax := TRUE
else:
isMax := FALSE
val := minimax(child, depth - 1, isMax)
bestValue := max(bestValue, val)
return bestValue
else
bestValue := +∞
for each child of node
if freeTurn(child):
isMax := FALSE
else:
isMax := TRUE
val := minimax(child, depth - 1, isMax)
bestValue := min(bestValue, val)
return bestValue
您的函数
freeTurn
返回您在当前移动之后是否有免费转换。请注意,对于此算法,您连续进行2次操作还是5次操作没有区别。
关于曼卡拉游戏:
曼卡拉游戏有许多变体,但它的分支因子非常小(在我所知道的那个变体中是<=6)。现在假设您有三个步骤A、B、C、D,步骤C使您可以再玩一次游戏。从位置C,您可以执行步骤C1、C2。因此,您可以将它们组合起来(C + C1,C + C2)并将它们视为一个步骤(需要做一些小型记账以记住这实际上是两个步骤)。因此,现在您拥有5个步骤而不是4个步骤的最小极大迭代:A、B、C + C1、C + C2、D。实际上,对于具有较大分支因子的游戏,使用此方法也没有问题。