Бизнес-идиллия с драматическим концом

Представим себе обычную фирму, занимающуюся поставками, например, компьютерной техники. У фирмы есть склад, где хранятся контейнеры, коробки и другие ёмкости разного размера с этой самой техникой. Представим обычного среднестатистического менеджера, который нашёл покупателя на технику, договорился с ним и сообщил на склад, что завтра в такое-то время прибудет фура — забирать товар. Представим себе диспетчера склада, который получил заказ от менеджера и понимает, что фура ждать не будет. Завтра к назначенному времени товар должен быть собран в непосредственной близости от погрузочного пандуса. Диспетчер проверил наличие товара по компьютерной базе: товар есть в наличии, лежит себе, миленький, пылится где-то на полках. Теперь дело за кладовщиком Васей. Кладовщик Вася сидит мирно у себя в каморке, разгадывает кроссворд, или жуёт лапшу быстрого приготовления, или занимается ещё чем-то интеллектуальным. В общем, отрывается человек и не знает, какая грозная туча над ним нависла.

Диспетчер одним своим взглядом свергает Васю с небес на землю. Вася знает, что явление диспетчера с бумажками в руках ничего хорошего не предвещает. А тут ещё погрузчик как назло сломался. И остаётся наш кладовщик Вася один на один со списком товаров. Так из трагедии маленького человека, который оказывается крайним в борьбе сильных мира сего, родилась бессмертная игра сокобан.

История и немного философии

Сокобан (кстати, многие источники указывают на то, что правильнее писать soukoban — так ближе к языку оригинала) родом из Японии. Вполне понятно, почему подобная игра появилась именно в Японии — стране восходящего солнца, самураев и трудоголиков. В ней так и чувствуется влияние японского «осс» — «терпи».

Терпение — это как раз то, что понадобится кладовщику — главному герою игры — на пути к заветной цели. Кстати, слово «soko-ban» — японское и переводится именно как «кладовщик». Правила игры просты и изящны как всё гениальное. На складе сложной конфигурации (в большинстве описаний его называют «лабиринтом», и это истинная правда) находится кладовщик и ящики. Все ящики необходимо поставить на конечные позиции (обычно они обозначаются ромбиками). Ящики можно только толкать, но нельзя тянуть. Кроме того, нельзя толкать больше одного ящика. Запрёшь ящик в угол — уже никогда его оттуда не вытащишь — придётся начинать всё с начала. Придвинешь один ящик вплотную к другому — и сдвинуть его сможешь, только подойдя к нему сбоку. Если, конечно, не помешают стенки. Или другие ящики.

Изобретена игра была в далёком 1980 году и довольно быстро её портировали сначала на Nintendo, а потом и на все известные платформы.

Позже под руководством изобретателя этой игры было выпущено несколько официальных сиквелов, главными из которых считаются Sokoban Perfect (1989) и Sokoban Revenge (1991). Они содержат по 360 уровней. Официальная страница игры сокобан находится по адресу www.sokoban.jp. К сожалению, она имеет только японскую версию.

Клоны и современность

Сейчас клонов этой игры, быстро ставшей классической, великое множество. Сокобан повторил судьбу тетриса, разве что в более скромных масштабах. Есть реализации игры для карманных компьютеров, игровых приставок, мобильных телефонов и, конечно же, для PC. Правила игры остаются неизменными. Меняются графика, оформление, даже количество измерений (существуют 3D-версии сокобана), но идея прежняя — всё тот же несчастный кладовщик, запертый в лабиринте (в классическом варианте все лабиринты умещались в поле 19х18 клеток) с кучей ящиков.

Возникновение клонов стало возможным, потому что автору игры и его компании принадлежат права непосредственно на программу как на конечный продукт, а не на идею. Кроме того, автору принадлежат права на планы уровней первой реализации (в версии 1984 года их было пятьдесят). Поэтому всяческие римейки, использующие уровни того самого первого сокобана, являются, строго говоря, незаконными.

