1. Introduction

Computer game, also known as machine game, takes computer chess as the research carrier, and builds a game information processing system that is closer to human intelligence by simulating the thinking process of human chess players [1]. It has the ability to think, judge and reason like human beings, makes rational decisions from the perspective of human intelligence, and plays various chess games with human players or another computer. In the field of artificial intelligence, computer game is a challenging subject. Its research results can be applied to economic, medical, military and other related fields, which greatly promotes the progress of science and technology.

The computer game mainly relies on chess and card games for experimental research, and its game system is mainly composed of a front-end game platform and a back-end search engine [2]. Among them, the game platform mainly includes: information transmission, interface display, chess rule judgment and chess control; Search engine is the core of game, including the search and evaluation of game and the formation of knowledge base. Among them, it is assumed that Party A plays the chess first. After Party A plays the chess, the referee will judge whether the move is legal according to the rules of the chess. If it is legal, it will be displayed on the chess board interface. Otherwise, it will send an instruction to reselect the landing point; After Party A finishes playing chess, Party B will play chess. Similarly, the judge will judge whether the move is legal according to the rules. If it is legal, it will be displayed on the chess board. Otherwise, it will be played again. At this point, the process of alternating rounds of popular chess between the two sides is completed.

According to the existing knowledge, machine games can be divided into two types: complete information games and incomplete information games based on the degree of chess players' mastery of other players [3]. Among them, complete information game means that in the process of computer game, each player has accurate information about the characteristics, strategy space and income judgment of other players, such as go, checkers, six piece chess and so on. If a chess player cannot accurately grasp the global situation and strategy space information of other participating players, or does not have accurate information of all participating players, then the computer game between the two sides in this case is called incomplete information game, such as bridge, poker, military chess, etc. Among them, the main technology and complexity of two person complete information games (such as go, Chinese chess, checkers, etc.) are representative, and they are also the focus of people's research on computer games [2].

Machine game is a classical field of artificial intelligence research [3]. Its history is almost as long as that of artificial intelligence. In 1956, at the first DAMOS conference, the term "artificial intelligence" was formally proposed, marking the formal birth of artificial intelligence as a new discipline. However, as early as the early 1950s, Alan Turing once discussed the relationship between the next stage and machine intelligence with the "paper chess machine". In 1956, the rise of artificial intelligence, Samuel's "checkers machine" computer program was successfully developed, which became one of the important signs of the rise of artificial intelligence as a discipline. From then on, the prelude of machines challenging human intelligence was opened.

In May 1997, the world-famous machine game system "deep blue" and the chess master Kasparov's man-machine war ended with a machine victory [2]. IBM called the victory of "deep blue" a milestone in the field of artificial intelligence, and machine game has become the focus of attention.

Up to now, the research of artificial intelligence on game is mostly focused on chess, but its purpose is not to let computers play chess with people, but mainly to provide a testing ground for artificial intelligence research, test the relevant technologies of artificial intelligence, and promote the development of these technologies [3]. Many concepts and methods in artificial intelligence are extracted from the game program, and many of his research results have been used in military command and economic decision-making systems. Machine game is considered as one of the most challenging research directions in the field of artificial intelligence.

The research of modern machine game mainly focuses on the man-machine game of go, chess and Gobang. Among them, the computer game research of chess has the longest history and has experienced a magnificent "fight". In particular, the victory of the "deep blue" computer not only left a deep impression on mankind, but also summarized a set of information about the process modeling, state representation, method generation, chess game evaluation, game tree search. The core technical points such as the development of the opening library and the residual library, system testing and parameter optimization have determined the research direction for the subsequent related research. This paper will introduce the domestic and foreign scholars' research on machine game in two person game.

2. Method

2.1. Research Abroad

In 1769, Wolfgang Von Kempelen showed the world his chess game machine, which was the first machine with the concept of artificial intelligence. In 1997, the famous chess computer Deep Blue (super deep blue) of IBM company in the United States defeated Garry Kasparov, the world chess champion at that time, and became famous in the world. In the 1950s, Arthur Samuel, one of the founders of artificial intelligence, began the development of a powerful Checkers (64) program in his pioneering work in the field of machine learning. In 1962, his program defeated a capable human player, and this result was recognized as a victory in the field of artificial intelligence [3]. The artificial intelligence research team of the computer science department of the University of Alberta in Canada cracked the 8 * 8 international Checkers (64). This achievement was selected by science magazine as one of the top ten breakthroughs in scientific research in 2007. However, there is no good breakthrough in the research of Checkers (100).

