Application And Enhancement Of The UCT Algorithm In Computer GO

Computer game is an important direction for research in artificial intelligence, and there are significant differences between computer GO game and other computer games:1. GO game is more akin to intelligence issues.2. GO game is the most complex game in human development history.3. Traditional game theory and methods being applied in computer GO game have severe limitations. Therefore, the researches on computer GO game get the attention of many scholars. Recently, The UCT algorithm has been widely used to deal with GO game. This thesis first describes fundamental ideas of the computer game, traditional methods, the Monte Carlo algorithm, the UCB algorithm and the UCT algorithm. It then shows UCT is more applicable to solve computer GO game with experimental verification.After summing up the advantages and disadvantages of the UCT algorithm, this thesis represents two proposed enhancement methods for the UCT algorithm:The first method is to improve the UCT algorithm itself. The paper makes three improvement strategies for the UCT algorithm and following these strategies we can screen points to achieve the purpose of pruning game trees. The second method adds replacement table into the application process of UCT algorithm. This thesis describes the technology implementation of replacement table and storage method. By using the replacement table, we can narrow the number of states in the searching process, and reusing the searching information to improve the accuracy. The effect of these improved methods have been verified which are uniform with theoretical analysis.Finally, with the theoretical analysis and application which have existed, this thesis gives the conclusion:although the current algorithm for computer GO game has limitations and shortcomings, there still are improvements in new direction and application scenarios. With the efforts of many researchers, we can except that computer GO game can make some breakthrough.