Sokoban

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Sokoban
Дата випуску 1982
Жанр(и) головоломка
Платформа Linux, ZX Spectrum, Microsoft Windows, Commodore 64 і macOS
Режим гри одиночна гра
Сайт sokoban.jp
Sokoban у Вікісховищі?
Розв'язання головоломки Sokoban.

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

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]

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

  • Logic puzzle
  • Sliding puzzle

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

  1. https://www.youtube.com/watch?v=uAVPSjGsdjU
  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 February 2013. 
  10. Low, Lafe (November 1988). News Line; Made in Japan. inCider (43). 14, 15. 

Посилання[ред. | ред. код]