Praktikumitöö: Kalah

(2005 aasta ülesandevariandi leiad siit ja 2006 sügissemestri ülesandevariandi leiad siit.)

Ülesandeks on kirjutada talutavalt mängiv kalahiprogramm. Kalahi reeglitest ja muust loe siit. Programmi võib kirjutada ja esitada <bkas üksi või kahekesi

Programm peab baseeruma T.Tammeti mittemõtlevale kalahiprogrammile, mille saad kas zip-ga pakitud java failina Kalah.zip või siit hiirega copy-pastetava failina.

Konkreetsed nõuded

Miinimumnõuded:

• Esimene nõue oli juba kirjas: sinu programm peab baseeruma T.Tammeti mittemõtlevale kalahiprogrammile (sama programm teisel kujul siit. Kasutajaliides tuleb jätta samaks ning positsiooni tuleb hoida samal viisil 13-elemendilises int massiivis, nagu mainitud programmis. Konkreetselt on näiteprogrammis vaja ümber kirjutada calcMove() funktsioon, tehes ta mõtlevaks.
• Teine nõue: programm peab mängima talutavalt hästi, kui ajapiiranguks on üks sekund käigu kohta. Talutavalt hästi tähendab seda, et (a) juhendaja ei suuda kiirelt mängides programmi võita ja (b) sinu programm alati võidab nõrgalt mängivat näiteprogrammi, mis ilmub siis lehele ca 10. detsembril. Nõrk näiteprogramm vaatab ette neli käiku ja kasutab staatilise seisuhindajana lihtsalt kogumispesades olevate nuppude arvu vahet.
• Neljas nõue: programmis peab olema realiseeritud minimax.

Muud nõuded, mille puudumisel võetakse veidi punkte maha, töö saab aga olema arvestatud:

• Peab olema realiseeritud iteratiivne sügavnemine.
• Peab olema realiseeritud alpha-beta.

Esialgseid, üldisi soovitusi

Alusta sellest, et tee valmis lihtne minimax (ilma alpha-betata) ja lihtne seisuhindaja, kus vaadatakse ainult seda, kas mõni osapooltest on võitnud. Debugi see programm ära, mängides talle ise vastu. Tee katseid nii otsinguga sügavuseni kaks, kolm, neli jne, kuni otsiaeg läheb liiga suureks.

Seejärel asu täiustama seisuhindajat. Peamised ideed:

• Kas on laual (otsene võit)?
• Loe kokku lihtnupud ja tammid mõlema jaoks. Tamm pane ca kaks korda väärtuslikumaks, kui lihtnupp.
• Lisa lihtnuppudele kaalud: mida lähemal vastase viimasele reale, seda parem.

Tee katseid aja-arvestusega ja määra otsingusügavus selline, et AK klassides kunagi ei mõeldaks üle ühe sekundi.

Programmi headuse jaoks kriitiline idee on analüüsida kõik löögiahelad ja vastulöögiahelad jne alati lõpuni läbi, vähendamata seejuures üldse otsingupuu sügavuse piirangut!

Võistlus ja lisapunktid

Pärast praktikumitöö esitamise tähtaja möödumist korraldab õppejõud programmide vahel võistluse, ning esimese kahe parema programmi autorid saavad eksami jaoks lisapunkte:

• Esikoha võitnud programmi autorid kumbki 15 punkti.
• Teise koha võitnud programmi autorid kumbki 10 punkti.
• Kolmanda koha võitnud programmi autorid kumbki 5 punkti.

Võistlus ei ole kohustuslik. Kuidas sellest osa võtta: ...

Õppejõule tuleb 2007 aasta jooksul (2008 on juba hilja!) saata emailiga järgmine info, kusjuures Subject real (emaili pealkiri) peab olema sõna KALAH:

• autorite nimed, matriklinumbrid, emailid
• programmi lähtekood

Sisulised nõuded:

• Teie programmi mõtlemiskomponendid peavad olema üleni teie enda kirjutatud. Artikleid lugeda ja teisi programme uurida tohib, neid otse kopeerida aga mitte.
• Kui õppejõul tekib eelmise punkti osas kahtlus, siis ta uurib autoritelt asja edasi, ning kahtluse püsimisel diskvalifitseerib kahtlase programmi võistluselt.

Tehnilised nõuded:

• Programm ei tohi AK arvutiklassides ühtegi käiku mõelda kauem, kui ühe sekundi.
• Programm peab kasutama T.Tammeti näiteprogrammi kasutajaliidest ja töötama OK kõigi variantidega (alustaja/mittealustaja, alumine/ülemine rida, 3,4,5 või 6 nuppu algseisu pesades).

Seejärel korraldab õppejõud laekunud programmide vahel turniiri, kus edasi pääseb igast matshist parem.

Kasulikke linke

• http://en.wikipedia.org/wiki/Kalaha.

• http://www.ocf.berkeley.edu/~yosenl/extras/alphabeta/alphabeta.html
• http://www.cs.ualberta.ca/~chinook/
• http://web.archive.org/web/20040607185428/www.cs.vu.nl/~victor/thesis.html

.