The traditional expert system method has been playing an important role in chess evaluation. In 1997, Chisholm and bradbeer used genetic algorithm to optimize the board evaluation function in the international checkers program [4]. The best program in the field of international checkers is blondie24. In 2001, chellapilla and Fogel added expert knowledge to the genetic algorithm, which greatly improved the game ability of the international checkers program blondie24. In order to find potential good moves, Fogel uses the evaluation strategies of minimax search tree and neural network. In blondie24, using these strategies, not every search can find good moves, because some of them will be selected more frequently as opponents' moves. In 2007, Kusiak et al. Proposed a new method used in the international checkers game in their paper "evolutionary approach to the game of checkers", that is, the genetic algorithm evaluation of linear and non-linear evaluation functions [4]. In each stage, the linear combination of parameters will be considered, and the coefficients of the linear combination are optimized through the continuous development process. In 2008, Dura and Oliveira used chessboard features in the parametric chessboard evaluation function, such as: chessboard flexibility, soldier structure, King's security and central control, and used particle swarm optimization (PSO) to optimize their weights [5]. Under the same experimental conditions, it was found that PSO can provide faster learning results than simulated annealing. Especially in the presence of finite computing time. At present, the evaluation functions used mainly include static evaluation, such as the evaluation of expert knowledge and the traditional linear evaluation function; In addition, there are dynamic evaluations, such as genetic algorithm evaluation and Monte Carlo evaluation.

After computer go created a new situation, researchers turned their research direction on computer games to Monte Carlo tree search. The use of Monte Carlo method in games can be traced back to 1973. Widrow et al. Applied Monte Carlo simulation to poker blackjack [5]. It is easy to think of using Monte Carlo method in incomplete information and random games. However, it is not easy for most games to think of adding some negligible artificial information to the complete information, and this idea was proposed by Abramson. Bazy and Helmstetter discussed the application of Monte Carlo method in go game. In 2015, Michael bowling and others published an article in the journal Science that the two person restricted Texas Hold'em has been solved in the improved CFR algorithm. In March 2016, the alphago intelligent program developed by Google's deepmind company defeated professional go player Li Shishi by 4:1 [1]. This is an epoch-making progress. Artificial intelligence once again brings people to the forefront of science and technology. Alphago uses an algorithm that combines Monte Carlo search tree, decision network and value network to win other go programs with a 99.8% victory rate. In May 2017, the upgraded version of alphago defeated the world go champion Ke Jie by 3:0 in China [1]. Compared with the previous version, this version of alphago only uses a single neural network and Monte Carlo tree search (MCTS).

The main landmark events in the development of machine game are as follows. In 1950, Shannon published an article on computer chess: programming a computer for playing chess; In 1951, Alan Turing developed the first complete computer chess program in his paper [1]. In 1956, John McCarthy invented α − β Pruning search algorithm; In 1967, the computer chess program designed by Richard Greenblatt and others defeated human players in an official competition for the first time; In 1981, Cray blitz, a computer chess program, defeated master level players in an official competition for the first time; In 1994, Gerald Tesauro used TD（ λ ) Reinforcement learning algorithm developed ten Gobang program; In 1997, deep blue, a Chinese chess program, defeated Garry Kasparov, the world champion, for the first time; In 2007, Jonathan Schaeffer of the University of Alberta, Canada, and others mathematically proved the solvability of checkers.

Machine game is considered as one of the most challenging research directions in the field of artificial intelligence, and computer go can be regarded as one of the most difficult fortresses [2]. The earliest Go program was proposed by Albert zobrist in his doctoral dissertation on pattern recognition in 1968. After that, Jon Ryder, Walter ritman, Bruce Wilcox and Elwyn Berlekamp all contributed to the development of computer go. Walter Reitman and Bruce Wilcox published their program interim in 1978 2. Defeat a level 22 chess player. Ten years later, Wilcox independently researched the integration of interim 2 was rewritten as the first commercial Go program nemesis. At the end of 1985, the first "Yingshi Cup" international computer go competition was held. With the holding of the computer Go program competition and the release of the first commercial program, computer go was officially established as a research field in the 1980s and flourished in the 1990s. In 2006, two Hungarian researchers, L. Kocsis and C. szepesvari, proposed to apply the uct algorithm to the go machine game, bringing the go research to a new stage [2]. Most of the previous Go programs relied on static evaluation based on knowledge. Since 1968, computer go has developed for more than 40 years. With the application of uct algorithm in go machine games, some scholars have divided the development history of computer go into two stages. From 1968 to 2005, it has become the "traditional computer go era" and from 2006 to now, it has become the "modern computer go era".

The main computer go events are as follows. Computer Olympiad (Olympic computer game program competition) held by ICGA (International Computer Games Association) every year since 1989; Since August 2006, the Chinese machine game Championship hosted by the Chinese Association of artificial intelligence (the second championship in 2007 began to join the computer go game). These competitions have greatly promoted the popularization and development of the computer go game in China.

2.2. Research at Home

Since the birth of computer game, it has been loved by researchers at home and abroad. With the update of computers, researchers are constantly producing new theoretical results. As a leisure and entertainment project with clear definitions and rules, chess and card games are loved by the public. They can represent a typical type of intelligent problems. Therefore, many AI researchers choose computer games as a breakthrough in the research of intelligent algorithms, which also means that they break through the public's acceptance threshold for emerging technologies.

