8

我想开发RISK 棋盘游戏,其中包括电脑玩家的人工智能。此外,我读了两篇关于它的文章,thisthis,我意识到我必须学习蒙特卡罗模拟马尔可夫链技术。我认为我必须一起使用这些技术,但我想它们是与计算过渡态概率相关的不同技术。

那么,谁能解释一下它们之间的重要区别和优缺点是什么?

最后,如果您要实现 AI for RISK 游戏,您会更喜欢哪种方式?

在这里,您可以找到关于风险棋盘游戏中战斗结果的简单确定概率,以及使用的蛮力算法。有一个树形图,它指定了所有可能的状态。我应该在这棵树上使用 Monte Carlo 还是 Markov 链?

4

2 回答 2

11

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

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

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

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

相比之下,蒙特卡洛技术是估计量。一旦你有了一个模型,无论是马尔可夫模型还是其他模型,你经常会发现自己处于想要估计它的位置。(通常情况下,如果你足够用力地眯着眼睛,你可以把它变成一个在这种格式下碰巧很难处理的东西的积分形式。)蒙特卡洛技术只是随机抽样并汇总结果估计会发生什么。

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

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

Wolf 论文的核心既不是马尔可夫方法也不是蒙特卡洛方法,它实际上是他所描述的评价函数。这是 AI 问题的核心:如何找出最佳行动。Blatt 论文中的 Monte Carlo 方法描述了一种计算动作的预期结果的方法,但这与找出最佳动作不同。此外,Wolf 的论文中有一个低调的陈述,即由于博弈树变得非常大,预测很难在风险中执行,这就是导致他(我认为)如此关注评估功能的原因。

所以我真正的建议是:阅读搜索树方法,如极小极大、α-β 修剪,尤其是期望极小极小。您可以在早期的 Russell 和 Norvig 甚至在 Wikipedia 上找到对这些问题的良好治疗方法。尝试理解为什么这些技术通常有效,但对风险来说很麻烦。这将引导您讨论董事会评估技术。然后回去看Wolf的论文,重点是他的动作评价函数。最后,关注他尝试自动学习良好评估函数的方式。

这是很多工作。但要为其开发人工智能,Risk 并不是一款简单的游戏。

(不过,如果你只是想弄清楚给定攻击的预期结果,我会说去蒙特卡洛。它很干净,很容易理解,而且很容易实现。唯一的困难——而且它不是最重要的——确保你进行了足够多的试验以获得好的结果。)

于 2013-05-07T18:07:46.473 回答
6

Markov chains are simply a set of transitions and their probabilities, assuming no memory of past events.

Monte Carlo simulations are repeated samplings of random walks over a set of probabilities.

You can use both together by using a Markov chain to model your probabilities and then a Monte Carlo simulation to examine the expected outcomes.

For Risk I don't think I would use Markov chains because I don't see an advantage. A Monte Carlo analysis of your possible moves could help you come up with a pretty good AI in conjunction with a suitable fitness function.

I know this glossed over a lot but I hope it helped.

于 2013-05-07T16:35:58.903 回答