Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Sokoban головоломка решаемой.

Sokoban (倉庫番, Соко-бан ) является игра - головоломка видео жанрав которой игрок толкает ящики или коробки вокруг в хранилище , пытаясь получить их в места хранения.

Сокобан был создан в 1981 году Хироюки Имабаяши. Первая коммерческая игра была опубликована в декабре 1982 года компанией Thinking Rabbit , разработчиком программного обеспечения, расположенной в Такарадзуке , Япония .

Геймплей [ править ]

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

Игрок прикован к доске и может перемещаться горизонтально или вертикально на пустые клетки (никогда не через стены или коробки). Игрок может переместить коробку, подойдя к ней, и толкнуть ее на квадрат. Ящики нельзя тянуть, их нельзя толкать на квадраты со стенами или другими коробками. Количество ящиков равно количеству мест хранения. Загадка решена, когда все ящики помещены на места хранения.

Избранные выпуски [ править ]

ГодЗаголовокСтранаПлатформаИздательСредства массовой информации
1982 г.Сокобан (倉庫番)ЯпонияNEC PC-8801Думающий кроликЛента
1983 г.Сокобан [Extra Edition] (倉庫 番 [番外 編] [1] [2] )ЯпонияNEC PC-8801ПК マ ガ ジ ンИсходный код
1984Сокобан 2 (倉庫 番 2 )ЯпонияNEC PC-8801Думающий кроликЛента
1988 г.Соко-БаннасIBM-PC и совместимыеСпектр HoloByteДискета
1989 г.Соко-бан Совершенный (倉庫 番 Perfect )ЯпонияNEC PC-9801Думающий кроликДискета
1990 г.BoxyboyЯпония, СШАTurbografx-16 и PC EngineNECHuCard
1991 г.Соко-бан Месть (倉庫 番 Revenge )ЯпонияNEC PC-9801Думающий кроликДискета
2016 г.Сокобан Тач (倉庫 番 Тач )Япония, СШАAndroid и Apple iOSДумающий кроликЦифровое распространение

Развитие [ править ]

В 1988 году Sokoban был опубликован в США Spectrum HoloByte для серий Commodore 64 , IBM-PC и Apple II под названием Soko-Ban . Sokoban пользовался успехом в Японии и к тому времени, когда Spectrum HoloByte импортировал его в США , было продано более 400 000 единиц в этой стране . [3]

Реализации [ править ]

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

Научные исследования [ править ]

Сокобан можно изучать с помощью теории вычислительной сложности . Проблема решения головоломок Сокобана впервые оказалась NP-сложной . [4] [5] Дальнейшая работа показала, что это было значительно сложнее, чем задачи NP ; это PSPACE-полный . [6] Это представляет интерес для исследований в области искусственного интеллекта (ИИ), поскольку решение проблемы Сокобана можно сравнить с автоматическим планированием, необходимым для некоторых автономных роботов .

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

Некоторые загадки Сокобана могут быть решены автоматически с помощью алгоритма поиска с одним агентом , такого как IDA * ; дополнены несколькими методами, использующими знания предметной области. [8] Это метод , используемый Rolling Stone , [9] Сокобан решатель , разработанный Университета Альберты ИГРЫ группы. Festival [10] был первым автоматическим решателем, решившим все 90 уровней стандартного набора тестов. Однако более сложные уровни Сокобана недоступны даже для лучших автоматических решателей. [11]

