非完备信息博弈中UCT算法策略的分析

摘要

UCT算法是UCB算法(Upper Confidential Bounds)在博弈树搜索问题中的应用.在大分支因子博弈树的搜索过程中,它表现出了独有的优越性.首先介绍了UCT算法实现过程中的不同策略.然后,基于四国军棋博弈系统,分别对UCT算法的不同策略在非完备信息博弈中的实验数据进行了比较和分析.在分析过程中,本文提出了挖掘-拓展因子EBF(exploration and exploitation balance factor)的概念.最后,针对不同UCT策略的性质和表现数据提出了几个结论,指出了不同性质的博弈游戏和与之相适应的最优UCT策略之间的关系.