13

对于井字游戏等游戏的两个玩家，极小极大算法得到了很好的描述。我需要为坦克游戏编写 AI。在这个游戏中，坦克必须在一个有墙壁形式障碍物的迷宫中移动。目标是收集硬币堆。如果只有两个玩家，则可以实现极小极大算法。但是如何实现两个以上呢？在每个回合中，每个玩家都会尝试最大化自己的获胜优势。我不能将所有玩家视为一个敌人，试图仅减少我的获胜优势，创建两个玩家级别，就像在原始的极小极大算法中一样。如果问题的格式不好，请原谅。这个论坛还是新手

4

3 回答 3

18

Mihai Maruseac 说 MiniMax 不能再使用只是部分正确。如果“MiniMax”指的是 MiniMax 的“标准变体”，那么他完全正确！（这就是他的意思。）但是，您也可以将 MiniMax 视为 MaxiMax，其中两个玩家各自最大化自己的奖励（这正是 AlphaWolf 在问题中所写的）。因此，对 n 个玩家的泛化称为Max^n，它仍然可以被视为 MiniMax，不知何故。无论如何，下面我将解释为什么标准的 2 人 MiniMax 确实不能用于 3 人或更多人的多人游戏环境。然后，最后，我给出了正确的替代方案，即Max^n算法的参考。

所以让我们首先考虑是否可以通过将所有对手都视为 Min-Players 来简单地将 2-player MiniMax 变成 n-player MiniMax，即他​​们都将尝试最小化 MAX 玩家的奖励。

好吧，你不能！让我解释一下为什么。

首先，回想一下 MiniMax 总是专门考虑 2 人零和游戏。因此，MiniMax 通常只用一个游戏结果来描述。但是，从技术上讲，有两个！MAX播放器的那个和MIN播放器的那个。因此，为了超形式上正确，必须为每个搜索节点提供一个 2 元组作为游戏结果，例如 (payoff-P1,payoff-P2)，其中 payoff-P1 是 P1 (MAX) 和 payoff 的结果-P2 是 P2 (MIN) 的结果。然而，由于我们通常考虑零和博弈，我们知道它们的总和总是为零，即 payoff-P1 + payoff-P2 = 0。因此，我们总是可以推断出对方的胜利，因此只代表来自P1的视角。此外，最小化收益-P2 与最大化收益-P1 相同。

对于几乎所有的游戏（除了现实生活中心理因素发挥作用的情况，比如报复而不考虑自己的损失），我们总是假设所有代理人都玩理性。当我们讨论两个以上的玩家时，这将非常重要！什么是理性？假设所有其他玩家也玩理性游戏，每个玩家的目标都是最大化他们自己的奖励（！）。

回到 2 人零和：我们确实利用/假设了理性，因为 P1 (MAX) 已经在最大化它的奖励（根据定义），而 MIN 也在最大化它自己的奖励，因为它正在最小化 MAX（即，因为零和与最大化 MINs 奖励相同）。因此，两个玩家都在最大化自己的奖励，因此玩得很理性。

现在让我们假设我们有超过 2 个玩家，为简单起见说 3 个。

不要让我们看看我们是否可以简单地用 MIN 玩家替换所有对手（有时会建议这样做，所以我发现从教学的角度来看它很有用）。如果我们这样做，两者都只会最小化 MAX 玩家的奖励，而 MAX 会继续最大化自己的奖励。然而，这在语义上意味着两个敌人合作对抗 MAX。这种合作打破了我们对理性的假设，即玩家不再最大化自己的奖励！（因此，最小化 MAX 的奖励仅相当于在有两个玩家时最大化自己的奖励，而不是在有更多玩家的情况下。）我举一个例子来说明：

在此处输入图像描述

我们在这里看到的是以下内容：

  • 像往常一样，我们有一个游戏树，其中三个玩家（P1、P2、P3）交替轮流。每个玩家有两个回合。最迟游戏在 3 步后结束（从技术上讲，P1 必须转身，但两个状态都是最终/叶子，所以游戏结束）。该游戏描述了一个 3 人零和游戏（尽管不再需要零和！所有描述的内容在没有这个假设的情况下也可以工作！）。
  • 最大胜利是 20，分配给 3 名玩家。（请注意，在我的版本中，所有胜利都是正数。但是，它仍然是零和，因为所有胜利总和的值完全相同，因此它可以很容易地转换为它们始终加起来为零的一个。 ) 胜​​利显示为元组“payoff-P1 / payoff-P2 / payoff-P3”。
  • 此外，我用两种不同的颜色展示了各自玩家所追求的策略：紫色是假设只有 P1 是 MAX 玩家而其他人只最小化其奖励的策略（不关心自己的奖励）。红色显示了假设所有玩家都是 MAX 玩家的理性策略，即最大化他们自己的奖励。

