Jak vybloudit z bludiště aneb nejde jen o šachy

Hned na úvod: bludištěm je v tomto článku myšlena síť s větvením, nikoliv zakroucená cesta typu říčního meandru...


Hned na úvod: bludištěm je v tomto článku myšlena síť s větvením, nikoliv
zakroucená cesta typu říčního meandru, která sice na první pohled vypadá
složitě a nepřehledně, ale bloudícímu poutníkovi (bez ohledu na to, zda se
jedná o člověka či počítačový program) nedává v žádném okamžiku možnost volby.
Zcela obecný návod na to, jak vybloudit z labyrintu, zřejmě neexistuje,
koneckonců labyrint ani žádný východ umožňovat vůbec nemusí a všechny chodby
mohou nakonec končit slepě. Jednotlivé metody si tedy jako cíl samozřejmě
kladou vybloudění z bludiště, nicméně jako minimální variantu nabízejí bezpečný
návrat na výchozí místo (tedy něco jako obdoba remízy v případě šachových
programů). Použitou metodou je prohledávání stavového prostoru (viz náš vložený
článek).
Pokud naproti tomu známe bludiště jako celek, můžeme ho znázornit jako graf
(opět viz náš vložený článek). Uzly grafu jsou pak křižovatky, konce slepých
cest, východy a uzavřené (odjinud nedostupné) prostory. Hrany našeho grafu jsou
veškeré spojnice (cesty).
Pravidlo jedné ruky
Nejčastěji se pro vybloudění z bludiště uvádí postup "pravidla jedné ruky" to
znamená, že na všech křižovatkách musíte vždy zabočit na stejnou stranu. Toto
řešení nicméně není zcela univerzální, protože pomíjí situaci, kdy se východ z
bludiště nachází v místech se specifickou topologií (v rámci příslušné
terminologie se tato místa označují tzv. ostrovy).
Univerzálnější postupy
Z báje o Théseovi je samozřejmě známé použití nitě. Na každé křižovatce se pak
postupuje tak, že se vydáte chodbou, kde je minimum nití (ideálně žádná, neboť
to je místo, kde jste dosud nebyli). Samozřejmě, nit lze nahradit např. určitým
systémem poznámek psaných na zeď (stejně jako při použití nitě lze v jedné
variantě nit zpět namotávat, i při psaní na zeď lze buď zprávy pouze zezdola
připisovat, nebo je při návratu na stejné místo mazat/škrtat).
Něco podobného činí příslušné algoritmy. Úloha je v tomto případě ulehčena tím,
že funkce se samy rekurzivně vyvolávají. Další ulehčení je pak dáno faktem, že
v rámci matematické reprezentace bludiště lze samozřejmě snadno pracovat s
nástroji typu "nekonečné" nitě, jejichž nasazení v reálném světě je naopak
poněkud problematické.
Zájemcům o tuto problematiku mohu doporučit mj. knihu Stanislava Vejmoly Chvála
bludišť (Státní pedagogické nakladatelství, Praha, 1991), kde najdeme popis
řady variant prohledávání bludiště hledání cesty od vchodu do bludiště,
prozkoumávání bludiště, kde jsme již zabloudili, algoritmy, jejichž cílem je
nejen z bludiště vybloudit, ale navíc se jako kritérium úspěšnosti používá
rychlost nalezení východu (ta může být zase měřena buď počtem úseků, nebo
jejich délkou atd., atd.).
Generování bludišť
Jakýmsi inverzním postupem k problému vybloudění je naopak generování bludišť.
Ta se pak mohou použít např. v počítačových i nepočítačových hrách typu RPG
(Role Playing Games). Cílem hráče zde ovšem není pouze najít cestu bludištěm,
ale spíše se vypořádat s úkoly a nástrahami, které do jeho jednotlivých částí
lokalizoval tvůrce hry. Vlastní tvorba bludiště ve smyslu jeho topologie je
tedy pouze jednou z částí tvorby scénáře hry.
Existuje celá řada programů generujících podle zvolených podmínek nějaké
bludiště. Některé z těchto programů jsou volně stažitelné prostřednictvím
Internetu, často včetně podrobně okomentovaného zdrojové-ho kódu. K tomu se
samozřej-mě přidává řada víceméně grafických programů pro následnou úpravu
prvotně vytvořeného bludiště.
Podívejme se na několik relevantních internetových adres, kde se můžeme setkat
s tvorbou bludišť:
http://www.jofo.ee/labyrinth/ medium.html Toto je jedna ze stránek, kde se
počítačově generují labyrinty, autor slibuje, že při každé návštěvě stránky
jiný. Bludiště bohužel není interaktivní.
http://www.speakeasy.org/ ~cruiser1/labyrnth/java.htm Javový applet tvoří
labyrinty. Lze získat i zdrojový kód programu.
http://www.speakeasy.org/ ~cruiser1/labyrnth.htm Zde kromě programu na
vytváření labyrintů najdeme i jeho bratříčka, který tvoří puzzle, dále odkazy
na další podobně orientované stránky.
http://www.amz.com/maze/2n. html Zde můžete přímo on-line procházet labyrintem.
http://www.pom.wb.utwente.nl/ staff/hans/index.htm I odtud si lze stáhnout
program generující labyrinty. Jsou zde také odkazy týkající se algoritmů pro
programy této kategorie.
http://www.speakeasy.org/ ~cruiser1/labyrnth/algrithm.htm
Charakter a dělení labyrintů a jejich topologie, jednotlivé typy, 2D, 3D i
vícedimenzionální. Najdeme zde návody na kreslení bludišť i mimo počítače.
Závěr
V tomto TECH-Tipu jsme probrali konkrétní algoritmy, realizující běh šachových
programů, stejně tak jako hravější programy týkající se bludišť. Je samozřejmé,
že podobné téma pokrývá poměrně speciální oblast využití IT. Nicméně si
nemyslím, že tyto informace mají význam pouze pro programátory, šachisty či
hráče her typu RPG. Otázka, nakolik lze určité lidské dovednosti
algoritmizovat, má, poněkud nadneseně řečeno, vztah k mnohem obecnějším
záležitostem.
9 0928 / pahn
Malé shrnutí a slovníček některých pojmů
Ve své původně zamýšlené verzi se tento článek měl jmenovat "Inteligentní
algoritmy pro deskové hry". Je jasné, že to obnáší podstatně širší pole, kde
jsou šachové programy pouze jednou z aplikací.
Spadají sem samozřejmě programy pro jiné stolní deskové hry (dáma, piškvorky,
GO apod.). V tomto článku se soustředíme na algoritmy pro nalezení optimální
cesty z bludiště. I to je však pouze jedna z aplikací.
Obecně nám zde jde o všechny inteligentní (nebo "inteligentní") systémy se
schopností vytvářet si vnitřní strojový model světa a pracovat s ním. Ve
většině úloh máme přitom definován počáteční stav a požadovaný koncový stav
(buď výčtem těchto stavů jako v případě nějaké jednodušší skládačky, nebo
podmínkami, které konečný stav musí splňovat v šachové partii např. mat, v
bludišti stav mimo chodby). Mezi počátkem a koncem leží svět "řešení
úloh" (míněno jako termín z oblasti umělé inteligence).
Množina všech stavů prostředí se přitom označuje jako stavový prostor a
reprezentuje se orientovaným grafem. Graf přitom v tomto případě zahrnuje útvar
složený z bodů (neboli uzlů) a jejich spojnic (nebo hran).
Často (např. v šachách) nemáme předem k dispozici žádný jednoznačný výpočetní
postup, který by nás dovedl k cíli. V takových případech se postupuje metodou
prohledávání stavového prostoru.
V rámci tohoto oboru se lze setkat i s celou řadou souvisejících pojmů
(produkční systém, báze dat, produkční pravidla, řídicí mechanismus). Zájemce
lze odkázat na další prameny (stránky na Internetu existuje ale i řada prací v
tištěné podobě), které se věnují problematice umělé inteligence a to v poněkud
vědečtější a vážnější rovině, než jsme to udělali my v případě našeho přece jen
lehce hravého TECH-Tipu.









Komentáře
K tomuto článku není připojena žádná diskuze, nebo byla zakázána.