Szókoban

A szókoban (倉庫番, nyugaton sōkoban, „raktáros”) egy olyan fejtörő, ahol a játékosnak egy felülnézetes labirintusban kell dobozokat tologatnia a helyükre. Egyszerre csak egy dobozt lehet mozgatni, és csak tolni lehet, húzni nem. Mivel nagyon nehéz lenne a fizikai megjelenítése, ezért legtöbbször számítógépes játék formájában lehet vele találkozni. A szókobant 1980-ban alkotta meg Imabajasi Hirojuki, és 1982-ben adta ki a Thinking Rabbit („gondolkodó nyúl”) szoftvercég Japánban, Takadzurában. A Thinking Rabbit még három folytatást adott ki: a Boxxle-t, a Sokoban Perfectet és a Sokoban Revenge-et.

Szókobant nagyon sokféle platformra készítettek, beleértve szinte az összes otthoni és személyi számítógépet. Megjelent Game Boyokon, játékkonzolokon, mobilkészülékeken, kalkulátorokon és egy Canon márkájú digitális kamerán is. Sok más játék is alapul vette a szókobant, mint például a Chip’s Challenge vagy a Rock and Diamonds is. A Nethack című népszerű számítógépes játék is tartalmaz egy pályát, ahol egy szókobanjátékot szimulálnak.

Súgó

A csiga dobozokat tologat egy labirintusban, és megpróbálja őket meghatározott helyekre eljuttatni. Nyomja meg a szomszédos mezőt a doboz tologatásához. Nyomja meg a "#"-et a visszavonáshoz, a "2"-est a felfele mozgáshoz, a "8"-ast a lefele mozgáshoz, a "4"-est a balra mozgáshoz, a "6"-ost a jobbra mozgáshoz,az "1"-est az előző szinthez, és a "3"-ast a következő szinthez.

Szókobanváltozatok

Nagyon sok játék tekinthető szókobanklónnak, ha azt vesszük alapul, hogy a szókobanban egy irányítható karakter ládákat tologat egy labirintusban. Az alábbi szempontok mentén születtek új szókobanváltozatok:

• Alternatív játéktér: A játék alapverziója négyzetekből álló játékteret („csempézést”) használ. Számos későbbi változat viszont azonos szabályok mellett a labirintust más idomokkal fedi le. A Hexoban hatszögeket, a Trioban egyenlő oldalú háromszögeket használ.
• Több karakter: Az Interlock és a Multiban verziókban a játékos több karaktert irányíthat.
• Alternatív célok: Sok klónban van nehezítés: például a Block-o-Maniában a dobozok különböző színűek, és az a cél, hogy minden dobozt ugyanolyan színű helyére toljunk. A Sokomind Plus is hasonló, csak itt már minden egyes doboz különböző színű. Az Interblockban és a Sokolorban is különböző színűek a dobozok, de itt az a cél, hogy a hasonló színűek határosak legyenek. A Cyber Boxban minden szinten van egy kilépő négyzet, és a cél az, hogy ezt elérjük.
• Plusz játékelemek: A Sokonex, Xsok, Cyberboy és a Block-o-Mania új elemeket adott hozzá a játékhoz, például teleportokat, üregeket, mozgó blokkokat vagy egyirányú utakat.

A szókoban tudományos megközelítése

A szókoban a bonyolultságelmélet tárgykörébe tartozik. A játék megoldása bizonyítottan NP-nehézségű, mivel egy olyan mozgásszervező probléma része, ahol egyszerre több dobozt is lehet tolni vagy húzni. Érdekes továbbá a mesterséges intelligencia kutatóinak is, mert a szókoban hasonlítható egy robottervezéshez is, ami dobozokat mozgat egy raktárban. További kutatások megerősítették, hogy a szókoban PSPACE-teljes.

A szókoban nem csak a pillanatnyilag lehetséges lépések magas száma (branching factor) miatt nehéz (ami a sakkhoz hasonlítható, de még mindig sokkal kisebb, mint a go), hanem a számos keresőfájának mélysége miatt is; sok pálya több mint ezer „tolást” követel meg. Tapasztalt emberi játékosok leginkább a heurisztikájukban bíznak; ők általában gyorsan eldobják a haszontalan vagy redundáns lehetséges utakat a játékból és felismerik azokat a mintákat és részcélokat, amik drasztikusan lecsökkentik a keresések számát.

Néhány szókobanprobléma megoldható automatikusan a single-agent kereső algoritmussal, mint például az IDA, felfejlesztve sok technikával, amik a doménspecifikus tudást használják. Ezt használja a Rolling Stone, egy szókobanmegoldó program is, amit az Albertai Egyetem GAMES (Game-playing, Analytical methods, Minimax search and Empirical Studies) csoportja fejlesztett ki. A komplexebb pályák még így is kivül esnek a megoldhatóság körén a legjobb automatikus megoldószoftverek számára is.

Irodalom

• Dorit Dor, Uri Zwick, Sokoban and other motion planning problems. Computational Geometry: Theory and Applications 13, 215-228 (1999).
• Joseph C. Culberson, Sokoban is PSPACE-complete. Technical Report TR 97-02, Dept. of Computing Science, University of Alberta, 1997. Also: http://web.cs.ualberta.ca/~joe/Preprints/Sokoban^{[halott link]}.
• Andreas Junghanns, Jonathan Schaeffer, Sokoban: A Case-Study in the Application of Domain Knowledge in General Search Enhancements to Increase Efficiency in Single-Agent Search. Artificial Intelligence, special issue on search, 2000.

Lásd még

• sógi (shogi), kínai sakk (xiangqi), koreai sakk (janggi), sakk, go.

Fordítás

• Ez a szócikk részben vagy egészben a Sokoban című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

További információk

• A szókoban hivatalos oldala (japánul)
• A szókobanról az albertai GAMES Csoport honlapján (angolul)
• Szókoban a tablajatekos.hu-n