Research On Search Algorithms In Computer Go

Go has been considered to be a major challenge in the field of artificial intelligence for a long time, and provides a good experimental platform for artificial intelligence research. The branching factor of Chess search tree are only a few dozens, but the choice of every move of Go is up to a few hundred, which makes it extremely complicated to solve Go problems. Before MCTS (Monte Carlo Tree Search algorithm) the computer Go can even not beat an amateur. While the playing performance of UCT algorithm is nearly the same as that of top professionals on a9X9Go board, but its performance on19×19board still needs great improvements. so far many researchers has taken a lot of efforts to improve the algorithm of Computer Go, but it still fails to radically solve the problem of sharp decrease of the strength from small chessboard to big chessboard in the computer Go.One possible way is to use multiple local UCT searches in parallel, which could use the same computing resources for a deeper and more efficient search. This paper tries to do some tentative work in this direction. In order to explore the applicability of the local search algorithm and complexity of solving Go local problems, This paper proceed from Tsume Go problems. The main contents of this paper are as follows:1) This paper discusses the history, research status and the encountered problems in the field of Computer Go. Then it focuses on the models, theory and the classical search algorithms involved in Computer Go and analyzes some features of every search algorithm. At last, this paper demonstrates superiority rendered by the improved UCT algorithm in the field of Computer Go.2) This paper propose the concept of the closed domain UCT algorithm, 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 using64standard Tsume Go problems. We find that the speed and accuracy of fully-enclosed-region UCT algorithm are better than GoTools and professional players.3) This paper propose the concept of the minimum number of iterations which are used to analyze the relationship between the size of the search time and the initial blank points. Present results show that fully-enclosed region UCT can reduce original branching factors from5-16to2.3without using any domain knowledge on Go.Judged by the accuracy of testing results and computing speed, it has been proved the validity of fully-enclosed-region UCT in Tsume Go problems, and it is promising to do further research on running multiple local UCT searches in parallel.