Варианты [ править ]

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

  • Альтернативные варианты : в стандартной игре лабиринты располагаются на квадратной сетке . Несколько вариантов применяют правила Сокобана к лабиринтам, расположенным на других плитах. Hexoban использует правильные шестиугольники , а Trioban использует равносторонние треугольники .
  • Множественные толкатели : в вариантах Multiban и Interlock игрок может управлять несколькими персонажами.
  • Альтернативные цели : несколько вариантов регулируют требования для прохождения уровня. Например, в Block-o-Mania коробки имеют разные цвета, и цель состоит в том, чтобы поместить их на квадраты с соответствующими цветами. Sokomind Plus реализует аналогичную идею с однозначно пронумерованными квадратами и квадратами. В Interlock и Sokolor ящики также имеют разные цвета, но цель состоит в том, чтобы переместить их так, чтобы ячейки одного цвета были рядом. В CyberBox на каждом уровне есть обозначенный квадрат выхода, и цель - достичь этого выхода. В варианте под названием « Бобовый стебель» элементы уровня должны быть помещены на целевой квадрат в фиксированной последовательности.
  • Дополнительные игровые элементы : Push Crate , Sokonex , Xsok , Cyberbox и Block-o-Mania - все они добавляют новые элементы в основную головоломку. Примеры включают дыры, телепорты, движущиеся блоки и односторонние переходы. В игре Sokoban 1982 года ( NEC PC-8801 ) были уровни с разрушаемыми стенами . [12]
  • Действия персонажа : В Pukoban персонаж может тянуть коробки в дополнение к их толканию.
  • Обратный режим : игрок решает загадку в обратном направлении, от конца к исходному положению, вытягивая, а не толкая коробки. Стандартные головоломки Sokoban можно играть в обратном режиме, а решения в обратном режиме можно преобразовывать в решения для головоломок стандартного режима. Следовательно, игровой процесс в обратном режиме также может быть полезен при решении стандартных головоломок Сокобана .

См. Также [ править ]

  • Логическая головоломка
  • Раздвижная головоломка
  • Транспортная головоломка
  • Планирование движения

Ссылки [ править ]

  1. ^ «今 回 は こ の ゲ ー THINKING RABBIT さ ん に, 販 販 に 10 の を っ« Мы разработали эту игру ». склады отдельно от товарной продукции]. PC マ ガ ジ ン(на японском). Август 1983. С. 52–56.
  2. ^ «題 し て『 倉庫 番 PC マ ガ ジ ン 番外 編 (こ の プ ロ グ ラ ム は, PC-8801/9801 で 使 え ま) »[Под названием« Sokoban »PC Magazine Extra Edition (эта программа может использоваться с PC-8801) / . PC マ ガ ジ ン(на японском). Август 1983. С. 52–56.
  3. ↑ Low, Lafe (ноябрь 1988 г.). «Лента новостей; Сделано в Японии». inCider (43). 14, 15.
  4. ^ М. Фрайерс; М. Т. Грин (1995). «Сокобан». Эврика (54).
  5. ^ Дор, Дорит; Цвик, Ури (1999). «СОКОБАН и другие проблемы планирования движения». Вычислительная геометрия . 13 (4): 215–228. DOI : 10.1016 / S0925-7721 (99) 00017-6 . ISSN 0925-7721 . 
  6. ^ Джозеф С. Калберсон, Сокобан является PSPACE-полным ( PS ). Технический отчет TR 97-02, Департамент компьютерных наук, Университет Альберты, 1997.
  7. ^ Дэвид Холланд и Ярон Шохам, "Теоретический анализ Пикокосмоса 17" .
  8. ^ Андреас Юнгханс, Джонатан Шеффер (2001) Сокобан: Улучшение общих методов поиска с одним агентом с использованием знаний предметной области , Искусственный интеллект 129 (1-2): 219-251 (специальный выпуск об эвристическом поиске в искусственном интеллекте).
  9. ^ Юнгханс, Андреас; Шеффер, Джонатан (1997). «Сокобан: сложная проблема поиска одного агента» (PDF) . В семинаре IJCAI по использованию игр в качестве экспериментального стенда для исследований ИИ . Университет Альберты . С. 27–36.
  10. ^ Ярон Шохам, Джонатан Шеффер (2020) Алгоритм FESS: подход на основе характеристик к поиску с одним агентом . Опубликовано: Конференция IEEE по играм, 2020 г. (CoG)
  11. ^ "Статистика решателя - Sokoban Wiki" . Проверено 8 февраля 2013 года .
  12. ^ THE 倉庫 番(на японском). 1987. с. 113. ISBN 4-88239-606-8.

Внешние ссылки [ править ]

  • Официальный сайт Сокобана (на японском языке)
  • Страница Сокобанского университета Альберты
  • Вирккала, Тимо (2011). Решение Сокобана (PDF) (Магистерская диссертация). Университет Хельсинки . Проверено 24 сентября 2014 года .