A Middle Game Search Algorithm Applicable to Low-Cost Personal Computer for Go

Abstract

Go Artificial Intellects(AIs) using deep reinforcement learning and neural networks have achieved superhuman performance, but they rely on powerful computing resources. They are not applicable to low-cost personal computer(PC). In our life, most entertainment programs of Go run on the general PC. A human Go master consider different strategies for different stages, especially for the middle stage that has a significant impact on winning or losing. To study arguably a more humanlike approach that is applicable to low-cost PC while not reducing chess power, this paper proposes a new search algorithm based on hypothesis testing and dynamic randomization for the middle stage of the game Go. Firstly, a new method to decide the intervals of different playing stages more reasonable based on hypothesis testing is proposed. Secondly, a new search algorithm including a layered pruning branch method, a comprehensive evaluation function and a new selecting node method is proposed. The pruning method based on domain knowledge and upper confidence bound formula(UCB) are all applied to subtract the branches from the lower evaluation score, which was ranked behind 20%. The comprehensive evaluation function with adjustable parameters is proposed to evaluate the tree nodes after pruning. The new selecting node method based on dynamic randomization is used to expand the tree by selecting a node randomly from the high-quality node interval. Finally, the experimental results show that the designed algorithm outperforms Gnugo3.6 and Gnugo3.8 in chess power while reducing average search time and average RAM cost for one move effectively on a 19×19 board.

Keywords

• Go
• search algorithm
• MCTS
• UCT
• hypothesis test
• dynamic randomization