Research And Implementation Of UCT Algorithm In Dots And Boxes Computer Game

Google AlphaGo beat world chess champion Lee Sedol 9p In March 2016, so artificial intelligence (AI), computer games once again become the focus of the public.Artificial intelligence is an important research direction of computer science, the main goal is to study that using the computer to simulate and executor the function of brain, making the computer do some mental activities such as learning, thinking and judgment. Computer games combine the game theory and computer science together for computers to make some rational decisions just like human. Computer games are one of the most challenging branches of artificial intelligence that has been known as the "drosophila" of artificial intelligence. The research of computer games promotes the development of artificial intelligence and it developed earlier abroad while the speed of development is still relatively slow in domestic that mainly uses chess as the carrier is the method of the current studies.Dots and boxes is the pencil-and-paper game that played by two people and it is proposed by Eduard Lucas in 1891 who is a French mathematician. The system of dots and boxes game mainly composed by four parts that are board representation, move generation, search algorithm and evaluation function and the core part is the search algorithm. The search algorithm of traditional dots and boxes game system is the a-P pruning algorithm. The algorithm generates a game tree with certain depth according to the current situation and the game tree is searched from top to bottom. However, the problem using the α-β pruning search algorithm is low depth, waste of time and other issues. On the other hand, the α-β pruning algorithm must uses a valuation function to assess the merits of the chessboard. Currently, common assessing methods for assessment are accurate without safety edage in chessboard. But if chessboard contains safety edage, errors are caused during the process of valuation due to the different order of the capture of safety edage. So, the evaluation function is relatively difficult to design in the system of dots and boxes game.UCT algorithm is an extension of the Monte Carlo algorithm and the algorithm achieve assessing the node of game tree by law of large numbers that simulate the chess game for many times. Meanwhile, it also applies UCB to the search of game tree. The UCT algorithm select the node by the value of UCB instead of random selection and it guides the better direction for the growing up of the game tree, the optimum solution will be obtained faster. It judges the merits of the chessboard and predicts the good from the bad of the nodes by the results after doing large number of simulated chess game and choice the node with good performance firstly. This approach solves existing evaluation function problem of the dots and boxes game. Therefore, the UCT algorithm is applied to dots and boxes game and it proved that the dots and boxes Game of UCT algorithm is higher than the level of α-β pruning algorithm.Due to the situation that there will be many edges with the same value, equivalent edges, during the game of dots and boxes. We will obtain the same result by choosing one of them to do the search or search them together. So, it only need to search for one edge from the equivalent edge, if it is no influence to the level of the game, the equivalent edges will be during the stage of the expansion of child node, we put forward UCT algorithm based on pruning equivalent edges, Finally, experimental results demonstrate that the improved UCT algorithm can reduce the number of nodes for searching and improve the level of the game.Profit value represents the value of simulative chess that affects the result of choosing node during the searching of game tree and also decides the direction and the depth. In order to improve the accuracy of computing the profit value in the phase of simulating the chess by UCT algorithm, it proposes a method to compute the profit value based on revised value according to the original method that not only distinguish the outcome but also quantify the degree of outcome and get the accurate profit value furtherly. To increase the number of times of simulation by UCT algorithm, it achieved that the UCT algorithm is executed based multi-core CPU and make full use of the computing performance of multi-core CPU. In summary,we put forward-Parallel UCT algorithm based on modify profit value Experiments show that improved algorithms of UCT provide higher levels of the game than original UCT algorithm.Innovations of this thesis are shown as follows:1. After the carefully analysis of the common searching algorithm that used in dots and boxes game.We found that UCT has the advantage of time and space algorithm compared to conventional α-β search algorithms and the algorithm is applied to dots and boxes game.2. In the stage of the expansion of child node, we put forward the conception of equivalent edges, before the expansion of child nodes; we pruning them to reduce the time and space complexity of the algorithmImprove the level of software.3. In the phase of simulation chess game of UCT algorithm, we put forward Parallel UCT algorithm based on modify profit value, include two points in this thesis. Firstly, to improve the accuracy of the profit value, we propose an improved equation to compute the profit value based on modify value Secondly, we achieve the parallelization of UCT algorithm to increase the number of times of simulation.