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 kas ü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 ja 14, neli jne, kuni otsiaeg läheb liiga suureks. Kasuta seisuhindamiseks lihtsalt oma ja vastase kogumispesade (massiivis nr 6 ja 13) kivide arvu vahet. Hea mõte on anda programmile koodis ette mõni lihtne ja konkreetne algseis, mille juures sa saad ise aru, milline oleks tark käik, ja siis kasutada seda seisu debugimisel.
Ideid minimaxi praktiliseks programmeerimiseks:
- Kasuta arusaamiseks loengus toodud näiteid, samuti näiteid viidatud artiklitest. Mehaaniliselt neid kopeerida pole mõtet, koodimaht näidetes on väga väike.
- Eraldi käikude genereerimist pole mõtet teha, selle asemel käi tsükliga läbi lihtsalt kõik ühe poole pesad, käik on võimalik, kui pesas on nuppe.
- Arvesta, et vahel juhtub, et üks mängija saab teha mitu käiku järjest (vaata ülalviidatud kalahi reegleid: kui viimane nupp kukub oma kogumispesasse). Seega ei saa programmis alati teha min ja max tasemeid vaheldumisi. Pigem võib vahel tulla järjest mitu min või mitu max taset (kui üks mängija saab mitu käiku järjest). Soovitus realisatsiooniks: pane info selle kohta, kes teeb järgmise käigu, minimax funktsiooni argumendiks ja kasuta siis seda infot.
- Arvesta, et kui minimaxis järjest käike läbi vaatad ja uut seisu genereerid, tuleb igakord jälle minimax funktsiooni calli alguses olev seis taastada. Seda on hea teha massiivi mehaaniliselt üle kirjutades. Seega peaks sul olema mingi ajutine massiiv, kus calli algseisu olla. Seejuures ei ole aga hea mõte teha iga calli juures new-ga ajutine massiiv: see raiskaks tohutult aega. Parem on hoida ajutisi massiive kahemõõtmelise int-massiivina, kus esimene parameeter on calli sügavus. Siis on igal sügavusel oma ajutine massiiv, uusi jooksvalt ei tehta ja asjad segi ei lähe.
Seejärel täiusta veidi seisuhindajat. Ära teda aga väga aeglaseks tee, see ei tasu jälle ära. Mõned ideed:
- Kas on laual otsene võit?
- Kogumispesade kivide arvu vahe asemel on võibolla parem kasutada nende suhet (jagatist).
- Eriti lõppmängu puhul (vähe kivisid vms) võib olla tark arvestada lisaks mingi koefitsiendiga ka kivide koguarvu kummalgi poolel (suurem on parem).
- 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
.