#матлог #учёба #спецсеминар #не_мехмат #МИАН #ТД

Семинар отдела математической логики МИАН, Logic Online Seminar (www.mathnet.ru/rus/conf876), понедельник 16:00 MSK (UTC+3), ауд. 313 + Kontur Talk

30.03.2026
А. А. Оноприенко (МГУ, https://www.mathnet.ru/person111160): Алгоритмическая сложность кооперативной игры «Ханаби» (очный доклад)

С середины XX столетия игры рассматриваются в качестве полигона для тестирования возможностей компьютера. Сейчас явные алгоритмы уступили место ИИ, который успешно играет в игры с противоположными интересами участников (типа шахмат или го). «Ханаби» является примером игры сотрудничества, в которой участники совместно достигают общей цели. На данный момент успехи ИИ в игре «Ханаби» довольно скромные: компьютер уступает даже командам из игроков-новичков. Очевидное препятствие для «лобового» решения задачи автоматизации игры – «экспоненциальный взрыв». С одной стороны, такой «взрыв» очевиден на практике при попытке запрограммировать игру, а с другой стороны, математически это выражается в виде утверждения об NP-трудности соответствующих вычислительных задач. Я расскажу об NP-полноте игры «Ханаби» в простейшем её варианте - случае одного игрока, который пытается «выложить пасьянс». Установлена точная граница параметров игры «Ханаби», при которой она всё ещё остаётся NP-полной, а при уменьшении любого из этих чисел игра «Ханаби» перестаёт быть NP-трудной (разумеется, если P не равно NP). Эти значения параметров оказываются очень маленькими, что демонстрирует практическую невозможность точного анализа «Ханаби» даже при небольших параметрах игры.