Сокобан - Sokoban

A Сокобан жұмбақ шешілуде.

Сокобан (倉庫 番, Sko-ban) Бұл басқатырғыштар видео ойыны ойыншы а-да қораптарды немесе қораптарды итеретін жанр қойма, оларды сақтау орындарына жеткізуге тырысу.

Сокобан 1981 жылы Хироюки Имабаяши жасаған. Бірінші коммерциялық ойын 1982 жылдың желтоқсанында жарық көрді Қоян, а бағдарламалық жасақтама үйі негізделген Такаразука, Жапония.

Геймплей

Ойын а тақта туралы квадраттар, мұнда әр шаршы еден немесе қабырға. Кейбір еден алаңдарында қораптар, ал кейбір алаңдарда сақтау орны ретінде белгіленген.

Ойыншы тақтада тұрады және көлденең немесе тігінен бос квадраттарға қозғалуы мүмкін (ешқашан қабырғалар мен қораптар арқылы жүрмейді). Ойыншы қорапты оның жанына қарай жылжып, оны шаршы алаңға итере алады. Қораптарды тартуға болмайды, оларды қабырғалары немесе басқа қораптары бар квадраттарға итеру мүмкін емес. Қораптардың саны сақтау орындарының санына тең. Жұмбақ барлық қораптар қоймаға қойылған кезде шешіледі.

Таңдалған шығарылымдар

ЖылТақырыпЕлПлатформаБаспагерБАҚ
1982Сокобан (倉庫 番)ЖапонияNEC PC-8801ҚоянТаспа
1983Сокобан [Қосымша шығарылым] (倉庫 番 [番外 編][1][2])ЖапонияNEC PC-8801ДК マ ガ ジ ンБастапқы код
1984Сокобан 2 (. 番 2)ЖапонияNEC PC-8801ҚоянТаспа
1988Соко-БанАҚШIBM-PC және үйлесімдіHoloByte SpectrumИілгіш
1989Soko-ban Perfect (Fect 番 Керемет)ЖапонияNEC PC-9801ҚоянИілгіш
1991Soko-ban Revenge (倉庫 番 Кек)ЖапонияNEC PC-9801ҚоянИілгіш
2016Sokoban Touch (. 番 түртіңіз)Жапония, АҚШAndroid және Apple iOSҚоянСандық тарату

Даму

1988 ж Сокобан АҚШ-та жарияланған HoloByte Spectrum үшін Commodore 64, IBM-PC және Apple II сериясы сияқты Соко-Бан. Сокобан Жапонияда хит болды және сол уақытта бұл елде 400 000 данадан астам сатылды HoloByte Spectrum оны Америка Құрама Штаттарына импорттады.[3]

Іске асыру

Жүзеге асыру Сокобан көптеген адамдар үшін жазылған компьютерлік платформалар соның ішінде барлығын қосқанда үйдегі компьютер және Дербес компьютер жүйелер. Әр түрлі нұсқалары да бар бейне ойын консолі, Ұялы телефондар, графикалық калькуляторлар, сандық камералар және электрондық ұйымдастырушылар.

Ғылыми зерттеулер

Сокобан теориясын қолдану арқылы зерттеуге болады есептеу күрделілігі. Шешу проблемасы Сокобан жұмбақтар бірінші болып дәлелденді NP-hard.[4][5] Әрі қарайғы жұмыс бұл қарағанда қиынырақ болғандығын көрсетті NP мәселелер; Бұл PSPACE аяқталды.[6] Бұл қызығушылық тудырады жасанды интеллект (AI) зерттеу, өйткені шешу Сокобан мен салыстыруға болады автоматтандырылған жоспарлау кейбіреулер талап етеді автономды роботтар.

Сокобан тек үлкен болғандықтан ғана қиын емес тармақталу факторы, сонымен қатар оның үлкендігіне байланысты іздеу ағашы тереңдік. Кейбір деңгей түрлерін әрқайсысымен бірге шексіз ұзартуға болады қайталану талап ететін экспоненталық өсуде жүрістер мен итерулер саны.[7] Шебер ойыншылар көбіне сенім артады эвристика және әдетте көптеген пайдасыз немесе артық ойын сызықтарын заңдылықтар мен бағынышты мақсаттарды тану арқылы тез алып тастауға қабілетті, осылайша іздеу көлемін күрт азайтады.

Кейбіреулер Сокобан басқатырғыштар көмегімен автоматты түрде шешуге болады бір агентті іздеу сияқты алгоритм IDA *; доменге арналған білімді қолданатын бірнеше әдістермен жетілдірілген.[8] Бұл қолданылатын әдіс Домалақ тас,[9] а Сокобан шешуші Альберта университеті GAMES тобы. Фестиваль[10] стандартты эталондық тест жиынтығында барлық 90 деңгейлерді шешкен алғашқы автоматты шешуші болды. Алайда, неғұрлым күрделі Сокобан деңгейлер тіпті ең жақсы автоматтандырылған еріткіштерге қол жетімді емес.[11]

Нұсқалар

