为什么零和完美信息博弈满足冯诺依曼定理的条件?

人工智能 博弈论 搜索 极小极大
2021-11-14 08:25:07

冯诺依曼的Minimax 定理给出了使max-min 不等式相等的条件。

我基本上了解最大最小不等式min(max(f))>=max(min(f))

冯诺依曼定理指出,对于给定的 y,不等式变为等式f(.,y)应该始终是凸的,对于给定f(x,.)的 x 应该始终是凹的,这也是有道理的。

该视频说,对于零和完美信息博弈,冯诺依曼定理始终成立,因此极小极大始终等于极大极小,我并没有完全遵循。

问题

  • 为什么零和完美信息博弈满足冯诺依曼定理的条件?

  • 如果我们将规则放宽为非零和或非完美信息,条件将如何变化?

1个回答

以下是专门介绍 Minimax 在井字游戏求解中的应用的众多网页之一:博弈论中的 Minimax 算法 | 第 3 组(井字游戏 AI - 寻找最佳移动)

谷歌搜索会产生很多这样的结果。(当我有更多时间时,我会回到这个答案,并发布更多包含更多上下文的链接。)

以下是关于如何在非机会、完美信息、顺序、党派、零和游戏集[M]中使用极小极大值的高级解释

  • 非极小极大评估函数将寻求将整数放置在游戏板上赋予最大值(权力和影响力)的位置
  • 极小极大评估函数将寻求将整数放置在游戏板上的最大价值位置,同时最小化对手下一次放置的最大值

这部分是由于在 [M] 游戏中使用了“资源窃取策略”。


注意:除了零和、完全信息博弈之外,我需要对有关应用程序的子问题做更多的思考,但我认为这没有任何问题。Minimax/maximin 在一系列上下文中具有广泛和基本的效用,与游戏没有严格的关系,除非每个问题都可以理解为一种游戏或谜题。