Вычислительная сложность некоторых игр и головоломок (часть 2)
В предыдущей статье мы рассмотрели сложность некоторых игр и головоломок. Данная тема вызвала некоторый интерес, вот и продолжение. В комментариях некоторые читатели высказали свои пожелания, которые я постарался учесть.
В первой статье и правда по справедливому замечанию avsmal «не хватает каких-то более строгих и конкретных утверждений», но не стоит забывать, что любой даже самый нудный материал нужно стараться подать интересно. В прошлый раз я пожертвовал структурой и конкретностью в пользу читабельности и привлечения интереса к теме. Сильно «душные» статьи заходят с большим скрипом и больше отпугивают читателя.
Прежде всего, нужно отметить, что теория вычислительной сложности анализирует сложность различных алгоритмических задач, а теория вычислимости — какие проблемы могут быть решены с помощью алгоритмов. Теория сложности рассматривает проблемы, которые в принципе могут быть решены алгоритмически, и пытается установить экстремумы ресурсов, необходимых для их решения. Это важно, потому что некоторые проблемы в принципе могут быть решаемы, но требовать неосуществимого количества ресурсов.
— Сорок два! — взвизгнул Лунккуоол. — И это всё, что ты можешь сказать после семи с половиной миллионов лет работы?
— Я всё очень тщательно проверил, — сказал компьютер, — и со всей определённостью заявляю, что это и есть ответ. Мне кажется, если уж быть с вами абсолютно честным, то всё дело в том, что вы сами не знали, в чём вопрос.
«Автостопом по Галактике» Дуглас Адамс
Анализ чаще всего проводится путем связывания неизвестных проблем с другими хорошо изученными проблемами. Так в теории сложности появилось определение различных классов, то есть наборов задач соразмерной сложности. Другой подход теории сложности заключается в изучении отношений между самими классами. Так появилась самая известная открытая проблема перебора (P=NP).
Для формализации любой проблемы необходимо определить критерии измерения (обычно время и память, хотя могут использоваться и другие, в зависимости от контекста, например, энергия) и подходящую модель вычислений. Также в комментариях прозвучал тезис о неоднозначности понятия вычислительной сложности игры или головоломки, и далее я конкретно отмечу, какого рода сложность имеет место. В контексте головоломок вопрос чаще всего заключается в поиске оптимального решения. То есть само решение ещё требует доказательства его оптимальности. Тогда как сложность игры почти всегда связана с семейством проблем, а не с конкретными экземплярами какой-либо одной игры. Требуемые ресурсы всегда растут с размером проблемы. В результате большинство доказательств, связанных с играми, требуют обобщения анализируемой игры.
По классам сложности в основном ни у кого вопросов не возникло, да и информации об этом предостаточно в других статьях (в том же руководстве по сложным вычислительным задачам). Хотя я бы сделал несколько замечаний. Касательно PSPACE можно сказать, что пространство в некотором смысле сильнее времени, потому что его можно использовать повторно. В результате задачи, требующие полиномиального объема памяти, могут потребовать экспоненциального времени.
NPSPACE — класс задач, которые можно решить в полиномиальном пространстве на недетерминированной машине. Однако недетерминизм в пространстве не играет такой большой роли, как во времени. Согласно теореме Сэвича, можно смоделировать любую недетерминированную машину в детерминированной с квадратом пространства (PSPACE = NPSPACE).
Одни из самых сложных задач принадлежат EXPTIME. Они могут быть решены за экспоненциальное время. Этот класс как раз и включает в себя наиболее популярные настольные игры для двух игроков (го, шахматы и шашки). Одним из важнейших аспектов этих игр является то, что количество ходов в игре неограничено, и это увеличивает сложность от PSPACE до EXPTIME. Кроме того, это единственный класс, который, как было безусловно доказано, сложнее, чем P, а PSPACE и NP только предполагаются более сложными, чем P.
С момента постулирования NP-полноты в начале 1970-х годов теория вычислительной сложности играла важную роль в анализе сложности задач. В частности теория во многом облегчила доказательство того, что некоторая задача действительно в какой-то степени сложна. Например, NP-полная задача не может быть решена эффективно с помощью детерминированных алгоритмов (разумеется, если только P = NP, что, собственно, не доказано, хотя справедливости ради стоит отметить, что не доказано и обратное). В этом случае знание класса сложности проблемы помогает не терять время на бесплодные поиски, и для решения следует рассмотреть альтернативные варианты, например такие, как аппроксимация.
Большинство изучаемых игр и головоломок прошли определённый период «взросления» (появление более эффективных решений). Что интересно, поиск таких вариантов сложнее, чем простой поиск решения. Когда имеется не только экземпляр задачи, но и ответ, найти решение, отличное от уже известного несколько сложнее. Такие задачи интересны, так как существует вероятность того, что заранее известное решение облегчит задачу, но это неточно скорее всего, наличие решения только помешает в поисках. Некоторые исследователи выделяют такие задачи в отдельный класс сложности ASP(Another Solution Problem).
Примером может служить известная NP-полная задача о гамильтоновом графе. Даже если граф является гамильтоновым, задача поиска гамильтонова цикла, отличного от известного, является NP-полной. Также известно, что задача поиска гамильтоновой цепи остается NP-полной, если входные графы ограничены кубическими (неориентированный граф G называется кубическим графом, если степень всех вершин равна трём). Теорема Смита утверждает, что каждое ребро в кубическом графе G находится в чётном числе гамильтоновых цепей графа G. Отсюда следует, что если у кубического графа есть гамильтонова цепь, то она не одна.
Проблема определения существования другой гамильтоновой схемы, когда задан гамильтонов кубический граф, тривиальна. Однако найти другую гамильтонову цепь сложно.
Сокобан
Итак, пожалуй, начнём с классической задачи планирования движения. К этой задаче сегодня можно отнести большое количество игр и на первый взгляд может показаться, что игры, построенные на этой механике примитивны. Однако именно в настоящее время исследования в этой области как никогда востребованы. Эта вычислительная задача поиска последовательности допустимых конфигураций перемещений находит применение в самых разных сферах: машинное обучение, управление беспилотными транспортными средствами, роботизированная хирургия и другая робототехника, биофизика и многое другое. Пожалуй, первой и самой бессмертной игрой, использующей эту механику, стал сокобан. Эта игра, так же как в своё время и Кубик Рубика, давно стала культовой и представляет собой массовое культурное явление. Несмотря на кажущийся примитивизм, это один из математических монстров, в решении которого пальма первенства пока принадлежит человеку. Сложные уровни сокобана так и не поддались машинам.
Не зря говорят, что всё гениальное просто. Казалось бы, простейшая игра оказалась просто культурным шоком для своего времени. В простые и незамысловатые правила игры оказалась обёрнута серьёзная по глубине и сложности задача. Первичные исследования с помощью теории вычислительной сложности выявили NP-трудность игры, однако в дальнейшем оказалось, что игра ещё сложнее и принадлежит множеству PSPACE-полных задач. В 1997 году профессор Альбертского университета и один из создателейChinook (программа-игрок в шашки) Джо Калберсон опубликовал доказательство PSPACE-полноты сокобана, взяв за основу доказательства идею невосстановимой конфигурации.
Вычисление оптимального алгоритма прохождения игры из-за большого коэффициента ветвления и глубины дерева поиска, в некоторых случаях расширяемого до бесконечности, требует экспоненциально растущего количества перемещений персонажа и ящиков. Сегодня исследователи продолжают активно работать над разработкой эффективных алгоритмов решения сложных уровней сокобана с использованием современных методов. Игра стала одной из самых популярных платформ для конструирования и анализа алгоритмов, а также исследований в области искусственного интеллекта.
Сокобан стал первым коммерчески успешным релизом компании Thinking Rabbit. В интервью 1983 года Хироюки Имабаяси, основатель компании и создатель сокобана, описывал игру как новый тип игры-головоломки, не вписывающейся ни в один из расплывчато определенных игровых жанров того времени, в чём-то похожей на Цумэ Сёги.
Оригинальные кассеты Sokoban (PC-8801), изготовленные вручную и упакованные самим автором
На Хабре много статей, в которых так или иначе упоминается эта игра, мне больше всего зашли статьи Евгения Грязнова и Александра Клименкова.
Морской бой
Для меня до сих пор остаётся открытым вопрос, как множество самых разных игр практически мгновенно распространялись среди людей, живших в самых разных уголках мира до появления интернета. В воспоминаниях из представляющегося далёким детства эта игра, безусловно, занимает важное место. «Морской бой» — как много в этой фразе «драмы». Вряд ли на Хабре найдётся человек, который хотя бы раз не играл в морской бой.
Происхождение этой игры неясно, но существуют какие-то апокрифические теории о её изобретении в конце XIX — начале XX века. Так как игра носит в основном вероятностный характер, она относится к множеству игр с неполной информацией. Тем не менее существуют определённые стратегии игры, которые условно можно разделить на два типа: стратегия расстановки кораблей и стратегия атаки, которая включает в себя алгоритмы добивания поражённых кораблей соперника. Существующие исследования игры в основном затрагивают поиск эффективных алгоритмов расстановки и атаки с помощью статистических методов. Однако не все знают, что у морского боя есть ещё одно игровое приложение — головоломка «морской бой». Эта головоломка впервые была опубликована в 1982 году в испанском журнале Humor&Juegos.
На международном уровне морской бой успешно дебютировал в 1992 году на первом чемпионате мира по головоломкам в Нью-Йорке. В этой игре флот прячется в квадратной сетке 10×10. В состав входит один линкор длиной четыре клетки, два крейсера — три клетки, три эсминца — две клетки и четыре одноклеточных подводных лодки. Правила расположения кораблей аналогичны оригинальной игре. Игровая сетка размечается цифрами, обозначающими количество кораблей или их частей в определённой строке или столбце. В исходном виде такая головоломка уже содержит ряд подсказок. Существуют варианты с сеткой большего или меньшего размера, а также использующие гексагональную сетку.
По классу сложности обобщённая игра является NP-полной, однако так же как и в судоку, остаётся открытым вопрос о минимальном количестве подсказок, необходимых для уникального решения головоломки.
Отелло (Реверси)
Считается, что эта игра впервые появилась в конце XIX века, однако имеются основания полагать, что это случилось намного раньше. Двойное название игры появилось исторически, так как помимо упоминаний о том, что в эту игру играл Наполеон, будучи в изгнании на острове Святой Елены, реверси была придумана ещё несколько раз. Англичанин Джон Моллетт изобрёл реверси в 1870 году, а в 1876 году издал игру с крестообразным полем под названием «The Game of Annexation». Чуть позже другой англичанин Льюис Уотерман предложил практически ту же самую игру только под названием «Reversi», единственным отличием была форма игрового поля (квадрат). Уже в 1886 году Моллетт отказался от крестообразного поля, и некоторое время продолжались патентные споры, однако вскоре игра была благополучно забыта, и только в 1971 году японец Горо Хасэгава вновь запатентовал игру и назвал её «Отелло».
C:\Users\drsob\Desktop\FirstVDS\puzzle\game complete\2\pic\othello.png
Основной смысл игры заключается в захвате территории, при этом механика игры предусматривает обращение фишек соперника в свой цвет при ограничении группы фишек. Выигрывает тот игрок, фишек которого больше на доске. С математической точки зрения, задача определения, есть ли выигрышный ход у первого игрока в определённой позиции обобщённой игры, является PSPACE-полной. Так же как го и шахматы, эта игра уже не принадлежит человеку, поскольку начиная с 1997 года, когда программа Logistello обыграла чемпиона мира Такэси Мураками 6:0, у людей-игроков нет никаких шансов против программ. Оказалось, что игра достаточно легко формализуется и обсчитывается алгоритмами. Сегодня лавры AlphaGo не дают покоя разработчикам, вынуждая исследовать возможности свёрточных нейронных архитектур, работающих со сложными пространственными паттернами. При этом даже текущие результаты исследований уже превосходят по возможностям программы, созданные для игры в Othello (Edax).
Нарды
Из всех игр, в которые я когда-либо играл, эта по необъяснимым для меня причинам всегда вызывала какое-то отторжение. Не знаю, с чем это связано, но факт остаётся фактом — нарды я не люблю, а упустить тот факт, что игра принадлежит к определённым классам сложности, я не мог. Как бы то ни было, нарды — одна из старейших известных и процветающих игр в мире. Этой игре больше нескольких тысяч лет, и точное время её изобретения неизвестно, но археологи находили похожие игры, датированные 3000 лет до н.э.
На данный момент более всего распространены два варианта нардов — длинные и короткие. Несмотря на древность игры, свод правил появился только в 1743 году, автором которого был англичанин Эдмонд Хойл, а современные
международные правила проведения соревнований были введены в 1931 году в США. Целью игры является перемещение фигур игрока в свой «дом», а затем — за пределы доски.
Количественное изучение игры в нарды началось в 1970-х годах, и алгоритмы игры быстро развивались. К 1979 году программа обыграла чемпиона мира по нардам со счетом 7:1. Это событие ознаменовало собой первый раз, когда компьютерная программа превзошла известного игрока-человека в признанной интеллектуальной деятельности. С тех пор прогресс программ-игроков в нарды продолжается, особенно за счёт развития современных нейронных сетей.
С теоретической стороны нарды изучались с вероятностной точки зрения как непрерывный процесс и случайное блуждание. Однако вычислительная сложность игры в нарды оставалась открытой проблемой спустя два десятилетия после того, как она была впервые поставлена. С точки зрения сложности, нарды резко контрастируют со многими другими популярными играми. Одно из возможных объяснений сложившейся ситуации заключается в сложности обобщения игры.
Есть две основные технические проблемы, которые делают нарды особенно сложными для анализа. Во-первых, сложность принуждения игрока к определенному ходу. Все фигуры в нардах следуют одним и тем же правилам движения, и за ход можно получить не менее 15 уникальных комбинаций бросков костей. Для других игр эта проблема была решена более серьёзными упрощениями и подробными рассуждениями о том, почему игрок должен следовать определенным ходам. В доказательствах сложности проблема игры в нарды рассматривалась с точки зрения одного игрока, при этом действия оппонента и броски костей служили рычагами вынуждения игрока делать определенные ходы.
Вторая проблема заключается в том, что доска для игры в нарды одномерна. Большинство других исследуемых в отношении вычислительной сложности игр имеют, по крайней мере, два измерения игры, что создаёт большую свободу обобщения. Результаты исследования показали, что решение задачи о возможности выигрыша может являться как NP-сложным, так и PSPACE- и EXPTIME-сложным для различных вариаций известности или неизвестности результатов бросков костей и стратегий противника.
В частности, в сеттинге, наиболее похожем на обычную игру, когда стратегия противника и результаты бросков костей неизвестны, решение о возможности выигрыша игрока соответствует классу сложности EXPTIME-трудных задач. Решение при известных всех последующих результатах бросков костей и открытой стратегии противника является NP-трудным. При известных результатах бросков и неопределённой стратегии соперника задача относится к PSPACE-трудным.
Интересно и пока совершенно неясно, действительно ли можно отнести проблемы поиска решений в нардах к EXPTIME, потому что игра в нарды теоретически может продолжаться бесконечно, и тогда естественным образом возникает вопрос, к какому вообще классу сложности отнести такие задачи?
Маджонг
В прошлой и этой статье мы, прежде всего, рассматривали детерминированные игры (без элемента случайности), однако всё игровое многообразие отнюдь не ограничивается такими играми. Фактор случайности влияет на предсказуемость игры и вносит неопределённость в игровой процесс. Случайность в играх является одним из самых мощных стимулов вовлечения. С точки зрения современного представления об играх, любая игра с элементами случайности является азартной. На протяжении многих веков азартные игры то захватывали массы людей, то уходили в подполье. Сегодня статус азартных игр в разных странах также варьируется от полного запрета до повсеместного распространения, однако в любом государстве осуществляется строгий контроль этой сферы. Лудомания — это однозначно плохо, но как по мне — это проблемы человека, а не игры. В любом случае психологическое влияние случайности в игре оказывает мощный притягательный эффект, что легко объяснимо человеческой природой. Что интересно, возникновение такого раздела математической науки, как теория вероятностей, напрямую обязано азартным играм. Именно попытки математического анализа азартных игр легли в фундамент этой дисциплины.
С самого начала исследований в области искусственного интеллекта многие популярные игры использовались в качестве испытательных стендов для многих техник и идей. В последние десятилетия создано множество программ, способных играть на равных с человеком, а некоторые из них не стесняются побеждать лучших игроков-людей в играх с полной информацией, включая такие игры как шашки, шахматы и го. Байесовские игры с неполной информацией, как правило, сложнее, однако и в этих играх намечается определённый прогресс. Одной из таких игр и является маджонг.
В комментариях к прошлой статье просили включить в продолжение темы информацию об этой игре, поэтому я не мог проигнорировать этот факт. Я сам не очень давно знаком с ней и первым приобщением, наверное, можно назвать пасьянс маджонг, хотя, строго говоря, пасьянс — совершенно другая игра и единственное, что объединяет игры — это игровой инвентарь. Так или иначе, до определённого времени я и не знал, что существует «настоящий» маджонг. Здесь, в общем-то, нет ничего странного, поскольку не в каждом магазине с играми на витрине был маджонг, да и партнёров для игры в офлайне найти было не так-то легко. Сейчас всё намного проще, но если вспомнить времена хотя бы двадцатилетней давности, то становится понятно, почему эта игра не так распространена на постсоветском пространстве. В Википедии статья об истории и правилах маджонга довольно подробна, поэтому описывать их не имеет смысла.
Типы игральных костей маджонг
Маджонг — очень популярная многопользовательская игра, в которую играют во всем мире. В классической игре для четверых игроков используется набор из 144 игральных костей, напоминающих домино. Существует много вариантов используемых игровых принадлежностей и правил (подробнее об этом).
Основной принцип игры, как и покера, заключается в сборе определённых выигрышных комбинаций (рук). С математической точки зрения, классическая игра только недавно привлекла внимание исследователей, а учитывая характер и механику игры, для изучения маджонга с использованием математических и вычислительных методов требуется подход, в корне отличающийся от применяемых в изучении игр с полной информацией. На данный момент трудно точно отнести классическую игру к какому-либо классу сложности. Одно можно сказать точно — для исследования необходимо применить синтетический подход на стыке комбинаторики, теории вероятностей, теории игр и психологии. Чтобы разработать алгоритмы оптимальной игры и программную реализацию, потребуется ещё масса исследований и расчётов. Несколько исследований, которые мне удалось найти и изучить, довольно поверхностны и рассматривают только вероятностные аспекты сбора выигрышных комбинаций.
Раз уж выше я упомянул пасьянс маджонг, то неплохо бы написать пару слов и о нём. В 1981 году Броди Локард создал одиночную игру на базе маджонг, пришедшуюся многим пользователям по вкусу. Позже Activision наняла его, и в 1986 году была выпущена игра Shanghai для платформ IBM Personal Computer, Commodore Amiga, Macintosh, Atari ST и Apple IIGS.
В пасьянсе кости случайным образом укладываются лицевой стороной вверх в стопки, образуя определенную форму (большинство компьютерных пасьянсов включают несколько форм разной сложности). Цель состоит в том, чтобы разобрать фигуру, удаляя совпадающие пары открытых костей.
Расклад «черепаха»
С точки зрения класса сложности, существуют два варианта решения задачи. Если костяшки нижних слоёв фигуры известны, нахождение оптимального решения относится к NP-полным. Если неизвестны — решение приобретает характер PSPACE-полной задачи.
Анализ 10 млн вариантов раскладов формы «черепаха» методом Монте-Карло показал, что 2,95%-2,96% вариантов не имеют решения, даже если разрешено смотреть под верхние кости. Данные по остальным раскладам можно увидеть здесь.
Комбинаторная теория игр обеспечивает теоретическую основу для получения положительных алгоритмических результатов для игр, но не всегда подходит для головоломок. Отрицательные алгоритмические результаты выявляют сложность и полноту в пределах классов вычислительной сложности. Головоломки и игры имеют похожий прототип структуры доказательств. Для того чтобы отнести проблему к определенному классу сложности нужно свести её к проблеме известной сложной проблемы в каком-либо классе. Например, каноническая проблема NP-трудности сводится к задаче выполнимости (SAT). Сведение SAT к интересующей головоломке доказывает, что эта головоломка является NP-сложной.
Многие игры обладают ожидаемой сложностью: ограниченные игры с одним игроком NP-полны, неограниченные игры для одного игрока и ограниченные игры для двух игроков являются PSPACE-полными, а неограниченные игры для двух игроков относятся к EXPTIME.
Большая часть игр ограниченной длины для двух игроков являются PSPACE-полными, и это довольно естественно. Результат PSPACE-полноты имеет два следствия. Во-первых, нахождение в PSPACE означает, что игру можно вести оптимально, и, как правило, все позиции можно перечислить, используя, возможно, экспоненциальное время, но полиномиальное пространство. Таким образом, подобные игры поддаются разумному и исчерпывающему поиску.
Во-вторых, игры не могут быть решены за полиномиальное время, если только P = PSPACE, что даже «менее вероятно», чем P = NP. Игры неограниченной продолжительности для двух игроков часто относятся к EXPTIME, и такой результат является одним из немногих типов истинных нижних оценок в теории сложности, подразумевая, что все алгоритмы в худшем случае требуют экспоненциального времени.
Изучение игр и их сложности довольно интересная тема, иногда превышающая интерес к самим играм, хотя на первый взгляд кажется, что такой подход к играм какой-то искусственный. Однако понимание того, что игры являются упрощённым отражением мира и обладают вполне прагматичными приложениями в самых разных областях, подталкивает исследователей к изучению всё большего количества игр.
P.S.
— Классы и алгоритмы, для решения пасьянса «Морской бой» (Python)
— Edax мощная программа для решения «Отелло».
— Сокобан-онлайн
НЛО прилетело и оставило здесь промокод для читателей нашего блога:
— 15% на заказ любого VDS (кроме тарифа Прогрев) — HABRFIRSTVDS
