Analysis of UCT algorithm policies in imperfect information game
Jiajia Zhang, Xuan Wang, Ling Yang, Jia Ji, Dongsheng Zhi · 2012
For the problem of mini-max tree search, Upper Confidence Bound (UCB) algorithm for multi-armed bandit problem has already been extended to algorithm UCT (UCB applied to Trees). It has shown advantages in the search tree with high branching factors and attained a great success in several domains such as Go program. In this paper, exploration and exploitation balance factor (EBF) is introduced as important parameter in UCT policies. Based on a known domain, which is called Siguo game, the performances for the different parameterized policies of UCT algorithm are compared and analysis is provided also. Following, some hypotheses about the cause of the problems are presented. Moreover, the suggested method about adoption and parameterization of UCT policies is provided for different type and characteristics of game problems.