Efficient Subgame Refinement for Extensive-form Games
Subgame solving is an essential technique in addressing large imperfect information games, with various approaches developed to enhance the performance of refined strategies in the abstraction of the target subgame. However, directly applying existing subgame solving techniques may be difficult, due to the intricate nature and substantial size of many real-world games. To overcome this issue, recent subgame solving methods allow for subgame solving on limited knowledge order subgames, increasing their applicability in large games; yet this may still face obstacles due to extensive information set sizes. To address this challenge, we propose a generative subgame solving (GS2) framework, which utilizes a generation function to identify a subset of the earliest-reached nodes, reducing the size of the subgame. Our method is supported by a theoretical analysis and employs a diversity-based generation function to enhance safety. Experiments conducted on medium-sized games as well as the challenging large game of GuanDan demonstrate a significant improvement over the blueprint.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Credible equilibrium
Credible equilibrium is a solution concept that imposes a stronger credibility notion than subgame perfect equilibrium. A credible equilibrium is a refinement of subgame perfect equilibrium such that if a threat in a sub…
Equilibrium Refinements for Multi-Agent Influence Diagrams: Theory and Practice
Multi-agent influence diagrams (MAIDs) are a popular form of graphical model that, for certain classes of games, have been shown to offer key complexity and explainability advantages over traditional extensive form game …
FormSolving Hierarchical Information-Sharing Dec-POMDPs: An Extensive-Form Game Approach
A recent theory shows that a multi-player decentralized partially observable Markov decision process can be transformed into an equivalent single-player game, enabling the application of \citeauthor{bellman}'s principle …
FormManagementSafe and Nested Subgame Solving for Imperfect-Information Games
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 entir…
TranslationA Category for Extensive-Form Games
This paper introduces Gm, which is a category for extensive-form games. It also provides some applications. The category's objects are games, which are understood to be sets of nodes which have been endowed with edges, i…
Form