Andrew Gilpin

AAMAS Conference 2010 Conference Paper

Speeding Up Gradient-Based Algorithms for Sequential Games

• Andrew Gilpin
• Tuomas Sandholm

First-order (i. e. , gradient-based) methods for solving two-personzero-sum sequential games of imperfect information have recentlybecome important tools in the construction of game theory-basedagents. The computation time per iteration is typically dominatedby matrix-vector product operations involving the payoff matrix$A$. In this paper, we describe two techniques for scaling up thisoperation. The first is a randomized sampling technique that approximates $A$ with a sparser matrix $\tilde{A}$. Then an approximate equilibrium for the original game is found by finding an approximateequilibrium of the sampled game. The second technique involvesthe development of an algorithm and system for performing thematrix-vector product on a cache-coherent Non-Uniform MemoryAccess (ccNUMA) architecture. The two techniques can be appliedtogether or separately, and they each lead to an algorithm that significantly outperforms the fastest prior gradient-based method.

AAMAS Conference 2008 Conference Paper

A heads-up no-limit Texas Hold'em poker player: Discretized betting models and automatically generated equilibrium finding programms

• Andrew Gilpin
• Tuomas Sandholm
• Troels Bjerre S
• oslash; rensen

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-07 Computer Poker Competition, in which Tartanian placed second out of ten entries.

AAAI Conference 2008 Conference Paper

Expectation-Based Versus Potential-Aware Automated Abstraction in Imperfect Information Games: An Experimental Comparison Using Poker

• Andrew Gilpin

Automated abstraction algorithms for sequential imperfect information games have recently emerged as a key component in developing competitive game theory-based agents. The existing literature has not investigated the relative performance of different abstraction algorithms. Instead, agents whose construction has used automated abstraction have only been compared under confounding effects: different granularities of abstraction and equilibrium-finding algorithms that yield different accuracies when solving the abstracted game. This paper provides the first systematic evaluation of abstraction algorithms. Two families of algorithms have been proposed. The distinguishing feature is the measure used to evaluate the strategic similarity between game states. One algorithm uses the probability of winning as the similarity measure. The other uses a potential-aware similarity measure based on probability distributions over future states. We conduct experiments on Rhode Island Hold’em poker. We compare the algorithms against each other, against optimal play, and against each agent’s nemesis. We also compare them based on the resulting game’s value. Interestingly, for very coarse abstractions the expectation-based algorithm is better, but for moderately coarse and fine abstractions the potentialaware approach is superior. Furthermore, agents constructed using the expectation-based approach are highly exploitable beyond what their performance against the game’s optimal strategy would suggest.

AAAI Conference 2008 Conference Paper

First-Order Algorithm with O(ln(1/ε)) Convergence for ε-Equilibrium in Two-Person Zero-Sum Games

• Andrew Gilpin

We propose an iterated version of Nesterov’s first-order smoothing method for the two-person zero-sum game equilibrium problem min x∈Q1 max y∈Q2 xT Ay = max y∈Q2 min x∈Q1 xT Ay. This formulation applies to matrix games as well as sequential games. Our new algorithmic scheme computes an equilibrium to this min-max problem in O(κ(A) ln(1/ )) first-order iterations, where κ(A) is a certain condition measure of the matrix A. This improves upon the previous first-order methods which required O(1/ ) iterations, and it matches the iteration complexity bound of interior-point methods in terms of the algorithm’s dependence on. Unlike the interior-point methods that are inapplicable to large games due to their memory requirements, our algorithm retains the small memory requirements of prior first-order methods. Our scheme supplements Nesterov’s algorithm with an outer loop that lowers the target between iterations (this target affects the amount of smoothing in the inner loop). We find it surprising that such a simple modification yields an exponential speed improvement. Finally, computational experiments both in matrix games and sequential games show that a significant speed improvement is obtained in practice as well, and the relative speed improvement increases with the desired accuracy (as suggested by the complexity bounds).

AAMAS Conference 2008 Conference Paper

GS3 and Tartanian: Game theory-based heads-up limit and no-limit Texas Hold'em poker-playing programs

• Andrew Gilpin
• Tuomas Sandholm
• Troels Bjerre Sorensen

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 the virtually 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.

AAMAS Conference 2008 Conference Paper

Solving two-person zero-sum repeated games of incomplete information

• Andrew Gilpin
• Tuomas Sandholm

