nips nips2009 nips2009-232 nips2009-232-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Kevin Waugh, Nolan Bard, Michael Bowling
Abstract: Extensive games are often used to model the interactions of multiple agents within an environment. Much recent work has focused on increasing the size of an extensive game that can be feasibly solved. Despite these improvements, many interesting games are still too large for such techniques. A common approach for computing strategies in these large games is to first employ an abstraction technique to reduce the original game to an abstract game that is of a manageable size. This abstract game is then solved and the resulting strategy is played in the original game. Most top programs in recent AAAI Computer Poker Competitions use this approach. The trend in this competition has been that strategies found in larger abstract games tend to beat strategies found in smaller abstract games. These larger abstract games have more expressive strategy spaces and therefore contain better strategies. In this paper we present a new method for computing strategies in large games. This method allows us to compute more expressive strategies without increasing the size of abstract games that we are required to solve. We demonstrate the power of the approach experimentally in both small and large games, while also providing a theoretical justification for the resulting improvement. 1
[1] Darse Billings, Neil Burch, Aaron Davidson, Robert Holte, Jonathan Schaeffer, Terance Schauenberg, and Duane Szafron. Approximating Game-Theoretic Optimal Strategies for Full-scale Poker. In International Joint Conference on Artificial Intelligence, pages 661–668, 2003.
[2] Andrew Gilpin, Samid Hoda, Javier Pe˜ a, and Tuomas Sandholm. Gradient-based Algorithms n for Finding Nash Equilibria in Extensive Form Games. In Proceedings of the Eighteenth International Conference on Game Theory, 2007.
[3] Andrew Gilpin and Tuomas Sandholm. A Competitive Texas Hold’em Poker Player via Automated Abstraction and Real-time Equilibrium Computation. In Proceedings of the Twenty-First Conference on Artificial Intelligence, 2006.
[4] Andrew Gilpin and Tuomas Sandholm. Expectation-Based Versus Potential-Aware Automated Abstraction in Imperfect Information Games: An Experimental Comparison Using Poker. In Proceedings of the Twenty-Third Conference on Artificial Intelligence, 2008.
[5] Daphne Koller and Avi Pfeffer. Representations and Solutions for Game-Theoretic Problems. Artificial Intelligence, 94:167–215, 1997.
[6] Martin Osborne and Ariel Rubinstein. A Course in Game Theory. The MIT Press, Cambridge, Massachusetts, 1994.
[7] Kevin Waugh, David Schnizlein, Michael Bowling, and Duane Szafron. Abstraction Pathologies in Extensive Games. In Proceedings of the Eighth International Joint Conference on Autonomous Agents and Multi-Agent Systems, pages 781–788, 2009.
[8] Kevin Waugh, Martin Zinkevich, Michael Johanson, Morgan Kan, David Schnizlein, and Michael Bowling. A Practical Use of Imperfect Recall. In Proceedings of the Eighth Symposium on Abstraction, Reformulation and Approximation, 2009.
[9] Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione. Regret Minimization in Games with Incomplete Information. In Advances in Neural Information Processing Systems Twenty, pages 1729–1736, 2008. A longer version is available as a University of Alberta Technical Report, TR07-14.
[10] Martin Zinkevich and Michael Littman. The AAAI Computer Poker Competition. Journal of the International Computer Games Association, 29, 2006. News item. 9