Definovanie problému S

Úlohou je nájsť riešenie hlavolamu Sokoban. Sokoban je chlapík, ktorý v sklade presúva debny. Jeho zvláštnosťou je, že sa pohybuje len vo dvoch kolmých smeroch – vľavo, vpravo a hore, dole (z nášho pohľadu na obrazovke). Debny, ktoré má presunúť, sú také ťažké, že ich dokáže len tlačiť. Ak napríklad stojí vľavo od debny, môže ju posunúť doprava a on sa zároveň dostane na miesto, kde bola pred tým debna. Podmienkou posunu je, že za debnou nesmie byť múr. Ak je debna pri múre, sokoban sa nedokáže dostať medzi debnu a múr a od múru ju odtlačiť. A ani Sokoban nemôže prechádzať cez stenu. Počiatočná pozícia Sokobana je označená písmenom S, cieľová pozícia debny je označená XXX (na svetlejšom podklade) a debna je označená svojím obrázkom. Svetlomodré štvorčeky predstavujú podlahu, tmavošedé štvorčeky a tmavé orámovanie predstavujú múr.
S
XXX

Možné riešenie úlohy je napríklad takéto:

CHOD_VPRAVO,CHOD_VPRAVO,CHOD_VPRAVO,CHOD_HORE,
CHOD_HORE, CHOD_HORE, CHOD_VPRAVO,TLAC_DOLE,
TLAC_DOLE, CHOD_VPRAVO,CHOD_DOLE, TLAC_VLAVO,
TLAC_VLAVO, CHOD_HORE, CHOD_VLAVO, TLAC_DOLE,
TLAC_DOLE, TLAC_DOLE, CHOD_VLAVO, CHOD_DOLE,
TLAC_VPRAVO,TLAC_VPRAVO,TLAC_VPRAVO,TLAC_VPRAVO.

Implementácia S

Keď chceme túto úlohu riešiť algoritmami prehľadávania stavového priestoru, musíme si konkretizovať niektoré pojmy. Uvádzame príklad reprezentácie stavu, opis operátorov a cieľového stavu.

STAV

Pri riešení tohto problému potrebujeme poznať pozície viacerých objektov, ale len Sokoban a debna svoju pozíciu menia. Ak číslujeme od nuly od ľavého horného rohu, tak počiatočný stav reprezentuje dvojica (S 3 0) (D 1 4). Celý stav hry nám dopĺňajú pozície nehybných objektov – múry a cieľová pozícia debny: (M 0 5) (M 0 6) (M 1 0) (M 1 6) (M 2 0) (M 2 1) (M 2 6) (M 4 3) (M 4 4) (M 5 3) (M 5 4) (C 6 6). Tieto údaje sú však statické a stačí ich mať zapamätané raz.

Cieľový stav sa dosiahne, keď debna má rovnaké súradnice ako cieľová pozícia, teda pre tento sklad bude platiť (D 6 6). Pretože Sokoban môže byť z ľubovoľnej korektnej strany debny, cieľových stavov môže byť viacero, v tomto prípade dva: (S 5 6) (D 6 6) a (S 6 5) (D 6 6).

Vstupom algoritmu je počiatočný stav hry a stav nehybných objektov. Tým je zároveň definovaná aj pozícia debny v cieľovom stave.

OPERÁTORY

Operátorov je osem – štyri na chôdzu vľavo, vpravo, hore, dolu a štyri na posun debny v rovnakých smeroch. Operátory chôdze sú použiteľné, ak v tom smere nie je žiadna prekážka – debna, múr alebo okraj skladu. Operátor posunu je použiteľný, ak je v tom smere debna a za debnou nie je prekážka.

Najjednoduchšie je definovať, že všetky operátory majú rovnakú váhu – vtedy je najlacnejšia cesta definovaná počtom krokov Sokobana. Je ale možné dať posúvaniu debny väčšiu váhu, napríklad aspoň dvojnásobnú. Vtedy zvyčajne najlacnejšia cesta obsahuje najmenší možný počet posunov debny a až potom sa berie do úvahy minimum voľnej chôdze. (Ak by sme chceli zaručiť, aby riešenie vždy obsahovalo minimum posunov, museli by sme dať operátory posunu toľkokrát drahšie, koľko krokov môže Sokoban urobiť, kým raz posunie debnu – napríklad sumu všetkých voľných políčok.) Tu však vzniká problém, že algoritmom sa do tlačenia debny „nechce“ a generujú veľké podstromy prehľadávania stavového priestoru.

UZOL

Ako v probléme 2

ALGORITMUS

Ako v probléme 2

HEURISTIKA

Pretože stavový priestor tohto problému je obrovský, je nevyhnutné použiť informované prehľadávanie s dobrou heuristikou. Heuristika musí tiež eliminovať vysokú cenu operátorov posunu zodpovedajúcim bonusom. To znamená, že vzdialenosť debny od cieľa je zdanlivo niekoľkokrát väčšia ako vzdialenosť Sokobana od debny.

Pri návrhu riešenia je vhodné vziať do úvahy, že keď je debna pri stene, Sokoban ju od steny nedostane, ak tá stena sama niekde nekončí. A keď je debna dvomi stranami pri stene, nemá zmysel generovať nasledovníkov (Sokoban nemusí pobehovať okolo), lebo debnu už zaručene nie je možné presunúť do cieľa. (Ak už v tom cieli samozrejme nie je.)