Research And Implementation Of Dots And Boxes Computer Game System

As known as "fruit fly", Computer Game is recognized as one of the most challenging research topics in the field of Artificial Intelligence. This research has introduced many important theories and technologies in the field of Artificial Intelligence and consequently it makes a profound impact on society and academia. The research of Computer Game can be traced back to 1950s internationally. In the past 60 years, it has made great achievements which have astonished the world. People have already recognized the power of the computer from either IBM’s "Deep Blue" or Inspur’s "Tissot". The Computer Intelligence has overstepped human in the game, and finally coming to the point of human virtue. Recently, with the development of the domestic Computer Game competitions, many game enthusiasts are attracted to Computer Game studies, which have greatly promoted the development of the Computer Game theory and technology.Traditional Computer Game model is like the Connection-Pattern model on which the intersection point on the chessboard is just the move later point. The design of data structure and the description of the chessboard state are relatively simple. Most research of Computer Game in China uses Connection-Pattern chess as study carrier. This article selects Dots and Boxes as the research object to study the related technology about Dots and Boxes Computer Game. Dots and Boxes focus on the edge between the two adjacent points, so compared with the traditional game model it has some particularity on rules and methods; therefore it has much more study significance.In this article, Dots and Boxes’game platform is the study carrier, and it studies the key technology in the field of Computer Game, including some basic concepts, attribute analysis of the study object and the components of game system. It designs the system of the Dots and Boxes Computer Game which including the structure design of the chessboard data, the record of the chessboard type, and the evaluation function design based on simulative playing game. Also it designs and implements the move generation method that removes the equivalent and redundant edges, which not only ensures the level of the game but also improves the searching efficiency comparing with searching all possible moves. Furthermore, based on Alpha-Beta pruning search, game tree searching algorithm is designed. It adopts transposition table, history heuristic and iterative deepening search technology to optimize efficiency and improves the level of the game.By the experimental verification from two angles of both the searching efficiency and the game level, we can get the following conclusions:Compared with the depth searching to all possible moves, parts of the depth search that deleting some equivalence and redundant edges can not only keep the level of the game but also improve the searching efficiency significantly. On the basis of alpha-beta pruning search algorithm, some optimization techniques are added to the algorithm such as transposition table, history heuristic, iterative deepening and so on. Experiments show that the searching efficiency of history heuristic technology to enhance the game tree is the highest, and iterative deepening the worst. Strategy performances are at the same level between adding three kinds of optimization technology and only adding history heuristic technology. Experimental results show that three kinds of optimization techniques all apply to Dots and Boxes game program.The implementation of the valuation method that based on the simulative playing game of chess type shows a certain level of intelligence. Its valuation in the end phase is rather precise. But at the start of the phase, due to the changing drop sequences of the safety-edge, its valuation may be not so accurate on the condition of the unclear division of chess broad. It remains further research in the future about how to design a set of valuation function that can depict chess’s advantages and disadvantages in all phases.The innovations are as follows:(1) According to the characteristics of Dots and Boxes, presenting the move generation method with width-pruning in Dots and Boxes game tree, it’s to delete the equivalent and redundant edge, and use alpha-beta pruning algorithm for game tree search. Through the comparison of the experiment it can improve the efficiency of the game tree search without reducing the level of game.(2) On the basis of alpha-beta pruning search algorithm, it improves the efficiency of the search algorithm by adding some optimization techniques such as transposition table, history heuristic and iterative deepening to reduce the number of nodes in the game tree search, and improve the efficiency of the search algorithm.(3) It designs and implements the valuation method based on simulative playing game of chess type and the method is applied to the program of Dots and Boxes game, which shows certain "intelligence" level.These methods have been successfully applied in Dots and Boxes Game System which is called "BoxKiller" program. The program won the first prize in "CDUT Cup", the Dots and Boxes project of the National Undergraduate Computer Game Competition in 2014. It proved that these methods are workable and practical.