The Study Of Algorithms In Computer Go

Game is one of the important subjects of Artificial Intelligence (AI) and AI's development contributes to the development of the study of game greatly. As one of the main subjects of game, the board game has been studied thoroughly, except for Go. The level of the most excellent Go programs is lower than the level of the primary human player at present. Because of the too large search space in Computer Go, computer is hard to get hold of the fuzzy concept of Go. Therefore, the level of Computer Go is hard to rise. 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 in the Computer Go programs. At the same time, it is helpful to comprehend the human cognition that develop the Computer Go programs, whose level is equal to human's. Therefore, the study of Computer go is important both in theory and in practice.At first, we review the study of Computer Go in the world from the aspects of basis algorithm, search algorithm and learning algorithm, and then we introduce some programs of Computer Go. Search algorithms in Computer Go chiefly include minmax algorithm,alphabeta algorithm,failsoft algorithm,negamax algorithm,negascout algorithm and mtdf algorithm. Learning algorithms and theories in Computer Go involve combinatorial games theory, mathematic morphology, Monte-Carlo algorithm, fuzzy learning, divide and conquer, reinforcement learning, genetic algorithm, neural network, support vector machine, bayesian pattern classification, generalization by explaining, parallel algorithm, and so on. At present, the mainly defects rest with the deficient method in representation of position, incomplete tactics of middle game, and immature learning algorithm. Subsequently, we introduce the relative theory in this study, including mathematics morphology, finite state machine, linear model, perception, and genetic algorithm.After that, we introduce the player's thinking model, basis algorithm, search algorithm and learning algorithm in this study, and the result of experiments of these algorithms. In detail, the major contributions of this study are:1. Put forward an integrated player's thinking model. We do this after putting forward the method of erarchical representation of position, generalizing and classifying plenty of Go terms, extracting target notion, setting up target graph, summarizing some target choices principle and move attributes, and analyzing the notion of player's style. The model's characteristics are comprised of integration, and completeness of the classification of Go terms, target choice principles and move attributes.2. Design an erarchical representation of position, Go cluster algorithm and area partitions based on mathematic morphology. These algorithms based on united theory are simple and have nicer effect tested by the experiment. More meaningful heuristic tactics will be introduced by utilizing the existing mathematic morphology methods.3. Design a pattern encoding method independent of symmetry (PEMIS). Its advantages are encoding based on adjacent character, queue character and figure character of pattern, while irrelevant to black-white symmetry, rotation and transposition symmetry, and translation symmetry of the pattern. The experiment shows that the method works well. In addition, we design a move increment algorithm as a basis algorithm.4. Design a compound target search algorithm. We think that a compound target is composed of simplex targets in two dimensions by AND or OR logic. Its advantages lie on that its basic function may be constituted of the basic functions of simplex target search algorithm. Furthermore, we compare the performances of classic search algorithms.5. Design a pattern/joseki library learning algorithm by PEMIS. The experiment shows that it work well, and the learned library occupied in a small storage area. We design a joseki library learning algorithm by ZOBRIST too, and it works well. Moreover, we design a Go shape and liberty term learning algorithm by teaching, and a player's style learning algorithm by genetic algorithm.6. Develop a Computer Go program named ShoutGo whose core is the player's thinking model, and put these algorithms into practice. ShoutGo deems that a human player own a pattern/joseki library and respective style. After making Go cluster and partitioning the area, a player can proceed to do target guess, focusing on the last stone of the opponent by target choice principle. Likewise, led by target choice principle and respective style, a player can generate new targets, and then piloted by the target searching move with the effect of recommendable move put by respective pattern library/joseki library, a player can select a special move based on move attributes. If the target is unsuccessful, or there is no feasible move, we need to partition areas again or generate other targets based on other decision principles, until finding suitable move. During this course, the pattern/joseki library will affect the recommendation of move, while the player's style model affects the switch of targets.Finally, we discuss the evaluation of the human thinking models, the relation between move increment algorithm and move scanning algorithm, the application of mathematics morphology methods in the basis algorithm, the effect on searching by ko and seki phenomenon, the relationship between characters of searching trees and psychology factors, estimation of searching time, position evaluation function, feasibility of the target search and player's style model building etc.; at the same time, we discuss the application possibility about the method of the machine learning in Computer Go, and put study plan forward.As a branch of AI, Computer Go is related with psychology naturally. In the study, we emphasize the principle of taking human players as model especially, and the identity with human players' thinking, and the perfection of its learning algorithm. Our future work will focus on the learning algorithm. Only when the Computer Go program can learn something just like a human player, Computer Go is hopeful.