Tato stránka vyžaduje podporu CSS stylů
Jazyky pro umělou inteligenci - semestrální práce
Bludiště
Oto Válek
FEL ČVUT, zimní semestr 2002/2003, cvičení Út 12:45
1. Zadání
Napište chování postavičky v bludišti. Bludiště je složeno z těchto prvků:
zeď, chodba, východ, klíč a střela. V bludišti se kromě vaší postavičky
pohybují také příšery a letící střely. V bludišti nejsou žádné další postavičky.
V každém kroku může provést vaše postavička jednu z následujících akcí:
pohyb dopředu/dozadu/doleva/doprava vzhledem ke směru pohledu,
změnit směr pohledu doleva/doprava/vzad a aktivovat střelu.
Střely je potřeba nejdříve nejít v bludišti.
Každá postavička má tři životy. Životy ubývají postavičce při srážce
se střelou nebo s příšerou a při nárazu do zdi. Příšeře ubývají životy jen
při srážce se střelou. Příšera sama střelu nemůže ani sebrat ani aktivovat.
Střely jsou programovatelné a mají maximální dolet
10 kroků, při nárazu do stěny či jiné střely se zničí. U střel, příšer
a ostatních postav jsou viditelné tahové funkce, směr pohledu a počet životů.
Postavička vidí půlkruh ve směru pohledu, maximálně do vzdálenosti 10 kroků,
přičemž stěny jsou neprůhledné.
Úkolem postavičky je najít co nejvíce klíčů, odstranit co nejvíce příšer
a dojít do východu, to vše v co nejkratším čase.
2. Princip řešení
Vlastní algoritmus je obsažen v třídě
trida_tahovy_objekt_postava_valeko
v souboru valeko.lsp.
Odladěno na verzi 37.
Rozhodování je založeno na ohodnocování jednotlivých možnosti tahu
(DOPREDU DOLEVA DOPRAVA DOZADU
OTOC_DOLEVA OTOC_DOPRAVA OTOC_DOZADU STRELA STOP)
celými čísly podle situace. Provedena je pak možnost s nejvyšším hodnocením.
3. Datové struktury
Datové struktury jsou uloženy v tahovém objektu:
(defclass trida_tahovy_objekt_postava_valeko(trida_tahovy_objekt)
(
(parametry :type trida_parametry_tahu :accessor slot_parametry
:initform nil)
(pozice :type trida_pozice :accessor slot_pozice
:initform (make-instance 'trida_pozice :x 0 :y 0))
(pohled :type symbol :accessor slot_pohled
:initform 'nahoru)
(posl_pozice :type trida_pozice :accessor slot_posl_pozice
:initform (make-instance 'trida_pozice :x 0 :y 0))
(posl_akce :type symbol :accessor slot_posl_akce
:initform nil)
(posl_otoceni :type symbol :accessor slot_posl_otoceni
:initform nil)
(navstiveno :type simple-vector :accessor slot_navstiveno
:initform (make-array '(200 200) :initial-element 0))
(x_max :type integer :accessor slot_x_max
:initform 0)
(x_min :type integer :accessor slot_x_min
:initform 0)
(y_max :type integer :accessor slot_y_max
:initform 0)
(y_min :type integer :accessor slot_y_min
:initform 0)
(posl_zbyva :type integer :accessor slot_posl_zbyva
:initform 0)
(tahu :type integer :accessor slot_tahu
:initform 0)
)
)
- parametry - zde je uložen odkaz na parametry tahu, předané tahové funkci, aby k nim měly přístup ostatní metody
- pozice - zde je udržována aktuální pozice (pozice v třídě trida_aktivni_objekt mi nefungovala)
- pohled - zde je udržován aktuální pohled
- posl_pozice - poslední pozice (před posledním pohybem)
- posl_akce - poslední provedená akce (návratová hodnota tahové funkce)
- posl_otoceni - poslední provedené otočení
- navstiveno - pole, udržující počet návštěv jednotlivých polí bludiště, také je použito k zapamatování zdí
- x_max,x_min,y_max,y_min - zatím objevený rozsah pole navstiveno
- posl_zbyva - poslední vypočtená hodnota funkce zbyva
- tahu - počitadlo provedených tahů
4. Tahová funkce
Metoda tahova_funkce provede několik jednoduchých
i složitějších testů, na základě kterých upravuje váhy možností tahu.
K tomu použije většinou jednoduché rekurzivní funkce a metody, ač je sama
poměrně dlouhá.
- iniciální nastaveni vah - např. preferovat otoc_doleva před doleva
- zapamatovat si, kde jsou zdi kolem mne (pole navstiveno)
- jít do východu, pokud je hned vedle
- nechodit a neotáčet se do směru, kde je střela
- nechodit do směru, kde je příšera, naopak jít rychle někam jinam, pokud nemáme střely, ani se neotáčet
- když nemáme střely, bojíme se příšer - nechodit a neotačet se do směru, kde je příšera ve vzdálenosti 2 nebo 3
- příšera šikmo vlevo a vpravo - nechodit dopředu, ani tím směrem
- nezůstávat zbytečně na místě
- nevracet se, odkud jsme právě přišli
- nestřílet, když není čím
- nestřílet dvakrát za sebou a nechodit za střelou
- zastřelit príšeru ve vzdálenosti <= 2
- rozhlédnout se po vidtelné mapě - detekce slepých uliček a východu v dohledu
- nechodit a neotáčet se tam, kde už jsme byli (pole navstiveno)
- ale překonat již prošlou uličku, pokud jsme za ní ještě nebyli
Preference procházení neznámých částí bludiště, a tím více zastřelených příšer
a sebraných klíčů byla dosažena heuristickou funkcí zbyva.
Funkce zjistí počet nenavštívených polí, sousedících s některým už navštíveným.
Je-li tento počet < 5, tahová funkce přestane ingnorovat východ.
Podrobnosti viz zdrojový text.
5. Výsledky
Algoritmus vyřešil všechna bludiště ve verzi 37 kromě tří, a to s těmito výsledky:
bodu tahu tahu/bodu
------------------------------------------
bludiste1_2 74 9326 126.03
bludiste2_2 126 2370 18.81 kolize
bludiste3_2 60 829 13.82
bludiste4_2 57 2978 52.25
bludiste5_2 80 5903 73.79
bludiste6_2 55 2398 43.60
bludiste7_2 53 497 9.38
bludiste8_2 67 1023 15.27 kolize
bludiste9_2 55 637 11.58 kolize
bludiste10_2 44 656 14.91
bludiste11_2 65 1135 17.46
bludiste12_2 92 3622 39.37
bludiste13_2 63 2908 46.16
bludiste14_2 61 926 15.18
6. Soubory
jui.zip - ZIP archiv zdrojových souborů a této dokumentace