#产业气象站#AI研习丨专题：爱恩斯坦棋中概率启发的并行蒙特卡洛树搜索算法
【#产业气象站#AI研习丨专题：爱恩斯坦棋中概率启发的并行蒙特卡洛树搜索算法】本文提出一种概率启发的并行蒙特卡洛树搜索算法 ， 用于解决爱恩斯坦棋的随机性带来的问题 。 一方面 ， 针对随机事件的表示问题 ， 该算法在博弈树中使用概率节点表示掷骰子事件 ， 以多对多的形式连接概率节点与最大值、最小值节点；另一方面 ， 该算法通过修改随机事件的概率值 ， 引导线程选择不同的搜索方向 。 实验证明 ， 概率启发的并行蒙特卡洛树搜索算法具有较高的搜索效率和智能水平 。
关键字
计算机博弈；爱恩斯坦棋；蒙特卡洛方法；并行计算
0引言
计算机博弈（ComputerGame） ， 也称为机器博弈 ， 是人工智能的一个重要分支 。 计算机博弈可以通俗地理解为让计算机通过模拟人类思维过程来下棋 ， 自诞生以来便受到世界各地学者的关注 ， 被誉为人工智能的“果蝇” 。
爱恩斯坦棋(EinSteinWürfeltNicht! ， EWN)是具有随机性的完备信息博弈棋种 。 棋盘及规则如图1所示 ， 使用5×5大小的方格形棋盘 。 红蓝双方都有标着1~6号的6枚棋子 ， 行棋前双方可在各自出发区(如图1(a)所示的棋子位置)随意摆放棋子 。 双方轮流走子 ， 每轮走子前须投掷骰子 ， 走动与骰子点数相同的棋子 。 若该棋子不存在 ， 则走动大于或小于骰子点数且与骰子点数最接近的棋子 ， 如图1(b)所示 。 若目标棋位上存在棋子 ， 则移除(吃掉)该棋子 。 当我方任意棋子到达对方区域的角部位置或吃掉对方全部棋子时获胜 ， 如图1(c)和(d)所示 。
蒙特卡洛树搜索(MonteCarloTreeSearch ， MCTS)算法是博弈树搜索算法中广为使用的算法之一 ， 它是一种通过大量的蒙特卡洛模拟统计在博弈树中寻找最优解的方法 。 然而 ， 传统的MCTS算法并没有表示爱恩斯坦棋行棋过程中的投骰子动作 。 为解决该问题 ， 一般在博弈树中引入骰子节点表示投骰子事件 ， 如图2所示 。
文章图片
但是 ， 在对弈中后期 ， 经常会出现多个骰子点数允许走动同一棋子的情况 ， 因此上述博弈树中会存在大量冗余节点 ， 导致MCTS算法重复模拟 。 针对上述问题 ， 本文提出概率启发的并行蒙特卡洛树搜索（ProbabilityHeuristicParallelMonte-CarloTreeSearch ， PPMCTS）算法 。 首先 ， 用概率节点表示对弈过程中的随机事件；其次 ， 借助MCTS算法的树并行化思想对PPMCTS算法并行优化 ， 通过改变随机事件发生的概率 ， 引导多个线程选择不同的搜索方向 。
文章图片
文章图片
文章图片
3算法描述
概率启发的并行蒙特卡洛树搜索(ProbabilityheuristicparallelMonte-Carlotreesearch ， PPMCTS)算法构建于图3所示的博弈树 ， 树中包含最值节点和概率节点 。 最值节点存储数据{vis,cnt,val} 。 其中 ， vis≥0表示该节点的访问次数；-vis≤cnt≤vis表示该节点的总获胜次数；-1≤val≤1表示该节点的价值 ， 即胜率 。 对方行棋时cnt和val为负 ， 以保证对方能选择对自己最优的走法 。 概率节点存储数据{d,p} 。 其中 ， d∈{1,2,…,6}表示概率节点对应的投骰子事件 ， 即投掷到的骰子点数为d；0≤p≤1表示投骰子事件发生的概率 。 PPMCTS算法的线程执行过程如图4所示 ， 算法由选择、扩展、模拟和更新这四个阶段的迭代而建立 。
文章图片
推荐阅读
- 中国电子报智能传感器能占多大市场？，30万亿元智慧养老产业
- 长沙晚报打造“中国软件开发者产业中心城市”，长沙携手CSDN
- 数码狂人“云演唱会”会成为音乐产业新常态吗，5G+4K+VR+多视角技术融合
- 浙视频来看这份最新报告，想了解浙江人工智能产业发展全景
- 手机侃侃谈但王健林手里还有个世界第一产业，一年能赚800亿，去年亏7百亿
- 国商园区国贸电商产业园助力企业参展网上广交会
- 新龙网持续拓展5G、8K、半导体等产业边界，康佳科技创新步伐加快
- 燕赵都市报电商产业迅猛发展，肃宁：多措并举
- 雅格布别动不动就要做个平台、整合产业链
- 电商客节能产业加速度：全域节能增效化身“行业核动力”