Sokoban (яп. 倉庫番 sōkoban, warehouse keeper) — транспортна головоломка[en], в якій гравець штовхає ящики або контейнери, розташовані на складі, намагаючись пересунути їх до місць зберігання. Головоломка зазвичай реалізована як відео гра.

Sokoban
Жанр(и) головоломка і sokoban video gamed
Платформа Linux, NEC PC-8800 seriesd, Windows, Commodore 64, macOS і Family Computer Disk Systemd
Дата випуску 1982
Режим гри одноосібна відеогра
Офіційний сайт(яп.)
CMNS: Sokoban у Вікісховищі
Розв'язання головоломки Sokoban

Sokoban було створено 1981 року Hiroyuki Imabayashi, і видано у грудні 1982-го компанією[en] Thinking Rabbit[en], заснованою у Такарадзука[en], Японія.

Правила ред.

Гра відбувається на дошці з квадратів, де кожен квадрат є підлогою або стіною. Деякі квадрати містять ящики, а деякі — позначені, як їхні місця зберігання.

Гравець обмежений дошкою, і може рухатися горизонтально або вертикально на порожні квадрати (не через стіни або ящики). Також гравець може переміститися на місце ящика, штовхаючи його на вільне місце за ним. Ящик не можна рухати на  інший ящик або стіну. Кількість ящиків дорівнює кількості місць зберігання. Головоломка вирішена, коли всі ящики опинились на місцях зберігання.

Обрані офіційні релізи Sokoban ред.

Sokoban, виданий у Thinking Rabbit ред.

  • Sokoban (1982) (Sony ПК-8801) з 20 рівнями.
  • Sokoban 2 (1984) (Sony ПК-8801) з 50 рівнями.
  • Sokoban Perfect (1989) (Sony ПК-9801) з 306 рівнями.
  • Sokoban Revenge (1991) (Sony ПК-9801) з 306 рівнями.
  • Sokoban Perfect Plus — сторона A (2015) (для Windows) з 200 рівнями.
  • Sokoban Perfect Plus — сторона B (2015) (для Windows) з 200 рівнями.
  • Sokoban Firststep Plus (2016) (для Windows) з 200 рівнями.
  • Sokoban Touch (2016) (Apple iOS і Android) з рівнями, які постійно додаються через оновлення.

Sokoban, виданий компанією Namco ред.

  • Sokoban DELUXE (1990) (аркада) з 92 рівнями.

Sokoban, виданий компанією DreamWorks ред.

Sokoban, виданий Spectrum HoloByte ред.

У 1988 році Sokoban виданий в США Spectrum HoloByte[en], як Soko-Ban для IBM-PC і сумісних комп'ютерів, Комодор 64, і серії Apple II. (Текст на екрані заставки «Copyright 1984 ASCII Corp.» є посиланням на авторські права, а не датою виходу) Огляд у Computer Gaming World[en] відзначив гру як «чиста і проста, дуже грабельна і розумово складна».[2] В огляді у Dragon[en] отримала 4½ з 5 зірок[3].

Реалізації Sokoban ред.

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

Наукове дослідження Sokoban ред.

Sokoban може вивчатись за допомогою теорії обчислювальної складності. Було доведено, що задача вирішення головоломок Sokoban є NP-складною.[4] Подальші роботи показали, що вона є значно складнішою, ніж НП задачі; вона є PSPACE-повною[5]. Це також зацікавило дослідників штучного інтелекту, оскільки рішення Sokoban можна порівнювати з автоматизованим плануванням, яке повинен виконувати робот, який рухає ящики на складі.

Sokoban складний не тільки через його фактор розгалуження (який є порівняним з шахами), але й через величезну глибину дерева пошуку; деякі рівні можуть розширятись невизначеним чином, коли кожна ітерація призводить до експоненційного росту кількості ходів[6]. Досвідчені гравці спираються на евристику, вони, як правило, здатні швидко відкинути безцільні або надлишкові лінії гри, і розпізнають закономірності та локальні цілі, істотно скорочуючи обсяг пошуку.

Деякі головоломки Sokoban можна вирішити автоматично з допомогою алгоритмів пошуку інтелектуального агента, таких як IDA*, посилених кількома методами для використання предметно-специфічних знань[7]. Цей метод використовується в Rolling Stone,[8] вирішувачі Sokoban, розробленому в GAMES Group університету Альберти. Складніші рівні Sokoban, однак, поза досяжності навіть для найкращих автоматичних вирішувачів[9].

Варіанти Sokoban ред.

