面向搜索时间受限的完全信息博弈UCT算法改进研究

张宜放　孟坤　蒋志文　高世静　张蕴瀚

摘要：针对完全信息博弈中搜索时间受限的算法设计问题，在考虑博弈模型不同特点及对结局影响程度的基础上，提出了分阶段的算法模型，给出了三阶段博弈算法设计方法。通过改造影响搜索策略的目标函数，使得在时间受限的前提下，能够方便控制每一阶段均更有效地搜索出较好策略，并给出相应的算法实现与分析。以点格棋为对象，给出了通过改造UCT算法中UCB公式的实现思路，设计了方向引导控制策略、多种算法混合、二进制压缩和并行化处理等技巧，有效提升了算法的效率和稳定性，并通过试验验证了所给出方法的有效性和效率。

关键词：UCT算法优化;三阶段模型;点格棋

中图分类号：TP301.6      文献标识码：A

文章编号：1009-3044（2021）04-0195-06

Abstract： To deal with the algorithm design of the Time-Constrained problem in the complete information game， based on the different characteristics of the game model and the degree of influence on the outcome， a staged algorithm model is proposed and a three-stage game algorithm design is given. By transforming the user's reward function that affects the search strategy， under the premise of limited time， it is convenient to control each stage to search for better strategies more effectively， and to give corresponding algorithm implementation and analysis. The realization idea of the UCB formula in the UCT algorithm is given based on Dots and Boxes， and the techniques of direction guiding control strategy， multiple algorithm mixing， binary compression， and parallel processing are designed， which effectively improves the efficiency and stability of the algorithm. The effectiveness and efficiency of the proposed method were verified by experiments.

Key words： Optimization of UCT algorithm; Three-stage model; Dots and boxes

博弈模型常被用来刻画多主体独立参与、行为相互制约的问题[1]，目的在于计算给定用户最优收益的行为策略，根据博弈参与者对其他参与者潜在行为集合信息的知晓多少，博弈模型被分为完全信息博弈和非完全信息博弈[2]。当前，博弈模型已经被广泛用于经济政策制定、管理策略设计、通信调度算法研发，以及网络协议设计等场景，也是人工智能算法设计的模型工具之一。然而，用户收益函数（Users reward function）定义的多样性制约了博弈模型的策略计算，即使针对完全信息博弈模型，尚缺乏得到博弈模型显式均衡策略的通用方法[3]，因此，高效近似解的计算方法成为计算机学科研究的重要方向。

以博弈模型的人工智能算法设计为例，当前主要采用的研究思路为基于博弈树搜索最优策略路径，典型算法包括α-β剪枝搜索[4]（α-βpruning，α-β）和蒙特卡洛树搜索[5]（Monte Carlo Tree Search，MCTS）。α-β搜索算法主要依赖基于收益函数回溯计算的局面收益评估函数，通过剪去非占优分枝减少搜索空间，进而得到最优策略。蒙特卡洛树搜索旨在通过大量仿真，使用收益统计值替代局面收益函数评估，进而贪婪地得到给定局面下的最优策略。由于，实施过程中对经验知识依赖程度的不同，蒙特卡洛树搜索更具备可扩展性，因此，在人工智能算法设计中蒙特卡洛树搜索的应用更为广泛。由于足够多的仿真次数是MCTS准确性的根本保证，较好地实践算法均需要较长的仿真（训练）时间，效率和准确性成为MCTS难以兼顾的两个对立方面[6]，因此，提高上述两方面指标的MCTS算法成为重要研究方向。具有代表性地，UCT（Upper Confidence Bound Apply to Tree）算法[7]中使用UCB公式，在UCB值的引导下实现了更有针对性的仿真搜索，较大程度地提高了收敛到最优策略的效率，并在诸多问题中得到应用。但是，针对时间受限的博弈AI算法设计问题，相关的研究成果还较为有限，主要采用强制停止搜索、使用当前值近似替代的方法，算法准确度难以得到保障。

