Praktikumitöö: reversi

Allikas: Lambda

(Vanad variandid: 2005 aasta 2006 aasta, 2007 aasta ja 2007 aasta kalahi võistluse tulemused.


Ülesandeks on kirjutada talutavalt mängiv reversiprogramm. Reversi reeglitest ja muust loe nendest materjalidest: wikipedia sissejuhatus reversi oma wiki ja detailsem strateegia-õpetus. Keerulisemaid strateegianõkse ära õppida ei ole praktikumitöö jaoks vaja.

Programmi võib kirjutada ja esitada kas üksi või kahekesi.

Programm peab baseeruma T.Tammeti modifitseeritud (mittemõtlevale!) Reversi programmile, mille algversiooni kirjutas Keith Fenske: Reversi3.zip või soovi korral oluliselt täiustatud variandile Reversi4.zip.

Konkreetsed nõuded

Miinimumnõuded:

  • Esimene nõue oli juba kirjas: sinu programm peab baseeruma etteantud programmile Reversi3.zip või Reversi4.zip. Kasutajaliides tuleb jätta samaks ning positsiooni tuleb hoida samal viisil 8x8 int maatriksis. 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 detsembri alguses.
  • 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

Esimene oluline ja lihtne tähelepanek: sul ei ole vaja muuta enamust selle programmi koodist: Reversi3.zip. Vaja on muuta funktsiooni findBestMove (pluss lisada vajalikke abifunktsioone ja muutujaid ja massiive, mida täiustatud findBestMove kasutama hakkab).

Teine soovitus: tunduvalt lihtsam on alustada koodi täiustamist uuest variandist Reversi4.zip ,kuhu on juba lisatud käikude genereerija, käigu tegija ja lihtsakoeline seisu hindaja. Ka selles variandis on vaja muuta funktsiooni findBestMove, mis on aga oluliselt erineva sisuga kui eelmise Reversi3 variandi findBestMove.

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

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

  • 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.
  • Programmis peab olema realiseeritud alustaja valik: kas alustab programm või vastane (inimene, teine programm). Selleks pead veidi muutma kasutajaliidest ja arvestama alustajaga käikude rehkendamisel.
  • Programm peab kasutama eelpool viidatud näiteprogrammi (Reversi3 või Reversi4: kasutajaliidesed samad) kasutajaliidest.

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

Kasulikke linke

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