In repeated games with incomplete information, rational agents must carefully weigh the tradeoffs of advantageously exploiting their information to achieve a short-term gain versus carefully concealing their information so as not to give up a long-term informed advantage. The theory of infinitelyrepeated two-player zero-sum games with incomplete information has been carefully studied, beginning with the seminal work of Aumann and Maschler. While this theoretical work has produced a characterization of optimal strategies, algorithms for solving for optimal strategies have not yet been studied. For the case where one player is informed about the true state of the world and the other player is uninformed, we provide a non-convex mathematical programming formulation for computing the value of the game, as well as optimal strategies for the informed player. We then describe an efficient algorithm for solving this difficult optimization problem to within arbitrary accuracy. We also discuss how to efficiently compute optimal strategies for the uninformed player using the output of our algorithm.

IJCAI Conference 2007 Conference Paper

• Andrew Gilpin
• Tuomas Sandholm

Deciding what question to branch on at each node is a key element of search algorithms. We introduce the information-theoretic paradigm for branching question selection. The idea is to drive the search to reduce uncertainty (entropy) in the current subproblem. We present four families of methods that fall within this paradigm. In the first, a variable to branch on is selected based on lookahead. This method performs comparably to strong branching on MIPLIB, and better than strong branching on hard real-world procurement optimization instances on which CPLEX’s default strong branching outperforms CPLEX’s default branching strategy. The second family combines this idea with strong branching. The third family does not use lookahead, but instead exploits the tie between indicator variables and the other variables they govern. This significantly outperforms the state-of-the-art branching strategies. The fourth family is about branching using carefully constructed linear inequality constraints over sets of variables.

AAMAS Conference 2007 Conference Paper

Better Automated Abstraction Techniques for Imperfect Information Games, with Application to Texas Hold'em Poker

• Andrew Gilpin
• Tuomas Sandholm

We present new approximation methods for computing gametheoretic strategies for sequential games of imperfect information. At a high level, we contribute two new ideas. First, we introduce a new state-space abstraction algorithm. In each round of the game, there is a limit to the number of strategically different situations that an equilibrium-finding algorithm can handle. Given this constraint, we use clustering to discover similar positions, and we compute the abstraction via an integer program that minimizes the expected error at each stage of the game. Second, we present a method for computing the leaf payoffs for a truncated version of the game by simulating the actions in the remaining portion of the game. This allows the equilibrium-finding algorithm to take into account the entire game tree while having to explicitly solve only a truncated version. Experiments show that each of our two new techniques improves performance dramatically in Texas Hold'em poker. The techniques lead to a drastic improvement over prior approaches for automatically generating agents, and our agent plays competitively even against the best agents overall.

AAAI Conference 2007 Conference Paper

Potential-Aware Automated Abstraction of Sequential Games, and Holistic Equilibrium Analysis of Texas Hold’em Poker

• Andrew Gilpin

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 a custom 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 program solvers 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 (rather than 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.

AAAI Conference 2006 Conference Paper

A Competitive Texas Hold’em Poker Player via Automated Abstraction and Real-Time Equilibrium Computation

• Andrew Gilpin

We present a game theory-based heads-up Texas Hold’em poker player, GS1. To overcome the computational obstacles stemming from Texas Hold’em’s gigantic game tree, the player employs our automated abstraction techniques to reduce the complexity of the strategy computations. Texas Hold’em consists of four betting rounds. Our player solves a large linear program (offline) to compute strategies for the abstracted first and second rounds. After the second betting round, our player updates the probability of each possible hand based on the observed betting actions in the first two rounds as well as the revealed cards. Using these updated probabilities, our player computes in real-time an equilibrium approximation for the last two abstracted rounds. We demonstrate that our player, which incorporates very little poker-specific knowledge, is competitive with leading poker-playing programs which incorporate extensive domain knowledge, as well as with advanced human players.

AAMAS Conference 2006 Conference Paper

A Texas Hold'em Poker player based on automated abstraction and real-time equilibrium computation

• Andrew Gilpin
• Tuomas Sandholm

AAMAS Conference 2006 Conference Paper

Information-theoretic approaches to branching in search

• Andrew Gilpin
• Tuomas Sandholm

AAMAS Conference 2006 Conference Paper

Sequences of Take-It-or-Leave-It Offers: Near-Optimal Auctions Without Full Valuation Revelation

• Tuomas Sandholm
• Andrew Gilpin

AAAI Conference 2005 System Paper

Optimal Rhode Island Hold’em Poker

• Andrew Gilpin

Rhode Island Hold’em is a poker card game that has been proposed as a testbed for AI research. This game, with a tree size larger than 3. 1 billion nodes, features many characteristics present in full-scale poker (e. g. , Texas Hold’em). Our research advances in equilibrium computation have enabled us to solve for the optimal (equilibrium) strategies for this game. Some features of the equilibrium include poker techniques such as bluffing, slow-playing, check-raising, and semi-bluffing. In this demonstration, participants will compete with our optimal opponent and will experience these strategies firsthand.