蒙特卡洛搜索树(MCST)算法应用实例

发布:2022-10-10 14:53:25
阅读:2091
作者:网络整理
分享:复制链接

用于增强个性化游戏体验的更高级方法是蒙特卡洛搜索树(MCST)算法。MCST算法是使用随机试验来解决问题。

MCST在游戏中的应用实例

这也是Deep Blue—1997年第一个击败人类国际象棋冠军的计算机程序使用的AI策略。对于国际象棋中的每一步,Deep Blue使用MCST算法考虑它可能做出的所有可能的移动,然后考虑人类玩家会跟进这种移动作出所有的反应,依此类推。可以想象所有可能的动作都在扩展,就像树枝从茎上长出来一样——这就是我们称之为“搜索树”的原因。

在多次重复此过程后,人工智能将计算回报,然后决定要遵循的最佳分支。在采取真正的行动之后,人工智能将根据可能的结果再次重复蒙特卡洛搜索树(MCST)算法。

在电子游戏中,许多策略游戏也应用了类似的算法。然而,由于可能的动作比国际象棋要多得多,因此不能考虑到所有可能性。因此,在这些游戏中,MCST算法会随机选择一些可能的动作。所以,策略游戏中的AI作出的操作对人类玩家来说变得更加不确定。

比如在《文明中,玩家在游戏中与做同样事情的游戏AI竞争开发城市,不可能为游戏AI预先编程每一个动作。MCST算法的AI不像FSM那样仅根据当前状态采取行动,而是评估一些可能的下一步行动,例如开发城市、攻击人类玩家、保卫堡垒等等。然后游戏AI会执行MCST算法来计算每个动作的总体回报,并选择最有价值的一个。

下图展示了蒙特卡洛搜索树(MCST)算法在游戏中的使用方式的简化流程图。在更加开放自由的游戏中,游戏情况的演变从来不是预先确定的,因此每次都能为玩家提供新鲜感,带来不一样的游戏体验。

扫码进群
微信群
免费体验AI服务