AI研习丨专题：爱恩斯坦棋中概率启发的并行蒙特卡洛树搜索算法

摘要

本文提出一种概率启发的并行蒙特卡洛树搜索算法，用于解决爱恩斯坦棋的随机性带来的问题。一方面，针对随机事件的表示问题，该算法在博弈树中使用概率节点表示掷骰子事件，以多对多的形式连接概率节点与最大值、最小值节点；另一方面，该算法通过修改随机事件的概率值，引导线程选择不同的搜索方向。实验证明，概率启发的并行蒙特卡洛树搜索算法具有较高的搜索效率和智能水平。

关键字

计算机博弈；爱恩斯坦棋；蒙特卡洛方法；并行计算

0 引言

计算机博弈（Computer Game），也称为机器博弈，是人工智能的一个重要分支。计算机博弈可以通俗地理解为让计算机通过模拟人类思维过程来下棋，自诞生以来便受到世界各地学者的关注，被誉为人工智能的“果蝇”。

爱恩斯坦棋(EinStein Würfelt Nicht!，EWN) 是具有随机性的完备信息博弈棋种。棋盘及规则如图1所示，使用5×5大小的方格形棋盘。红蓝双方都有标着1~6号的6枚棋子，行棋前双方可在各自出发区(如图1(a)所示的棋子位置)随意摆放棋子。双方轮流走子，每轮走子前须投掷骰子，走动与骰子点数相同的棋子。若该棋子不存在，则走动大于或小于骰子点数且与骰子点数最接近的棋子，如图1(b)所示。若目标棋位上存在棋子，则移除(吃掉)该棋子。当我方任意棋子到达对方区域的角部位置或吃掉对方全部棋子时获胜，如图1(c)和(d)所示。

蒙特卡洛树搜索(Monte Carlo Tree Search， MCTS)算法是博弈树搜索算法中广为使用的算法之一，它是一种通过大量的蒙特卡洛模拟统计在博弈树中寻找最优解的方法。然而，传统的MCTS算法并没有表示爱恩斯坦棋行棋过程中的投骰子动作。为解决该问题，一般在博弈树中引入骰子节点表示投骰子事件，如图2所示。

但是，在对弈中后期，经常会出现多个骰子点数允许走动同一棋子的情况，因此上述博弈树中会存在大量冗余节点，导致MCTS算法重复模拟。针对上述问题，本文提出概率启发的并行蒙特卡洛树搜索（Probability Heuristic Parallel Monte-Carlo Tree Search，PPMCTS）算法。首先，用概率节点表示对弈过程中的随机事件；其次，借助MCTS算法的树并行化思想对PPMCTS算法并行优化，通过改变随机事件发生的概率，引导多个线程选择不同的搜索方向。

3 算法描述

概率启发的并行蒙特卡洛树搜索(Probability heuristic parallel Monte-Carlo tree search，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所示，算法由选择、扩展、模拟和更新这四个阶段的迭代而建立。