Praktikumitöö: Kalah

Allikas: Lambda

(2005 aasta ülesandevariandi leiad siit ja 2006 sügissemestri ülesandevariandi leiad siit.) Vaata ka: Kalahi võistluse tulemused.


Ü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 14-elemendilises int massiivis, nagu mainitud programmis (kogumispesad peavad olema 6-s ja 13-s). Konkreetselt on näiteprogrammis vaja ümber kirjutada calcMove() funktsioon, tehes ta mõtlevaks. Hoopis teistsuguse kasutajaliidesega programme ei arvestata! Mõtestatud pisiparandused/täiustused liideses on siiski lubatud.
  • 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 alati ette neli käiku ja kasutab staatilise seisuhindajana lihtsalt kogumispesades olevate nuppude arvu vahet. Võid sellise nõrga programmi ka ise realiseerida, ei pea ootama 10. detsembrit.
  • Kolmas nõue: programmis peab olema realiseeritud minimax.

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

  • Peab olema realiseeritud iteratiivne sügavnemine.
  • Peab olema realiseeritud alpha-beta.
  • Peab olema tehtud väike uuring oma programmi kohta ja kirjutatud sellest uuringust pisike ülevaate-jutt. Konkreetselt tee järgmist:
    • Pane oma programm iseenda vastu mängima (kas samas koodis automaatselt, või käsitsi, vaheldumisi kahe rakendusega). Seejuures las üks programm mõtleb sügavamale kui teine (näiteks 5 ja 6 või 7, 6 ja 7 või 8 jne). Vaata, kas sügavamale vaatav programm võidab nii alustaja kui mittealustajana. Kui ei võida, suurenda sügavuse vahet, kuni sügavamale vaatav programm võitma hakkab! Trüki oma programmist välja ka otsingus läbitud seisude arv.
    • Kirjuta kogu sellest uuringust väike jutt: mis sügavustel ja sügavustevahega proovisid, kui palju seise läbi vaadati, mis oli mängu tulemus (kumb võitis mis seisuga nii alustades kui mitte alustades). Näita see jutt koos oma programmiga ette.

Soovitusi

Pane kõigepealt tähele, et sul tuleb eeskätt muuta koodis olevat calcMove() funktsiooni. See peaks välja kutsuma minimax funktsiooni, mille pead ise kirjutama. Muid olemasoleva koodi osasid tingimata muuta polegi vaja. Minimaxi progemise juures saad kasutada ka doMove(int n) ja checkEnd() funktsioone olemasolevast koodist (sul võib osutuda mugavaks teha neist oma versioonid, jättes algsed versioonid UI osa jaoks muutmata paika).

Alusta sellest, et tee valmis lihtne minimax (ilma alpha-betata) ja lihtne seisuhindaja, kus kasutatakse seisuhindamiseks oma ja vastase kogumispesades olevate kivide vahet. 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. 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.

NB! Loe siin lehe lõpus olevaid linke!

Ideid minimaxi praktiliseks programmeerimiseks:

  • Kasuta arusaamiseks loengus toodud näiteid, samuti näiteid lehe lõpus 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).
  • Tihti on kasulik, kui on rohkem käiguvariante (vähem tühje pesasid?). Samas võimaldavad tühjad pesad teha nö löögikäike. Võibolla tasub seisuhindamisel kohe vaadata, kas on löögikäike.

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. Minimaxi ei tehtaks siis üldse ühe fikseeritud sügavuseni, vaid pigem sügavuseni N ja sealt edasi ebastaabiilse seisu korral osa harusid kuni mingi maksimumpiirini M.

Alpha-beta

Püüa alpha-beta mehhanismist aru saada, kasutades loengu-koodinäiteid, allpool viidatud linke ja ühe lingitud artikli sees 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 kolme 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.

Siin leiad nüüd Kalahi võistluse tulemused.

Kasulikke linke

.

Pärit leheküljelt "http://lambda.ee/w/index.php?title=Praktikumitöö:_Kalah&oldid=8087"