Сокобан

Сокобан ( 倉庫番 , Соко-бан , букв. « Хранитель склада »). ^[1]) — видеоигра-головоломка , в которой игрок передвигает коробки на складе , пытаясь доставить их к местам хранения. Игра была разработана в 1981 году Хироюки Имабаяси и впервые опубликована в декабре 1982 года.

Геймплей [ править ]

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

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

и стратегия Проблемы

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

Избранные официальные релизы [ править ]

Год	Заголовок	Страна	Платформа	Издатель	СМИ
1982	Sokoban (倉庫番Сокобан	Япония	НЭК ПК-8801	Думающий кролик	Кассетная лента
1983	Сокобан [Дополнительное издание ] ^[3]^[4])	Япония	НЭК ПК-8801	Журнал ПК	Введите программу
1984	Сокобан 倉庫番22	Япония	НЭК ПК-8801	Думающий кролик	Кассетная лента
1986	Специальный выпуск Намида но Сокобан ( Специальный выпуск Намида но Сокобан )	Япония	Дисковая система Famicom	ASCII-корпорация	дискета
1988	Соко-Бан	НАС	IBM-ПК	Спектр ГолоБайт	дискета
1989	Соко-бан Перфект ( складской вентилятор Perfect )	Япония	НЭК ПК-9801	Думающий кролик	дискета
1990	Боксибой	Япония, США	Двигатель Turbografx-16/PC	НЭК	HuCard
1990	Засунь это! ...Игра «Склад»	Япония, США	Генезис / Мега Драйв	Веселые игры	ПЗУ-картридж
1991	Соко-бан Месть ( запрет склада Месть )	Япония	НЭК ПК-9801	Думающий кролик	дискета
2016	Sokoban Touch ( складской вентилятор Touch )	Япония, США	Андроид, iOS	Думающий кролик	Цифровая дистрибуция
2018	Сокобан 倉庫番スマートСмарт	Япония	Окна	Думающий кролик	Цифровая дистрибуция
2019	Минна Но Сокобан ( Minna no Sokoban )	Япония	Переключатель, PS4	Дисбаланс	Цифровая дистрибуция
2021	Воры	НАС	Переключатель, PS4	Дисбаланс	Цифровая дистрибуция

Развитие [ править ]

Сокобан был создан в 1981 году Хироюки Имабаяси. ^[5]^[6] Первая коммерческая игра была опубликована в декабре 1982 года компанией Thinking Rabbit , компанией-разработчиком программного обеспечения, расположенной в Такарадзуке , Япония . Сокобан стал хитом в Японии: было продано более 400 000 копий, прежде чем он был выпущен в США. ^[7] В 1988 году Sokoban был опубликован в США компанией Spectrum HoloByte для IBM PC , Commodore 64 и Apple II под названием Soko-Ban . ^[8]

Реализации [ править ]

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

Научные исследования [ править ]

Сокобан изучался с использованием теории вычислительной сложности . Впервые было показано, что вычислительная задача решения головоломок Сокобана является NP-трудной . ^[10]^[11] Дальнейшая работа доказала, что он также является PSPACE-полным . ^[12]^[13]

Поиск решения головоломки Сокобана сложен для компьютеров из-за множества возможных допустимых толчков на каждом ходу ( фактор ветвления ) и, возможно, длинной последовательности ходов, необходимой для достижения решения ( глубина дерева поиска ). ^[14]^[15] Даже небольшие головоломки могут потребовать длительного решения. ^[16]

Игра Сокобан представляет собой сложную испытательную площадку для разработки и оценки методов планирования . ^[17]^[18] Первым задокументированным автоматическим решателем был Rolling Stone , разработанный в Университете Альберты . Его основные принципы заложили основу для многих новых решателей. Он использовал традиционный алгоритм поиска, дополненный знаниями, специфичными для предметной области. ^[19] Festival , использующий свой алгоритм FESS, был первым автоматическим решателем, который решил все 90 головоломок в широко используемом наборе тестов XSokoban. ^[20]^[21] Однако даже лучшие автоматические решатели не могут решить многие из наиболее сложных головоломок, которые люди могут решить, затратив время и усилия. ^[22]^[23]

Варианты [ править ]

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

