Potential-Aware Automated Abstraction of Sequential Games, and Holistic Equilibrium Analysis of Texas Hold'em Poker
Potential-Aware Automated Abstraction of Sequential Games, and Holistic Equilibrium Analysis of Texas Hold'em Poker
复制标题
序列博弈的潜力感知自动抽象以及德州扑克的整体均衡分析
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
T. Lund
中科院分区：
文献类型：
--
作者：
Andrew Gilpin;T. Sandholm;T. Lund
提出了一种新的序列不完全信息博弈的抽象算法。虽然大多数先前的抽象算法都使用近视期望值计算作为相似性度量，但我们的算法考虑的是由游戏后期抽象状态类的直方图组成的高维空间。这使得我们的自下而上的抽象算法能够自动考虑到潜力：随着时间的推移，一手牌可以变得相对更好（或更差），不同手牌的实力可以在游戏的早期或后期得到解决。我们通过对抽象进行多次检查来进一步提高抽象质量，使算法能够将分析范围缩小到与游戏早期部分的抽象决策相关的信息。我们还提出了一种基于西服同构的自定义索引方案，使人们能够处理比以前大得多的模型。我们将这些技术应用于顶限时德州扑克。鉴于之前所有基于博弈论的德克萨斯扑克工作都使用了通用的现成线性规划解算器来对抽象游戏进行均衡分析，我们使用了最近开发的基于凸优化的过度间隙技术的算法。据我们所知，这篇论文是第一个在一次运行中抽象并从游戏理论上分析所有四个投注回合（而不是将游戏分成几个阶段）的论文。结果，GS3击败了BluffBot、GS2、Hyperborean、Monash-BPP、Sparbot、Teddy和Vexbot，每一个都有统计学意义。据我们所知，这些竞争者是游戏中最好的预先程序。
We present a new abstraction algorithm for sequential imperfect information games. While most prior abstraction algorithms employ a myopic expected-value computation as a similarity metric, our algorithm considers a higher-dimensional space consisting of histograms over abstracted classes of states from later stages of the game. This enables our bottom-up abstraction algorithm to automatically take into account potential: a hand can become relatively better (or worse) over time and the strength of different hands can get resolved earlier or later in the game. We further improve the abstraction quality by making multiple passes over the abstraction, enabling the algorithm to narrow the scope of analysis to information that is relevant given abstraction decisions made for earlier parts of the game. We also present a custom indexing scheme based on suit isomorphisms that enables one to work on significantly larger models than before. We apply the techniques to heads-up limit Texas Hold'em poker. Whereas all prior game theory-based work for Texas Hold'em poker used generic off-the-shelf linear program solvers for the equilibrium analysis of the abstracted game, we make use of a recently developed algorithm based on the excessive gap technique from convex optimization. This paper is, to our knowledge, the first to abstract and game-theoretically analyze all four betting rounds in one run (rather than splitting the game into phases). The resulting player, GS3, beats BluffBot, GS2, Hyperborean, Monash-BPP, Sparbot, Teddy, and Vexbot, each with statistical significance. To our knowledge, those competitors are the best prior programs for the game.