如何调整我的极小化极大搜索树以处理非基于回合的游戏？

Question

我需要完成一个项目，实现mancala棋盘游戏，并为其实现人工智能。指导我们需要修改或更改极小极大树，以便使其能够与mancala游戏配合使用，因为在该游戏中，玩家可能会连续多次行动。

我已经实现了我的游戏逻辑和GUI，但在开始实现AI之前，我想尝试了解一下它背后的理论。我在网上搜索非回合制的极小极大树，但似乎没有找到任何内容。但我看到很多人谈论在mancala中使用minimax。

现在我理解了正常的极小极大树，以及每个层级如何在一个最小节点和一个最大节点之间交替。对于我现在需要的树，如果第二个玩家有两个回合，我应该这么说： min>max>max>min>max 吗？

我们还需要能够指定Minimax树的给定ply深度。我们还需要进行Alpha Beta剪枝，但那是在我真正拥有树之后才需要考虑的事情。

- Zapnologica

Answer 1

根据我的理解，您的主要问题如下：您已经知道了如何在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
            # here is a small change
            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
            # here is a small change
            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。实际上，对于具有较大分支因子的游戏，使用此方法也没有问题。

- Salvador Dali

---

当有一个空闲的回合时，bestValue := max/min(bestValue, val) 中的max和min不应该改变吗？ - Helder Daniel

Answer 2

如果一方在一个回合中可以有多个移动，则必须有某种方法来检测。当检测到时，让对手的移动生成器生成一个仅包含空移动（即不执行任何操作的移动）的列表。对手将被迫执行该移动（即不做任何事情），然后第一位玩家可以计算出他的下一步。

- Kyle Jones

---

好的，那么它将保留最小值、最大值、最小值、最大值的结构，你会在每个重复的最大值之间放置一个无用的最小值吗？ - Zapnologica

是的，除非您有更好的想法。 - Kyle Jones

这会对可能的棋盘深度产生什么影响？ - Zapnologica

@KyleJones，我该如何放置一个无用的 min 或 max？ - Jane Kapoor