Harjoitustöiden yleistä byrokratiaa

Harjoitustöitä on kolme kappaletta, ja niiden tiukat deadlinet ovat 24. lokakuuta (ensimmäinen) sekä 10. joulukuuta (toinen ja kolmas). Deadlinen tiukkuus tarkoittaa, että harjoitustyö on palautettava harjoitustyöassistentille viimeistään kello 23:59 kyseisenä päivämääränä, eikä tavallisia tai bumerangipalautuksia oteta kyseisen ajanhetken jälkeen enää vastaan.

Harjoitustyöt arvostellaan asteikolla 0-6, missä alin hyväksytty arvosana on 1. Tosin 1. harjoitustyöstä on mahdollista saada hyväksytystä työstä 0 pistettä. Hylätyt harjoitustyöt lähetetään bumerangeina takaisin. Kerran hyväksyttyä harjoitustyötä ei voi enää myöhemmin palauttaa uudelleen paremman arvosanan toivossa.

Assistentti päivystää huoneessa HA226B torstaisin klo 10-12, jolloin voi tulla kyselemään harjoitustöihin liityvistä asioista.

Tulokset

Harjoitustöistä saadut pisteet ovat nähtävissä täällä.

Harjoitustyö 1: Hakualgoritmityö

Ensimmäisessä harjoitustyössä opiskelijan täytyy toteuttaa likimääräinen hakualgoritmi, joka ratkaisee kaistanleveyden minimointitehtävän. Kyseisen tehtävän instanssina olevalle suuntaamattomalle graafille muodostetaan solmujen numerointi luvuilla 1, 2, ..., n siten, että suurin graafista löytyvä naapurisolmujen numeroiden erotus on mahdollisimman pieni.

Kaistanleveyden minimointi on tunnetusti NP-kova optimointitehtävä. Toivoa kaikille mahdollisille syötegraafeille optimaalisen numeroinnin nopeasti rakentavasta algoritmista ei siis ole, eikä tällaista tässä harjoitustyössä siksi vaaditakaan. Harjoitustyön tarkoituksena on keksiä ja ohjelmoida likimääräismenetelmiä ja nyrkkisääntöjä, joilla löydetään useimmissa tapauksissa tehokkaasti hyvä ratkaisu. Kaikkia mahdollisia hakutekniikoita on tässä harjoitustyössä lupa käyttää. Harjoitustyön arvosana määräytyy sen mukaan, miten hyviä ratkaisuja kirjoitettu ohjelma löytää harjoitustyöassistentin etukäteen valmistamille koegraafeille.

Harjoitustyössä kirjoitettava ohjelma lukee graafin kuvauksen standard inputista. Graafi koodataan välilyönneillä erotetuksi sarjaksi positiivisia kokonaislukuja, joka alkaa graafin solmujen ja kaarten lukumäärillä n ja m. Graafin solmujen oletetaan olevan positiivisia kokonaislukuja 1, 2, ..., n . Tämän jälkeen sarjassa seuraa 2m lukua kuvaten luetteloa graafin kaarista, missä kukin kaari on esitetty antamalla sen yhdistämät solmut. Ohjelma voi olettaa syötteen olevan muodoltaan virheetöntä. Ohjelma palauttaa laskemansa tuloksen tulostamalla n välilyönneillä erotettua lukua standard outputiin, missä paikassa i tulostettu luku on ohjelman solmulle i antama numero. Solmujen määrä n on maksimissaan 50 ja graafin voi olettaa kytketyksi. Ohjelman on palautettava jokaiselle syötegraafille laskettu tulos viimeistään kahden minuutin kuluttua ohjelman käynnistämisestä harjoitustyöassistentin SparcStation 5-työasemalla.

Harjoitustyön toteutuskielenä on noweb-käsitelty C++, missä samaan dokumenttiin on literate programming -tekniikan mukaisesti yhdistetty itse ohjelma että sen dokumentaatio. noweb löytyy lintulasta hakemistosta /share/noweb/. Koska tämän harjoitustyön tarkoituksena ei ole perustietorakenteiden ja -algoritmien ohjelmointi vaan korkeamman tason algoritmisuunnittelu, niin STL-kirjaston valmiita tietorakenteita ja perusalgoritmeja saa käyttää vapaasti. Ohjelman on silti käännyttävä varoituksitta ja toimittava lintulassa käytettäessä noweb-konvertteria ja g++-kääntäjää.

