Ifi6057lab3

Allikas: Lambda

Ülesanne

Viimases ülesandes tuleb kirjutada Prologis programm, mis oskaks mängida laevade pommitamist. Täpsemalt mängib programm ainult ühte poolt mängust: pakub välja koordinaadid, kuhu järgmisena pommitada ning võtab teadmiseks, kas tegu oli möödalasu, tabamuse või koguni laeva põhja laskmisega. Sellisel viisil kogutud infot kasutab programm siis järgmiste käikude "välja mõtlemiseks". Programmil oma laevu pole.

5grid.gif

Mängu reeglid on klassikalisest laevade pommitamisest natuke erinevad:

  • mängitakse 5x5 ruudustikul
  • koordinaadid on mõlemal küljel 1-st 5-ni
  • pole täpselt teada, mitu ja kui suurt laeva ruudustikul on. Õppejõud kasutab testimisel max 4 ruudu pikkust laeva

Sarnaselt klassikalise laevade pommitamisega on laevad sirged ja ei puutu külgi ega nurki pidi kokku

Oluline on, et programm suudaks lõpuks kõik laevad põhja lasta. Maksimaalselt kulub selleks 25 käiku. Et paremat hinnet saada, võiks programm üritada ka natuke kavalamalt tegutseda - tabamuste ja põhja minekute alusel on võimalik järeldusi teha, kuhu on eelkõige mõtet järgmist rünnakut suunata. Mida vähema käikude arvuga keskmiselt programm kõik laevad põhja saab, seda parem.

Selleks kasutame Prologi kui teadmusbaasi: paneme sinna sisse reeglid, mille järgi programm oskab järgmist käiku välja mõtelda. Uusi teadmisi paneme sisse asserta/1 või assertz/1 predikaatidega. Kustutada saab retract/1 või retractall/1 predikaatidega.

See ei ole väga klassikaline ja ilus viis Prologi kasutada, aga see eest on väga lähedane teadmusbaasil põhineva agendi ideele (vt. 8. loengu slaide).

Ülesande tähtaeg (emailiga priit at whitedb.org) on 1. detsembril. Ärge unustage ka kaitsma tulla, eriti kuna selleks on piiratud võimalused (2. detsembri ja 9. detsembri harjutustunnid). Alati on võimalik ka enne tähtaega kaitsta.

Nõuded

Et üliõpilaste programme saaks automatiseeritult testida, peab neil TÄPSELT selline liides olema tehtud, nagu allpool kirjeldatud:

Defineerida sellised predikaadid:

  • target/2. Parameetriks koordinaadid X, Y. Päringu vastuseks tulevad X ja Y väärtused - numbrid 1st 5-ni, mis viitavad järgmisele pommitatavele ruudule.
  • miss/0. Parameeteid pole. Annab programmile teada, et tema eelmine pomm läks mööda.
  • hit/0. Parameeteid pole. Annab programmile teada, et tema eelmine pomm läks pihta, aga laev veel põhja ei läinud.
  • sunk/0. Nagu eelmine, aga laev läks põhja ("Pihtas-põhjas!").

Vihje: pommitamise tulemuse juures ei ole kirjas, mis koordinaatide kohta või mis käigul tabamus/möödalask tuli. Seetõttu peab target/2 predikaat ise teadmusbaasi viimase tegevuse salvestama. See muudab programmi põhimõttelt sarnasemaks raamatus visandatud teadmusbaasiga agendi algoritmiga.

Näide interaktsioonist

2 ruudu pikkune laev asub koordinaatidel (1,2) ja (2,2). Programm laseb selle suhteliselt edukalt põhja (kasutaja sisend on paksus kirjas). Pange tähele, et üks samm koosneb target queryst, millele järgneb iga kord ka programmile tulemuse teada andmine. 

 | ?- target(X, Y).
 
 X = 1
 Y = 1 ? 
 
 yes
 | ?- miss.
 
 yes
 | ?- target(X, Y).
 
 X = 1
 Y = 2 ? 
 
 yes
 | ?- hit.
 
 yes
 | ?- target(X, Y).
 
 X = 1
 Y = 3 ? 
 
 yes
 | ?- miss.       
 
 yes
 | ?- target(X, Y).
 
 X = 2
 Y = 2 ?
 
 yes
 | ?- sunk.
 
 yes
 | ?-

Antud näide on GNU Prologis, SWI-Prologi väljund on sisu poolest sama, aga näeb natuke teistsugune välja.

Punktid

Kodutöö arvesse minekuks piisab, kui teha elementaarne versioon, mis suudab kõiki ruute pommitada, nii et kõik laevad lõpuks põhja lastud on. Selle jaoks on eelkõige vaja Prologi mõttemaailmasse sisse elada. See on enamusest programmeerimiskeeltest radikaalselt erinev ja võib natuke pusimist nõuda, seetõttu annab sellise kodutöö esitamine kohe 12 punkti. Programm ise on triviaalne ja selle saab teha paari-kolme reegliga (lisaks kohustuslikele liidese predikaatidele).

Et rohkem punkte saada, tuleks proovida juba mingit strateegiat realiseerida. Kui mingisugunegi toimiv loogika on tehtud, mis suudab pommitamist efektiivsemaks teha, tõuseb töö hinne 18 punkti peale.

