Study On Key Algorithms For Games With Imperfect Information And Phantom Go

Computer game is an ancient and challenging topic in AI field, which forms a good testing platform for AI. The imperfect information game is an important subfield of computer games and is a problem that is worth researching, for that players can read only part of the information about opponents, so it is more close to decision-making problems in real world. This thesis studies key algorithms for games with imperfect information, especially for those with large scale and high complexity, and then tests and compares the efficiency of these algorithms in Phantom Go.In this thesis, imperfect information extensive form games are considered as the foundation and based model, and the model of imperfect information games is presented based on the concept of belief-state. Based on such model, the key algorithms are studied for games with imperfect information, and one belief-state tree is designed to represent the process of imperfect information games, and one algorithm called belief-state Monte-Carlo Tree Search is presented based on Monte-Carlo Tree Search algorithm. Then two belief learning methods, which are partly-paranoia belief learning method and Quantal-Response based belief leaning method, are suggested for the tree search algorithm, aiming at getting more rewards by taking advantage of the hidden information in games. The belief-state Monte-Carlo Tree Search algorithm is applied to Phantom Go, then methods of dealing with messages are studied and three advanced method based on the features of Phantom Go are suggested, which are mixed strategy, AMAF heuristic and information exploration. Finally, the performance of belief-state Monte-Carlo Tree Search is tested based on the game of Phantom Go and the difference of playing strength among these algorithms is tested.