Research And Improvement Of Game Algorithm Based On Dots-and-Boxes

Artificial intelligence is a branch of computer science,the purpose is to enable the machine to be able to perceive the environment as human intelligence and maximize the possibility of achieving the goal.Machine game is one of the most challenging branches of artificial intelligence,and its research has a positive effect on the development of artificial intelligence.The research on machine game in foreign countries is earlier,and has made some achievements,and domestic research lags behind.Using chess as the carrier is the main research method of machine game.Machine game system can be divided into four parts: situation representation,action set,evaluation function and game tree search,and the first two are relatively simple.In this paper,we focus on the evaluation function and game tree search algorithm based on Dots-and-Boxes.In the respects of evaluation function,analyzes the influence factors of Dots-and-Boxes chess game evaluation,designed a parametric evaluation function.Genetic algorithm is used to optimize the parameters.In order to speed up the convergence speed,the heuristic information is used to direct the search,and the fitness matrix and the cross variance matrix are introduced,each parameter in the chromosome is considered separately.In order to reduce the training time,a gradient training scheme is proposed.Finally,the experiments are carried out to verify the analysis,the results show that the chess force after whose evaluation function parameters optimized is improved,gradient training scheme effectively reduces the training time.In the respects of game tree search,researched the classic game tree search algorithm.The idea of the algorithm and its improvement measures are analyzed.The number of nodes and time cost of different search algorithms are compared by experiments,and the shortcomings of the algorithm are also pointed out,these deficiencies are often the basis for the optimization of other search algorithms.This paper also briefly introduced several optimization strategies,the optimization method is analyzed,and the optimization results are verified by experiments.Traditional game tree search algorithm search for equal depth so that the time resources can’t be allocated reasonably resulting in low efficiency.In this paper,we propose the concept of dispersion as a standard to judge the different situation of different depth search.History heuristic algorithm may not be accurate and the efficiency of iterative deepening is low.So this paper proposes a HT-IT algorithm.The algorithm has the advantages of both history heuristic algorithm and iterative deepening,and search efficiency is improved;studied the parallel game tree search algorithm based on PVM,which combines the game tree search algorithm with parallel and distributed.The experiments have verified the above improvement strategies,results show that compared with other algorithms,variable length search scheme and HT-IT algorithm reduced the number of search nodes,parallel game tree search algorithm effectively reduces the search time.