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 年度计算机扑克比赛中赢得 3 人比赛冠军的代理。我们将确定 CFR 的哪些特征 -生成的代理有助于“玩得好”。我们认为，在三人游戏中，计算纳什均衡是不必要的。我们认为算法应该专注于消除主导策略，我们的目标是根据 CFR 的能力来描述 CFR 的特征。在消除所有主导策略后，算法必须过滤剩余策略以限制可利用性并利用其他代理。我们将证明 CFR（以及一些变体）可以提供见解。