Lõpuks, kõik kodutööd, eeldusel et neil on nõuetekohane liides, läbivad õppejõu poolt automaatse testimise, mis leiab keskmise käikude arvu ~100 juhuslikult genereeritud laevastiku põhja laskmiseks. Kõige parema tulemusega grupp saab 3 boonuspunkti, teine tulemus 2 punkti ja klassi peale kolmas tulemus 1 boonuspunkti. Neid boonuspunkte jagatakse ainult gruppidele, kes on mingi pommitamise strateegia ehitanud.

Abiks

Mõned lihtsamad reeglid: 

 person(sokrates).              % Sokrates on inimene
 mortal(X):-                    % kõik inimesed on surelikud
   person(X).
 mortal(X):-                    % teine reegel surelikkuse kohta. Prolog vaatab ükshaaval kõiki reegleid
   dead(X).
 dead(platon).                  % veel üks fakt

Kui me teeme päringu ?- mortal(platon). või ?- mortal(sokrates)., siis mõlemale saame vastuseks "yes" (või midagi analoogset, sõltuvalt Prologi versioonist). ?- dead(sokrates). annab aga vastuse "no", kuna selle kohta otsest fakti, ega ka sobivat reeglit ei eksisteeri.

Rekursiivne reegel (elementaarse versiooni saab kindlasti ilma teha, aga keerulisemate asjade juures võib kasuks tulla): 

 % faktid
 parent(john,paul).             % paul on johni vanem  
 parent(paul,tom).              % tom on pauli vanem
 parent(tom,mary).              % mary on tomi vanem
   
 % reegel: esivanema leidmine
 ancestor(X,Y):-  % baasjuhtum. Kui Y on X otsene vanem, siis ta ongi kohe esivanem
   parent(X,Y).   
 ancestor(X,Y):-  % rekursiivne reegel
   parent(X,Z),   % Valime mingi Z-i, kes on X-i vanem ja vaatame, kas temale
   ancestor(Z,Y). % on võimalik rekursiivselt esivanemat leida. Z esivanem on ka X esivanem.

Prologis on küll sisse ehitatud debugger, aga esialgu võib vigade otsimise jaoks lihtsam olla teksti välja trükkida. See näeb välja protseduurilise programmeerimise moodi, aga write/1 ja nl/0 on lihtsalt loogikapredikaadid, mille väärtus on alati true. 

 mortal(X):-
   write('kas X on inimene?'), nl,
   person(X).
 mortal(X):-
   write('kas X on surnud?'), nl,
   dead(X).

Cut ("!") on kasulik, kui tahetakse otsingut varakult lõpetada. Näiteks, kui ma teen eelnevate näidete puhul päringu ?- mortal(X)., pakutakse mulle nii Sokratest, kui Platonit. Kui ma tean ette, et mind huvitab ainult üks vastus, siis ma võin teha nii: 

 existmortal(X):-
   mortal(X),
   !.                        % Kui Prolog ühe sobiva X väärtuse on leidnud ja siia kohta jõudnud
                             % siis ta rohkem enam ei proovi.

Eituse jaoks on sümbol "\+" (siin on pikem seletus): 

 deceased(X):-
   mortal(X),
   \+ alive(X).
 mortal(mccartney).
 mortal(lennon).
 alive(mccartney).

Kui mingit asja tahetakse dünaamiliselt modifitseerida, siis tuleb seda Prologile ette deklareerida. 

 :- dynamic(person/1).

Peale seda query ?- retract(person(sokrates)). õnnestub.

Kui mingi predikaat on dünaamiline, siis saab selle kohta ka reegleid teha, ilma et predikaat ise oleks defineeritud. Alljärgnev on OK, isegi kui breeze fakte Prologi andmebaasis ei leidu: 

 :- dynamic(breeze/1).
 agentpos(1, 1, 1).  % agent asus ajahetkel 1 kohal 1, 1
 breezy(X, Y):-        % koordinaat X, Y on tuuline, kui
   agentpos(X, Y, T),  % agent on kohal X, Y ajahetkel T ja
   breeze(T).          % agent tajub tuuletõmmet ajahetkel T

Alakriips on anonüümne muutuja (meid ei huvita, mis ta väärtus on): 

 visited(X, Y) :-
   agentpos(X, Y, _). % agendi positsioon mingil suvalisel ajahetkel oli X, Y

Tuleb tähelepanelik olla, mis on tundmatud muutujad ja mis on teadmusbaasist tuletatavad. 

 nopit(X, Y) :-              % saab küsida nopit(X, Y).
   visited(L, Y),
   X is L + 1,               % kui X on tundmatu, siis arvutatakse ta visited(L, Y) abil leitud L-ist
   \+ breezy(L, Y).
 
 nopit_katki(X, Y) :-        % nopit_katki(X, Y) annab vea. Suudab ainult kontollida väiteid nagu nopit_katki(1,2).
   visited(L, Y),
   L is X - 1,               % kui X on tundmatu, siis Prolog L-i väärtust kontrollida ei oska :-(
   \+ breezy(L, Y).
Pärit leheküljelt "http://lambda.ee/w/index.php?title=Ifi6057lab3&oldid=12874"