Альтернативные покрытия : в стандартной игре лабиринты расположены на квадратной сетке . В нескольких вариантах правила Сокобана применяются к лабиринтам, выложенным на других плитках. Hexoban использует правильные шестиугольники , а Trioban использует равносторонние треугольники .
Несколько толкателей : в варианте Multiban головоломка содержит более одного толкателя. В игре Sokoboxes Duo для решения головоломки сотрудничают строго два толкача.
Определенные места хранения : в Sokomind Plus некоторые коробки и целевые квадраты имеют уникальные номера. В Block-o-Mania коробки имеют разные цвета, и цель состоит в том, чтобы переместить их на квадраты соответствующего цвета.
Альтернативные цели игры : несколько вариантов имеют цели, отличные от целей традиционного игрового процесса Сокобан. Например, в «Интерлоке» и «Соколоре » коробки имеют разные цвета, но цель состоит в том, чтобы переместить их так, чтобы коробки одинакового цвета оказались рядом. В CyberBox на каждом уровне есть определенная клетка выхода, и цель состоит в том, чтобы добраться до этого выхода, толкая коробки, возможно, более одной одновременно. В варианте под названием Beanstalk цель состоит в том, чтобы переместить элементы уровня на целевой квадрат в фиксированной последовательности.
Дополнительные игровые элементы : Push Crate , Sokonex , Xsok , Cyberbox и Block-o-Mania — все они добавляют новые элементы к основной головоломке. Примеры включают дыры, телепорты, движущиеся блоки и односторонние проходы.
Действия персонажа : В Пукобане персонаж может не только толкать коробки, но и тянуть их.
Обратный режим : в этом варианте игрок решает стандартную головоломку задом наперед, начиная со всех ящиков на клетках ворот. Затем игрок тянет ящики, чтобы достичь исходной позиции. Решения, полученные в обратном режиме, можно напрямую применить для решения стандартной головоломки, изменив порядок ходов на обратный. Это делает реверсивный режим полезным инструментом для игроков, позволяющим разрабатывать стратегии решения головоломок в стандартной игре. ^[24]

См. также [ править ]

Внешние ссылки [ править ]

Официальный сайт Сокобана (на японском языке)
Страница Сокобанского университета Альберты

Ссылки [ править ]

^ Ёсио Мурасе; Хитоши Мацубара; Юдзуру Хирага (1996). Норман Фу; Рэнди Гебель (ред.). Автоматическое решение задач Сокобана . Springer Science & Business Media. п. 592. ИСБН 978-3-540-61532-3 .
^ Жан-Ноэль Демаре; Франсуа Ван Лишут; Паскаль Грибомонт (2008). Иерархическое планирование и обучение для автоматического решения задач Сокобана (PDF) . стр. 1, 2, 5.
^ «На этот раз мы попросили THINKING RABBIT, разработавшего эту игру, построить 10 складов в дополнение к коммерчески доступным продуктам», журнал PC Magazine (на японском языке, стр. 52–56).
^ «Название «Sokoban» PC Magazine Extra Edition (эту программу можно использовать с PC-8801/9801)» PC Magazine (на японском языке, август 1983 г., стр. 52–56).
^ «Думающий кролик — интервью с разработчиком, 1983 год» .
^ «Мой разговор с господином Хироюки Имабаяси» .
^ Лафе Лоу (ноябрь 1988 г.). «Лента новостей; Сделано в Японии». inСидр . п. 14.
^ Остин Барр; Кэлвин Чанг; Аарон Уильямс (2021). Пазлы Block Dude NP-сложны (и коврики действительно связывают сокращения) (PDF) . КККГ (2021). п. 1.
^ «Руководство пользователя CHDK 1.5» . ЧДК Вики . Проверено 13 июля 2023 г.
^ Майкл Фрайерс; Майкл Грин (1995). «Сокобан» (PDF) . Эврика (54): 25–32.
^ Дорит Дор ; Ури Цвик (1999). «СОКОБАН и другие проблемы планирования движения» . Вычислительная геометрия . 13 (4): 215–228. дои : 10.1016/S0925-7721(99)00017-6 .
^ Джозеф К. Калберсон (1997). «Сокобан является PSPACE-полным» (PDF) . Технический отчет TR 97-02, факультет вычислительной техники, Университет Альберты .
^ Роберт Обри Хирн (2006). Игры, головоломки и вычисления (PDF) (кандидатская диссертация). Массачусетский технологический институт. стр. 98–100.
^ Андреас Юнгханнс; Джонатан Шеффер (2001). Сокобан: Улучшение поиска за счет сокращения релевантности (PDF) . п. 5. дои : 10.1016/S0304-3975(00)00080-3 .
^ Ярон Шохам (2020). «Проект ФЭСС» (PDF) . п. 3.
^ Дэвид Холланд; Ярон Шохам. «Теоретический анализ Пикокосмоса 17» . Архивировано из оригинала 7 июня 2016 г.
^ Андреас Юнгханнс; Джонатан Шеффер (1998). Сокобан: Оценка стандартных методов поиска с одним агентом при наличии тупиковой ситуации (PDF) . п. 4.
^ Тимо Вирккала (2011). Решение Сокобана (PDF) (магистерская диссертация). Университет Хельсинки. п. 1.
^ Андреас Юнгханнс; Джонатан Шеффер (2001). «Сокобан: Улучшение общих методов поиска с одним агентом с использованием знаний предметной области» . Искусственный интеллект . 129 (1–2): 219–251. дои : 10.1016/S0004-3702(01)00109-6 .
^ Ярон Шохам; Джонатан Шеффер (2020). Алгоритм FESS: функциональный подход к одноагентному поиску (PDF) . Конференция IEEE по играм 2020 года (CoG). Осака, Япония: IEEE. дои : 10.1109/CoG47356.2020.9231929 .
^ Ярон Шохам (2020). «Презентация ФЭСС на конференции CoG (17,5 минут)» (видео) . archive.org .
^ «Статистика ботов Let's Logic» (PDF) . Проверено 19 апреля 2024 г.
^ «Статистика решателя Sokoban — большой набор тестов» . Проверено 14 апреля 2024 г.
^ Фрэнк Такс (2008). «Сокобан: Обратное решение» (PDF) .