基于上述问题，本文针对时间受限的完全信息博弈AI算法设计问题，提出了一種基于UCT算法UCB（Upper Confidence Bound）公式的改进方案，引入了平衡系数C，实现对不同阶段探索与开发比例的动态调整策略;引入贪心系数G，利用经验对UCT探索过程进行方向引导，加快收敛速度，适应了时间受限的情景。此外，通过对完全信息博弈的博弈过程研究，提出一种三阶段模型，针对不同阶段的特点设计不同控制策略，并辅以算法并行化处理方法、局面二进制压缩等多种优化策略和技巧，极大地提升了算法性能，实现兼顾准确性和效率的优化UCT三阶段模型。

1 UCT算法优化

1.1 公式改进——引入平衡系数和贪心系数

UCB公式最初是针对K臂赌博机问题提出的[8]，目的是平衡开发与探索之间的关系。应用于博弈领域时，在以当前局面为根节点建立的博弈树中共有i个分支，用UCBi表示对第i个分支的评估值。

式中，Xi为第i个分支的平均收益值，Ti为第i个分支被探索的次数，N为总探索次数。公式中前项Xi为开发项，表示该分支过去开发的平均表现，后项式[2lnNTi]为探索项调整值，表示该分支被探索的价值，最终通过开发项和探索项的加和作为当前该分支的综合评价值，来平衡开发与探索之间的关系[9]。

由于开发与探索间的比例关系依赖具体问题，针对不同问题有不同的比例选择，因此设计在UCB公式探索项部分引入平衡系数C，以动态地改变开发和探索间的比例关系。同时在针对时间受限N值较小情况下，探索项对整体评价影响大、探索收敛速度慢等问题，引入贪心系数G，对仿真方向进行引导，加速收敛过程，减少冗余计算。

改进后的公式如下所示：

应用UCB公式的UCT算法在搜索策略上类似广度优先遍历，通过在同一广度方向上的不断向下延展保证UCB值的准确性;而延展的深度则决定估值函数评估值的准确性，直接影响UCB公式前项Xi值。加大搜索深度，意味着单次仿真时间呈指数级增长，仿真次数N大幅下降，后项式对UCB值的影响幅度增大。通过设计时间参数h，直接影响仿真次数;设计深度参数t调整搜索深度，间接影响仿真次数。要在可接受的时间范围内平衡仿真次数和搜索深度，就需要针对不同模型进行大量的测试和参数调整。

算法1 加入时间参数t和深度参数h的优化算法

输入：当前局面信息。

输出：最优解对应边。

1） 以当前局面创建根节点root

2） while 有时间剩余t

3） Node <- Node_root

4） while 当前搜索深度 < h and 非叶节点

5） 为当前Node节点创建子节点

6） 使用公式（2）计算每个子节点UCBi值

7） Node <- 使UCBi值最大化的子节点

8） end while

9） 使用估值函数对当前Node给出客观评价值value

10） while Node ！= root

11） 更新Node节点在公式（2）中的Xi值

12） Node <- 父节点

13） end while

14） end while

15）选择根节点中使公式（2）UCBi值最大化的子节点对应边输出

1.2 探索方向控制策略

UCT 的任意时间终止特性是传统的搜索算法所无法比拟的[10]。它可以在算法执行过程中的任何时间突然终止算法，并返回一个较理想的结果。当然如果给予更为充分的时间的话，算法结果会非常逼近实际的最优值。但这一点在α-β搜索中是绝对行不通的，当使用迭代控制突然中断α-β搜索程序时，某些处于根节点之下第一层的节点甚至可能还没有被探索过，此时搜索程序返回的结果和实际的最优解相距甚远。

利用UCT算法可以在任何時刻直接终止的特性，本文提出一种探索方向控制策略，当判断程序已经得到当前最优解时提前终止算法，以减少冗余计算，间接加大搜索深度。

UCT算法可以直接通过仿真探索方向来判断是否已经找到最优分支。不同于剪枝搜索算法找到最优解的策略，UCT算法的核心目的是找到最优分支。针对UCB公式，随着某一分支探索次数的增加，探索项调整值的大小会逐渐趋近于0，公式UCB值也越来越接近该分支的真实评估值。

