Jul, 2014

使用 CFR + 求解大规模不完全信息博弈

PDF
TL;DR本文介绍了 CFR$^+$ 算法，它通常在计算时间上比以前已知算法快一个数量级或更多，同时可能需要更少的内存。该算法可用于不完美信息博弈中，是近似纳什均衡解的最佳方法之一。
发现论文，激发创造
  • 通过折现遗憾最小化解决不完美信息博弈

    本文介绍了改进的 Counterfactual regret minimization（CFR）算法，包括折扣遗憾值、迭代加权和非标准遗憾值最小化等四个变量，我们的新算法在大规模现实环境下的每个游戏中都优于之前的方法 CFR+。另外，与 CFR + 相比，我们的算法更容易应用于现代的不完美信息游戏修剪技术和采样方法。

    Sep, 2018

  • 纯蒙特卡罗反事实遗憾最小化

    基于 Counterfactual Regret Minimization（CFR）方法，该研究提出了一种名为 Pure CFR（PCFR）的新算法，扩展了 CFR 并结合了 Fictitious Play（FP）的概念，通过使用最佳响应策略而非遗憾匹配策略提高算法性能。PCFR 具备与 CFR 及其变种算法包括 Monte Carlo CFR（MCCFR）相结合的能力，实验证明了其能够通过 Blackwell 可达性来达到收敛，而 PMCCFR 能显著降低时间和空间复杂度，至少比 MCCFR 收敛速度快三倍。此外，由于 PMCCFR 不通过严格劣势策略路径，研究者还开发了一种新的启动算法，该算法受严格劣势策略消除方法的启发，结果表明使用新的启动算法的 PMCCFR 优化比 CFR + 算法收敛速度快两个数量级。

    Sep, 2023

  • 深度对抗性遗憾最小化

    本文介绍了一种新的 CFR 形式：Deep CFR，它不再需要抽象，而是使用深度神经网络来近似 CFR 在完整游戏中的行为，并展示了它在大型扑克游戏中的成功表现。

    Nov, 2018

  • 具有不完全回忆的拓展形式博弈中的无悔学习

    本文提出无法完全回忆的游戏中，针对使用 CFR 算法的一般类游戏的第一个遗憾上限及其不适用性，同时证明使用 CFR 在任何抽象类游戏中都适用，且在三种情况下证明不完全回忆可用于交换少量遗憾和显著降低内存。

    May, 2012

  • 稳定预测性乐观反事实遗憾最小化

    本文提出了第一个在 CFIR 基础上打破了迭代次数平方根的收敛速度的 CFR 变体，通过优化后的遗憾最小化器和新的稳定性概念，在 CFR 中引入了稳定可预测性，并将每个遗憾最小化器稳定性设置为所在决策树中的位置，实现了 $O (T^{-3/4})$ 的收敛速率。

    Feb, 2019

  • 复盘 CFR+ 和交替更新

    CFR + 算法是 CFR 算法在解决不完全信息博弈时的一个变种，在各种问题中具有更快的实证性能。尽管其漏洞并不影响解决方案的准确性，我们还是可以提供新的证据来证明其理论上限正确性。

    Oct, 2018

  • 行为受限零和博弈中的遗憾最小化

    使用 CFR 框架开发算法以解决行为约束的 extensive-form games，同时计算近似 Nash 平衡改进。比标准算法更好，收敛速率与最先进的 Nash 平衡计算算法相当。

    Nov, 2017

  • CFR-p: 带有层次策略抽象的反事实遗憾最小化及其在二人麻将中的应用

    应用反事实遗憾最小化（CFR）算法于麻将这一不完全信息游戏，通过进行博弈论分析、基于获胜策略的分级抽象，研究了两人麻将的复杂性及其与扑克游戏的差异，此框架可以推广到其他不完全信息游戏。

    Jul, 2023

  • 用于零和平衡点求解的稀疏线性规划

    该论文提出了一种新颖的方法利用线性规划解决计算均衡的问题，这种方法比以往的算法更高效，并可以用于解决大型的信息不完备博弈，特别是在极限状态下。

    Jun, 2020

  • 利用序贝叶斯游戏模型快速求解扑克

    本文通过对顺序贝叶斯博弈的理解，提出了一种名为公共状态 CFR（PS-CFR） 的算法，能够有效地解决类似德州扑克等复杂博弈的问题，同时在极限复杂度方面获得了二次降低的优势，同样也成功地将这一算法用于推广到广泛的对弈游戏中。

    Dec, 2021