Доклад Анастасии Оноприенко «Алгоритмическая сложность кооперативной игры "Ханаби"»

10 декабря прошло заседание научно-исследовательского семинара «From the Logical Point of View».

фото МЛ ЛогЛинФФ

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