Implementation and Performance Evaluation of the Fully Enclosed Region Upper Confidence Bound Applied to Trees Algorithm

摘要

While the playing performance of UCT (upper confidence bound applied to trees) algorithm is nearly the same as that of top professionals on a 9 × 9 Go board, its performance on a 19 × 19 board still needs great improvements. One possible way is to use multiple local UCT searches in parallel by the same computing resources to reach deeper depth. This paper tries to do some tentative work in this regard. After modifying Fuego's implementation of global UCT search algorithm, we have implemented a fully enclosed region UCT local search algorithm and tested it by 64 standard tsume go problems. Present results show that the fully enclosed region UCT can reduce original branching factors from 5-16 to 2.3 without using any domain knowledge on Go. According to the accuracy of testing results and computing speed, it is promising to do further research on running multiple local UCT searches in parallel.