Sokoban

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

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

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

Правила

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

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

Обрані офіційні релізи 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, як Soko-Ban для IBM-PC і сумісних комп'ютерів, Комодор 64, і серії Apple II. (Текст на екрані заставки «Copyright 1984 ASCII Corp.» є посиланням на авторські права, а не датою виходу) Огляд у Computer Gaming World відзначив гру як «чиста і проста, дуже іграбельна і розумово складна».[2] В огляді у Dragon отримала 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]

Див. також
  • Logic puzzle
  • Sliding puzzle

Список літератури
  1. Shove It! Game Sample - Genesis/MD. YouTube. Vysethedetermined2. 20 червня 2010. Процитовано 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. Technical Report TR 97-02, Dept. of Computing Science, University of Alberta, 1997. Also: https://webdocs.cs.ualberta.ca/~joe/TR/TR97-02.ps
  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.
  9. Solver Statistics - Sokoban Wiki. Процитовано 8 лютого 2013.
  10. Low, Lafe (November 1988). News Line; Made in Japan. inCider (43). 14, 15.

Посилання
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.