Safe and Nested Subgame Solving for Imperfect-Information Games
Safe and Nested Subgame Solving for Imperfect-Information Games
复制标题
DOI：
--
复制
发表时间：
2017-05
期刊：
影响因子：
--
通讯作者：
Noam Brown;T. Sandholm
中科院分区：
文献类型：
--
作者：
Noam Brown;T. Sandholm
在不完全信息博弈中，子博弈中的最优策略可能取决于其他未达成的子博弈中的策略。因此，子博弈不能孤立地解决，而必须考虑整个博弈的策略，这与完全信息博弈不同。然而，有可能首先近似整个游戏的解，然后通过求解个别的子博弈来改进它。这就是所谓的子博弈求解。我们引入子博弈求解技术，在理论和实践上都优于以前的方法。我们还展示了如何调整它们和过去的子博弈求解技术，以响应原始动作抽象之外的对手动作；这大大超过了以前最先进的方法，动作翻译。最后，我们证明了子博弈的求解可以随着游戏向下发展而重复进行，从而导致可利用性大大降低。这些技术是Libratus的关键组成部分，它是第一个在德克萨斯无限制扑克中击败顶级人类的人工智能。
In imperfect-information games, the optimal strategy in a subgame may depend on the strategy in other, unreached subgames. Thus a subgame cannot be solved in isolation and must instead consider the strategy for the entire game as a whole, unlike perfect-information games. Nevertheless, it is possible to first approximate a solution for the whole game and then improve it by solving individual subgames. This is referred to as subgame solving. We introduce subgame-solving techniques that outperform prior methods both in theory and practice. We also show how to adapt them, and past subgame-solving techniques, to respond to opponent actions that are outside the original action abstraction; this significantly outperforms the prior state-of-the-art approach, action translation. Finally, we show that subgame solving can be repeated as the game progresses down the game tree, leading to far lower exploitability. These techniques were a key component of Libratus, the first AI to defeat top humans in heads-up no-limit Texas hold'em poker.