Michael Johanson

AIJ Journal 2020 Journal Article

Negotiating team formation using deep reinforcement learning

• Yoram Bachrach
• Richard Everett
• Edward Hughes
• Angeliki Lazaridou
• Joel Z. Leibo
• Marc Lanctot
• Michael Johanson
• Wojciech M. Czarnecki

When autonomous agents interact in the same environment, they must often cooperate to achieve their goals. One way for agents to cooperate effectively is to form a team, make a binding agreement on a joint plan, and execute it. However, when agents are self-interested, the gains from team formation must be allocated appropriately to incentivize agreement. Various approaches for multi-agent negotiation have been proposed, but typically only work for particular negotiation protocols. More general methods usually require human input or domain-specific data, and so do not scale. To address this, we propose a framework for training agents to negotiate and form teams using deep reinforcement learning. Importantly, our method makes no assumptions about the specific negotiation protocol, and is instead completely experience driven. We evaluate our approach on both non-spatial and spatially extended team-formation negotiation environments, demonstrating that our agents beat hand-crafted bots and reach negotiation outcomes consistent with fair solutions predicted by cooperative game theory. Additionally, we investigate how the physical location of agents influences negotiation outcomes.

IJCAI Conference 2015 Conference Paper

Solving Heads-Up Limit Texas Hold'em

• Oskari Tammelin
• Neil Burch
• Michael Johanson
• Michael Bowling

Cepheus is the first computer program to essentially solve a game of imperfect information that is played competitively by humans. The game it plays is heads-up limit Texas hold’em poker, a game with over 1014 information sets, and a challenge problem for artificial intelligence for over 10 years. Cepheus was trained using a new variant of Counterfactual Regret Minimization (CFR), called CFR+, using 4800 CPUs running for 68 days. In this paper we describe in detail the engineering details required to make this computation a reality. We also prove the theoretical soundness of CFR+ and its component algorithm, regretmatching+. We further give a hint towards understanding the success of CFR+ by proving a tracking regret bound for this new regret matching algorithm. We present results showing the role of the algorithmic components and the engineering choices to the success of CFR+.

AAAI Conference 2014 Conference Paper

Solving Imperfect Information Games Using Decomposition

• Neil Burch
• Michael Johanson
• Michael Bowling

Decomposition, i. e. , independently analyzing possible subgames, has proven to be an essential principle for effective decision-making in perfect information games. However, in imperfect information games, decomposition has proven to be problematic. To date, all proposed techniques for decomposition in imperfect information games have abandoned theoretical guarantees. This work presents the first technique for decomposing an imperfect information game into subgames that can be solved independently, while retaining optimality guarantees on the full-game solution. We can use this technique to construct theoretically justified algorithms that make better use of information available at run-time, overcome memory or disk limitations at run-time, or make a time/space trade-off to overcome memory or disk limitations while solving a game. In particular, we present an algorithm for subgame solving which guarantees performance in the whole game, in contrast to existing methods which may have unbounded error. In addition, we present an offline game solving algorithm, CFR-D, which can produce a Nash equilibrium for a game that is larger than available storage.

AAMAS Conference 2012 Conference Paper

Efficient Nash Equilibrium Approximation through Monte Carlo Counterfactual Regret Minimization

• Michael Johanson
• Nolan Bard
• Marc Lanctot
• Richard Gibson
• Michael Bowling

Recently, there has been considerable progress towards algorithms for approximating Nash equilibrium strategies in extensive games. One such algorithm, Counterfactual Regret Minimization (CFR), has proven to be effective in two-player, zero-sum poker domains. While the basic algorithm is iterative and performs a full game traversal on each iteration, sampling based approaches are possible. For instance, chance-sampled CFR considers just a single chance outcome per traversal, resulting in faster but less precise iterations. While more iterations are required, chance-sampled CFR requires less time overall to converge. In this work, we present new sampling techniques that consider sets of chance outcomes during each traversal to produce slower, more accurate iterations. By sampling only the public chance outcomes seen by all players, we take advantage of the imperfect information structure of the game to (i) avoid recomputation of strategy probabilities, and (ii) achieve an algorithmic speed improvement, performing O($n^2$) work at terminal nodes in O($n$) time. We demonstrate that this new CFR update converges more quickly than chance-sampled CFR in the large domains of poker and Bluff.

AAAI Conference 2012 Conference Paper

Finding Optimal Abstract Strategies in Extensive-Form Games

• Michael Johanson
• Nolan Bard
• Neil Burch
• Michael Bowling

