algorithm - 如何调整我的 Minimax 搜索树来处理没有基于术语的游戏？

Question

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

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

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

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

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

Answer 1

据我所知，您的主要问题如下:您已经看到如何在 max/min 循环的情况下使用 minimax，现在您有一个游戏，有时一个玩家可以在一个行。

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

所以一般做法

标准的 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

用 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 次移动，都没有区别。

关于 gem 棋

gem 棋有多种变体，但游戏的分支因子非常小(据我所知<= 6)。现在假设您有三个 Action A、B、C、D 和 Action C 让你多玩一次。从 C 位置开始，您可以执行移动 C1、C2。所以你可以将它们组合起来(C + C1，C + C2)并将它们视为只是一步(应该做小簿记以记住这实际上是两步) .所以现在你结束了你的最小最大迭代，你没有 4 而是 5 步:A, B, C + C1, C + C2，D。实际上，对于分支因子较大的游戏，使用这种方法并没有错。