在到达一定仿真次数后（蒙特卡洛算法具有统计性质，必须保证一定的统计量UCB值才具有较高的可信度），某一分支被多次仿真UCB值仍高居不下，认为收敛过程已经完成并判断该分支为最优分支。如果算法已经计算出了当前的最优分支，则其UCB值仅前项Xi值就应远大于剩余分支综合评价UCB值，算法的仿真方向也被一直引导向该分支探索，此时剩余时间内的探索将均被限制在该分支，对该分支后续的探索也不会影响根节点的决断，成为不必要的冗余计算，此时可以直接终止算法。

1.3 二进制压缩技术

二进制压缩技术[11]可以将棋盘矩阵转换成位图存储，有效减少存储空间，减小算法的内存压力，为并行化提供保障。其实现原理是将复杂数据结构表示的棋盘矩阵抽象、分离成多个bool数组，对数组中的数据分别予以不同权值，压缩成多个二进制数表示。

对于一个m×n大小的棋盘，首先对棋盘上所有的点位编号为1至m×n号，对第i号点赋予权值2i-1，k表示当前点的二进制状态，并利用如下公式计算出bool矩阵的二进制压缩值：

由于多数非完全信息博弈棋盘较大，无法压缩存储在一个二进制数中，实际使用时需分别用多个二进制数表示一组点。以c++编程为例，其语法定义的无符号长整型最大存储长度为8字节，所以将相邻64个点划分为一组进行压缩。此时压缩值递推公式如下：

式中m、n分别表示被压缩棋盘的长和宽，t表示压缩所需的二进制数下标最大值，B0至Bt分别表示对应点组的压缩值。最终将m×n大小的bool矩阵压缩成t+1个长整型数。

以围棋棋盘为例，它是一个二维19×19的三状态数组，三种状态分别是该点未被填子、被黑棋填子和被白棋填子。首先将棋盘数组的三种状态分离，设黑棋所占点位和白棋所占点位两个二维两状态矩阵，矩阵的大小为19×19，其对应项表示原始棋盘上该点有没有被黑棋（白棋）填子，0表示未被占领1表示被黑棋（白棋）填子，两数组相加值为0的部分即为未被黑白双方填子的部分，这样就把一个复杂的int数组转化成了两个bool数组。取m、n等于19，利用公式（3）计算出t值为5，分别用B0至Bt公式组计算出黑棋、白棋点位矩阵的压缩值即可。这样就把一个19×19大小的二维三状态矩阵压缩成了12个长整数，存储效率提升93%。

对于二进制压缩技术，其优势在于使棋盘占用存储空间下降，压缩效率高，且以位图方式存储，在转移出原始棋盘时不会损失局面信息。该技术主要适用于棋盘规模大，棋子状态（种类）少的棋类局面存储中，棋盘规模越大，棋子状态越少，压缩效率越高。但对于小规模多状态棋类棋盘，如国际象棋、象棋等棋子种类较多的棋类，原始棋盘分离状态后转化的bool矩阵数量过多，压缩的效率会大幅下降。

1.4 并行化处理

UCT算法主要以模拟对局为主，每次选择、扩展、模拟、回溯的过程相对独立[12]，所以将其做并行化处理，每一个线程负责一次UCT模拟过程，共同维护更新同一棵搜索树[13]。

在拥有多个CPU核心的情况下，通过并行的展开多个线程，分别进行不同对局模拟。某一线程在模拟完成后，先给公共资源区（整棵博弈树）加X锁，修改部分节点UCB值，该线程再展开下一轮模拟。这一过程中不需要访问博弈树的线程仍可以继续工作。

对于传统剪枝函数，它不像UCT仿真在整次模拟结束后才更新节点权值，而是在每一次回溯时更新父节点权值。在做并行化时，它的每一个线程对公共资源区的访问频率更高，导致公共资源区被频繁加锁，其他线程等待时间增加，CPU利用率下降。也是由于锁机制的存在，实际应用中每次模拟并不完全独立，因而性能的优化效果会有所减弱。