Extensive-form games are a powerful model for representing interactions between agents. Nash equilibrium strategies are a common solution concept for extensive-form games and, in two-player zero-sum games, there are efficient algorithms for calculating such strategies. In large games, this computation may require too much memory and time to be tractable. A standard approach in such cases is to apply a lossy state-space abstraction technique to produce a smaller abstract game that can be tractably solved, while hoping that the resulting abstract game equilibrium is close to an equilibrium strategy in the unabstracted game. Recent work has shown that this assumption is unreliable, and an arbitrary Nash equilibrium in the abstract game is unlikely to be even near the least suboptimal strategy that can be represented in that space. In this work, we present for the first time an algorithm which ef- ficiently finds optimal abstract strategies — strategies with minimal exploitability in the unabstracted game. We use this technique to find the least exploitable strategy ever reported for two-player limit Texas hold’em.

IJCAI Conference 2011 Conference Paper

Accelerating Best Response Calculation in Large Extensive Games

• Michael Johanson
• Kevin Waugh
• Michael Bowling
• Martin Zinkevich

One fundamental evaluation criteria of an AI technique is its performance in the worst-case. For static strategies in extensive games, this can be computed using a best response computation. Conventionally, this requires a full game tree traversal. For very large games, such as poker, that traversal is infeasible to perform on modern hardware. In this paper, we detail a general technique for best response computations that can often avoid a full game tree traversal. Additionally, our method is specifically well-suited for parallel environments. We apply this approach to computing the worst-case performance of a number of strategies in heads-up limit Texas hold'em, which, prior to this work, was not possible. We explore these results thoroughly as they provide insight into the effects of abstraction on worst-case performance in large imperfect information games. This is a topic that has received much attention, but could not previously be examined outside of toy domains.

ICML Conference 2008 Conference Paper

Strategy evaluation in extensive games with importance sampling

• Michael H. Bowling
• Michael Johanson
• Neil Burch
• Duane Szafron

NeurIPS Conference 2007 Conference Paper

Computing Robust Counter-Strategies

• Michael Johanson
• Martin Zinkevich
• Michael Bowling

Adaptation to other initially unknown agents often requires computing an effective counter-strategy. In the Bayesian paradigm, one must find a good counter-strategy to the inferred posterior of the other agents' behavior. In the experts paradigm, one may want to choose experts that are good counter-strategies to the other agents' expected behavior. In this paper we introduce a technique for computing robust counter-strategies for adaptation in multiagent scenarios under a variety of paradigms. The strategies can take advantage of a suspected tendency in the decisions of the other agents, while bounding the worst-case performance when the tendency is not observed. The technique involves solving a modified game, and therefore can make use of recently developed algorithms for solving very large extensive games. We demonstrate the effectiveness of the technique in two-player Texas Hold'em. We show that the computed poker strategies are substantially more robust than best response counter-strategies, while still exploiting a suspected tendency. We also compose the generated strategies in an experts algorithm showing a dramatic improvement in performance over using simple best responses.

NeurIPS Conference 2007 Conference Paper

Regret Minimization in Games with Incomplete Information

• Martin Zinkevich
• Michael Johanson
• Michael Bowling
• Carmelo Piccione

Extensive games are a powerful model of multiagent decision-making scenarios with incomplete information. Finding a Nash equilibrium for very large instances of these games has received a great deal of recent attention. In this paper, we describe a new technique for solving large games based on regret minimization. In particular, we introduce the notion of counterfactual regret, which exploits the degree of incomplete information in an extensive game. We show how minimizing counterfactual regret minimizes overall regret, and therefore in self-play can be used to compute a Nash equilibrium. We demonstrate this technique in the domain of poker, showing we can solve abstractions of limit Texas Hold’em with as many as 1012 states, two orders of magnitude larger than previous methods.

TCS Journal 2005 Journal Article

Solving 7 × 7 Hex with domination, fill-in, and virtual connections

• Ryan Hayward
• Yngvi Björnsson
• Michael Johanson
• Morgan Kan
• Nathan Po
• Jack van Rijswijck

We present an algorithm that determines the outcome of an arbitrary Hex game-state by finding a winning virtual connection for the winning player. Our algorithm recursively searches the game-tree, combining fixed and dynamic game-state virtual connection composition rules to find a winning virtual connection for one of the two players. The search is enhanced by pruning the game-tree according to two new Hex game-state reduction results: under certain conditions, (i) some moves dominate others, and (ii) some board-cells can be “filled-in” without changing the game's outcome. The algorithm is powerful enough to solve arbitrary 7 × 7 game-states. In particular, we use it to determine the outcome of a 7 × 7 Hex game after each of the 49 possible opening moves, in each case finding an explicit proof-tree for the winning player.