На прошлой неделе появилось сразу несколько новостей, касающихся сложностей тех или иных игр - в том числе, принадлежащих к золотой классике компьютерных развлечений. Вопросы, затрагиваемые в этих работах, относятся, пожалуй, к числу самых фундаментальных в теории алгоритмов. Они, равно как и результаты ученых, заслуживают подробного изложения. В связи с этим мы в "Ленте.Ру" решили написать развернутую статью по этой теме.
Представим, что перед нами стоит некоторая очень важная задача. Сами мы решать ее не хотим - вместо этого, формализовав ее условие (представив в виде машинного кода), мы подсовываем ее компьютеру. Пусть трудится за нас. При этом, однако, возникает естественный вопрос: насколько сложна задача, которую мы поставили перед компьютером? Это необходимо знать хотя бы для того, чтобы понимать, справится ли наша машина с этой задачей или решать ее вообще не имеет смысла. Ответ на вопрос о сложности можно давать в привычных нам терминах "легкая задачка", "сложная", "очень сложная". Однако, к несчастью, подобная классификация не очень информативна. Это отчасти связано с тем, что понятие сложности не формализовано - что сложно для выпускника филфака, например, может оказаться простым для парня с ВМК, и наоборот.
Машина Тьюринга
Чтобы формализовать понятие сложности, нужно формализовать понятие компьютера. К счастью, в 30-х годах прошлого века это уже сделал Алан Тьюринг. Он придумал так называемый универсальный исполнитель, который позже получил название машины Тьюринга. Эта машина состоит из двух частей - ленты, разделенной на ячейки, и управляющего устройства (УУ). У устройства есть некоторое (конечное) количество состояний, и оно способно двигаться по ленте вправо и влево. При этом оно способно записывать в пустые или перезаписывать в уже занятые ячейки некоторые символы (тоже конечного) алфавита.
Компьютерная программа, реализующая данный алгоритм, - это машина Тьюринга с набором правил (они называются правилами перехода), которые позволяют по символу в текущей ячейке и состоянию устройства однозначно вычислить три вещи: новый символ, который надо записать в текущую ячейку, новое состояние устройства и направление, в котором производится промотка ленты (вправо или влево, причем всегда считаем, что перемотка осуществляется на одну ячейку). В начальный момент времени на ленте заданы входные данные в виде n записанных символов алфавита.
Сложность алгоритма, как уже говорилось выше, вещь неоднозначная. В качестве меры этой самой сложности можно использовать несколько естественных параметров. Первый - время работы компьютера. В нашем случае считаем, что вычисление всех трех параметров по правилам перехода вместе с переездом на следующую ячейку занимает одну единицу времени. Это предположение естественно, поскольку все подобные операции связаны с непосредственной физической реализацией машины Тьюринга. По сложившейся традиции, количество шагов определяется как функция от n - то есть от длины входных данных. Так как точную зависимость определить можно далеко не всегда (а на самом деле, из-за громоздкости комбинаторных вычислений, почти никогда невозможно), то обычно ограничиваются оценкой сложности сверху (то есть в терминах "не более чем...").
Зная все это, мы можем определить несколько естественных классов сложности - P и EXPTIME. Эти классы состоят из задач, которые решаются за полиномиальное время (то есть когда количество шагов не превосходит многочлена p(n)) и за экспоненциальное время (2q(n)) соответственно. Первый класс считается относительно "легким" и состоящим из задач, которые действительно можно решить на компьютере для достаточно больших n. К ним относятся умножение чисел, деление, взятие остатка и многие другие задачи.
Тут, кстати, надо заметить, что, как показывает довольно длительная практика реализации алгоритмов в виде программ для ЭВМ, если задача решается за полиномиальное время машиной Тьюринга, то она решается за полиномиальное время и настоящим, сделанным из кремния и железа компьютером. Понятное дело, что
формально никто не доказывал этого для разных языков программирования, операционных систем, архитектур процессоров и многого другого (от чего зависит программная реализация алгоритма), но общая убежденность в этом факте присутствует.
Итак, вернемся к вопросу сложности. Время - не единственная естественная мера сложности, есть еще, например, количество памяти, то есть ячеек на ленте, которое требуется для работы алгоритма. Аналогично предыдущему случаю, сложность измеряется при помощи оценок на количество памяти. Самые известные здесь классы - это L, PSPACE и EXPSPACE. Это задачи, для которых количество памяти оценивается через логарифм от n, помноженный на константу, полином от n и экспоненту от n соответственно.
Немного случайности
К несчастью, обычной машины Тьюринга для изучения алгоритмов оказалось недостаточно. Поэтому возникло понятие так называемой недетерминированной машины Тьюринга. Представим себе машину Тьюринга, у которой во время работы возникла неоднозначность: так получилось, что правила перехода не дают однозначного ответа на то, как ей дальше поступить в сложившейся ситуации. То есть компьютер оказался перед выбором из двух и более вариантов и ему нужно сделать выбор. Дальнейшая работа машины может интерпретироваться двумя эквивалентными способами.
Способ первый. Машина делает случайный выбор, однако всегда выбирает правильный вариант. Это так называемая схема удачливой машины Тьюринга, которая полезна в теоретических рассуждениях. Вариант второй - машина разделяется на копии, каждая из которых начинает изучать свой вариант развилки (этот способ позволяет с некоторыми допущениями программировать недетерминированную машину на практике).
При помощи недетерминированной машины Тьюринга определяются классы NL и NP - задачи, требующие для работы соответствующей машины порядка логарифм от n памяти и выполняемые через полиномиальное время от n соответственно. Примечательно, что другие классы, например, NPSPACE для недетерминированной машины Тьюринга, совпадают с классами сложности детерминированной машины Тьюринга. Этот нетривиальный факт следует из теоремы Сэвича. Отдельный и самый существенный интерес представляют задачи класса NP - к ним относятся многие важные проблемы, например задача коммивояжера - поиск кратчайшего пути в графе, проходящего через все вершины хотя бы по одному разу. Есть еще одно определение NP, эквивалентное представленному выше - это задачи, правильность решения которых можно проверить за полиномиальное время.
Все введенные классы можно отсортировать следующим образом: L, NL, P, NP, PSPACE, EXPTIME, EXPSPACE, - где каждый класс лежит в следующем справа за ним классе. Взаимоотношение между разными типами задач - одна из центральных проблем теории алгоритмов. Например, институт Клэя выбрал семь так называемых Задач тысячелетия, за решение каждой из которых полагается премия в миллион долларов (одной из задач была гипотеза Пуанкаре, а россиянин Григорий Перельман, решивший задачу, напомним, от премии отказался). Так вот, доказательство того, что классы P и NP не совпадают, то есть существуют задачи, решаемые за полиномиальное время на недетерминированной машине Тьюринга, но не решаемые за такого же порядка время на детерминированной, входит в этот список.
Немного об играх и задачах
Осталось уточнить еще один нюанс и можно переходить к описанию игр и связанных с ними результатов исследователей. Всюду мы считаем, что задача сформулирована в форме вопроса, на который можно дать односложный ответ "да" или "нет". На первый взгляд, это существенно ограничивает класс вопросов, с которыми мы можем обратиться к нашей машине, однако это не так.
Например, говоря об упоминавшейся выше задаче коммивояжера, мы можем сформулировать вопрос не так: "какова длина кратчайшего пути в графе, проходящего через все его вершины ровно один раз?" - а так: "есть ли в графе путь, проходящий через все вершины графа, длиной не больше D?". Меняя D в последнем вопросе и последовательно запуская гипотетический компьютер несколько раз, мы можем получить однозначный ответ: например, если для D = 5 был ответ "нет", а для D = 6 ответ уже "да", то, очевидно, длина кратчайшего пути равна 6. Такие задачи будем называть задачами распознавания (при этом читателю стоит держать в уме, что задачами распознавания еще называют задачи, связанные с распознаванием визуальных образов - объект из совсем другой области прикладного научного знания).
Теперь перейдем к описанию сложностей классических игр. Первая на очереди - "Скрэббл", известная в русском варианте как "Эрудит". Правила игры таковы: дано поле 15 на 15 клеток и 104 буквы. Перед игрой каждый игрок получает по 7 букв из набора, а в центре доски выставляется некоторое слово. Затем, каждый из игроков по очереди выкладывает на доске, пользуясь только имеющимися у него на руках буквами, свое слово. Главное требование - слово игрока должно иметь общие буквы с уже имеющимися на доске словами (на самом деле, конечно, это не все правила, полный их список есть здесь).
Сформулируем формальную задачу, которая (разумеется, лишь с некоторой степенью точности) характеризует сложность всей игры. Мы считаем, что игра ведется в открытую, то есть игроку известны буквы, которые остались в куче, у противника и его собственные. Также известно расположение букв на доске. Какова вычислительная сложность алгоритма, который позволяет определить выигрышную стратегию, если таковая имеется в данной ситуации? Оказывается, задача относится к классу PSPACE (препринт). Более того, она PSPACE-полная, то есть любая другая задача из этого класса за полиномиальное время сводится к данной (PSPACE-полные - это, в некотором смысле, самые сложные задачи класса PSPACE). Примечательно, что сложность игры определяется тем, что игроку приходится составлять новые слова, а также решать, куда и в каком порядке их ставить - ученые показали, что оба этих процесса PSPACE-трудны.
В рамках другой работы итальянский ученый Джованни Вильетта из Пизанского университета посчитал сложности классических компьютерных игр (препринт). Он моделировал их в виде графов, к которым применял машину Тьюринга для решения некоторой подходящей задачи распознавания. В результате, он установил, что
- Boulder Dash (1984) - сложность NP
- Deflektor (1987) - сложность L
- Doom (1993) - сложность PSPACE
- Lemmings (1991) - сложность NP
- Lode Runner (1983) - сложность NP
- Mindbender (1989) - сложность NL
- Pac-Man (1980) - сложность NP
- Pipe Mania (1989) - NP-полная игра
- Prince of Persia (1989) - PSPACE-полная игра
- Puzzle Bobble 3 (1996) - NP-полная игра
- Skweek (1989) - NP-полная игра
- Starcraft (1998) - сложность NP
- Tron (1982) - сложность NP
Примечательно, что работа Вильетта - далеко не первая по этой тематике. Ученые занимаются изучением комбинаторных головоломок (к которым и относятся перечисленные игры, то есть они лишены элемента случайности - все процессы определяются только действиями игрока и ответными действиями компьютера). Среди прочего раньше было установлено, например, что "Сапер" представляет собой NP-трудную задачу (pdf), то есть задачу из того же класса, что и шахматы.