Key Technologias Research Of EinStein Wurfelt Nicht! Computer Game

Computer game is one of the important fields of artificial intelligence,and it is known as the "flies" of artificial intelligence.EinStein Wurfelt Nicht! is a complete information game,which the game information is completely transparent,that is,both players of the game can completely grasp the current game information at any time.However,It is different from other complete information game.In the process of playing chess,both players need to throw the dice to determine the pieces which can be taken.Therefore,it has some randomness,which brings the computer game system a new challenge to the analysis of the chessboard.When EinStein Wurfelt Nicht! was listed as the China Computer Game Competition in 2012,more and more people are focusing on the research of EinStein Wurfelt Nicht! technology.In the research of the evaluation function,the existing technology often analyzes the board state from three factors of offensive,defensive and probability,and these factors are linearly added with different weights to construct the evaluation function.The evaluation function constructed in this way is generally limited by the designer's game level,and it is difficult to obtain an optimal weight.In the research of game tree search algorithm,most of people are aimed at the improvement of Alpha-Beta pruning algorithm and expectiminimax algorithm.These algorithms depend on the evaluation function.And the quality of the evaluation function determines the level of the game system.This thesis takes the EinStein Wurfelt Nicht! as the research object and studies the computer game technology in EinStein Wurfelt Nicht!.In the aspect of game tree search algorithm,this thesis introduces the Monte-Carlo tree search(MCTS)algorithm,and proposes a probability heuristic parallel Monte-Carlo tree search algorithm.The probability node is used to represent the dice-thrown event,and connects maximum or minimum nodes in a many-to-many manner.Then,this thesis optimizes the parallel efficiency of probability node.In the aspect of the evaluation function,this thesis designs the feature to represent the chess board,and uses the value network based on the multi-layer perceptron to evaluate chess board.Then,the value network is combined with the probability heuristic Monte-Carlo tree search algorithm during training procedure to improve sample quality.In the aspect of the game system,the EinStein Wurfelt Nicht! game system is designed and implemented,which has functions such as human-computer interaction,automated game,game record saving and training network.The main innovations of this thesis are as follows:1.In the aspect of game tree search,this thesis studies and designs the data structure used to represent random events,and proposes probability heuristic parallel Monte-Carlo tree search algorithm.On the one hand,probability nodes are used in the game tree to represent the dice-thrown event,and the probabilistic node and the maximum or minimum node are connected in a many-to-many form;on the other hand,the Monte-Carlo tree search algorithm is used in the above game tree,and optimize the tree parallelization method of the algorithm.Through the practice and analysis of experiments,the probability heuristic parallel Monte-Carlo tree search algorithm has higher search efficiency and intelligence,and won the runner-up(first prize)in the 2018 Chinese University Computer Game Competition;2.In the aspect of evaluation function,this thesis studies and designs a value network based on multi-layer perceptron to predict the value of the board.Firstly,this thesis extracts 48-dimensional feature vectors from the chess board,designs the structure of value network,and combines it with the probability heuristic parallel Monte-Carlo tree search algorithm.Secondly,inspired by the AlphaGo Zero program,the training process of the value network in the three stages of sample collection,network training and strength evaluation is designed.Through the analysis of experiments,the value network proposed in this thesis has a higher level of intelligence after training,and has a higher winning rate when combined with the probability heuristic parallel Monte-Carlo tree search algorithm;3.In the aspect of computer game system,this thesis designs and implements the EinStein Wurfelt Nicht! game system,including the training subsystem and the game interaction subsystem.The training subsystem is used to execute and manage the training process of value network.This subsystem trains the value network according to the parameters set by the user,views and saves the loss and winning rate during the training process.In addition,it can save the network model,which can be provided to the game interaction subsystem.The game interaction subsystem provides the user with the function of playing the algorithm in the system.The user can select the existing strategy in the system,manually set the policy parameters,and realize the automatic game between human-human,human-computer or computer-computer.The game procedure can be visualized and stored.In summary,this thesis studies the EinStein Wurfelt Nicht! computer game technologies in three aspects:search,evaluation and computer game system.Firstly,the Monte-Carlo tree search algorithm is modified and optimized in parallel for the problem of randomness,which improves the search efficiency and intelligence.Secondly,the value network model based on multi-layer perceptron and its training method are designed to further improve intelligence;Finally,the EinStein Wurfelt Nicht! computer game system is realized,which establishes the verification tool for designing and analyzing of computer game algorithms.