第6期 王亚杰，等：计算机博弈的研究与发展 ·793. 博弈。 面、越准确，获胜的机率就会越高。但是，博弈有个 l)蒙特卡罗搜索(MCTS,Monte Carlo Tree 很重要的约束条件就是时间。评估中考虑的问题越 Search)【6-0 全面细致，则耗费的时间就越多，搜索的深度和速度 在人工智能的问题中，蒙特卡罗搜索是一种最 必然受到影响。另外，随着搜索深度加深，信息处理 优决策方法，它结合了随机模拟的一般性和树搜索 量也会大幅提升。 的准确性。由于海量搜索空间、评估棋局和落子行 设计评估函数需要考虑诸多因素，在完全信息 为的难度，围棋长期以来被视为人工智能领域最具 博弈中双方的子力、领地、位置、空间、机动性、拍节 挑战的经典游戏。近年来，MCTS在类似计算机围 威胁、形状、图案都可以作为评估参数，非完备信息 棋等完备信息博弈、多人博弈以及其他随机类博弈 博弈中除了己方已知参数外，还要猜测对手的情况 难题上的成功应用而受到快速关注。理论上， 并通过量化后加权组合而成。 MCTS可以被用在以{状态，行动}定义并用模拟预 国内外有不少学者在计算机博弈评估方面做了 测输出结果的任何领域。 大量深入研究[。针对不同棋种的特点，学者们提 基本的MCTS算法根据模拟的输出结果，按照 出了各种不同的方式进行评估与优化：通过博弈记 节点构造博弈树，其过程如图3所示，包括路径选择 录来评估博弈树搜索[]：针对六子棋应用遗传算法 (Selection)、节点扩展(Expansion)、模拟实验(Simu- 进行寻优处理，优化机器博弈评估函数[：在中国 lation)、反向传播(Backpropagation)4个步骤。 象棋里，把自适应遗传算法引入评估函数中，通过锦 多次重复 标赛算法对评估函数中的参数组合进行自动调整和 优化]：根据棋子的数量、移动范围、攻击范围、子 路径 节点 摸拟 反向 选择 扩展 实验 传播 力攻击力、盘面分值和占弧价值等对苏拉卡尔塔棋 局面评估函数进行了研究[0]：根据亚马逊棋领地」 图3构造MCTS博弈树的过程 位置和机动性等特征在不同阶段的重要程度及权重 Fig.3 Process of constructing the MCTS game tree 值，给出一个分阶段的评估函数[，4]。 MCTS算法适用于有较大分支因子的博弈程 提高计算机博弈能力不能单纯依靠加大搜索深 序，如AlphaGo就是采用MCTS算法进行搜索)。 度，还需要将必要的相关博弈知识引人到相应的博 2)UCT算法[13,25】 弈搜索中，只有协调搜索算法与评估函数，博弈系统 UCT算法，即上限置信区间算法，是一种基于 才能发挥有效作用。 MCTS发展的博弈树搜索算法，该算法通过扩展 UCB(upper confidence bound)到极大极小树搜索， 6综合优化技术 将MCTS方法与UCB公式结合。 计算机博弈中，目前应用较多的综合优化技术 UCB计算方法如公式1所示，在向下遍历博弈 主要有并行计算、遗传算法和基于神经网络的深度 树时，通过选择最大化该值来实现节点的选择。 学习。 In N 6.1并行计算 UCB=U:+C× 并行计算4，]是为了提高计算速度，把博弈树 (1) 动态分开，发挥计算机多CPU强大的并行处理能 式中：v:是节点i估计的值，n:是节点i被访问的次 力，同时执行多个指令的算法。它不裁剪和缩小博 数，而N是其父节点已被访问的总次数，C是可调参 弈树的规模，通过提高搜索速度，而进行优化系统。 数。相对于传统的搜索算法，UCT时间可控，具有 并行计算有两种体系，单机体系SMP(Symmet- 更好的鲁棒性，可以非对称动态扩展博弈树，在超大 ric Multiprocessor)和分布式体系Cluster(计算机集 规模博弈树的搜索过程中，表现出时间和空间方面 群)，对应多线程并行和多机并行。两者最大的区 的优势。目前，UCT在搜索规模较大的完备信息博 别是，前者可以共享存储器（并且共享同一地址的 弈、复杂的多人博弈、非完备信息博弈以及随机类博 存储单元)，后者则必须通过网络来交换数据。由 弈项目中，表现出色[)。 于博弈搜索通常需要用到置换表，所以适合以SMP 的方式多线程并行处理，但随着大数据、云计算等技 5局面评估 术的成熟与完善，计算机集群技术将被越来越多地 在计算机博弈系统中，对博弈局面评估得越全 运用到计算机博弈中。博弈。 １） 蒙 特 卡 罗 搜 索 （ ＭＣＴＳ， Ｍｏｎｔｅ Ｃａｒｌｏ Ｔｒｅｅ Ｓｅａｒｃｈ） ［６７－７０］ 在人工智能的问题中，蒙特卡罗搜索是一种最 优决策方法，它结合了随机模拟的一般性和树搜索 的准确性。 由于海量搜索空间、评估棋局和落子行 为的难度，围棋长期以来被视为人工智能领域最具 挑战的经典游戏。 近年来，ＭＣＴＳ 在类似计算机围 棋等完备信息博弈、多人博弈以及其他随机类博弈 难题上的成功应用而受到快速关注［７１］ 。 理论上， ＭＣＴＳ 可以被用在以｛状态，行动｝定义并用模拟预 测输出结果的任何领域。 基本的 ＭＣＴＳ 算法根据模拟的输出结果，按照 节点构造博弈树，其过程如图 ３ 所示，包括路径选择 （Ｓｅｌｅｃｔｉｏｎ）、节点扩展（Ｅｘｐａｎｓｉｏｎ）、模拟实验（Ｓｉｍｕ⁃ ｌａｔｉｏｎ）、反向传播（Ｂａｃｋｐｒｏｐａｇａｔｉｏｎ）４ 个步骤。 图 ３ 构造 ＭＣＴＳ 博弈树的过程 Ｆｉｇ．３ Ｐｒｏｃｅｓｓ ｏｆ ｃｏｎｓｔｒｕｃｔｉｎｇ ｔｈｅ ＭＣＴＳ ｇａｍｅ ｔｒｅｅ ＭＣＴＳ 算法适用于有较大分支因子的博弈程 序，如 ＡｌｐｈａＧｏ 就是采用 ＭＣＴＳ 算法进行搜索［３］ 。 ２）ＵＣＴ 算法［ １３，２５ ］ ＵＣＴ 算法，即上限置信区间算法，是一种基于 ＭＣＴＳ 发展的博弈树搜索算法，该算法通过扩展 ＵＣＢ（ ｕｐｐｅｒ ｃｏｎｆｉｄｅｎｃｅ ｂｏｕｎｄ） 到极大极小树搜索， 将 ＭＣＴＳ 方法与 ＵＣＢ 公式结合。 ＵＣＢ 计算方法如公式 １ 所示，在向下遍历博弈 树时，通过选择最大化该值来实现节点的选择。 ＵＣＢ ＝ ｖｉ ＋ Ｃ × ｌｎ Ｎ ｎｉ （１） 式中： ｖｉ 是节点 ｉ 估计的值，ｎｉ 是节点 ｉ 被访问的次 数，而 Ｎ 是其父节点已被访问的总次数，Ｃ 是可调参 数。 相对于传统的搜索算法，ＵＣＴ 时间可控，具有 更好的鲁棒性，可以非对称动态扩展博弈树，在超大 规模博弈树的搜索过程中，表现出时间和空间方面 的优势。 目前，ＵＣＴ 在搜索规模较大的完备信息博 弈、复杂的多人博弈、非完备信息博弈以及随机类博 弈项目中，表现出色［７１］ 。 ５ 局面评估 在计算机博弈系统中，对博弈局面评估得越全 面、越准确，获胜的机率就会越高。 但是，博弈有个 很重要的约束条件就是时间。 评估中考虑的问题越 全面细致，则耗费的时间就越多，搜索的深度和速度 必然受到影响。 另外，随着搜索深度加深，信息处理 量也会大幅提升。 设计评估函数需要考虑诸多因素，在完全信息 博弈中双方的子力、领地、位置、空间、机动性、拍节、 威胁、形状、图案都可以作为评估参数，非完备信息 博弈中除了己方已知参数外，还要猜测对手的情况， 并通过量化后加权组合而成。 国内外有不少学者在计算机博弈评估方面做了 大量深入研究［７２］ 。 针对不同棋种的特点，学者们提 出了各种不同的方式进行评估与优化：通过博弈记 录来评估博弈树搜索［７３］ ；针对六子棋应用遗传算法 进行寻优处理，优化机器博弈评估函数［４０］ ；在中国 象棋里，把自适应遗传算法引入评估函数中，通过锦 标赛算法对评估函数中的参数组合进行自动调整和 优化［１９］ ；根据棋子的数量、移动范围、攻击范围、子 力攻击力、盘面分值和占弧价值等对苏拉卡尔塔棋 局面评估函数进行了研究［４０］ ；根据亚马逊棋领地、 位置和机动性等特征在不同阶段的重要程度及权重 值，给出一个分阶段的评估函数［４７，７４］ 。 提高计算机博弈能力不能单纯依靠加大搜索深 度，还需要将必要的相关博弈知识引入到相应的博 弈搜索中，只有协调搜索算法与评估函数，博弈系统 才能发挥有效作用。 ６ 综合优化技术 计算机博弈中，目前应用较多的综合优化技术 主要有并行计算、遗传算法和基于神经网络的深度 学习。 ６．１ 并行计算 并行计算［１４，７５］ 是为了提高计算速度，把博弈树 动态分开，发挥计算机多 ＣＰＵ 强大的并行处理能 力，同时执行多个指令的算法。 它不裁剪和缩小博 弈树的规模，通过提高搜索速度，而进行优化系统。 并行计算有两种体系，单机体系 ＳＭＰ（ Ｓｙｍｍｅｔ⁃ ｒｉｃ Ｍｕｌｔｉｐｒｏｃｅｓｓｏｒ）和分布式体系 Ｃｌｕｓｔｅｒ（计算机集 群），对应多线程并行和多机并行。 两者最大的区 别是，前者可以共享存储器（并且共享同一地址的 存储单元），后者则必须通过网络来交换数据。 由 于博弈搜索通常需要用到置换表，所以适合以 ＳＭＰ 的方式多线程并行处理，但随着大数据、云计算等技 术的成熟与完善，计算机集群技术将被越来越多地 运用到计算机博弈中。 第 ６ 期 王亚杰，等：计算机博弈的研究与发展 ·７９３·