Research And Application Of Imperfect Information Game Decision Based On Knowledge And Game-tree Search

Where there are conflicts of interest in human life,there will be games,and in real life,most of the game problems belong to imperfect information games,such as financial transactions,military games,political negotiations,board games,etc.,so the study of related problems has great economic value and practical significance.Due to the characteristics of information asymmetry,the complex game background leads to the exponential growth of the number of decision nodes.In view of the above problems,this thesis proposes to solve the imperfect information game problem by using the opponent modeling and the improved game-tree searching strategy algorithm,and applies it to the four-player competitive mahj ong game.The main work and innovation of this thesis are as follows:1.Combine knowledge with Monte Carlo simulation method to construct the opponent model to predict the hidden information and convert it into relative probability.There are huge hidden information in imperfect information game,and only depending on the visible information may lead to a large deviation.In this thesis,Monte Carlo method is used to simulate the hand of each opponent,and a method for calculating the distribution degree of hand is designed by combining the time sequence information,historical information and relevant domain knowledge,which makes the simulation results more consistent with the real situation.Finally,the simulation results are converted into the acquisition probability and risk table of each tile,which provides important help for the subsequent evaluation value calculation.2.According to the characteristics of mahjong game rules,an improved game-tree searching method is designed to explore the winning path.Firstly,based on the analysis of the game mechanism,the game model is simplified and the search object is transformed into the update process of the hand.Then,the heuristic information is used to design the hand splitting algorithm to generate the combined information.Based on the combined information,the three strategies of fast win,high score exploration and improved exploration are designed to improve the search efficiency from different aspects.Finally,an evaluation function of both offense and defense is designed to calculate the optimal solution by combining with the assessment of winning rate,score and risk probability.3.The intelligent decision system and test platform of imperfect information game based on knowledge are designed.The designed decision model is deployed to the cloud server to build the intelligent decision system,and the decision service is provided through the cloud service,and it is applied to man-machine battle,decision support and game behavior analysis.A test platform is built to test and evaluate the decision-making ability of the system,and an evaluation system is built to analyze the possible defects of the decision system,so as to speed up the iterative updating of the model.Based on the above methods,the mahjong AI program "ZONST-KF-TREE"participated in the Computer Olympiad 2019 championship held by ICGA(International Computer Game Association)and finally won the silver medal.The practice proved that the method in this thesis has a high decision-making level and operability.