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

我想开发RISK棋盘游戏,其中包括用于计算机玩家的AI.Moreovor,我读了两篇文章,这个和这个,这事,我意识到,我必须了解蒙特卡罗模拟和马尔可夫链技术.我认为我必须一起使用这些技术,但我猜它们是与计算过渡状态概率相关的不同技术.

那么,有谁可以解释它们之间的重要区别和优缺点是什么？

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

在这里,您可以找到关于风险板游戏中战斗结果的简单确定概率,以及所使用的强力算法.有一个树图,指定所有可能的状态.我应该在这棵树上使用蒙特卡罗或马尔可夫链吗？

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

一个马尔可夫链是一个简单的系统从状态如何进入状态的模型.从头开始制作马尔可夫模型有时会很困难,但是一旦掌握了它们,它们就相对容易使用,并且相对容易理解.基本的想法是你的游戏会有某些与之相关的状态; 作为游戏的一部分,你将从一个州搬到另一个州; 而且,关键的是,这种从一个州到另一个州的运动是基于概率发生的,并且你知道这些概率.

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

短篇文章实际上是关于马尔可夫链的方法,但是 - 这很重要 - 它正在使用这种方法,只是作为一种快速的方法来估计如果军队A攻击领土并且军队B捍卫它将会发生什么.这是一种很好的使用技术,但它不是风险的AI,它只是AI中的一个模块,有助于找出可能的攻击结果.

相比之下,蒙特卡罗技术是估算器.一旦你有了某个模型,无论是马尔可夫模型还是其他模型,你经常会发现自己处于想要估计它的位置.(通常情况下,如果你足够眯眼,你就可以把它变成一种非常难以用这种格式工作的积分形式.)蒙特卡罗技术只是随机抽样并汇总结果估计会发生什么.

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

这就是他们的本质.如果我必须实施风险AI,您还会询问我将使用哪一个.好吧,这些都不够.正如我所说,蒙特卡洛不是一种人工智能技术,它是一种通用的数学工具.而Markov模型,虽然它们理论上可以代表整个风险游戏,但最终会变得非常笨拙:你需要代表游戏的每个状态,这意味着每个地区的军队配置和每个可能的配置手中的牌等等(我在很多细节上,这里:这种方法还有很多其他困难.)

沃尔夫论文的核心既不是马尔可夫方法,也不是蒙特卡罗方法,它实际上是他所描述的评价函数.这是人工智能问题的核心:如何找出最佳动作.Blatt论文中的蒙特卡罗方法描述了一种方法,可以找出一个动作的预期结果,但这与确定哪种动作最好是不一样的.此外,沃尔夫的论文中有一个低调的关于前瞻性难以在风险中执行的声明,因为游戏树变得非常庞大,这使得他(我认为)非常关注评估功能.

所以我真正的建议是:阅读搜索树方法,如minimax,alpha-beta修剪,尤其是expecti-minimax.您可以在Russell和Norvig,甚至维基百科上找到这些早期的良好治疗方法.试着理解为什么这些技术在一般情况下有效,但对于风险来说却很麻烦.这将引导您对电路板评估技术进行一些讨论.然后回过头看看沃尔夫的论文,重点关注他的行动评价功能.最后,关注他试图自动学习良好评估功能的方式.

这是很多工作.但是风险并不是开发人工智能的简单游戏.

(如果你只想弄清楚特定攻击的预期结果,我会说去蒙特卡罗.它很干净,非常直观易懂,而且非常容易实现.唯一的困难 - 它不是大的 - 确保你运行足够的试验以获得好的结果.)

马尔可夫链只是一组过渡及其概率,假设没有对过去事件的记忆.

蒙特卡罗模拟是对一组概率的随机遍历的重复采样.

您可以通过使用马尔可夫链来模拟概率,然后使用蒙特卡罗模拟来检查预期结果.

对于风险我不认为我会使用马尔可夫链,因为我没有看到优势.对您可能的动作进行蒙特卡罗分析可以帮助您提供一个非常好的AI以及合适的健身功能.

我知道这很多,但我希望它有所帮助.