Search

We demonstrate two game theory-based programs for headsup limit and no-limit Texas Hold’em poker. The first player, GS3, is designed for playing limit Texas Hold’em, in which all bets are a fixed amount. The second player, Tartanian, is designed for the no-limit variant of the game, in which the amount bet can be any amount up to the number of chips the player has. Both GS3 and Tartanian are based on our potential-aware automated abstraction algorithm for identifying strategically similar situations in order to decrease the size of the game tree. Tartanian, in order to deal with thevirtually infinite strategy space of no-limit poker, in addition uses a discretized betting model designed to capture the most important strategic choices in the game. The strategies for both players are computed using our improved version of Nesterov’s excessive gap technique specialized for poker. In this demonstration, participants will be invited to play against both of the players, and to experience first-hand the sophisticated strategies employed by our players.

We show how to find a normal form proper equilibrium in behavior strategies of a given two-player zero-sum extensive form game with imperfect information but perfect recall. Our algorithm solves a finite sequence of linear programs and runs in polynomial time. For the case of a perfect information game, we show how to find a normal form proper equilibrium in linear time by a simple backwards induction procedure.

At AAAI'07, Zinkevich, Bowling and Burch introduced the Range of Skill measure of a two-player game and used it as a parameter in the analysis of the running time of an algorithm for finding approximate solutions to such games. They suggested that the Range of Skill of a typical natural game is a small number, but only gave heuristic arguments for this. In this paper, we provide the first methods for rigorously estimating the Range of Skill of a given game. We provide some general, asymptotic bounds that imply that the Range of Skill of a perfectly balanced game tree is almost exponential in its size (and doubly exponential in its depth). We also provide techniques that yield concrete bounds for unbalanced game trees and apply these to estimate the Range of Skill of Tic-Tac-Toe and Heads-Up Limit Texas Hold'em Poker. In particular, we show that the Range of Skill of Tic-Tac-Toe is more than 100,000.

Predicting the future is a useful skill to have. It may not be impressive to predict that a stone will fall if we drop it, or that a tree will tumble if we chop it, as these systems follow predetermined behavior. It becomes harder to predict when free will enters the picture. If a single rational agent enters the picture, we would expect to see it strive to achieve the best situation for itself. We can expect it to choose whatever course of action that has the most promising outcome. Such prediction gets a whole lot more complicated when several rational agents simultaneously try to achieve individual goals. Actions of one agent influences the situations and outcomes of other agents. The situation is not any easier if we are one of the agents in the system, trying to choose what action to take. We still want to predict what the others might do, so we can plan our best response with respect to the prediction. Predicting behavior of rational agents has many application areas. The phrasing of the last paragraph was vague for sole purpose of not implying any restriction on what agents are and in what context they act. The whole area of reasoning about rational interaction of agents is known as Game Theory. The application areas of Game Theory fathoms most academic disciplines, all the way from Political Science and Economics through Biology to Computer Science. It also has played an important role in areas Philosophy and Ethics. It has even been used to politically justify military conflicts and arms races. The applications of game theory all construct formal mathematical model for whatever system that is to be analyzed. A common solution sought after is the notion of an equilibrium. An equilibrium is a strategy for each agent, such that no agent can gain from deviating from the given strategy, assuming that all the other agents follow their given strategies. It is so to say a minimum requirement for a prediction to be reasonable. If some agent could do better by deviating from the given strategy, we cannot expect the prediction to hold, as the agent would surely deviate. This thesis deals with computing equilibria of game theoretic models where only two agents are involved. The work described ranges from the theoretical development of algorithms for computing refined equilibria, which satisfy additional constraints beyond being an equilibrium, to the practical solving of real life games. Part I contains an overview of the results of the thesis, as well as the necessary background to appreciate the results. Part II contains most of the papers published during the PhD study. Seven papers are included here, all of which have been presented at conferences. Two of the papers are included in their extended versions, one of which has been accepted for a journal.

We present Tartanian, a game theory-based player for heads-up no-limit Texas Hold'em poker. Tartanian is built from three components. First, to deal with the virtually infinite strategy space of no-limit poker, we develop a discretized betting model designed to capture the most important strategic choices in the game. Second, we employ potential-aware automated abstraction algorithms for identifying strategically similar situations in order to decrease the size of the game tree. Third, we develop a new technique for automatically generating the source code of an equilibrium-finding algorithm from an XML-based description of a game. This automatically generated program is more efficient than what would be possible with a general-purpose equilibrium-finding program. Finally, we present results from the AAAI-07 Computer Poker Competition, in which Tartanian placed second out of ten entries.

We present Tartanian, a game theory-based player for headsup no-limit Texas Hold’em poker. Tartanian is built from three components. First, to deal with the virtually infinite strategy space of no-limit poker, we develop a discretized betting model designed to capture the most important strategic choices in the game. Second, we employ potential-aware automated abstraction algorithms for identifying strategically similar situations in order to decrease the size of the game tree. Third, we develop a new technique for automatically generating the source code of an equilibrium-finding algorithm from an XML-based description of a game. This automatically generated program is more efficient than what would be possible with a general-purpose equilibrium-finding program. Finally, we present results from the AAAI-07Computer Poker Competition, in which Tartanian placed second out of ten entries.

We present a new abstraction algorithm for sequential imperfect information games. While most prior abstraction algorithms employ a myopic expected-value computation as a similarity metric, our algorithm considers a higherdimensional space consisting of histograms over abstracted classes of states from later stages of the game. This enables our bottom-up abstraction algorithm to automatically take into account potential: a hand can become relatively better (or worse) over time and the strength of different hands can get resolved earlier or later in the game. We further improve the abstraction quality by making multiple passes over the abstraction, enabling the algorithm to narrow the scope of analysis to information that is relevant given abstraction decisions made for earlier parts of the game. We also present acustom indexing scheme based on suit isomorphisms that enables one to work on significantly larger models than before. We apply the techniques to heads-up limit Texas Hold’em poker. Whereas all prior game theory-based work for Texas Hold’em poker used generic off-the-shelf linear programsolvers for the equilibrium analysis of the abstracted game, we make use of a recently developed algorithm based on the excessive gap technique from convex optimization. This paper is, to our knowledge, the first to abstract and gametheoretically analyze all four betting rounds in one run (ratherthan splitting the game into phases). The resulting player, GS3, beats BluffBot, GS2, Hyperborean, Monash-BPP, Sparbot, Teddy, and Vexbot, each with statistical significance. To our knowledge, those competitors are the best prior programs for the game.