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.

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.

Seisuhindaja ja minimaxi täiustamine

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).

Programmi headuse parandamiseks tasuks ilmselt minimaxi selliselt täiustada, et kui lõppseis (kus tehtaks staatilist hindamist) on ebastabiilne (näiteks on võimalik käia oma tühja pesasse ja vastasel on teiselpool vastas nuppe, nö löök, või on võimalik käia viimane kivi kogumispesasse), analüüsida seisu edasi, (sügavamale) kuni seis on stabiilne.

Alpha-beta

Püüa alpha-beta mehhanismist aru saada, kasutades loengu-koodinäiteid, viidatud juttu ja selle juures olevat simulatsiooni.

Realiseerimise juures arvesta, et alpha-beta töötab hästi, kui enamasti vaadatakse algul paremaid käike. Seetõttu on kasulik käikude läbivaatamise tsükkel nii ümber teha, et tõenäoliselt paremad käigud (need, mis lõpeva oma kogumispesas või tühjal väljal, kus vastasel on teiselpool nuppe) oleks kõigepealt vaadatud. Seda optimeeringut ei ole aga enam mõtet teha, kui jõuad viimasele sügavusele.

Iteratiivne sügavnemine

Siin eeldatakse, et sinu programm kontrollib aega: et ei kulutaks käigule kokku rohkem, kui 1 sekund.

Tee algul näiteks otsing sügavuseni 5 (see peaks olema väga kiire), salvesta parim leitud käik. Kui aega veel jätkub, tee otsing sügavuseni 6. Kui õnnestus lõpuni teha, salvesta seni parima käiguna 6-sel sügavusel saadud käik ja mine edasi 7-se sügavuse juurde jne. Kui ei õnnestunud kogu puud läbi käia (kell kukkus) siis kasuta viimatileitud parimat käiku. Idee niisiis selles, et mitte kasutada poolikult läbikäidud otsipuude tulemusi.

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

.