Research On Head-up No-limit Texas Hold'em Poker Strategy Based On State Abstraction And Midgame Solver

In the 1940 s when John von Neumann,one of the “fathers ”of computer science,created the field of game theory.This has been the basis of modern economics.More recently it has attracted significant interest in computer science and artificial intelligence in particular,as highlighted by the triumph of alphago from Deepmind over top human player Li shishi in 2016.The field of computational game theory incorporates ideas from traditional game theory with modern computational technology to produce computer agents that behave rationally.A major distinction in game theory is between games of perfect and imperfect information depending on whether agents have information that is private and not accessible to the other agents.Games of imperfect information are more challenging computationally and involve strategic tactics not found in perfect information,such as “bluffing ”in poker.Texas Holdem is a prime example of an imperfect-information game and is the most popular form of poker for humans.It has also received significant study within the artificial intelligence community as a major challenge problem in light of the annual computer poker competition held at the top conference AAAI.Currently the most efficient algorithm for approximating Nash equilibrium strategies in large imperfect-information games,called Counterfactual Regret Minimization(CFR),scales to games with approximately 1017 states,while the variant of two-player no-limit Texas hold 'em poker played in the competition has around 10165 states.Therefore,CFR cannot be scaled to solve the problem directly.To address this,the strongest agents first apply what is called an abstraction algorithm that produces a smaller game that is strategically similar to the original game.Then the smaller abstract game is solved with existing techniques such as CFR,and its solution is mapped back to the original game to produce full strategies.This paper presents new approaches for abstraction that can be applied to create strong poker agents.But using action translations causes the off-tree problem that is part of reasons why agent not well performed in the late game,we propose a new approach that generalizes endgame solving to apply to earlier portions of the game as opposed to just the final portion,by integrating a value function to approximate payoffs.This new approach is called midgame solving.By incorporating an evaluation technique called effective hand strength,we are able to integrate machine learning with the new midgame solving approach in order to create an algorithm for modeling the opponent's hand distribution and strategy,using historical data from the computer poker competition.Our approach integrates state-of-the-art techniques including CFR+ and efficient leaf node evaluation techniques for speed enhancement.A resulting agent came in third place in the 2017 Annual Computer Poker Competition for two-player no-limit Texas hold'em.In order to evaluate the validity of the system and to collect game data,we have also developed a web-based Texas Hold'em player system in addition to using the AAAI computer competition platform.