Аннотация:
Мы исследуем кооперативную карточную игру “Ханаби” с точки зрения алгоритмической сложности. Особенность “Ханаби” заключается в том, что игроки видят карты других игроков, но не свои, и обмениваются информацией путем подсказок. Даже в модели с одним игроком, обладающим полной информацией о колоде, “Ханаби” остается NP-трудной. Найдены минимальные параметры игры, при которых сохраняется NP-трудность. В случае дальнейшего уменьшения этих параметров игра оказывается разрешимой за полиномиальное время.
Ключевые слова:
алгоритмическая теория игр, вычислительная сложность, NP-полнота, Ханаби.
УДК:
004.8
Поступило: 12.08.2025 Принято к публикации: 22.09.2025
