Monte - Carlo Method In The Application Of The Computer Game

Game is one of the important subjects of Artificial Intelligence. Because of the too large search space in Computer Go, computer is hard to get hold of the fuzzy concept of Go. Presently, the best Computer Go players are at the level of weak amateurs. Computer Go is now considered one of the most difficult challenges for Artificial Intelligence, replacing Chess in this role. Go is a nicer environment to inspect the development level of AI. It is a puzzle in Artificial Intelligence about how to improve the capability of the Computer Go programs. Therefore, the study of Computer Go is important both in theory and in practice.This paper describes how to design and implement a Go engine based on UCT algorithm. The first part introduces the research background and significance of Computer Go, research status and key technologies, including the Monte Carlo method and the UCT algorithm theory. The second part gives out the overall function modules of Go engine after the general overview of it, and describes the various sub-modules, highlighting the alternate process and move generation modules. The third part clarifies how to design a Go engine based on the UCT algorithm. It illustrates the overall process design of Go engine followed by the specific design flow of the UCT algorithm module and the legality judgments of moves module and etc. The fourth part discusses the implementation of the Go engine based on the UCT algorithm. It gives detailed description of the mechanism of the candidate moves’generation and management, the UCT selection of the nodes, expanding nodes and Go game simulations. It points out the different factors and strategies on the impact of computer Go program, especially the pattern matching of moves during the Go game simulations and some other Go knowledge, which has a crucial role in thinking depth of the Go program. Finally, major work was summarized and further development goals was gave.Based on the above, a simple Go engine based on UCT algorithm, QMate, which supports the GMP and GTP Go protocol, SGF file outputs in debug mode, and statistics data of the UCT Go game simulations is implemented. Currently QMate can communicate with the Computer Go Clients properly to achieve Human-Versus-Machine and Machine-Versus-Machine of Go games.