Research On The Prediction And Life And Death Of The Game In Computer Go

Computer Go has always been the focus of computer game and artificial intelligence.Although the rules of the computer Go is simple,but its chess changes,but also caused the computer Go game high complexity,it's unable to complete the task which purely by violent search to calculate the move point by modern computers,the way of artificial Intelligent must be introduced to solve this problem.From the research of computer Go,a large number of artificial intelligence algorithms applied to computer Go,such as pattern matching,UCT algorithm,neural network,K-means algorithm and other machine learning algorithms have promoted the development of computer Go research to varying degrees.In the 9*9 size of the board,after the continuous study of scholars at home and abroad,the computer Go level has reached the level of professional chess players,but usually in the large formal competition,the size of the chess board is more than the size of 19*19 Board,and in the 19*19 size of the board,the computer chess level has reached the level of professional chess player.In this paper,the maximum entropy algorithm is used to study the move prediction on the 19*19 size board,and the solution of the life-death problem is studied by UCT algorithm.The main contents are as follows:1)A brief introduction to the computer Go,leads to the main research work and solutions,for the development of research work to make the appropriate preparation.2)In this paper,the maximum entropy algorithm and the OWL-QN(Orthogonal Wise Limited-memory Quasi-Newton)algorithm are used to predict the move of the computer Go.The pattern is matched by using the pattern template of different size,and each extracted pattern is coded by Zobrist hash,the model is trained by the maximum entropy algorithm and the OWL-QN algorithm,and then the model is tested by using the test data.Experiments show that the correct rate of 20.58%is obtained on 500 courses,and the time and space performance of training are greatly improved.3)In the problem of life-death,the traditional solvers can only deal with the problem of closed boundary life-death.In this paper,we propose a UCT(Upper Confidence bounds for Trees)algorithm for the problem of open boundary life-death.First,according to the given threshold,the search area is determined by calculating the membership degree of each empty point on the board,Then,the problem of given open boundary life-death is solved by a UCT algorithm whose search area for boundary color is one round larger than that of its opposite color.Experiment shows that this algorithm can correctly solve 101 problems out of the 123 test problems without using any Go knowledge or introducing extra stones.The accuracy rate is 82.1%.Furthermore,the algorithm can give correct answers under a broad range of threshold for most problems.Only a small portion of the problems are sensitive to the given threshold.