因为CPU进程调度的不可预知性，无法预知什么时候会出现死锁。而现在大多数博弈程序均采用前后端分离的设计模式，前端界面只负责接受对方和己方走棋输入，后端进行下一步走棋的计算。为预防算法因死锁崩溃的情况发生，本文利用二进制压缩技术局面存储数据量小且能转译出完整棋盘的特点，设计前端重传请求算法，在超过规定时限未收到后端回复时即认为并行算法部分发生死锁，前端重传一次局面参数，重新请求后端做并行计算，因而不会因死锁而导致整个博弈程序的崩溃。后端算法也需完成局面与过程的分离，在接受任意一个局面输入的情况下计算下一步，而不依赖之前的博弈过程。

在算法完成并行化处理后，对内存的需求量大大提升，而二进制压缩技术也很好地提供了一种能在不损失任何局面特征情况下的棋盘压缩存储方式，成功减小内存压力，为算法的并行化提供了切实保障。

2 完全信息博弈三阶段模型

本章针对完全信息博弈中搜索时间受限的算法设计问题，将整个博弈过程分为开局 、中局和残局三个阶段[14]。

2.1 开局——UCT模拟结合贪心选择策略

博弈开局走法较多，局面形势不明朗，且各种走法差异性较小，随机因素较大。而贪心算法时间复杂度小，效率高[15]，尽管求解可能是局部最优解但仍远强于随机。因此开局阶段设计以UCT算法为主，结合贪心选择策略作为蒙特卡洛模拟方向的引导，力求在短时间内计算出一个可接受的次优解。

当设计者以人类经验判断某步棋优势或劣势时（比如围棋的送入虎口、国际象棋的送后），通过修改公式（2）中的贪心系数G来控制UCT仿真方向，使探索策略偏向探索优势步，尽量不去模拟劣势步以减少无意义的冗余计算。贪心算法的时间复杂度一般在常数级别，耗时可以忽略不计，不会影响后续UCT算法的仿真时间。

这是一种基于修正收益值的貪心策略，借由人类经验来修正UCB值来引导仿真方向。但这种方式在中残局并不适用，因为这两阶段存在很多弃子抢先的技术存在，贪心策略会影响程序对局面的判断。

2.2 中局——优化UCT模拟

中局阶段是分胜负的关键阶段，在这个阶段，局面复杂走法多样，但每一步的处理都会对后续的局面发展产生很大的影响。在这一阶段可以采用优化UCT算法，充分利用开局和残局阶段节省的时间，在关键步予以较长的运算时间。

但即便在三阶段中，中局阶段分配了最长的时限，也无法做到模拟完整个对局的同时保证对局数量，所以仍需考虑搜索深度与统计数据量的平衡问题。考虑到UCT算法对估值函数的依赖性较小，可以中和部分估值函数错误带来的误差影响（对某一次探索的错误判断不会大幅影响对该分支的UCB评价值），随着中局的深入搜索深度可以慢慢减小。

初入中局时应以探索为主，通过使改进UCB公式中平衡系数C取较大的值，以获得更大的搜索广度，尽可能给每一种走法以探索的机会，同时避免因单次仿真效果不佳而导致某一分支整体仿真次数过少的情况发生;随着游戏的进行，探索与开发的天平逐渐向开发倾斜，单次仿真搜索的深度要慢慢增加，减少在不必要的分支产生过多的冗余计算，因此C值应逐渐减小。此时随着UCB公式的收敛，探索方向也慢慢集中，增加的仿真对局数也均限制在某几步可能的最优解中，算法的效率提升明显。

中局阶段存在关键步的问题，而关键步也是整盘棋的胜负手。关键步走后将出现两极分化现象，选择的节点UCB值要么趋近正无穷要么几乎为0（针对不存在和棋的完全信息博弈类游戏），游戏胜负已分。目前仍无法人为找出关键步的原理和具体数量，能进行处理的主要是对关键步位置的测试和对该位置参数的调整，增加时限的分配和加大搜索深度等。

