Scholarlink

Abstract <p>We study the algorithmic complexity of the cooperative card game Hanabi. A feature of Hanabi is that players can see other players’ cards, but not their own, and exchange information through hints. Even in the model with one player who has full information about the deck, Hanabi remains NP-hard. We found the minimal parameters of the game that preserve NP-hardness. If these parameters are further reduced, the game turns out to be solvable in polynomial time.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

NP-Completeness of Hanabi Game with Minimal Parameters

  • 期刊论文

  • 发表日期：

    2025年8月1日

查看全文
  • A. A. Onorpienko

摘要

Abstract

We study the algorithmic complexity of the cooperative card game Hanabi. A feature of Hanabi is that players can see other players’ cards, but not their own, and exchange information through hints. Even in the model with one player who has full information about the deck, Hanabi remains NP-hard. We found the minimal parameters of the game that preserve NP-hardness. If these parameters are further reduced, the game turns out to be solvable in polynomial time.