极小极大算法已被广泛用于两人游戏,如井字棋。我需要为坦克游戏编写人工智能。在这个游戏中,坦克必须在迷宫中移动,而迷宫中有墙壁等障碍物。目标是收集硬币堆。如果只有两位玩家,则可以实现极小极大算法。但如何为多于两名的玩家实现它呢? 因为在每个回合中,每个玩家都会尽力最大化自己的胜利优势。我不能把所有玩家都视为一个敌人,试图通过创建原始极小极大算法中的两个玩家级别来减少只有我自己的胜利优势。 如果问题格式不好,请谅解。我还是新来这个论坛的。
极小极大算法已被广泛用于两人游戏,如井字棋。我需要为坦克游戏编写人工智能。在这个游戏中,坦克必须在迷宫中移动,而迷宫中有墙壁等障碍物。目标是收集硬币堆。如果只有两位玩家,则可以实现极小极大算法。但如何为多于两名的玩家实现它呢? 因为在每个回合中,每个玩家都会尽力最大化自己的胜利优势。我不能把所有玩家都视为一个敌人,试图通过创建原始极小极大算法中的两个玩家级别来减少只有我自己的胜利优势。 如果问题格式不好,请谅解。我还是新来这个论坛的。
那么,如果将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个玩家显然是错误的。 (在一定程度上,即检测绝不会发生的情况时过于悲观。)我们可以看到,在假设理性代理的情况下,P1应该玩m1而不是m2,从而赢得15分而不仅仅是10分。
这是为了说明MiniMax必须以“不同”的方式扩展。
显然,只需按照上述方法,用向量分别表示每个玩家的结果。与其根据轮到谁来最大化或最小化,我们始终最大化当前玩家的结果。因此,得出的算法也被称为n人Max^n
。请注意,MiniMax只是使用元组(支付-P1,支付-P2)的Max^2
,其中定义了payoff-P2为-payoff-P1。Max^n
算法,收录于第五届人工智能国家会议论文集(AAAI'86),第158-162页,由AAAI Press出版。该论文可公开获取:https://www.aaai.org/Papers/AAAI/1986/AAAI86-025.pdf
请注意,由于搜索空间(即游戏树)呈指数级增长,实际上从不使用MiniMax,因此也从不使用Max^n
。相反,人们总是使用Alpha/Beta剪枝,这是一种相当直观的扩展,可以避免访问/探索树的无意义分支。Alpha/Beta也被扩展为适用于n个玩家(n>2)的游戏,Richard Korf在《人工智能》48(1991)中描述了这一点,第99-111页。该文章可公开获取:https://www.cc.gatech.edu/~thad/6601-gradAI-fall2015/Korf_Multi-player-Alpha-beta-Pruning.pdf
最后,让我补充一点非常有趣的观察结果:
在二人零和MiniMax中,计算出的策略是“完美的”,因为它肯定会至少实现由MiniMax保证/计算的胜利。如果对手玩得不理性,即偏离其策略,则结果只能更高。
但在n人零和MiniMax中,即Max^n
,情况就不再如此!回想一下,P1的理性策略是玩m1,从而赢得15(如果对手理性地玩)。然而,如果对手不理性地玩m2,那么P1的输出完全取决于P3的行动,因此P1也可能赢得更少。原因在于,在二人零和中,对手的行动直接影响自己的结果--仅限于这种情况!但是,对于三个或更多的玩家,胜利也可以分配给其他玩家。对于这个问题,你不能再使用极小极大算法。除非你将最大化自己的利润和最小化对手利润总和这两个目标结合起来。但是这个方法很难实现。
更好的方法是创建能够在战略层面上学习需要做什么的算法。将游戏转化为一个双人对抗的形式:我vs.其他人,然后从这里开始。
如何处理具有多个最小化代理的最小化函数是运行一个具有所有代理相同深度的最小化函数。一旦所有最小化代理都经过了,您可以在最后一个最小化代理上运行最大化函数。
# 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