Harjoitustyö 1: Prolog-työ

Kurssin Prolog-tutoriaalissa käytetty materiaali:

Materiaalissa esiintyvät esimerkkikoodit löytyvät Lintulasta hakemistosta /home/ai/prolog_esimerkkeja/.

Lintulasta löytyy GNU Prolog hakemiston /usr/local/lang/prolog/ alta.

Työohje

Toisessa harjoitustyössä pitää toteuttaa miinaharavaa pelaava agentti Prologilla. Useimmille miinaharava on varmasti tuttu, mutta kertauksen vuoksi säännöt ovat myös tässä.

Kenttä on MxN ruudukko, jossa on joku ennalta tunnetty määrä X miinoja. Jokaisessa kentän ruudussa joko on miina tai ei ole miinaa. Agentin tarkoituksena on päätellä tietämyksensä pohjalta mahdollisimman monen miinan sijainti ja vastaavasti mahdollisimman monen ruudun turvallisuus. Agentille annetaan alussa turvallinen ruutu, jossa ei ole miinaa. Tutkiessaan jonkun ruudun agentti saa selville tämän ruudun vieressä (kulmittainkin käy) olevien miinojen määrän. Tästä agentin pitää tutkia omin avuin niin suuri osa miinakenttää kuin se turvallisesti osaa.

Parhaiten pelin ideasta saa selvää pelaamalla itse muutaman pelin. Ihmispelaajalle mielekkäämpänä versiona tämä peli on vakiona Windowsseissa ja Unixeilla yksi pätevä miinaharava tulee Xemacsin pluginina, tosin Lintulassa sitä ei näy olevan. Seitistä myös löytyy lukemattomia Javalla tehtyjä miinaharava-viritelmiä.

Toteutus

Harjoitustyönä pitää toteuttaa predikaatti agent(+Percept,-Action), joka on tosi, kun agentti tekee toiminnon Action sen hetkisen tietämyksensä ja Perceptin pohjalta. Predikaatin epäonistuminen laillisella syötteellä johtaa bumerangiin. +Percept tarkoittaa, että Percept on agenttia kutsuttaessa instantioitu ja -Action vastaavasti, että agentin pitää se instantioida haluamallaan toiminnolla. simulator-alkuisten nimien käyttö on harjoitustyössä kiellettyä, koska GNU-Prologissa ei ole moduuleita ja simulaattoria ei tietenkään saa sorkkia. Koska agentin pitää säilyttää tietonsa kutsukertojen välissä on assertin käyttö välttämätöntä, vaikka sen käyttämistä  normaaleissa Prolog-ohjelmissa kannattaakin välttää. Tässä harjoitustyössä suositellaan käytettäväksi assertz/1-predikaattia. Sen sijasta saa käyttää asserta/1-predikaattia ainoastaan, jos se ei muuta ohjelman semantiikkaa. Toisin sanoen se saa muuttaa ainoastaan järjestystä, jossa ratkaisut löydetään: ohjelman, jossa asserta:t on korvattu assertz:lla pitää osata paljastaa täsmälleen samat ruudut. Tämän tarkoituksena on karsia assertin väärinkäyttömahdollisuuksia. Retractia tai mitään muutakaan predikaattia, jonka avulla tietokannasta voi poistaa dataa, ei saa käyttää.

Percept on joko vakio nothing tai muotoa location(X,Y,Mines), jossa Mines on paikan (X,Y) vieressä olevien miinojen määrä. Ruutujen indeksointi alkaa ykkösestä. Jos Percept on nothing, niin edellinen toiminto ei tuottanut mitään uutta havaintoa. Ensimmäisellä vuorolla agentille annetaan tiedot jostakin aloituspaikasta, jonka ympärillä ei ole yhtään miinaa.

Action on joko stop, mark(X,Y) tai try(X,Y). Lopetustoimintoa stop on tarkoitus käyttää, kun agentti ei enää osaa edetä miinakentässä tai miinakenttä on kokonaan tunnettu.  Toiminnolla mark(X,Y) kerrotaan simulaattorille, että agentin mielestä paikassa (X,Y) on miina. Toiminnolla try(X,Y) agentti siirtyy paikkaan (X,Y). Mikäli siellä on miina, agentti räjähtää bitin palasiksi ja agentin tekijä saa bumerangin muotoista palautetta. Mikäli paikassa (X,Y) ei ole miinaa, agentti saa seuraavalla vuorolla tietää paikan (X,Y) vieressä olevien miinojen määrän.

Sama selvemmin:

Action:                Seuraavan vuoron Percept:

try(X,Y)                 location(X,Y,Mines)  (Jos (X,Y):ssä ei ole miinaa)
mark(X,Y)             nothing
stop                        Seuraavaa vuoroa ei tule

Miinakentän mitat ovat saatavilla agentille predikaateilla field_width(?Width) ja field_height(?Height) ja miinojen lukumäärä predikaatilla mine_count(?Mines).

Koska monet Prologit ovat paljon draft-vaiheessa olevaa ISO-Prologia laajempia, on hiukan vaarallista tehdä koodia yhdellä Prologilla ja luulla sen toimivan lähes muutoksitta jossain toisessa Prologissa. Tämän takia suosittelen tätä harjoitustyötä varten käyttämään GNU-Prologia alusta asti . Jos kuitenkin haluaa jotain muuta ympäristöä kehitysvaiheessa käyttää, on syytä käyttää ainoastaan tavallisia ISO-Prologin ominaisuuksia, joita niitäkään tämä käytössä oleva GNU-Prologin versio ei aivan kaikkia tue.