[1] Ёсио Мурасе; Хитоши Мацубара; Юдзуру Хирага (1996). Норман Фу; Рэнди Гебель (ред.). Автоматическое решение задач Сокобана . Springer Science & Business Media. п. 592. ИСБН 978-3-540-61532-3 .

[2] Жан-Ноэль Демаре; Франсуа Ван Лишут; Паскаль Грибомонт (2008). Иерархическое планирование и обучение для автоматического решения задач Сокобана (PDF) . стр. 1, 2, 5.

[3] «На этот раз мы попросили THINKING RABBIT, разработавшего эту игру, построить 10 складов в дополнение к коммерчески доступным продуктам», журнал PC Magazine (на японском языке, стр. 52–56).

[4] «Название «Sokoban» PC Magazine Extra Edition (эту программу можно использовать с PC-8801/9801)» PC Magazine (на японском языке, август 1983 г., стр. 52–56).

[5] «Думающий кролик — интервью с разработчиком, 1983 год» .

[6] «Мой разговор с господином Хироюки Имабаяси» .

[7] Лафе Лоу (ноябрь 1988 г.). «Лента новостей; Сделано в Японии». inСидр . п. 14.

[8] Остин Барр; Кэлвин Чанг; Аарон Уильямс (2021). Пазлы Block Dude NP-сложны (и коврики действительно связывают сокращения) (PDF) . КККГ (2021). п. 1.

[9] «Руководство пользователя CHDK 1.5» . ЧДК Вики . Проверено 13 июля 2023 г.

[10] Майкл Фрайерс; Майкл Грин (1995). «Сокобан» (PDF) . Эврика (54): 25–32.

[11] Дорит Дор ; Ури Цвик (1999). «СОКОБАН и другие проблемы планирования движения» . Вычислительная геометрия . 13 (4): 215–228. дои : 10.1016/S0925-7721(99)00017-6 .

[12] Джозеф К. Калберсон (1997). «Сокобан является PSPACE-полным» (PDF) . Технический отчет TR 97-02, факультет вычислительной техники, Университет Альберты .

[13] Роберт Обри Хирн (2006). Игры, головоломки и вычисления (PDF) (кандидатская диссертация). Массачусетский технологический институт. стр. 98–100.

[14] Андреас Юнгханнс; Джонатан Шеффер (2001). Сокобан: Улучшение поиска за счет сокращения релевантности (PDF) . п. 5. дои : 10.1016/S0304-3975(00)00080-3 .

[15] Ярон Шохам (2020). «Проект ФЭСС» (PDF) . п. 3.

[16] Дэвид Холланд; Ярон Шохам. «Теоретический анализ Пикокосмоса 17» . Архивировано из оригинала 7 июня 2016 г.

[17] Андреас Юнгханнс; Джонатан Шеффер (1998). Сокобан: Оценка стандартных методов поиска с одним агентом при наличии тупиковой ситуации (PDF) . п. 4.

[18] Тимо Вирккала (2011). Решение Сокобана (PDF) (магистерская диссертация). Университет Хельсинки. п. 1.

[19] Андреас Юнгханнс; Джонатан Шеффер (2001). «Сокобан: Улучшение общих методов поиска с одним агентом с использованием знаний предметной области» . Искусственный интеллект . 129 (1–2): 219–251. дои : 10.1016/S0004-3702(01)00109-6 .

[20] Ярон Шохам; Джонатан Шеффер (2020). Алгоритм FESS: функциональный подход к одноагентному поиску (PDF) . Конференция IEEE по играм 2020 года (CoG). Осака, Япония: IEEE. дои : 10.1109/CoG47356.2020.9231929 .

[21] Ярон Шохам (2020). «Презентация ФЭСС на конференции CoG (17,5 минут)» (видео) . archive.org .

[22] «Статистика ботов Let's Logic» (PDF) . Проверено 19 апреля 2024 г.

[23] «Статистика решателя Sokoban — большой набор тестов» . Проверено 14 апреля 2024 г.

[24] Фрэнк Такс (2008). «Сокобан: Обратное решение» (PDF) .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]