Harjoitustyöt, jotka eivät käänny varoituksitta tai eivät onnistu laskemaan jollekin testisyötteelle laillista tulosta vaaditussa ajassa (esim. kaatuvat, jäävät ikuiseen laskentaan tai palauttavat saman numeron kahdelle eri solmulle), lähetetään bumerangina takaisin tekijälleen. Testin läpäisseen harjoitustyön tekijälle lähetetään viesti harjoitustyön hyväksymisestä, mutta lopullista arvosanaa ei voida antaa ennen kuin kaikki harjoitustyöt on tarkastettu ja asetettu tehokkuusjärjestykseen. Testiaineiston hyväksytysti läpäissyttä harjoitustyötä ei voi enää myöhemmin palauttaa paranneltuna uudestaan paremman arvosanan toivossa.

Julkinen testiaineisto

Näitä graafeja voi ja kannattaa käyttää ohjelmansa testaukseen, mutta omiakin testigraafeja kannattaa tietenkin generoida. Tarkastuksen yhteydessä ohjelmien suorituskykyä testataan näillä sekä muutamalla salaisella graafilla, joten erikseen näitä graafeja varten ei kannata optimoida.

Harjoitustyö 2: Prolog-työ

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, jonka vieressäkään ei ole yhtään 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 seitistä löytyy lukemattomia Javalla tehtyjä miinaharava-viritelmiä. Yksi mikä tuntuu toimivan on http://nimbus.temple.edu/~jmillawa/mines/minesweeper.html

Toteutus

Harjoitustyönä pitää toteuttaa predikaatti agent(+Percept,-Action), joka on tosi, kun agentti tekee toiminnon Action sen hetkisen tietämyksensä ja Perceptin pohjalta. +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 se ei normaaleissa Prolog-ohjelmissa olekaan suositeltavaa. Tästä huolimatta retractia ei saa käyttää, jos ei keksi sille jotain erityisen hyvää ja vakuuttavaa syytä.

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

Harjoitustyöstä saa 0-6 pistettä, joista 1 on alin hyväksytty arvosana. 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ä. Osaltaan arvosteluun tietenkin vaikuttaa myös koodin kommentit, ratkaisun eleganssi ja muut hämärät osa-alueet. Tässä harjoitustyössä ei ole varsinaista aikarajaa, mutta ajankäytön pitää olla jotenkin järkevissä rajoissa. Käytännössä aikaa ei kulu liikaa, kunhan agentti pohdiskelee jatkotoimenpiteitään jotenkin järkevän lokaalisti.
 

Palautus

 Palautusohjeet

Harjoitustyö 3: Tutkielmatyö

Kolmannessa harjoitustyössä opiskelijan on etsittävä itselleen jokin häntä itseään kiinnostava aihe jostakin tekoälyn osa-alueesta, kysymyksestä, tekniikasta tai sovellutuksesta, ja kirjoitettava siitä noin 5-10 sivun mittainen tutkielma. (10 pisteen fontti, kohtuulliset marginaalit ja rivivälit.) Tutkielman aihe saa periaatteessa olla mikä tahansa, minkä opiskelija pystyy vakavalla naamalla väittämään liittyvän tekoälyyn. Tämän aiheen on lupa olla sellainen, että sitä on käsitelty kurssin luennolla, mutta tällaisessa tapauksessa tutkielmassa on oltava itsenäisesti hankittua sisältöä, joka ei ole peräisin luennoilta tai luentomateriaalista. Valmiit tutkielmat palautetaan paperimuodossa harjoitustyöassistentille, jonka tavoittaa huoneestaan HA226B parhaiten torstaisin 10-12, maanantaisin 12-16 ja epämääräisiin aikoihin iltaisin. Palauttaa voi myös ym. huoneen oven ali. Tutkielman saa kirjoittaa joko suomeksi tai englanniksi.

Valitun aiheen on oltava laajuudeltaan sopiva niin, että se kyetään taustoineen esittelemään ja käsittelemään tutkielman sivumäärän puitteissa. Tutkielma voi olla yleiskatsaus laajaan aihealueeseen tai vaihtoehtoisesti jotakin yksittäistä osa-aluetta tarkemmin valottava, tarkkaan rajattu esitys.Tutkielman tulee sisältää tarvittavat lähdeviitteet, mutta sen on kuitenkin oltava itsenäinen kokonaisuus siten, että hypoteettinen lukija voi ymmärtää esitetyn asian ja sen merkityksen pelkästään lukemalla pelkästään kyseisen tutkielman. Opiskelijan on hankittava tutkielmassa viitattavaa lähdetietoa useammasta kuin vain yhdestä lähteestä.

Ainakin seittisivulta Writing and Citation Guides on the WWW löytyy ohjeita tutkielman kirjoittamiseen. Kirjastoista ja seitistä etsivä löytänee muitakin kirjoitusoppaita.