Using computer poker as a testbed for solving multiagent decision problems

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

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.