Деякі пазли можуть розглядатися як варіанти оригінальної гри Sokoban, в тому сенсі, що вони використовують керований персонаж, який штовхає предмети лабіринтом.

Альтернативні розбиття: У стандартній грі, лабіринти викладені на квадратній сітці. Деякі версії застосовують правила Sokoban для лабіринтів, викладених на іншому паркеті. Hexoban використовує правильні шестигранники, а Trioban — рівносторонні трикутники.

Кілька штовхачів: У варіантах Multiban і Interlock гравець може управляти декількома персонажами.

Альтернативні цілі: У деяких варіантах змінено умови завершення рівня. Наприклад, у Block-o-Mania коробки мають різні кольори, і завданням є встановити їх на квадрати відповідних кольорів. Sokomind Plus реалізує подібну ідею, з унікально пронумерованими коробками та цільовими квадратами. У Interlock і Sokolor, коробки також мають різні кольори, але мета полягає у тому, щоб перемістити їх таким чином, щоб коробки з однаковими кольорами були суміжними. У CyberBox, кожен рівень має певне місце виходу, і метою є — дістатися його. У варіанті Beanstalk елементи рівня повинні бути переміщені у певній послідовності.

Додаткові ігрові елементи: Push Crate, Sokonex, Sokonex, Xsok, Cyberbox і Block-o-Mania додають нові елементи до основного пазла. Наприклад, діри, телепорти, рухомі блоки та проходи в одну сторону.

Характер дії: У Pukoban, персонаж, крім штовхання, може тягнути ящики.

Руйнування стін: У ранньому Sokoban (1982) (Sony ПК-8801) гра включала рівні зі стінами, які могли бути зруйнованими. Для того, щоб вирішити ці рівні, гравець повинен був знищити деякі з них, підійшовши до стіни й натиснувши на неї з певної сторони.

Непрохідні цільові клітини: У деяких варіантах порожні цільові клітини були недоступними для проходження, стававши прохідними тільки тоді, коли на них ставав ящик. Це характерно для Sokoban-подібних рівнів у LaserTank виступає і Chip's Challenge.

Зворотний режим: Гравець вирішує головоломки у зворотному напрямку, з кінця до початкового положення, тягаючи коробки замість того, щоб штовхати їх. Стандартні Sokoban головоломки можуть бути відтворені у зворотному режимі, а рішення зворотного режиму можуть бути перетворені в рішення для стандартного. Тому реверсний режим може також бути корисним у вирішенні стандартних Sokoban головоломок.

Реакція ред.

Sokoban став хітом в Японії, і був проданий тиражем понад 400,000 одиниць у цій країні до того часу, коли Spectrum HoloByte імпортував його в США[10].

Див. також ред.

Список літератури ред.

  1. Shove It! Game Sample - Genesis/MD. YouTube. Vysethedetermined2. 20 червня 2010. Архів оригіналу за 11 грудня 2015. Процитовано 4 травня 2021. 
  2. Wagner, Roy (May 1988). Puzzling Encounters. Computer Gaming World (47): 42–43. 
  3. Lesser, Hartley; Lesser, Patricia; Lesser, Kirk (April 1988). The Role of Computers. Dragon (132): 80–85. 
  4. M. Fryers and M.T. Greene (1995). Sokoban. Eureka (54). 
  5. Joseph C. Culberson, Sokoban is PSPACE-complete [Архівовано 15 січня 2018 у Wayback Machine.]. Technical Report TR 97-02, Dept. of Computing Science, University of Alberta, 1997. Also: https://webdocs.cs.ualberta.ca/~joe/TR/TR97-02.ps [Архівовано 22 квітня 2019 у Wayback Machine.]
  6. David Holland and Yaron Shoham, «Theoretical analysis on Picokosmos 17».
  7. Andreas Junghanns, Jonathan Schaeffer (2001) Sokoban: Enhancing general single-agent search methods using domain knowledge, Artificial Intelligence 129(1-2):219-251 (Special issue on heuristic search in artificial intelligence)
  8. Junghanns, Andreas; Schaeffer, Jonathan (1997). Sokoban: A Challenging Single-Agent Search Problem. In IJCAI Workshop on Using Games as an Experimental Testbed for AI Research. University of Alberta. с. 27–36. Архів оригіналу за 26 жовтня 2020. Процитовано 17 квітня 2018. 
  9. Solver Statistics - Sokoban Wiki. Архів оригіналу за 27 квітня 2013. Процитовано 8 лютого 2013. 
  10. Low, Lafe (November 1988). News Line; Made in Japan. inCider (43). 14, 15. 

Посилання ред.