游戏中的Minimax算法

Question

我正在尝试使用 minimax 算法创建我的第一个游戏，但我不知道如何使用树来实现它。

游戏规则如下：

在table上有M个立方体（例如40个），每个玩家必须从table中拿取1个或L个立方体（L在程序中定义。例如L=5).
获胜者是从 table 中拿走最后一个立方体的玩家。
第一个玩的是MAX（电脑），第二个玩的是MIN（人）。

首先我们必须运行 minimax 算法，然后玩家 MAX 使用最佳着法。

这是游戏，但我无法想象如何用树实现它。谁能帮我出出主意？

Answer 1

根据我的理解，通常（也许是最直观的方式）不是使用博弈树的显式表示，而是将算法的内部工作视为实际执行所需的动作，递归地评估动作，最后取消移动。这意味着游戏树中的导航由调用堆栈表示，可以看作是对隐式表示树的深度优先搜索。连续调用将分别采用任一对手的视角。

话虽如此，这样的实现在第一次尝试时可能并不容易。此外，请注意，您描述的游戏似乎与 Nim 密切相关，可能存在更有效的算法。

Answer 2

不是你造了一棵树，而是你的搜索可谓一棵树。

说是Tic-Tac-Toe，举个大家比较熟悉的例子。你是X，你有9种选择，9种可能的走法。

在那之后，碰巧的是，O 将有 8 种可能的着法。等等。

您可以执行 depth-first 搜索（一定要有深度限制），每次从 children 得到结果时，您都取最小值（或最大值）结果。

此页面通过 Tic-Tac-Toe 示例进行了更详细的讨论：http://neverstopbuilding.com/minimax。请注意，他们的算法是递归的，这使得累积 children 的分数相对简单。

Answer 3

minimax 计算应该通过深度优先搜索来执行。最好的方法是稍微抽象你的状态 space。实现一个名为 GetMoves 的函数，该函数 return 包含所有有效移动，以及一个 GameOver 函数，该函数 return 表示游戏结束。如果您不能搜索整棵树，您还应该限制搜索的深度（这将启用迭代加深）。那么你的代码是这样的（这只是伪代码）：

double maxPlayer(state, depth)
{
    if (state.GameOver() || depth == 0)
        return state.eval;
    auto moves = state.GetMoves();
    int best = NINF;
    for (m : moves)
    {
        state.ApplyMove(m);
        int tmp = minPlayer(state, depth-1);
        if (tmp > best)
            best = tmp;
        state.UndoMove(m);
    }
    return best;
}

这里需要编写相应的minPlayer函数。请注意，这不包括 alpha-beta 修剪。它也不是 return 最好的一步。您还可以使用 negamax 构造为 max/min 玩家编写一个函数而不是两个函数。

在您的情况下，您的移动可能只是整数，1 或 L。应用移动减去 1 或 L 立方，撤消移动增加 1 或 L 立方。

请注意，在此公式中，我们不检查树中的重复项，因此立方体的数量将呈指数增长。但是，由于您不关心确定获胜者的动作历史，因此您实际上只需要完整树中的 2M 个节点。使用 table 存储搜索结果 (memoization/transposition table) 会将树减少到最多 2M 个节点，而不是 2^M。

Answer 4

这个游戏可以用动态规划算法来解决。设置布尔数组 win[0] ... win[40]。如果游戏状态对您来说是赢家，每个元素中的值将为真，如果是输家则为假。最初 win[0] 为假。那么 win[1] 为真，因为有一个 1 比 0 的移动，另一方的失败位置所以你的获胜位置。 win[2] 则为假，因为没有任何动作将 2 带到失败的位置（对于另一方）。然后就可以按照这种方式填入数组的所有元素了。

一旦你有了数组，你的策略就是从获胜的位置移动到失败的位置。如果您一开始处于失败的位置，那么您只能希望其他玩家犯错并为您移动到获胜的位置。

游戏中的Minimax算法

Minimax algorithm in a game

algorithm

artificial-intelligence

minimax