artificial-intelligence - 蒙特卡罗和马尔可夫链技术有什么区别？

Question

我想开发 RISK 棋盘游戏，其中包括面向计算机玩家的 AI。另外，我看了两篇文章，this和 this ，关于它，我意识到我必须学习蒙特卡罗模拟和马尔可夫链技术。我认为我必须一起使用这些技术，但我想它们是与计算过渡状态概率相关的不同技术。

那么，谁能解释一下它们之间的重要区别和优缺点？

最后，如果您要为 RISK 游戏实现 AI，您会更喜欢哪种方式？

Here您可以找到关于风险棋盘游戏中战斗结果的简单确定概率，以及所使用的蛮力算法。有一个树状图，其中指定了所有可能的状态。我应该在这棵树上使用蒙特卡罗还是马尔可夫链？

Answer 1

好的，所以我浏览了这些文章以了解他们在做什么。以下是我对您询问的条款的概述:

马尔可夫链只是您的系统如何从一个状态移动到另一个状态的模型。从头开始开发马尔可夫模型有时可能很困难，但一旦掌握了，它们就相对容易使用，也相对容易理解。基本思想是您的游戏将具有与之相关的某些状态；作为游戏的一部分，你会从一个州转移到另一个州；并且，关键的是，这种从一个状态到另一个状态的移动是基于概率发生的，并且您知道这些概率。

获得这些信息后，您可以将其全部表示为图形，其中节点是状态，状态之间的弧线(用概率标记)是转换。您还可以表示为满足某些约束的矩阵，或其他几种更奇特的数据结构。

这篇短文实际上是关于马尔可夫链方法的，但是——这很重要——它使用这种方法只是作为一种快速的方法来估计如果军队 A 攻击一个领土而军队 B 保卫它会发生什么。这是该技术的一个很好的用途，但它不是风险 AI，它只是 AI 中的一个模块，可帮助确定攻击的可能结果。

相比之下，蒙特卡罗技术是估计器。一旦你有了某个东西的模型，无论是马尔可夫模型还是其他任何模型，你经常会发现自己处于想要估计它的位置。 (通常它碰巧是你可以的，如果你足够用力地眯眼，将其转化为在那种格式下很难处理的东西的积分形式。)蒙特卡洛技术只是随机抽样并汇总结果进入对将要发生的事情的估计。

在我看来，蒙特卡罗技术不是人工智能技术。它们是一种非常通用的技术，碰巧对 AI 有用，但它们本身并不是 AI。 (你可以对马尔可夫模型说同样的话，但这种说法较弱，因为马尔可夫模型对于人工智能中的规划非常有用，人工智能的整个哲学都是围绕该技术建立的。马尔可夫模型也被用于其他地方。 )

所以这就是他们。您还问我如果必须实现风险人工智能，我会使用哪一个。好吧，这些都不够。正如我所说，蒙特卡罗不是一种人工智能技术，它是一种通用的数学工具。马尔可夫模型虽然理论上可以代表整个风险游戏，但最终会变得非常笨拙:你需要代表游戏的每一个状态，这意味着领土上的每一种可能的军队配置和每一种可能的配置手中的卡片等(我在这里掩盖了许多细节:这种方法还有很多其他困难。)

Wolf论文的核心既不是马尔科夫方法也不是蒙特卡洛方法，它实际上是他所描述的评价函数。这是 AI 问题的核心:如何找出最佳行动。 Blatt 论文中的 Monte Carlo 方法描述了一种确定 Action 预期结果的方法，但这与确定最佳 Action 不同。此外，Wolf 的论文中有一个低调的陈述，即在 Risk 中很难执行前瞻，因为博弈树变得非常大，这也是他(我认为)如此关注评估函数的原因。

所以我真正的建议是:阅读搜索树方法，如极小极大、alpha-beta 剪枝，尤其是期望极小极大。您可以在 Russell 和 Norvig 或什至在 Wikipedia 上找到这些早期的好的治疗方法。尝试了解为什么这些技术通常有效，但对 Risk 来说却很麻烦。这将引导您对电路板评估技术进行一些讨论。然后回去看Wolf的论文，重点是他的 Action 评价函数。最后，关注他尝试自动学习一个好的评估函数的方式。

这是很多工作。但风险不是一个容易开发人工智能的游戏。

(不过，如果你只想弄清楚给定攻击的预期结果，我会说去蒙特卡洛。它很干净，理解起来非常直观，而且很容易实现。唯一的困难 - 它不是一个最大的问题是确保您进行了足够的试验以获得良好的结果。)