Сокобан - Sokoban

А Сокобан головоломка решается.

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

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

Геймплей

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

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

Избранные выпуски

ГодзаглавиеСтранаПлатформаИздательСредства массовой информации
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Думающий кроликДискета
1991Соко-бан Месть (倉庫 番 месть)ЯпонияNEC PC-9801Думающий кроликДискета
2016Сокобан Тач (倉庫 番 Коснитесь)Япония, СШАAndroid и Apple iOSДумающий кроликЦифровое распространение

Развитие

В 1988 г. Сокобан был опубликован в США Спектр HoloByte для Коммодор 64, IBM-PC и Apple II серии так как Соко-Бан. Сокобан был хитом в Японии, и к тому времени было продано более 400000 единиц в этой стране Спектр HoloByte импортировал его в США.[3]

Реализации

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

Научное исследование

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

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

Немного Сокобан головоломки можно решать автоматически, используя поиск по одному агенту алгоритм, такой как ИДА*; дополнены несколькими методами, использующими знания предметной области.[8] Это метод, используемый Катящийся камень,[9] а Сокобан решатель, разработанный Университет Альберты GAMES Group. Фестиваль[10] был первым автоматическим решателем, решившим все 90 уровней стандартного набора тестов. Однако более сложный Сокобан уровни недоступны даже для лучших автоматических решателей.[11]

Варианты

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

  • Альтернативные мозаики: В стандартной игре лабиринты расположены на квадратная сетка. Несколько вариантов применяют правила Сокобан в лабиринты, выложенные на других плитах. Гексобан использует правильные шестиугольники, и Триобан использует равносторонние треугольники.
  • Несколько толкателей: В вариантах Мультибан и Блокировка, игрок может управлять несколькими персонажами.
  • Альтернативные цели: Несколько вариантов регулируют требования для прохождения уровня. Например, в Блок-о-мания коробки имеют разный цвет, и цель состоит в том, чтобы поместить их на квадраты соответствующего цвета. Sokomind Plus реализует аналогичную идею с однозначно пронумерованными прямоугольниками и целевыми квадратами. В Блокировка и Соколор, коробки также имеют разные цвета, но цель состоит в том, чтобы переместить их так, чтобы коробки одинакового цвета находились рядом. В CyberBox, на каждом уровне есть обозначенный квадрат выхода, и цель состоит в том, чтобы добраться до этого выхода. В варианте под названием Бобовый стебель, элементы уровня должны быть помещены на целевой квадрат в фиксированной последовательности.
  • Дополнительные игровые элементы: Толкать ящик, Соконекс, Xsok, Cyberbox и Блок-о-мания все добавляют новые элементы к основной головоломке. Примеры включают дыры, телепорты, движущиеся блоки и односторонние переходы. 1982 год Сокобан (NEC PC-8801 ) игровые уровни с разрушаемые стены.[12]
  • Действия персонажа: В Пукобан, персонаж может не только толкать коробки, но и тянуть их.
  • Обратный режим: Игрок решает головоломку задом наперед, от конца к исходному положению, потянув, а не толкая коробки. Стандарт Сокобан в головоломки можно играть в обратном режиме, а решения в обратном режиме можно преобразовать в решения для головоломок в стандартном режиме. Следовательно, обратный режим геймплей также может помочь в решении стандартных Сокобан загадки.

Смотрите также

использованная литература

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

внешние ссылки