2.3残局——α-β剪枝

在整盘棋接近尾声时放弃UCT算法，选用α-β剪枝算法以节省时间，提高搜索效率。

残局阶段的处理较为简单，在博弈树规模急剧减小，接近完全搜索（暴力破解）可达范围时，只需选择能最快搜索到较高深度的算法即可。由于蒙特卡洛算法的统计特性，在样本量过少的情况下容易出现误判（比如因UCB公式调整项过大引起的误差），而保证样本量又需要一定的仿真时间。反观剪枝算法，它搜索时每个局面只模拟一次的优势在残局体现了出来，在接近残局时估值函数准确性极高，或者说已经可以计算到最终局面就不需要估值函数了。当计算结果准确性提高上来后，剪枝算法速度快，耗时少，探索局面不重复且不会出现未探索到某种局面的情况，所以在残局时选择剪枝算法中效果最好的α-β剪枝算法。

3 分阶段优化博弈模型

上述算法改进策略及三阶段模型均以点格棋为平台实现并进行优化。

3.1 具体阶段划分与时间分配策略

（1）开局阶段

开局阶段主要指10步以前的走法，此时局面形势不明朗，制胜的关键长链未形成，走法的随机性较大。

先将所有边分为以下几类：

1）非法边，已落过子的边，不可选择

2）得子边，可以得子的边

3） 失子边，使对手下一步得子的边

4）长链边，长链中的得子边

5）其它边

这其中第四类长链边虽然也属于得子边，但其相对复杂，涉及放弃得子强迫换手的操作，所以无法和第二类边归为一类讨论。不过因为开局阶段长链尚未形成，可以大胆假设在10步之前不存在第四类边，那么允许的选择就被限制在了得子边、失子边和其它边。

根据贪心策略将边的优先级设为得子边>其他边>失子边，对得子边UCB公式中的贪心系数G取0.2，对失子边G取-0.05，其余边G取0。对于优势走法，应给予合理的收益值加成;但对于劣势走法只做少许的收益修正，既降低该边的评估值从而减少模拟次数，又不至于过分影响调整项 使得算法持续忽略对该分支的模拟。这样就通过直接影响UCB公式强制加快算法收敛速度，在不超过十秒的极短时限内获得一个优于纯UCT模拟的次优解。

开局阶段不采用改进UCB公式中的开发探索平衡系数C（取C=1），此时开发与探索接近平衡即可，无需过度追求广度上的均衡，也无须通过减小C值提前收敛。

（2）中局阶段

中期局面的阶段划分相对复杂。根据以往下棋和比赛的经验分析，点格棋大概在20步进入中局，24-30步完成棋盘整个布局，形成制胜的长链，此后已经基本可以判断胜负了。但在20步之前，一方可以选择弃子断链、换手等技术，引导对手在中局形成对己方有利的布局。

所以本文将中局布局的概念提前到16步，认为16-20步为引导中局形势变化的关键步，分配较长的仿真时间，加大局面搜索深度，大量模拟该阶段的布局，尽可能选取有利的分支。对于UCB公式的使用，中局阶段直接舍弃贪心系数G，以防对手通过弃子断链等技术引导我方陷入不利布局。而对于平衡系数C，采取缓慢减少的策略，从刚进入中局布局的10-16步以探索为主，到中局关键步以对关键分支的开发为主，通过快速减小C值将函数收敛，模拟方向集中。

在中局16-20步关键步过后，局面呈两极分化，胜率要么接近正无穷要么几乎为0（UCT算法中采用节点的UCB值即为胜率），可见前文对关键步的处理是非常正确的。那么在中局后续阶段，只需保持上一阶段最后使用的C值大小，慢慢增加搜索深度（随局面深入算法复杂度减小）。

