| Since the 1950 s,the problem of machine games has been solved in perfect information games and two-player imperfect-information games.However,there still exists a huge challenge in solving approximate Nash equilibrium strategies in multi-player imperfect-information games.Counterfactual Regret Minimization is a key method for calculating Nash equilibrium in game theory,while reinforcement learning is a paradigm and methodology for learning strategies in machine learning.The combination of Counterfactual Regret Minimization and reinforcement learning is an important research direction in imperfect-information games.Competition Mahjong is an internationally popular competitive Mahjong game with a large number of information states and a long sequence of actions,making it a typical large-scale,multi-player imperfect-information game.This thesis takes the Competition Mahjong multi-agent machine game as the application background,and designs a large-scale imperfect-information game AI system using the Counterfactual Regret Minimization(CFR)and deep reinforcement learning(DRL)algorithms.Firstly,Counterfactual Regret Policy Gradient(CFR-PG)that combines CFR and DRL algorithms is demonstrated and proposed.Then,key technical implementation methods for large-scale imperfectinformation games based on CFR-PG are designed.Finally,a large-scale imperfect-information game system is constructed using Competition Mahjong as an example.The main innovation of the thesis is in the following four aspects:(1)a new variant of Deep CFR for imperfect information games is proposed,which is Counterfactual Regret Policy Gradient(CFR-PG)algorithm.The algorithm combines game theoretic reasoning with Deep Reinforcement Learning.To obtain a CFR theoretical reasoning result through DRL method,CFR-PG is proved being so as to obtain a solution approximating to Nash equilibrium.(2)the author describes the key technical points of large imperfect information games CFR-PG algorithm,include: sampling through self-play and MCCFR;training the counterfactual regret value network;improving the new strategy by counterfactual regret gradient ascent;obtaining a weighted average strategy converging to an ?-Nash equilibrium through the average strategy after T iterations,etc.Especially,the average strategy can not be simply obtained by Neural Networks,the author provides a new techniques to get it.(3)in order to speed up the CFR-PG iteration process and improve the iteration efficiency at the beginning of the program,the Simple Search algorithm is presented to warm-up the initial CFR iteration.By using Simple Search algorithm,we can obtain sampling experience more easily and quickly.(4)on the basis of the CFR-PG algorithm,the author has designed and built a large multi-agent imperfect information game AI,which is 4-player National Standard Mahjong AI system.The convergence of the CFR-PG algorithm is verified by the performance data of the system. |
