论文标题
大型两人游戏中利用量化对手的复杂性和算法
Complexity and Algorithms for Exploiting Quantal Opponents in Large Two-Player Games
论文作者
论文摘要
传统游戏理论的解决方案概念完全是理性的玩家；因此，他们利用次级对手的能力是有限的。很好地描述人类行为的一种亚理性类型是数量反应。尽管存在针对数量对手计算解决方案的算法，但它们要么不进行扩展，要么可能提供比完全理性的NASH策略更糟糕的策略。本文旨在分析并提出可扩展算法，以计算正常形式和广泛形式游戏中的量化对手的有效和强大策略。我们的贡献是：（1）我们定义了与利用数量对手并分析其特性有关的两个不同的解决方案概念； （2）我们证明计算这些解决方案在计算上很难； （3）因此，我们根据可扩展的反事实遗憾最小化（CFR）评估了几种启发式近似值； （4）我们确定了一个CFR变体，该变体比以前使用的变体更好地利用有限的对手，同时受到最差的完全理性的对手的利用。
Solution concepts of traditional game theory assume entirely rational players; therefore, their ability to exploit subrational opponents is limited. One type of subrationality that describes human behavior well is the quantal response. While there exist algorithms for computing solutions against quantal opponents, they either do not scale or may provide strategies that are even worse than the entirely-rational Nash strategies. This paper aims to analyze and propose scalable algorithms for computing effective and robust strategies against a quantal opponent in normal-form and extensive-form games. Our contributions are: (1) we define two different solution concepts related to exploiting quantal opponents and analyze their properties; (2) we prove that computing these solutions is computationally hard; (3) therefore, we evaluate several heuristic approximations based on scalable counterfactual regret minimization (CFR); and (4) we identify a CFR variant that exploits the bounded opponents better than the previously used variants while being less exploitable by the worst-case perfectly-rational opponent.
