Using computer poker as a testbed for solving multiagent decision problems

使用计算机扑克作为解决多智能体决策问题的测试平台

• 批准号: 8191-2011
• 负责人: Szafron, Duane
• 金额: $ 2.11万
• 依托单位: University of Alberta
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=568568
• 关键词: Using; computer; poker; testbed; solving

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.

游戏被用来推进多智能体决策技术。许多游戏是确定性的(没有机会)，具有完美的信息(所有信息对所有代理都可见)，如国际象棋和跳棋。然而，许多现实世界中存在竞争代理的场景是不确定的，信息不完全。对于两人零和完美回忆游戏，最近一种名为反事实遗憾最小化(CFR)的技术计算出了可证明收敛于epsilon-Nash均衡的策略。纳什均衡策略在两人博弈中很有用，因为它最大化了对最坏情况下的对手的效用。 研究了多个决策点具有多个参数值的两智能体不确定不完全信息决策问题。一个例子是无限制扑克，其中除了选择采取每一种动作的概率外，下注和加注动作都有关联的金额。虽然这个参数不是连续的(以筹码为单位)，但有太多的值，使用所有有效的离散值生成一个巨大的博弈树。其他例子包括农民决定何时出售粮食以及卖出多少，以及股票交易员决定何时买卖以及卖出多少。我们将创建一个新的CFR变体来解决这个问题。对于简单的无限制扑克变化，我们已经可以在一定条件下计算出最优连续参数值。 对于多人(三人或更多人)游戏，尽管我们失去了所有理论上的保证，但我们使用CFR生成了在2009年和2010年AAAI年度计算机扑克比赛中赢得三人比赛的代理。我们将确定CFR生成的代理的哪些特征有助于“良好发挥”。我们认为，在三人博弈中，计算纳什均衡是不必要的。我们认为，算法应该专注于消除主导策略，我们的目标是根据CFR做到这一点的能力来描述它的特征。在所有被支配的策略都被消除后，算法必须过滤剩余的策略以限制可利用性和利用其他代理。我们将展示CFR(和一些变体)可以提供洞察力。