Strategy improvement method of search game tree on Go

Abstract

The invention relates to a strategy improvement method for a search game tree on Go. The method comprises the following steps: establishing a search tree by taking a current state as a root node; selecting a child node of the root node for simulation, and if a child node is not simulated, randomly selecting a child from the child node of the root node for simulation; if all the child nodes are simulated for at least one time, selecting the child node with the highest UCB sub-tree; starting to simulate from the selected child node to the leaf node; combining the simulation strategy with uniform sampling and a minimum and maximum strategy; propagating the final simulation result reversely to the root node, and updating the Q value and the N value of the action value function of all leaves on the path; and repeating the steps for many times, and finally selecting the node with the highest utilization item score in the UCB. According to the invention, the improved algorithm is applied to the search strategy of the Go, the evaluation of GNUGo and CGOS is passed, and the final experimental result shows that the algorithm can improve the accuracy of game search in the Go.

Description

technical field [0001] The invention relates to a strategy improvement method for searching a game tree on Go, in particular to a strategy improvement method for searching a game tree on Go. Background technique [0002] Monte Carlo methods have a long history in numerical algorithms and have achieved notable success in various artificial intelligence game algorithms, especially in games of incomplete information such as Scrabble and bridge. However, its real success on the computer is through the recursive application of the Monte Carlo method in the tree building process, which is the main research content of MCTS. Go is one of the few classic games in which human players are far ahead of computer players, MCTS has played a huge role in closing this gap, and it now competes with the best human players on small boards, although MCT plays on standard The 19×19 chessboard is well below their level. Go is a difficult game for computers to play: it has a high branching factor...

AI Technical Summary

Problems solved by technology

Although the minimax search method and some other pruning algorithms can effectively improve the search efficiency, these methods are not enough for a deep search tree like Go, and the search time has not been reduced to a satisfactory result.

Images