#матлог

--------------------------------------------------------------
↪ Логика, лингвистика и формальная философия
10 декабря в 18:10 состоится заседание научно-исследовательского семинара «From the Logical Point of View».

Тема доклада: Алгоритмическая сложность кооперативной игры "Ханаби".

Докладчик: Анастасия Оноприенко (к.ф.-м.н., департамент больших данных и информационного поиска).

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

Ждём вас в кабинете А-117 или в Zoom!

Анонс и регистрация: https://llfp.hse.ru/announcements/1108058816.html

➰ ВК