Бірнеше жұмбақты түпнұсқаның нұсқасы деп санауға болады Сокобан ойын, олардың барлығы басқарылатын таңбаны а айналасындағы итергіштерді қолданатын мағынада лабиринт.

  • Балама плиткалар: Стандартты ойында лабиринттер а шаршы тор. Ережелері қолданылады Сокобан басқа тақтайшаларға салынған лабиринттерге. Гексобан қолданады тұрақты алтыбұрыштар, және Триобан қолданады тең бүйірлі үшбұрыштар.
  • Бірнеше итергіштер: Нұсқаларында Multiban және Блоктау, ойнатқыш бірнеше таңбаны басқара алады.
  • Альтернативті мақсаттар: Бірнеше нұсқалар деңгейді аяқтауға қойылатын талаптарды реттейді. Мысалы, in Блок-о-Мания қораптар әртүрлі түстерге ие, ал оларды сәйкес түстермен төртбұрыштарға итеру. Sokomind Plus ұқсас идеяны жүзеге асырады, қораптар мен мақсатты квадраттар ерекше нөмірленген. Жылы Блоктау және Соколор, қораптардың түсі де әр түрлі, бірақ олардың мақсаты оларды ұқсас түсті қораптар іргелес болатындай етіп жылжыту. Жылы CyberBox, әр деңгейдің белгіленген квадраты бар және мақсаты осы шығуға жету. Деп аталатын нұсқада Бұршақ, деңгей элементтерін мақсатты квадратқа бекітілген реттілікпен итеру керек.
  • Қосымша ойын элементтері: Итергіш жәшік, Соконекс, Xsok, Кибербокс және Блок-о-Мания барлығы негізгі басқатырғышқа жаңа элементтер қосады. Мысалдарға саңылаулар, телепорттар, қозғалмалы блоктар және бір бағыттағы өтулер жатады. 1982 ж Сокобан (NEC PC-8801 ) ойын деңгейлері бұзылатын қабырғалар.[12]
  • Кейіпкерлердің әрекеттері: Жылы Пукобан, кейіпкер оларды итеруге қосымша қораптарды тарта алады.
  • Кері режим: Ойыншы жұмбақты артқа қарай, итеру қораптарының орнына тарту арқылы бастапқы күйіне дейін шешеді. Стандартты Сокобан жұмбақтарды кері режимде ойнатуға болады, ал кері режимдегі шешімдерді стандартты режимдегі басқатырғыштарға арналған шешімдерге айналдыруға болады. Сондықтан, кері режим геймплей стандартты шешуде де маңызды болуы мүмкін Сокобан басқатырғыштар.

Сондай-ақ қараңыз

Әдебиеттер тізімі

  1. ^ «今 回 は こ の ゲ ー ム 開 開 発 し た IN IN R お 願 い し て に お と は 別 10 の 倉庫 を つ 別 に 10 の 倉庫 を つ く っ て も ら い ま く who time ら ら い い ま ware く time time This time time time time time time time time time time time time time time time time time time time time time time time time time time time time time time time time time time time time time time time time time time time time time time time time time time time time time time time time time time time time коммерциялық өнімдерден бөлек]. ДК マ ガ ジ ン (жапон тілінде). Тамыз 1983. 52-56 бб.
  2. ^ «題 し て『 倉庫 番 番 PC マ ガ ジ ン 番外 編 (こ の プ ロ グ ラ ム は, PC-8801/9801 で 使 え ま す) »[« Sokoban »PC Magazine Extra Edition (бұл бағдарламаны PC-8801-мен қолдануға болады) / 9) ДК マ ガ ジ ン (жапон тілінде). Тамыз 1983. 52-56 бб.
  3. ^ Төмен, Лафе (қараша 1988). «News Line; Жапонияда жасалған». inCider (43). 14, 15.
  4. ^ М. Фрайерс; М. Т. Грин (1995). «Сокобан». Эврика (54).
  5. ^ Дор, Дорит; Цвик, Ури (1999). «SOKOBAN және қозғалысты жоспарлаудың басқа мәселелері». Есептеу геометриясы. 13 (4): 215–228. дои:10.1016 / S0925-7721 (99) 00017-6. ISSN  0925-7721.
  6. ^ Джозеф С.Колберсон, Сокобан PSPACE-мен аяқталған (PS ). Техникалық есеп TR 97-02, Есептеу ғылымдары бөлімі, Альберта университеті, 1997 ж.
  7. ^ Дэвид Холланд пен Ярон Шохам, «Пикокосмос 17 бойынша теориялық талдау».
  8. ^ Андреас Джунганнс, Джонатан Шеффер (2001) Сокобан: домендік білімді қолдана отырып, бір агенттік жалпы іздеу әдістерін кеңейту, Жасанды интеллект 129(1-2): 219–251 (Жасанды интеллекттегі эвристикалық іздеу туралы арнайы мәселе).
  9. ^ Джунганндар, Андреас; Шеффер, Джонатан (1997). «Сокобан: бір агенттік іздеудің күрделі проблемасы» (PDF). IJCAI-да ойындарды AI зерттеуі үшін эксперименттік сынақ алаңы ретінде пайдалану бойынша семинар. Альберта университеті. 27-36 бет.
  10. ^ Ярон Шохам, Джонатан Шефер (2020) FESS алгоритмі: бір агенттік іздеуге арналған ерекшелікке негізделген тәсіл. Жарияланған: IEEE ойындары бойынша 2020 конференциясы (CoG)
  11. ^ «Шешуші статистикасы - Sokoban Wiki». Алынған 8 ақпан 2013.
  12. ^ THE 倉庫 番 (жапон тілінде). 1987. б. 113. ISBN  4-88239-606-8.

Сыртқы сілтемелер