| Sequential simultaneous move games of imperfect information have been a challenging topic of artificial intelligence.However,the simultaneous move of sequential simultaneous games leads to some problems such as lack of information,large state space,uncertain reward.The existing computer game technologies are restricted for the needs of practical application,particularly significant in solving the large-scale sequential simultaneous move games.It is known that existing search technologies are capable of dealing with small problem set,but tend to be ineffective for the large-scale problems with enormous action combinations.This thesis studies the related technology and theory of computer game.Aiming at the sequential simultaneous game problem,Simultaneous Move Monte Carlo Tree Search(SM-MCTS)is selected to transform the structure of the game tree.Then,the characteristics and performances of simultaneous decision games are analyzed.Combined with the structure of the multiple trees,a novel algorithm named Sequential Simultaneous Monte Carlo Tree Search(SS-MCTS)is proposed in this paper.The novel algorithm which integrates simultaneous decisions and multiple trees is adopted finally.According to the shortcomings of the existing algorithm,this algorithm skillfully solves the exploration of the joint actions and overcomes the shortage of search depth by transforming the action combination into independent sets.SS-MCTS is different from the previous multiple-tree structure search algorithms,the information between the two trees can be mapped and shared with each other.The novel algorithm is designed for the more conventional online mode of play.In addition,the special node setting and state transition enable the algorithm to accurately simulate the game process of simultaneous decision-making.To prove the practical validity,our algorithm has been testified in several large-scale sequential simultaneous move problems.The convergence to an approximate Nash equilibrium(NE)is demonstrated in Goofspiel,while the efficiency is proved in StarCraft by obtaining remarkable winning rates.The experimental results show that our model has an excellent performance in large-scale sequential simultaneous move games. |
