游戏中的Minimax算法

我试图使用minimax算法创建我的第一个游戏,但我不知道如何使用树实现这一点 .

游戏规则如下:

  • 在 table 上有M个立方体(例如40个),每个玩家必须从表1或L立方体中获取(L在程序中定义,例如L = 5) .

  • 获胜者是从表中获取最后一个立方体的玩家 .

  • 首先播放的播放器是MAX(电脑),第二播放MIN(人) .

首先,我们必须运行minimax算法,然后播放器MAX播放最佳移动 .

这是游戏,但我无法想象如何用树实现这个 . 任何人都可以帮助我并给我一个想法吗?

回答(4)

2 years ago

这不是您创建树,而是您的搜索可以描述为树 .

说它是Tic-Tac-Toe,采取一个更熟悉的例子 . 你是X.你有9个选项,9个可能的动作 .

在那之后,当它发生时,O将有8个可能的移动 . 等等 .

您可以执行深度优先搜索(确保深度限制),每次从子项中获得结果时,您都会获得最小(或最大)结果 .

本页讨论了一个更长的Tic-Tac-Toe示例:http://neverstopbuilding.com/minimax . 请注意,他们的算法是递归的,这使得积累孩子的分数相对简单 .

2 years ago

根据我的理解,通常(也许是最直观的方式)不是使用游戏树的显式表示,而是将算法的内部工作视为实际执行所需的移动,递归地评估移动并最终取消移动 . 这意味着游戏树中的导航由调用堆栈表示,并且可以被视为在隐式表示的树上的深度优先搜索 . 成功的召唤将分别采取对手的视角 .

话虽这么说,这样的实现在第一次尝试时可能并不容易 . 此外,请注意,您描述的游戏似乎与Nim密切相关,因为可能存在更高效的算法 .

2 years ago

最小极大值计算应该通过深度优先搜索来执行 . 最好的方法是略微抽象你的状态空间 . 实现一个名为 GetMoves 的函数,它返回所有有效的移动,以及一个在游戏结束时返回的 GameOver 函数 . 如果无法搜索整个树,也应该限制搜索的深度(这将启用迭代加深) . 然后你的代码就像(这只是伪代码):

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 函数 . 请注意,这并不是最好的举动 . 您还可以使用negamax形式为最大/最小玩家编写单个函数而不是两个函数 .

在您的情况下,您的移动可能只是整数,1或L.应用移动减去1或L立方体,撤消移动会添加1或L个立方体 .

请注意,在此公式中,我们不检查树中的重复项,因此它将是多维数据集的指数 . 但是,由于您不关心确定获胜者的操作历史,因此实际上只需要完整树中的2M节点 . 使用表来存储搜索结果(memoization / transposition table)会将树减少到最多2M个节点而不是2 ^ M .

2 years ago

可以使用动态编程算法来解决该游戏 . 设置一个布尔数组win [0] ... win [40] . 如果游戏的状态对你来说是胜利者,那么每个元素的值都是真的,如果它是失败者则是假的 . 最初win [0]是假的 . win [1]然后才是真的,因为有一个移动需要1到0,另一边是失败的位置,因此对你来说是一个胜利的位置 . win [2]然后是假的,因为没有移动将2输入到失败位置(对于另一方) . 然后,您可以以这种方式填充数组的所有元素 .

一旦你拥有阵列,你的策略就是从获胜位置转变为失去位置 . 如果你最初是在一个失败的位置开始,那么你所希望的只是让其他玩家犯错误并为你赢得一个胜利的位置 .