С этими планами уровней произошла по-настоящему детективная история, которая рассказывается на различных сайтах фанатов игры. В начале 90-х годов некие программисты создали Unix-клон сокобана под названием XSokoban. В эту версию были перенесены классические уровни. Причём восемь из них перенесены с ошибками. Есть версия, что сами авторы XSokoban эти изменения ошибками не считали и сознательно упростили уровни. Так случилось, что об этих изменениях не было известно широкой общественности, и ошибки начали перекочевывать из одного клона сокобана в другой. В результате многие версии, позиционирующиеся как классические, на самом деле таковыми не являются.

Вообще, законных римейков с классическими уровнями не так уж много. Один из них называется Sokomind. Он был написан немцем по имени Геральд Холлер (Gerald Holler) в 1997 году, чья домашняя страничка сейчас закрыта по неизвестным причинам. Но раз уж хорошая игра появилась в Сети, она останется там навечно. Надо только уметь искать. В этой версии шестьдесят уровней. Пользователям предоставлена возможность создавать их самим. Есть даже некоторое усложнение и без того непростой задачи: ящики нужно не просто распихать по местам, а расставить в определённом порядке.

Стоит упомянуть и о совсем уж экзотических вариантах, существующих в Интернете. Например, о гексагональном сокобане где игровое поле составлено не из квадратиков, а из шестиугольников. Такую же форму имеют и контейнеры, и кладовщик. Есть ряд версий, где изменена конечная цель игры. Например, в игре CyberBox нужно не расставлять ящики по своим местам, а привести фигурку Васи на определённый квадрат, являющийся выходом из лабиринта. Изначально этот выход основательно загромождён ящиками и добраться до него можно, только растолкав их в разные стороны. Есть ряд игр, где задача усложняется тем, что каждый ящик требуется поместить на своё, строго определённое место.

Научная сторона вопроса

Сокобан — игра логическая, стоит в одном ряду с кубиком Рубика, шашками и даже шахматами. Простые, можно даже сказать, элегантные правила — вершина айсберга. В глубине — сложная математическая теория. Поэтому нет ничего удивительного, что игрой заинтересовались учёные. Наверное, несчастный кладовщик Вася очень бы удивился, если б узнал, что его действия можно изучать с точки зрения теории вычислительной сложности. Задача решения этой головоломки относится к так называемым NP-трудным задачам, как часть более общего класса задач планирования движения (в общем случае Вася будет иметь право не только толкать, но и тянуть, и не один, а сразу несколько ящиков). Сокобан представляет интерес и для исследователей искусственного интеллекта: хорошо бы построить такого робота, который выполнял бы задачу Васи и, перемещая ящики по лабиринту, ставил их на определённые места. При этом нужно, чтобы он выполнял свою задачу в оптимально короткие сроки за минимальное количество шагов.

Трудность прохождения сокобана заключается не только в уровне ветвления дерева вариантов ходов (многие исследователи сравнивают эту игру по сложности с шахматами), но и в огромной глубине поиска по этому дереву. Для того чтобы найти верное решение, требуется перебрать очень много вариантов. Необходимое количество «правильных» ходов, ведущих к выигрышу, на некоторых уровнях может достигать тысячи. Однако опытные игроки, вооружённые эвристикой, могут быстро отсеять в мозгу заведомо тупиковые варианты, тем самым существенно сузив область поиска.

Некоторые (заметьте, только некоторые) уровни игры могут быть решены «автоматически», с помощью определённых итерационных поисковых алгоритмов. С этой целью, например, была создана программа Rolling Stone, которая умеет самостоятельно проходить некоторые уровни сокобана. Она была разработана в недрах GAMES Group Университета Альберты (одной из провинций Канады). Сложные же уровни сокобана всё ещё не поддаются «автоматическому» прохождению.

Задачи и стратегия

