Research map / Learning theory and algorithms / Submodular and game algorithms
History Filtering in Imperfect Information Games: Algorithms and Complexity
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the TTCG Gibbs sampler instead of explicit enumeration | History filtering and value estimation in Oh Hell · Oh Hell, public belief states up to 544,320 histories | value estimation error | Helped |
| Use local Markov-chain history transitions rather than enumerate the full public belief state | TTCG Gibbs sampler · Oh Hell, 544,320-history public belief state | state transitions for value estimation: 8,000 total state transitions vs 544,320 histories | Helped |
| Use fewer burn-in transitions before collecting samples | TTCG Gibbs sampler · Oh Hell value estimation | value estimation error | Mixed |
| Use TTCG Gibbs sampling with randomly generated policies instead of policies learned via independent Q-learning | TTCG Gibbs sampler · Oh Hell value estimation | value estimation error | No clear effect |
| Enumerate histories when the public tree is sparse | History filtering in finite FOSGs · Games with polynomially many histories per public state | enumeration runtime | Helped |
| Construct a history for general FOSGs without exploiting domain structure | FILTER on 3-FSAT-GAME · 3-FSAT-GAME | computational tractability | Hurt |
Closest papers by meaning
- Refining Subgames in Large Imperfect Information Games (AAAI 2016 · similarity 0.91)
- The Update-Equivalence Framework for Decision-Time Planning (ICLR 2024 · similarity 0.88)
- Opponent-Model Search in Games with Incomplete Information (AAAI 2024 · similarity 0.88)
- Solving Hierarchical Information-Sharing Dec-POMDPs: An Extensive-Form Game Approach (ICML 2024 · similarity 0.87)
- Safe and Robust Subgame Exploitation in Imperfect Information Games (ICML 2024 · similarity 0.86)
- Implicit Search via Discrete Diffusion: A Study on Chess (ICLR 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.