Praktikumitöö:mõtlemismäng

(2005 aasta ülesandevariandi leiad siit.)

NB! See ülesanne on arhiivimaterjal, mitte reaalne laboriülesanne! Seda ülesannet ei tule programmeerida.

Ülesandeks on kirjutada talutavalt mängiv kabeprogramm. Programmi võib kirjutada ja esitada kas üksi või kahekesi. Kabeprogramm peab baseeruma D.Ecki mittemõtlevale kabeprogrammile sellest peatükist: kasuta alusena seda lähtekoodi. Erinevalt Ecki programmist peab sinu programm suutma inimmängija vastu ise mängida (ja mitte lootusetult halvasti).

"Kabe" all mõeldakse antud ülesandes Inglise (ameerika) kabet 64-ruudulisel laual.

Konkreetsed nõuded

Mida nõutakse:

• Esimene nõue oli juba kirjas: Sinu programm peab baseeruma Ecki programmikoodile.
• Teine nõue: juhendaja peab saama programmiga kergelt ja mugavalt mängida, kas siis graafilise kasutajaliidesega, või käsurealt (a la tikumäng).
• Kolmas nõue: programm peab mängima talutavalt hästi, kui ajapiiranguks on üks sekund käigu kohta. Talutavalt hästi tähendab seda, et kas (a) juhendaja ei suuda kiirelt mängides programmi võita või (b) juhendaja tuvastab, et programm teeb reeglina elementaarselt mõistlikke käike (näiteks, leiab paarikäigulised, lihtsad kombinatsioonid) ja reegline ei tee väga halbu käike, nagu nuppude niisama vastasele ette käimine, elementaarsete ähvarduste takistamata jätmine jne.
• Neljas nõue: programmis peab olema realiseeritud minimax alpha-beta täiustusega.

Mida ei nõuta, aga mis ei ole ka keelatud:

• Nagu mainitud, on see Sinu otsustada, kas jätkad Ecki kasutajaliidese tarvitamist apletina, teed apleti ümber graafiliseks omaette-rakenduseks või teed ilma graafikata käsurea-rakenduse, mis trükib seisu välja tähtede ja numbritega ja küsib mängijalt käike a la tikumäng.
• Programm ei pea tingimata lubama valida, kumba värviga mängija mängida tahab.
• Programm ei pea tingimata lubama valida , kui mitu sekundit masin mõelda võib (sel juhul peab piiriks olema üks sekund).

Esialgseid, üldisi soovitusi

vt ka: loengus tehtud kabe toorik

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. Uuri lihtsalt, kas programm leiab üles ühekäigulise võidu, kahekäigulise võidu jne, ning kas ta suudab blokeerida sinu ühekäigulise võidu, kahekäigulise võidu jne.

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 2006 aasta jooksul (2007 on juba hilja!) saata emailiga järgmine info, kusjuures Subject real (emaili pealkiri) peab olema sõna KABE:

• autorite nimed, matriklinumbrid, emailid
• programmi lähtekood
• programmi valmiskompileeritud class failid

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 suutma mängida nii mustade kui valgetega.

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

Täiendavad detailid ilmuvad siia lehele hiljem.

Kasulikke linke

• inglise kabe reeglid ja kabe üldiselt
• õpikus toodud apleti kood: peab kasutama aluskoodina!
• 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