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

On Search time Constrained UCT Algorithm for Complete Information Games

作　　者：张宜放 孟坤[1,2] 蒋志文 高世静 张蕴瀚 ZHANG Yi-fang;MENG Kun;JIANG Zhi-wen;GAO Shi-jing;ZHANG Yun-han(Beijing Information Science and Technology University,Department of Computer Science,Beijing 100101,China;Beijing In-formation Science and Technology University,Computer Department Perception and Computing Intelligence Joint Laboratory,Beijing 100101,China)

机构地区：[1]北京信息科技大学计算机学院,北京100101 [2]北京信息科技大学感知与计算智能联合实验室,北京100101

出　　处：《电脑知识与技术》2021年第4期195-200,共6页Computer Knowledge and Technology

基　　金：北京信息科技大学2020年促进高校内涵发展——大学生科研训练项目(5102010805);科技计划一般项目(KM201911232002)资助。

摘　　要：针对完全信息博弈中搜索时间受限的算法设计问题,在考虑博弈模型不同特点及对结局影响程度的基础上,提出了分阶段的算法模型,给出了三阶段博弈算法设计方法。通过改造影响搜索策略的目标函数,使得在时间受限的前提下,能够方便控制每一阶段均更有效地搜索出较好策略,并给出相应的算法实现与分析。以点格棋为对象,给出了通过改造UCT算法中UCB公式的实现思路,设计了方向引导控制策略、多种算法混合、二进制压缩和并行化处理等技巧,有效提升了算法的效率和稳定性,并通过试验验证了所给出方法的有效性和效率。To deal with the algorithm design of the Time-Constrained problem in the complete information game,based on the differ⁃ent characteristics of the game model and the degree of influence on the outcome,a staged algorithm model is proposed and a threestage 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 algo⁃rithm implementation and analysis.The realization idea of the UCB formula in the UCT algorithm is given based on Dots and Box⁃es,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 pro⁃posed method were verified by experiments.

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]