那么如果 P2 和 P3 被认为是 MIN 玩家，这个游戏会发生什么？他们会最小化 P1 的奖励，所以 P1 假设在玩 m1 时它只会收到 5，因为 P2 可以通过玩 m2 来最小化 P1 的奖励。因此 P1 将选择它的第二步 m2 赢得（仅）10。

然而，这两个对手都是 MIN 玩家的假设可以被视为两个玩家的合作（这是不合理的）。因为，在假设理性的情况下，玩家 P2 永远不会玩 m2，因为 P3 实际上会玩 m3（所以 P3 赢得 5 而不是 0）。但是假设所有对手都最小化 P1 将使 P2 选择 m2，因为这使 P3 能够玩 m1，从而将 P1 的胜利减少到 5（而不是如果 P3 理性地玩，则为 15）。因此，使用 MAX/MIN/MIN 策略可以找到（或假设）对手合作对抗 P1/MAX 的策略，这在现实中（假设理性）永远不会发生！所以 MiniMax 适应超过 2 名玩家显然是错误的。（即，在检测永远不会发生的情况方面过于悲观。）我们可以在图中看到，当假设理性代理人时，

这是为了表明 MiniMax 必须以不同的方式进行扩展。

应该如何显而易见：简单地用一个向量分别表示每个玩家的结果，如上所述。而不是根据轮到谁来最大化或最小化，我们总是最大化当前玩家的结果。由此产生的算法也被称为Max^n用于 n 个玩家。再次注意，MiniMax 仅Max^2包含元组 (payoff-P1,payoff-P2)，其中 payoff-P2 定义为 -payoff-P1。

该Max^n算法由 CA Luckhardt 和 KB Irani 在“N 人游戏的算法解决方案”中描述，第五届全国人工智能会议论文集 (AAAI'86)，p.158-162，AAAI 出版社。该论文可在以下网址公开获取：https ://www.aaai.org/Papers/AAAI/1986/AAAI86-025.pdf

请注意，Max^n由于搜索空间（即博弈树）呈指数增长，因此在实践中从未使用过 MiniMax。相反，人们总是使用 Alpha/Beta 修剪，这是一种相当直观的扩展，它永远不会访问/探索树的分支，无论如何搜索都毫无意义。Alpha/Beta 还扩展到适用于 n 玩家游戏 (n>2)，Richard Korf 在《人工智能》第 48 期（1991 年）第 99-111 页的“多人 alpha-beta 修剪”中进行了描述。该文章可在以下网址公开获取：https ://www.cc.gatech.edu/~thad/6601-gradAI-fall2015/Korf_Multi-player-Alpha-beta-Pruning.pdf

最后，让我添加一个非常有趣的观察：在 2 人零和 MiniMax 中，计算的策略是“完美的”，因为它肯定会至少实现 MiniMax 保证/计算的胜利。如果对手打得不理性，即偏离了自己的策略，那么结果只会更高。在 n 玩家零和 MiniMax 中，即，Max^n，现在不是这样了！回想一下，P1 的理性策略是玩 m1 从而赢得 15（如果对手玩理性）。但是，如果对手不理智地打球，那么几乎所有事情都会发生。在这里，如果P2确实非理性地打m2，那么P1的输出完全取决于P3的做法，所以P1也可以严重少赢。原因在于，在 2 人零和游戏中，对手的行为会直接影响自己的结果——而且仅此而已！但是如果有 3 个或更多玩家，胜利也可以分配给其他玩家。

于 2020-08-27T04:40:19.357 回答
5

您不能再为此使用极小极大。除非您制定一个混合目标，即最大化一个人的利润和最小化另一个人的利润总和。但这很难实现。

更好的是创建能够在战略层面上学习需要做什么的算法。将游戏转变为两人游戏：我与其他人，从这里开始。

于 2013-02-12T12:49:35.000 回答
-1

如何使用多个最小化代理处理最小化函数是运行一个最小化函数，所有代理的深度相同。一旦最小化代理全部通过，您就可以在最后一个最小化代理上运行最大化函数。

# HOW YOU HANDLE THE MINIMIZING FUNCTION - If this pseudocode helps make better sense out of this.
scores = []
if agent == end_of_minimizing_agents: # last minimizing agent
    for actions in legal_actions: 
        depth_reduced = depth-1
        scores.append(max(successor_state, depth_reduced))
else:
    for actions in legal_actions: 
        scores.append(min(successor_state, depth))
bestScore = min(scores)
return bestScore
于 2019-09-28T00:52:27.660 回答