EUVIMEDEUVIMED entdecken
Crossref

Subgame Pruning: Efficiently Solving Two-Player Imperfect Information Games by Accelerated Public Tree Traversal in CFR

Shenkai Zhang, Peipei Yang, Zekeng Zeng, Junge Zhang

IEEE Transactions on Games · 2026-06 · 18 (2) · 411-417

DOI: 10.1109/tg.2026.3675377 ↗

Kurz gefasst

Fachartikel in der Zeitschrift IEEE Transactions on Games, 2026-06. Verfasst von Shenkai Zhang und 3 weiteren Autor:innen. Die Arbeit nennt 18 Literaturangaben. Gefördert von: National Key R&D Program of China, Beijing Major Science and Technology Project.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Counterfactual regret minimization (CFR) is the state-of-the-art algorithm for solving imperfect information games, yet it struggles against scalability. While existing pruning techniques primarily focus on pruning unreachable branches, they fail to account for subgames, in which strategies have temporarily converged. Continuing to update strategies within these subgames leads to unnecessary computational overhead. To address this, we propose Subgame Pruning, a novel regret-based pruning paradigm that accelerates traversal of the public tree by dynamically pruning subgames where strategies remain stable across iterations. To ensure safe and efficient pruning, we introduce two key mechanisms: pruning constraint checking, which verifies whether a subgame satisfies pruning criteria, and regret matching compensation, which defers regret matching and average strategy updates until the pruned subgames are revisited. Our method significantly reduces computational overhead while preserving the theoretical convergence guarantees of CFR. In particular, the exploitability of the average strategy profile remains bounded by $\mathcal {O}(1/\sqrt{T})$. Experimental results across five benchmark games demonstrate substantial reductions in the number of traversed nodes, with exploitability comparable to that of standard CFR.

Förderung

  • National Key R&D Program of China
  • Beijing Major Science and Technology Project

Zitieren

APA

Zhang, S., Yang, P., Zeng, Z., & Zhang, J. (2026). Subgame Pruning: Efficiently Solving Two-Player Imperfect Information Games by Accelerated Public Tree Traversal in CFR. IEEE Transactions on Games, 18(2), 411-417. https://doi.org/10.1109/tg.2026.3675377

Vancouver

Zhang S, Yang P, Zeng Z, Zhang J. Subgame Pruning: Efficiently Solving Two-Player Imperfect Information Games by Accelerated Public Tree Traversal in CFR. IEEE Transactions on Games. 2026;18(2):411-417. doi:10.1109/tg.2026.3675377

BibTeX
@article{Zhang2026,
  author = {Zhang, Shenkai and Yang, Peipei and Zeng, Zekeng and Zhang, Junge},
  title = {Subgame Pruning: Efficiently Solving Two-Player Imperfect Information Games by Accelerated Public Tree Traversal in CFR},
  journal = {IEEE Transactions on Games},
  year = {2026},
  volume = {18},
  number = {2},
  pages = {411--417},
  doi = {10.1109/tg.2026.3675377}
}
Kostenlos starten →