Кроме главной задачи головоломки — расставить ящики по своим местам — существует ещё две задачи для игрока: минимизировать перемещения ящиков по лабиринту и число движений кладовщика. Решение этих задач уже схоже с решением шахматных этюдов — правила те же, но игра обрастает дополнительными условиями. В общем, стратегия ходов осваивается игроком с первых минут игры. Есть несколько действий, которые нельзя совершать ни при каких обстоятельствах:

• нельзя допускать, чтобы два ящика оказались друг рядом с другом у стены (вы никогда их не вытащите оттуда: тянуть ящики нельзя, толкать два ящика — тоже);

• нельзя задвигать ящик в угол;

• нельзя сдвигать ящики в квадрат 2x2.

Кроме того, могут возникнуть такие ситуации, когда ящиками будет заблокирована определённая область лабиринта. И любая попытка разблокировать эту область, подвинув ящик, приведёт к одной из описанных выше ситуаций.

Вообще, игра сокобан — хороший экзамен на логическое мышление. Действует лучше и надёжнее всяческих многочисленных тестов. Причём для этого вовсе не обязательно владеть сложным арсеналом приёмов и стратегий. Достаточно освоить только несколько несложных правил.

Как мы уже говорили, универсального алгоритма решения этой головоломки фактически не существует. Однако есть программы, которые позволяют упростить решение: вычислить предположительно правильные ходы на определённую глубину, помочь в записи решения на диск. Если забыть про математический формализм, существует ряд программ, которые с полным правом могут носить название «solver». Они действительно умеют решать многие, даже не самые простые уровни. Но и у них есть предел.

В мире шахмат существуют определённые правила записей ходов и позиций на доске. В мире сокобана тоже выработаны такие правила. План уровня и первоначальное положение объектов записывается в обычном текстовом файле с помощью следующих символов: «#» — стены, «.» — пустое место, куда надо поставить ящик (так называемая «цель»), «@» — кладовщик, «+» — кладовщик, который стоит на той клетке, где находится одна из целей, «$» — ящик на пустом месте, «*» — ящик на одной из целей. Такой формат записи получил название «XSB File Format». Файлы этого формата могут иметь расширения: xsb, sok, rdf, lp0, dat, pak и даже просто txt. Этот формат хранения уровней вы найдёте во многих клонах сокобана.

Кстати, генерация уровней — тоже не самая простая задача. Попробуйте создать новый уровень сокобана с нуля. Недостаточно просто нарисовать причудливый лабиринт и раскидать по нему ящики. Нужно чтобы уровень имел как минимум одно решение. Количество возможных вариантов решения определяет сложность уровня.

Задача генерации уровней для сокобана так и просилась под клавиатуру программистов. Поэтому за годы существования игры появилось немало программ, которые умеют автоматически создавать интересные уровни, основываясь на различных исходных настройках. В качестве исходных настроек выступают, например, размер уровня по горизонтали и вертикали, количество ящиков, количество «пустого» пространства внутри лабиринта.

Есть ещё более простой формат, где план уровня записывается в строчку. Уровень в таком формате выглядит, например, так:

[2-5#|3#3-#|#2-*#-2#|#-#2-*-#|#-*2-#-#|2#-#+2-#|-#3-$2#|-3#2-#|3-4#]

Цифрами обозначается количество повторений символа, который идёт за этой цифрой. Символом «|» даётся команда на начало новой строки.

Есть также отдельный формат для записей перемещений кладовщика по лабиринту. В нём все перемещения записываются буквами r, l, u и d (соответствующие четырём направлениям перемещений). Если при перемещении двигается ящик, то буквы записываются в верхнем регистре.

За годы своего существования сокобан превратился из простой логической игрушки в культовый объект. С каждым годом появляются всё новые и новые версии этой игры. По нему пишут диссертации и научные статьи. Он оброс различными вспомогательными программами и файловыми форматами. Ну и кроме всего прочего, сокобан — это неплохой способ убить время и потренировать мозги.

Статья была впервые опубликована в журнале «Компьютерра» 24 июля 2007.