Testaaminen

Hakemistossa ~/ai/mines on ohjelma nimeltä simulate, joka simuloi agentin toimintaa miinakentässä. Simulatea käytetään tyyliin simulate minefield agent.pl, jossa minefield on tiedosto, jossa on alla kerrottua muotoa oleva miinakentän kuvaus, ja agent.pl on agentin Prolog-lähdekoodi.  Jos simulatesta löytyy bugi tai keksit muuten vaan hyviä ideoita sen kehittämiseksi,  ota yhteyttä osoitteeseen eleinion@cs.tut.fi

Agentin koodin pitää kääntyä/tulkkautua virheittä ja varoituksitta, paitsi alussa tulevasta allaolevan tyylisestä varoituksesta ei tarvitse välittää, koska se johtuu simulaten tavasta käyttää agenttia.
warning: /home/ai/mines/sorsat/sweeper.pl:3: redefining procedure agent/2
         /home/ai/mines/sorsat/simulate.pl:4: previous definition

Samassa hakemistossa on myös simulaten lähdekoodi simulate.pl, jota voi käyttää tulkissa (gprolog), jolloin saa tämän debuggerin käyttöön mukavasti. Koodia katselemalla saa ehkä myös hiukan käsitystä kuinka joitakin asioita voi prologilla tehdä.

Esimerkki simulaten kätöstä tulkissa

Miinakentät

Miinakenttätiedostojen muoto on yksinkertainen, joten niitä on helppo rakentaa käsin tai automaattisesti. Se koostuu whitespacella erotetuista numeroista. Ensin tiedostossa on sarakkeiden määrä, rivien määrä ja miinojen määrä, joita seuraavat aloituspisteen koordinaatit x ja y ja lopuksi jokaiselle miinalle koordinaatit x ja y. Hakemistossa ~/ai/mines on miinakenttätiedosto minefield1, jota voi käyttää agenttinsa testaamiseen ja esimerkkinä miinakenttätiedoston rakenteesta.

Arvostelu

Arvosana määräytyy pääasiassa sen mukaan, kuinka hyvin agentti selviää eri miinakentillä. Oikein merkityt miinat ja löydetyt turvalliset ruudut lisäävät pistesaldoa, väärin merkitty miina tuottaa sakkoa ja miinaan astuminen tuottaa bumerangin. Simulate kertoo agentin saavuttaman pistemäärän simuloidulla miinakentällä. Agentin kannattaa siis jatkaa toimintaa vain niin kauan kuin uutta tietoa tuottavia, mutta varmasti turvallisia  toimintoja on jäljellä. Agenttien ei tarvitse osata haravointia täydellisesti, riittää, kun agentti on aidosti parempi kuin /home/ai/mines/testagent. Osaltaan arvosteluun tietenkin vaikuttaa myös koodin kommentit, ratkaisun eleganssi ja muut hämärät osa-alueet kuten myös selostuksen taso. Ohjelma ei saa käyttää kohtuuttomasti aikaa. Aiempana vuonna aikarajana on pidetty kolmea minuuttia. Käytännössä aikaa ei pitäisi kulua liikaa, kunhan agentti pohdiskelee jatkotoimenpiteitään jotenkin järkevän lokaalisti.

Deadlinen jälkeen ei oteta vastaan bumerangejakaan, joten palauta ajoissa!

Palautus

Harjoitustyössä 1 palautetaan hyvin kommentoitu miinaharava-agentin Prolog-koodi, ja pieni selostus sen korkean tason toimintaperiaatteista ja arvio siitä millaisilla miinakentillä agentti toimii hyvin ja millaisten tilanteiden kanssa agentilla on ongelmia, jos sellaisia on tiedossa. Simulaten käyttämä predikaatti agent/2 pitää sijaita tiedostossa nimeltä agent.pl. Jos haluaa jakaa koodin useampaan tiedostoon, kannattaa tässä tapauksessa käyttää direktiiviä include/1 sisällyttämään muut tiedostot tulkkauksen aikana agent.pl:ään. Selostuksen pitää olla erillisessä raakatekstitiedostossa, pituudeltaan jotain puolen ja yhden sivun väliltä ja lisäksi siinä pitää mainita tekijän nimi, opiskelijanumero sekä sähköpostiosoite.

Itse palautus tapahtuu taas sähköpostitse osoitteeseen ai@cs.tut.fi,subjectina ai palautus 1, ja itse tiedostot tar-paketoituna ja mime-koodattuna, esimerkiksi näin:

tar cf - agent.pl selostus | mimencode | elm -s"ai palautus 1" ai@cs.tut.fi

Onnistuneesta tämän harjoitustyön palautuksesta tulee nopeasti automaattinen vastaus. Tämä vastaus siis tarkoittaa, että harjoitustyö on saapunut perille, ei suinkaan hyväksymistä. Hyväksymis- ja hylkäystuomioita tulee hieman hitaampaa tahtia, mutta vasteaika ei nouse yli viikkoon ja useimmiten muutama päivä riittänee. Varsinaiset harjoitustyöstä saatavat pisteet julkistetaan dediksen jälkeen, kun keskinäinen paremmuusvertailu on suoritettu. Hyväksytystä työstä ei voi lähettää paranneltua versiota, kun taas hylätystä työstä täytyy lähettää hyväksyttävä versio entiseen deadlineen mennessä.

Deadlinen jälkeen ei oteta vastaan bumerangejakaan, joten palauta ajoissa!