A Logical Analysis of Hanabi

Elise PerrotinAAAI 2025 · DOI

TL;DR

This paper presents a formal logical framework for the cooperative card game Hanabi, moving beyond machine learning approaches to model the game's complex epistemic reasoning. By extending the epistemic logic EL-O with generalized common knowledge and a novel "reasoning action," the authors demonstrate that Hanabi's knowledge dynamics can be captured efficiently, even within a finite, computationally tractable model.

What Problem Does This Paper Address?

The card game Hanabi, a popular benchmark for AI systems, presents a significant challenge for formal reasoning due to its reliance on "epistemic reasoning" – understanding what players know, what they know others know, and so on. Traditional epistemic logics, like Dynamic Epistemic Logic (DEL), become computationally intractable when modeling multi-agent common knowledge, leading most Hanabi research to rely on heuristic or machine learning approaches. This paper aims to bridge this gap by developing a formal logical framework that can accurately represent and reason about knowledge evolution in Hanabi, making it amenable to logical analysis and potentially more robust AI agents.

Methods

The authors introduce a novel approach by extending the epistemic logic EL-O. EL-O uses an "observability" operator ("seeing") instead of the standard "knowing that" operator, which helps manage complexity. The key methodological contributions are:

  • Generalized Common Knowledge: They extend EL-O's common knowledge to apply to arbitrary groups of agents, not just the entire set of players. This is crucial for Hanabi, where knowledge might be shared among subsets of players.
  • "Reasoning Action": To overcome EL-O's limitation of not allowing agents to know disjunctions (e.g., knowing a card is "blue or red"), they introduce a special "reasoning action." This action allows agents to deduce new knowledge based on what they can observe, simulating a step-by-step reasoning process that humans might undertake.
  • Finite Semantics: They demonstrate that for Hanabi, the complexity of knowledge states can be restricted to a modal depth of at most 2. This allows for a finite and computationally tractable semantics, making satisfiability checking NP-complete.

Datasets

Not discussed in the paper. The paper focuses on formalizing the game of Hanabi itself, rather than training or evaluating on external datasets.

Key Insights and Ideas

  • The Power of "Seeing": The shift from "knowing that" to "seeing" (observability) in EL-O is a clever way to manage the explosion of knowledge states in multi-agent systems.
  • Explicit Reasoning as an Action: Modeling reasoning not as an implicit logical consequence but as an explicit action is a powerful way to capture human-like deduction and avoid the problem of logical omniscience (agents knowing all tautologies).
  • Hanabi's Finite Knowledge Structure: The discovery that Hanabi's knowledge states can be effectively represented with a modal depth of 2 is a significant simplification, making formal analysis feasible. This suggests that many complex games might have underlying structures that allow for such reductions.
  • Bridging Logic and Game Theory: The paper successfully bridges formal logic with the practical challenges of game AI, offering a principled way to build agents that can reason about their own and others' knowledge.

Key Results

  • The paper provides a formalization of Hanabi using an extended epistemic logic (EL-O with generalized common knowledge and a reasoning action).
  • They establish that the relevant knowledge states in Hanabi can be captured within a modal depth of 2.
  • This leads to a finite semantics for Hanabi's knowledge evolution, with an NP-complete satisfiability problem for the proposed logic (H-EL-O).
  • The proposed framework is shown to be complete for modeling the evolution of knowledge in Hanabi.

Limitations and Future Work

  • Handling the Last Round: The paper acknowledges that the final round of the game (when the deck is empty) is not explicitly handled for simplicity, though it's noted as easily extendable.
  • Action Selection: The current framework models how agents reason and gain knowledge, but not which action they choose to perform. Future work could explore agents reasoning about action outcomes and selecting optimal moves.
  • Theoretical Guarantees: Further theoretical work is needed to formally prove that the proposed general semantics correspond to standard epistemic logic S5 and that the action descriptions accurately simulate DEL representations.
  • Practical Applicability: The authors suggest exploring the practical application of this method in actual playing systems, moving beyond theoretical modeling to real-world AI agents.
  • Complexity of General DEL: While this paper sidesteps the complexity of general DEL for Hanabi, the problem of efficient reasoning in multi-agent DEL remains an open challenge.

Summary updated

BibTeX
@inproceedings{perrotin2025logical,
  author = {Elise Perrotin},
  title = {{A Logical Analysis of Hanabi}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i14.33658},
}
Figure