6

我必须做一个项目，我们需要实现 mancala 棋盘游戏，然后还为它实现 AI。

我们被告知，我们需要修改或更改极小极大树以能够与 mancala 一起使用，因为在游戏中玩家可以连续进行多个回合。

我已经实现了我的游戏逻辑和 GUI，但现在在我开始使用 AI 之前，我想尝试了解它背后的理论。我在网上搜索了基于非回合的迷你最大树，但我似乎找不到任何东西。但是我看到很多人在谈论使用 minimax 做 mancala。

现在我了解了正常的极小极大树以及每个级别如何在最小节点和最大节点之间交替。有了我现在需要的树，我会说： min > max > max > min > max如果第二个玩家有两个回合？

我们还需要能够指定 Minimax 树的给定层深度。我们还需要进行 alpha beta 修剪，但那是稍后，一旦我真的有一棵树。

4

2 回答 2

4

据我了解，您的主要问题如下：已经向您展示了如何在 max / min 循环的情况下使用 minimax，现在您有一个游戏，有时一个玩家可以连续执行多个动作。

我将向您解释基本上适用于任何游戏的一般方法，然后我将添加一些可以为 mancala 以不同方式完成的事情。

所以一般做法

标准极小极大是这样的：

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

用 max/min 初始化 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 次，此算法都没有区别。

关于曼卡拉

mancala 有很多变体，但游戏的分支因子非常小（我知道的那个是 <= 6）。现在假设你有 3 个动作A, B, C,D和 moveC可以让你再玩一次。从C你可以做动作的位置C1，C2。因此，您可以将它们组合在一起（C + C1, C + C2）并将它们视为一个动作（应该做一些小簿记以记住这实际上是两个动作）。所以现在你最终得到了你的最小最大迭代，你没有 4 步而是 5 步：A, B, C + C1, C + C2, D. 实际上，将这种方法用于具有较大分支因子的游戏并没有错。

于 2015-10-21T04:54:20.047 回答
0

如果一方可以在一个回合中有多个动作，那么必须有某种方法可以检测到这一点。当检测到对手的移动生成器时，生成一个仅包含空移动的列表，即什么都不做的移动。对手将被迫下这个动作（什么都不做），然后第一个玩家可以计算他的下一步动作。

于 2013-05-21T04:45:31.413 回答