Sokoban - Sokoban

Sokoban puzzle je vyřešen.

Sokoban (倉庫番, Soko-ban ) je logická videohra žánr, ve které hráč tlačí bedny nebo krabice kolem ve skladu , snaží se je dostat do úložných míst.

Hratelnost

Hra se hraje na desce ze čtverců , kde každý čtverec je podlaha nebo stěna. Některé podlahové čtverce obsahují boxy a některé podlahové čtverce jsou označeny jako skladovací místa.

Hráč je připoután k hrací ploše a může se pohybovat vodorovně nebo svisle na prázdná pole (nikdy skrz zdi nebo krabice). Hráč může přesunout krabici tak, že k ní přijde a zatlačí ji na pole za ní. Krabice nelze tahat a nelze je tlačit na čtverce se stěnami nebo jinými boxy. Počet boxů se rovná počtu úložných míst. Hádanka je vyřešena, když jsou všechny boxy umístěny na úložných místech.

Vybraná vydání

Rok Titul Země Plošina Vydavatel Média
1982 Sokoban (倉庫 番) Japonsko NEC PC-8801 Myšlení králíka Páska
1983 Sokoban [Extra Edition] (倉庫 番 [番外 編] ) Japonsko NEC PC-8801 PC マ ガ ジ ン Zadejte program
1984 Sokoban 2 (倉庫 番 2 ) Japonsko NEC PC-8801 Myšlení králíka Páska
1988 Soko-Ban NÁS IBM-PC a kompatibilní Spektrum HoloByte Disketa
1989 Soko-ban Perfect (倉庫 番 Perfect ) Japonsko NEC PC-9801 Myšlení králíka Disketa
1990 Boxyboy Japonsko, USA Turbografx-16 a PC Engine NEC HuCard
1991 Soko-ban Revenge (倉庫 番 Revenge ) Japonsko NEC PC-9801 Myšlení králíka Disketa
2016 Sokoban Touch (倉庫 番 Touch ) Japonsko, USA Android a Apple iOS Myšlení králíka Digitální distribuce

Rozvoj

Sokoban vytvořil v roce 1981 Hiroyuki Imabayashi. První komerční hra byla vydána v prosinci 1982 Thinking Rabbit , softwarovým domem se sídlem v Takarazuce , Japonsko .

V roce 1988 byl Sokoban v USA vydán nakladatelstvím Spectrum HoloByte pro řady Commodore 64 , IBM-PC a Apple II jako Soko-Ban . Sokoban byl hitem v Japonsku a v době, kdy jej Spectrum HoloByte importoval do USA, se v této zemi prodalo přes 400 000 kusů .

Implementace

Implementace Sokobanu byla napsána pro mnoho počítačových platforem , včetně téměř všech domácích počítačových a osobních počítačových systémů. Různé verze existují také pro herní konzole , mobilní telefony , grafické kalkulačky , digitální fotoaparáty a elektronické organizéry .

Vědecký výzkum

Sokoban lze studovat pomocí teorie výpočetní složitosti . Problém řešení sokobanských hádanek se nejprve ukázal jako NP-tvrdý . Další práce ukázala, že to bylo výrazně obtížnější než problémy NP ; je kompletní s PSPACE . To je zajímavé pro výzkum umělé inteligence (AI), protože řešení Sokobanu lze přirovnat k automatizovanému plánování, které vyžadují někteří autonomní roboti .

Sokoban je obtížný nejen kvůli velkému faktoru větvení , ale také kvůli velké hloubce vyhledávacího stromu . Některé typy úrovní lze dokonce prodloužit na neurčito, přičemž každá iterace vyžaduje exponenciálně rostoucí počet tahů a zatlačení. Kvalifikovaní lidští hráči se spoléhají převážně na heuristiku a jsou obvykle schopni rychle odhodit mnoho marných nebo nadbytečných herních linií rozpoznáváním vzorů a dílčích cílů, čímž drasticky sníží množství vyhledávání.

Některé sokobanské hádanky lze automaticky vyřešit pomocí vyhledávacího algoritmu s jedním agentem , jako je IDA* ; vylepšeno několika technikami, které využívají znalosti specifické pro doménu. Toto je metoda používaná Rolling Stone , o Sokoban řešitel vyvinutý University of Alberta GAMES Group. Festival byl prvním automatickým řešením, které vyřešilo všech 90 úrovní ve standardní testovací sadě benchmarků. Složitější úrovně Sokobanu jsou však mimo dosah i těch nejlepších automatizovaných řešitelů.

Varianty

Několik hádanek lze považovat za varianty původní hry Sokoban v tom smyslu, že všechny využívají ovladatelnou postavu, která tlačí krabice v bludišti .

  • Alternativní obklady : Ve standardní hře jsou bludiště rozložena na čtvercové mřížce . Několik variant aplikuje pravidla Sokobanu na bludiště vyložená na jiných obkladech. Hexoban používá pravidelné šestiúhelníky a Trioban používá rovnostranné trojúhelníky .
  • Více tahačů : Ve variantách Multiban a Interlock může hráč ovládat více postav.
  • Alternativní cíle : Několik variant upravuje požadavky na dokončení úrovně. Například v Block-o-Mania mají krabice různé barvy a cílem je zatlačit na čtverce s odpovídajícími barvami. Sokomind Plus implementuje podobný nápad, přičemž krabice a cílové čtverce jsou jedinečně očíslovány. V Interlock a Sokolor mají boxy také různé barvy, ale cílem je přesunout je tak, aby podobně zbarvená políčka sousedila. V CyberBoxu má každá úroveň určené únikové pole a cílem je dosáhnout tohoto východu. Ve variantě zvané Beanstalk musí být prvky úrovně vysunuty na cílové pole v pevné sekvenci.
  • Další herní prvky : Push Crate , Sokonex , Xsok , Cyberbox a Block-o-Mania přidávají do základní logiky nové prvky. Mezi příklady patří otvory, teleporty, pohyblivé bloky a jednosměrné pasáže. Hra Sokoban ( NEC PC-8801 ) z roku 1982 představovala úrovně s zničitelnými zdmi .
  • Akce postav : V Pukobanu může postava kromě toho, že je tlačí, tahat i boxy.
  • Obrácený režim : Hráč řeší hlavolam dozadu, od konce do výchozí polohy tahem místo tlačení políček. Standardní hlavolamy Sokoban lze hrát v reverzním režimu a řešení v reverzním režimu lze převést na řešení pro hádanky ve standardním režimu. Proto může být hra v reverzním režimu také nápomocná při řešení standardních sokobanských hádanek.

Viz také

externí odkazy

  • Oficiální stránka Sokoban (v japonštině)
  • Stránka University of Alberta Sokoban
  • Virkkala, Timo (2011). Řešení Sokoban (PDF) (diplomová práce). University of Helsinki . Citováno 24. září 2014 .

Reference