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

摘要：针对完全信息博弈中搜索时间受限的算法设计问题，在考虑博弈模型不同特点及对结局影响程度的基础上，提出了分阶段的算法模型，给出了三阶段博弈算法设计方法。通过改造影响搜索策略的目标函数，使得在时间受限的前提下，能够方便控制每一阶段均更有效地搜索出较好策略，并给出相应的算法实现与分析。以点格棋为对象，给出了通过改造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]，因此，高效近似解的计算方法成为计算机学科研究的重要方向。……