对于时间分配，在中局阶段采取内部细分阶段的策略，关键步分配超过两分钟的时限，而在其余步分配30-60s的时限不等，通过较长的时限分配来保证关键步的质量。通过实验观察，受平衡系数C及时间分配策略影响10-16步UCT仿真次数在5W次左右，而在关键步16-24仿真次数超过55W次。

（3）残局阶段

残局阶段主要指30步以后的走法，此时可以通过等价边裁剪[16]的方式，提升剪枝算法的效率，更早的完成对局面的完全搜索。

在上述情况中，虚线所示的边均为等价边，走其中一条和另一条或多条的效果相同，在探索时仅需探索其中一条，剪掉其余等价边所在分支即可。

在残局阶段，长链基本完全形成，局面上存在大量等价边，原本高达30的阶乘的算法复杂度很可能在高效剪枝的情况下减少至15的阶乘甚至进入完全搜索可达的范围，几乎不存在估值函数误差对剪枝算法带来的影响。

3.2 二进制压缩技术应用

对于点格棋棋盘，先将60条边按水平边和纵边进行分类，分别进行编号H1-H30和V1-V30。设二进制数H、V，H的第一位表示H1的状态，V的第一位表示V1的状态，已被占领为1，未被占领为0，通过这种转换来构成这两个30位长的二进制数H、V。

在计算时首先对H1-H30和V1-V30邊分别赋予一个固定权值，n号边对应权值为2n-1，k表示当前边的状态，利用如下公式分别计算H和V的值：

其中H、V分别存储当前局面边的状态，S数组分别存储己方和对方占据的格子数，Turn用来表示轮到哪一方走棋。通过二进制压缩技术，将棋盘存储最小化和唯一表示，同时不损失任何特征信息。

3.3 并行化优化

在利用二进制压缩技术处理棋盘后，将其做并行化处理。

定义博弈树中节点结构：

其中rwMutex为节点的读写锁，parent指向父节点，board存储当前节点局面。为保证节点的数据安全，当欲访问某节点时需要获得它的锁和其父节点的锁（若不为根节点）。因为必须同时得到访问节点和其父节点的锁，才能保证访问的节点和其兄弟节点在选择、扩展时不被修改。

4 实验结果与分析

测试棋盘大小为6×6，比赛单方总时限为15分钟。6×6点格棋棋盘共60条边，假设一方走30步（会有得子连走情况，一方走棋未必为30步），单步时限为15分钟/30步，即30s。

测试硬件环境如下：i7，6700HQ，主频2.6GHz，内存12G，显卡960M，四核八线程。

4.1 与α-β剪枝算法程序对弈

将基于点格棋设计的优化UCT三阶段模型（下简称三阶段模型）与使用相同估值函数的α-β剪枝算法对弈。

可以看出在估值函数不稳定且均使用相同估值函数时，UCT算法能明显规避误差，显著提高胜率。

4.2 与深度学习算法训练的神经网络模型对弈

与使用深度学习训练，水平相当于单步搜索500次纯蒙特卡洛算法的神经网络模型对弈。

深度学习的神经网络训练严重受限于外部条件，包括样本质量、数量，硬件设备和训练时间等，效果远不如UCT算法。

4.3 优化后的UCT算法测试

优化UCT算法不再采用统一分配每步时限，而是采用集中式统筹分配时间策略，所以不再为其设置单步时限。三阶段模型中采用贪心策略、二进制压缩技术、α-β剪枝以及多种控制策略优化的UCT算法与纯UCT算法（均完成并行化），在使用相同估值函数的情况下进行对弈。

优化UCT算法对整个博弈程序的棋力提高效果显著。

5 结束语

计算机博弈是一个复杂和具有挑战的课题，对与博弈论的学习和研究具有深远的意义。本文提出了一种针对完全信息博弈的三阶段模型，在多领域完全信息博弈问题中具有很强的通用性和实用性。并针对UCT算法提出了改进UCB公式、方向引导控制策略、多种算法混合、二进制压缩和并行化处理等多种优化策略，完成了基于点格棋项目的算法实现，效果非常不错。