In China, in the early 1990s, Mr. Chen Zhixing, a professor of Chemistry Department of Sun Yat sen University, took the lead in developing the Go program "hand talk", which became a good story for a while and won the world championship with excellent results [3]. The famous six pieces chess developed from Gobang was invented by Professor Wu Yi Cheng of the Department of information engineering at National Chiao Tung University in Taiwan in response to the ban on playing Gobang. Except for the first player who played one piece in the first hand, the other players played two pieces at a time, which greatly improved the fairness of the game. Therefore, liuziqi is currently considered the most equitable chess game. In response to this research result, Professor Wu explained the origin of liuziqi to the public at the 11th International Conference on advances in computer games in September 2005, and officially published the world's first international paper on liuziqi, which has received considerable response in the world's computer field.

Compared with go, the development of Chinese chess in the field of computer games is also obvious to all. In recent years, many chess programs with high chess power have gradually emerged. In the 1980s, Professor Huang Yunlong of Nankai University led his students to develop a series of Chinese chess programs [3]. With the development of computer games, researchers have become more and more enthusiastic about the research of games. Among them, the "chess day Saint" of the Institute of artificial intelligence and robotics led by Professor Xu Xinhe of Northeastern University adopts deep T-U pruning (deep) α-β Cut-off) algorithm. In the first Chinese chess man-machine battle in August 2006, master Xu Yinchuan, who was the first Chinese chess player, was defeated by the fierce attack of the chess program of "chess day Saint" [3]. As a result, China has reached a higher level in the development history of computer games with complete information, which also marks that the research in this field has reached a certain level.

From the perspective of domestic research, scholars study international checkers relatively late, but they are deeply loved by domestic people, and there are authoritative competitions on international checkers in China. Driven by some scholars who love research, China held the first world intelligence games in Beijing, China, in October 2008. Approved by the General Administration of sport of China, the first national intellectual games will be held in 2009 [3]. International checkers is one of the official competitions, which greatly promotes the development of international checkers in China. Checkers was introduced into the national computer game competition in 2012 [6-10]. In 2015, the organizing committee renamed it international checkers, which attracted many scholars to study it in depth. In recent years, although domestic computer game has made some theoretical achievements, there are still some shortcomings compared with foreign countries, which need researchers to continue to work hard.

3. Result and Discussion

The history table and iteration deepening are combined with the basic algorithm α − β, and compared with this basic algorithm to test their performance. Under the same conditions, when the search depth is from 1 to 5, the number of search nodes and the search time used by the three methods are shown in Table 1 and Table 2, respectively.

Table 1. Comparison in Search Nodes.

Table 2. Comparison in search time (/ms).

From Table 1 and Table 2, it can be found that iteration deepening algorithm is basically same to the basic algorithm α − β on search nodes and search time as shallow search begins. With the increment of depth, iteration deepening algorithm bears certain comprehensive advantages compared with other algorithms, but not stands out in pruning effect from the perspective of numbers. It can be supposed that, at this time, the pruning effect of iteration deepening algorithm is better than others, however, owing to more search nodes at the same time, the number of total nodes is close to the basic algorithm α − β. In the following trial of program battle, this assumption is attested. There are ten tests, and each one is finished in 5 seconds, with seven wins of iteration deepening algorithm and three draws. The results show clearly that the search depth of iteration deepening algorithm is much higher than basic algorithm α − β, so is the pruning effect and chess skill.

In addition, pruning algorithm α − β is strongly pertinent to nodes range which can be seen from the Table. History table can effectively reduce the search time of algorithm α − β, and the more the number of layers the more reductions. For example, when the search time of the second layer reduces 1 second, the third layer shrinks more than double, and the search time of the fifth history table algorithm has reduced to approximately one tenth of the original and the number of nodes drops dramatically too. All these show that algorithm α − β is sensitive to the sequence.

4. Conclusion

This paper introduces the progress of domestic and foreign studies on board games. Jiuqi, which is also a board game, is a complete information game like go, chess, general chess and other board games; Compared with go, chess, general chess and other board games with more traditional academic research, Jiuqi has less research. The current research has only done corresponding research in pattern matching, Bayesian network and TD algorithm application, and there is no literature on deep reinforcement learning; Although Jiuqi's computer game algorithm is limited to the lack of resources such as laboratories and experts, and has not reached the level of experts, it has made certain achievements in the principle research of computer game. Both Jiuqi and Weiqi have similar state space scales, so this game cannot simply use the deep reinforcement learning algorithm used in Atari series games; Compared with the usual turn based board games such as go, Jiuqi has an uncertain turn length, so the representation of the state is more complex than go, and it is difficult to simply apply the existing game model based on uct search tree. These factors make it difficult for games like Jiuqi to be promoted and publicized in the field of computer games, which is not conducive to the development of this game.