Sokoban (倉庫番, Sōko-ban , букв. « складской смотритель » [1] ) — видеоигра-головоломка , в которой игрок толкает коробки по складу , пытаясь доставить их в места хранения. Игра была разработана в 1981 году Хироюки Имабаяси и впервые опубликована в декабре 1982 года.
Геймплей
Склад изображен в виде сетки квадратов , каждый из которых представляет собой либо секцию пола, либо секцию стены. Некоторые квадраты пола содержат коробки, а некоторые отмечены как места хранения. Игрок, часто представленный как рабочий персонаж, может перемещаться на одну клетку за раз по горизонтали или вертикали на пустые квадраты пола, но не может проходить сквозь стены или коробки.
Чтобы переместить ящик, игрок подходит к нему и толкает его на пустой квадрат прямо за ящиком. Ящики нельзя толкать на квадраты со стенами или другими ящиками, и их нельзя тянуть. Количество ящиков соответствует количеству мест хранения. Головоломка решена, когда все ящики занимают места хранения.
Проблемы и стратегия
Прохождение игры требует тщательного планирования и точного маневрирования. Одна ошибка, например, толкание ящика в угол или преграждение пути другим, может сделать головоломку неразрешимой, заставив игрока отступить или начать заново. Предвидение последствий каждого толчка и рассмотрение общей компоновки головоломки имеют решающее значение для избежания тупиков и успешного завершения головоломки. [2]
Разработка
Sokoban был создан в 1981 году Хироюки Имабаяси. [3] [4] Первая коммерческая игра была опубликована в декабре 1982 года его компанией Thinking Rabbit , базирующейся в Такарадзуке , Япония . Sokoban стал хитом в Японии, было продано более 400 000 копий, прежде чем он был выпущен в Соединенных Штатах. [5] В 1988 году Spectrum HoloByte опубликовала Sokoban в США для IBM PC , Commodore 64 и Apple II под названием Soko-Ban . [6] В 2001 году японская компания-разработчик программного обеспечения Falcon приобрела товарные знаки Sokoban и Thinking Rabbit. С тех пор Falcon продолжает разрабатывать и лицензировать официальные игры Sokoban.
Сокобан изучался с использованием теории вычислительной сложности . Впервые было показано, что вычислительная задача решения головоломок Сокобан является NP-трудной . [9] [10] Дальнейшие исследования доказали, что она также является PSPACE-полной . [11] [12]
Решение нетривиальных головоломок Сокобана является сложной задачей для компьютеров из-за высокого коэффициента ветвления (множество допустимых нажатий на каждом ходу) и большой глубины поиска (много нажатий, необходимых для достижения решения). [13] [14] Даже небольшие головоломки могут потребовать длительных решений. [15]
Игра Sokoban предоставляет сложную испытательную площадку для разработки и оценки методов планирования . [16] Первым задокументированным автоматизированным решателем был Rolling Stone , [17] разработанный в Университете Альберты . Его основные принципы заложили основу для многих новых решателей. Он использовал обычный алгоритм поиска, улучшенный знаниями, специфичными для предметной области. [18] Festival , использующий свой алгоритм FESS, был первым автоматическим решателем, который завершил все 90 головоломок в широко используемом тестовом наборе XSokoban. [19] [20] Однако даже лучшие автоматизированные решатели не могут решить многие из более сложных головоломок, которые люди могут решить со временем и усилиями. [21] [22]
Варианты
Некоторые головоломки можно считать вариантами оригинальной игры Sokoban в том смысле, что все они используют управляемого персонажа, толкающего ящики по лабиринту .
Несколько толкателей : В варианте Multiban головоломка содержит более одного толкателя. В игре Sokoboxes Duo строго два толкателя сотрудничают для решения головоломки.
Обозначенные места хранения : В Sokomind Plus некоторые коробки и целевые квадраты имеют уникальные номера. В Block-o-Mania коробки имеют разные цвета, и цель состоит в том, чтобы задвинуть их на квадраты с соответствующими цветами.
Альтернативные цели игры : Несколько вариантов имеют цели, отличные от традиционного игрового процесса Sokoban. Например, в Interlock и Sokolor ящики имеют разные цвета, но цель состоит в том, чтобы переместить их так, чтобы ящики одинакового цвета были рядом. В CyberBox на каждом уровне есть обозначенный квадрат выхода, и цель состоит в том, чтобы достичь этого выхода, толкая ящики, потенциально более одного одновременно. В варианте под названием Beanstalk цель состоит в том, чтобы толкать элементы уровня на целевой квадрат в фиксированной последовательности.
Дополнительные игровые элементы : Push Crate , Sokonex , Xsok , Cyberbox и Block-o-Mania добавляют новые элементы к базовой головоломке. Примерами служат отверстия, телепорты, движущиеся блоки и односторонние проходы.
Действия персонажа : В Pukoban персонаж может не только толкать ящики, но и тянуть их.
Обратный режим : В этом варианте игрок решает стандартную головоломку в обратном порядке, начиная со всех ящиков на целевых квадратах. Затем игрок тянет ящики, чтобы достичь исходного положения. Решения, полученные в обратном режиме, могут быть напрямую применены для решения стандартной головоломки, изменив порядок ходов. Это делает обратный режим полезным инструментом для игроков, позволяя им разрабатывать стратегии для решения головоломок в стандартной игре. [23]
Избранные официальные релизы
В этой таблице перечислены некоторые важные официальные релизы Sokoban , которые знаменуют собой вехи, такие как выход на новые платформы или достижение широкой популярности. Они организованы по дате выпуска.
^ Ёсио Мурасе; Хитоши Мацубара; Юзуру Хирага (1996). Норман Фу; Рэнди Гебель (ред.). Автоматическое решение задач Сокобана. Springer Science & Business Media. п. 592. ИСБН 978-3-540-61532-3.
^ Жан-Ноэль Демаре; Франсуа Ван Лишут; Паскаль Грибомонт (2008). Иерархическое планирование и обучение для автоматического решения задач Сокобана (PDF) . стр. 1, 2.
^ «Думающий кролик — интервью с разработчиком 1983 года».
^ «Мой разговор с господином Хироюки Имабаяси».
↑ Lafe Low (ноябрь 1988 г.). «Новостная линия; Сделано в Японии». inCider . стр. 14.
^ Майкл Фрайерс; Майкл Грин (1995). «Сокобан» (PDF) . Эврика (54): 25–32.
^ Дорит Дор ; Ури Цвик (1999). "SOKOBAN и другие проблемы планирования движения". Computational Geometry . 13 (4): 215–228. doi : 10.1016/S0925-7721(99)00017-6 .
^ Джозеф К. Калберсон (1997). "Sokoban is PSPACE-complete" (PDF) . Технический отчет TR 97-02, Кафедра вычислительной техники, Университет Альберты .
^ Роберт Обри Хирн (2006). Игры, головоломки и вычисления (PDF) (диссертация). Массачусетский технологический институт. С. 98–100.
^ Андреас Юнгханс; Джонатан Шеффер (2001). "Sokoban: улучшение поиска с помощью сокращения релевантности" (PDF) . Теоретическая информатика . 252 (1–2): 5. doi : 10.1016/S0304-3975(00)00080-3 .
^ Ярон Шохам (2020). «Проект ФЭСС» (PDF) . п. 3.
^ Дэвид Холланд; Ярон Шохам. "Теоретический анализ Пикокосмоса 17". Архивировано из оригинала 2016-06-07.
^ Тимо Вирккала (2011). Решение Сокобана (PDF) (магистерская диссертация). Университет Хельсинки. п. 1.
^ Андреас Юнгханс (1999). Раздвигая границы: новые разработки в одноагентном поиске (диссертация). Университет Альберты. doi : 10.7939/R3W95103S .
^ Андреас Юнгханс; Джонатан Шеффер (2001). «Sokoban: Улучшение общих методов поиска с одним агентом с использованием знаний предметной области». Искусственный интеллект . 129 (1–2): 219–251. doi : 10.1016/S0004-3702(01)00109-6 .
^ Ярон Шохам; Джонатан Шеффер (2020). Алгоритм FESS: подход к одноагентному поиску на основе признаков (PDF) . Конференция IEEE по играм (CoG) 2020 года. Осака, Япония: IEEE. doi :10.1109/CoG47356.2020.9231929.
^ Ярон Шохам (2020). "Презентация FESS на конференции CoG (17,5 минут)" (видео) . archive.org .
^ "Let's Logic Bots Statistics" (PDF) . Получено 6 октября 2024 г.
^ "Статистика решателя Sokoban - Большой тестовый набор" . Получено 14 апреля 2024 г.
^ "今回はこのゲームを開発した ДУМАЮЩИЙ КРОЛИК さんにお願いして,市販品とは別に10の倉庫をつくってもらいましたので» [На этот раз мы попросили THINKING RABBIT, разработавшего эту игру, построить 10 складов отдельно от коммерческих продуктов]. ПКマガジン(на японском языке). Август 1983. стр. 52–56.
^ "題して『倉庫番』PCマガジン番外編 (このプログラムは, PC-8801/9801 で使えます)" [Дополнительное издание журнала PC Magazine под названием "Sokoban" (эту программу можно использовать с ПК-8801/9801)]. ПКマガジン(на японском языке). Август 1983. стр. 52–56.
