Культ сокобана

АрхивВ фокусе

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

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

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

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

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

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

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

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

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

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

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

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

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

Одна из первых версий Сокобана для Spectrum Holobyte, 1984

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

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

Для любителей браузера Opera существует виджет с этой игрой. Есть несколько версий для Pocket PC и Java-вариантов для сотовых телефонов. Вообще, достаточно в поисковой системе набрать слово "Sokoban", и вы получите множество ссылок на варианты этой замечательной игры.

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

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

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

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

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

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

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

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

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

Объёмный сокобан

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

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

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

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

Некоторые из многочисленных клонов игры сокобан

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

Есть еще более простой формат, где план уровня записывается в строчку. Такой формат удобен, например, для пересылки уровня по SMS (напомню, что имеется целый ряд мобильных версий сокобана). Уровень в таком формате выглядит, например, так:

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

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

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

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

- Из журнала "Компьютерра"