Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Alberta

$29,000.00

Using computer poker as a testbed for solving multiagent decision problems

EF 2011-12

Résumé
Games are used to advance multi-agent decision-making techniques. Many games are deterministic (no chance) with perfect information (all info visible to all agents) like Chess and Checkers. However, many real-world scenarios with competing agents are non-deterministic with imperfect information. For two-player zero-sum perfect recall games, a recent technique called Counterfactual Regret Minimization (CFR) computes strategies that are provably convergent to an epsilon-Nash equilibrium. A Nash equilibrium strategy is useful in two-player games since it maximizes its utility against a worst-case opponent. We study two-agent non-deterministic imperfect information decision problems that have a many-valued parameter at many decision points. One example is no-limit poker where in addition to selecting a probability of taking each action, the bet and raise actions have an associated amount. Although this parameter is not continuous (measured in chips), there are so many values that using all valid discrete values generates a huge game tree. Other examples include a farmer deciding when to sell grain and how much to sell and a stock-trader deciding when to buy or sell and how much. We will create a new variation of CFR to solve this problem. We can already compute the optimal continuous parameter value under certain conditions for simple no-limit poker variations. For multiplayer (three or more player) games, although we lose all theoretical guarantees, we used CFR to generate agents that won the 3-player events in the AAAI Annual Computer Poker Competition in 2009 and 2010. We will determine what characteristics of CFR-generated agents contribute to ""good play"". We believe that in 3-player games, computing Nash equilibria is unnecessary. We think that algorithms should focus on removing dominated strategies and our goal is to characterize CFR with respect to its ability to do this. After all dominated strategies have been eliminated, the algorithm must filter the remaining strategies to limit exploitability and exploit other agents. We will show that CFR (and some variations) can provide insights.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Alberta, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
8191-2011
Name nom
Szafron, Duane
Department département
Computing Science
Organization id
9
Institution établissement
University of Alberta
Province en
Alberta
Province fr
Alberta
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2011
Competition year année de concours
2011
Award amount
29000
Program id
RGPIN
Program nane en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
802
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Information systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
Research subject code
2800
Research subject group en
Artificial intelligence
Research subject group fr
Intelligence artificielle
Research subject en
Artificial intelligence (computer vision, use2603)
Research subject fr
Intelligence artificielle (vision artificielle, utiliser 2603)
Partie
1
Nb partie
5
Application title
Using computer poker as a testbed for solving multiagent decision problems
Keyword
NSERC
Application summary
Games are used to advance multi-agent decision-making techniques. Many games are deterministic (no chance) with perfect information (all info visible to all agents) like Chess and Checkers. However, many real-world scenarios with competing agents are non-deterministic with imperfect information. For two-player zero-sum perfect recall games, a recent technique called Counterfactual Regret Minimization (CFR) computes strategies that are provably convergent to an epsilon-Nash equilibrium. A Nash equilibrium strategy is useful in two-player games since it maximizes its utility against a worst-case opponent. We study two-agent non-deterministic imperfect information decision problems that have a many-valued parameter at many decision points. One example is no-limit poker where in addition to selecting a probability of taking each action, the bet and raise actions have an associated amount. Although this parameter is not continuous (measured in chips), there are so many values that using all valid discrete values generates a huge game tree. Other examples include a farmer deciding when to sell grain and how much to sell and a stock-trader deciding when to buy or sell and how much. We will create a new variation of CFR to solve this problem. We can already compute the optimal continuous parameter value under certain conditions for simple no-limit poker variations. For multiplayer (three or more player) games, although we lose all theoretical guarantees, we used CFR to generate agents that won the 3-player events in the AAAI Annual Computer Poker Competition in 2009 and 2010. We will determine what characteristics of CFR-generated agents contribute to ""good play"". We believe that in 3-player games, computing Nash equilibria is unnecessary. We think that algorithms should focus on removing dominated strategies and our goal is to characterize CFR with respect to its ability to do this. After all dominated strategies have been eliminated, the algorithm must filter the remaining strategies to limit exploitability and exploit other agents. We will show that CFR (and some variations) can provide insights.