此次研究虽小有成果，但仍存在一些不足有待进一步的研究和改进，其中最主要就是对估值函数的处理。无论是蒙特卡洛算法还是传统剪枝算法，都无法摆脱程序本身对估值函数的依赖，估值函数的好坏也完全左右程序棋力的强弱。而目前大部分估值函数仍旧由专家给出，严重依赖专家的水平，AI也无法摆脱“人”的影响，实现真正的智能。

目前非深度学习算法有两个方向发展前景较好：

1）从算法设计角度减小估值函数不稳定带来的影响;

2）使用神经网络训练得出估值函数。

前者只能减小估值函数的影响，如UCT算法，治标不治本，但成效快效果好;而后者需要大量数据集进行训练，耗时久且对硬件要求高，在没有高算力计算机的情况下很难出效果。

上文所述棋盘二进制压缩理论，最初的设想不仅是用于节省内存和便于通信，还准备将其作为人工神经网络的输入进行训练。二进制压缩棋盘数据的另一优势在于没有信息丢失，每个输入唯一对应于一种局面状态，但问题是输入信息量大，网络规模大，运算速度慢，训练难度大;如果使用传统特征提取作为输入，那么必定存在信息丢失，虽然能减小网络规模、加快训练速度，训练效果肯定不如前者。

受各种条件限制，本文最终着眼于从博弈模型划分、算法性能优化角度入手，弱化估值函数带来的影响，没有使用人工神经网络。

参考文献：

[1] 王元卓，于建业，邱雯，等.网络群体行为的演化博弈模型与分析方法[J].计算机学报，2015，38（2）：282-300.

[2] SandholmT.Thestate of solving large incomplete-information games，andapplication to poker[J].AI Magazine，2010，31（4）：13-32.

[3] O. Baran， M. Kasal. Modeling of the Simultaneous Influence of the Thermal Noise and the Phase Noise in Space Communication Systems[J]. Radioengineering， 2010， 19（4）.

[4] Knuth D E，Moore R W.An analysis of alpha-beta pruning[J].Artificial Intelligence，1975，6（4）：293-326.

[5] Silver D，HuangA，Maddison C J，etal.Mastering the game of Go with deep neural networks and tree search[J].Nature，2016，529（7587）：484-489.

[6] 季辉，丁泽军.双人博弈问题中的蒙特卡洛树搜索算法的改进[J].计算机科学，2018，45（1）：140-143.

[7] Gelly S， Wang Y， Teytaud O， et al. Modification of UCT with patterns in Monte-Carlo Go[J]. 2006..

[8] Auer P，Cesa-Bianchi N，FischerP.Finite-time analysis of the multiarmed bandit problem[J].Machine Learning，2002，47（2/3）：235-256.

[9] Gelly S， Wang Y. Exploration exploitation in go： UCT for Monte-Carlo go[C]//NIPS： Neural Information Processing Systems Conference On-line trading of Exploration and Exploitation Workshop. 2006.

[10] YimengZhuang. Improving Monte-Carlo tree search for dots-and-boxes with a novel board representation and artificial neural networks[J]. IEEE CIG， 2015：314-321.

[11] KamstraL.The design of linear binary wavelet transforms and their application to binary image compression[C]//2003，3：241-244.

[12] Coquelin， Pierre-Arnaud， and RmiMunos.Bandit algorithms for treesearch[J].arXiv preprint cs/0703062 （2007）

[13]Chaslot G M J B，Winands M H M，Van Den H J ， et al.Parallel Monte-Carlo tree search[J]. Lecture Notes in Computer Science，2008， 5131：60-71.

[14] 徐心和，王驕.中国象棋计算机博弈关键技术分析[J].小型微型计算机系统，2006，27（6）：961-969.

[15] Wei XJ，Ye PX.Efficiency of orthogonal super greedy algorithm under the restricted isometry property[J].Journal of Inequalities and Applications，2019，2019：124.

[16] 丁濛，张亦鹏，李淑琴.棋盘局面数据标定方法研究[J].计算机应用研究，2020，37（2）：470-472.

【通联编辑：光文玲】