Using computer poker as a testbed for solving multiagent decision problems

游戏被用于推进多智能体决策技术。许多游戏都是具有确定性（没有机会）的完美信息（所有主体都能看到的所有信息），如象棋和跳棋。然而，许多具有竞争代理的现实世界场景具有不完全信息的不确定性。对于两个人的零和完美回忆游戏，最近一项名为反事实遗憾最小化（CFR）的技术计算出的策略可以证明收敛于一个epsilon-Nash均衡。纳什均衡策略在双人博弈中很有用，因为它在面对最坏情况的对手时能使效用最大化。

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.