Praktikumitöö: mõtlemismäng 2005

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

Ülesandeks on lisada etteantud viis-nuppu-ritta programmile nö mõtlemiskomponent: jupid programmi, mis leiavad etteantud seisust võimalikult hea käigu. Nende juppide lisamise tulemusena peab sinu programm mängima viit nuppu ritta nö "mõistliku headuse" tasemel.

Konkreetselt nõutakse, et sinu programm peab rõhuval enamikul juhtudel võitma õppejõu poolt etteantavat viis-nuppu-ritta võrdlusprogrammi, eeldades, et mõlemal on iga käigu jaoks aega üks sekund. See võrldusprogramm tuleb - ilma lähtekoodita - siia lehele 1. detsembriks. Igal juhul on garanteeritud, et:

kui sinu programm kasutab korrektselt minimaxi
oled programmeerinud mõistliku lihtsa seisuhinde (vaatab viieste olemasolu, loeb kokku lahtised neljased, poollahtised neljased, lahtised kolmesed)

siis sinu programm võidab etteantud võrdlusprogrammi, kui mõlemal on ajapiir üks sekund käigu kohta.

NB! Sinu programm peab suutma mõistliku headusega mängida nii 10x10 kui 20x20 laual.

Sisukord

1 Kahekesi programmeerimine
2 Etteantud lähtekood
3 "auto" nupp ja võrdlusprogramm
4 Võistlus ja lisapunktid
5 Kuidas minimaxi ja seisuhinde arvutamist programmeerida
6 Lisaviiteid

Kahekesi programmeerimine

Viis nuppu ritta ülesannet võib programmeerida kas üksi või kahekesi. Kahekesi programmeerimise puhul saab kumbki täispunktid, tingimusel, et:

Programmi ettenäitamisel on kohal mõlemad tudengid. Kui ühte pole, siis tema lihtsalt punkte ei saa.
Kumbki tudeng saab programmi tekstist aru (st ka nendest osadest, mida tema programmeerinud ei olnud). Kui juhendajale tundub, et üks tudeng ei saa programmi tekstist hästi aru, siis ta jätab sellele tudengile punktid panemata või paneb lihtsalt vähem.

Etteantud lähtekood

Sinu programm peab olema järgmise etteantud koodi edasiarendus. Mingeid muid alternatiive - üleni isetehtud või mujalt saadud GUI või muud klassid - ei aktsepteerita.

Etteantud kood koosneb neljast failist selles zip failis:

Five.zip

Kood on kohe edukalt kompileeritav ja töötav. Paraku mängib ta väga halvasti: käib alati esimesele vabale kohale. Selleks, et ta paremini mängiks, pead lisama funktsiooni best_move (failis FiveLogic.java) minimaxi kasutamise ja mõistliku seisuhinde (st kirjutama need funktsioonid lisaks ja kutsuma neid best_move seest välja). Mingeid muid funktsioone või kasutajaliidese nüansse muutma ei pea.

Etteantud lähtekood baseerub siin lehel varem viidatud lähtekoodile http://www.leepoint.net/notes-java/45examples/55games/five/five.html

Võrreldes viimasega on lisatud masina käik, autoplay rezhiim ja 20x20 laua valik, samuti on vaikimisi lauasuuruseks võetud 10x10, mitte aga 9x9.

"auto" nupp ja võrdlusprogramm

"auto" nupule vajutamise korral hakkab programm täisautomaatselt mängima: toimub võistlus funktsiooni best_move (failis FiveLogic.java) ning funktsiooni best_opponent_move (failis FiveOpponent.java) vahel. Inimmängija rolli võtab siis best_opponent_move.

Ka best_opponent_move mängib väga halvasti: ta püüab samuti käia esimesele vabale ruudule, alustades aga paremalt alt, mitte vasakult ülalt, nagu best_move.

Järgnevas zip failis antud võrdlusprogramm kujutab endast valmiskompileeritud klass-faili FiveOpponent.class, millega pead algul isekompileeritud FiveOpponent.class faili lihtsalt asendama (st kustutad kataloogist nii FiveOpponent.class kui FiveOpponent.java ning paned asemele siit lehelt laetud FiveOpponent.class):

FiveOpponent.zip: paki zip fail lahti ja saad faili FiveOpponent.class

Siintoodud FiveOpponent mõtleb kaks käiku ette (valge - tema - käik, ja siis musta - vastase, st sinu programmi käigud). Seisuhinnangus loeb ta kokku viiesed, lahtised neljased, kolmesed, kahesed, pluss poollahtised neljased ja kolmesed, ning annab igale sellisele ähvardusele/võimalusele mingi koefitsiendi. Alfa-beetat ta ei tee, ühtegi optimeerimist pole programmeeritud: seetõttu töötab ta ka üpris aeglaselt.

Sinu programm peab seda nigelat FiveOpponent.classi üldjuhul siis võitma.

Kui siiski selgub, et Sinu programm kipub FiveOpponent.classile alla jääma, võid kasutada veel nõrgemat FiveOpponent.class faili:

FiveOpponent_weak.zip: paki zip fail lahti ja saad faili FiveOpponent.class

Viimane fail - FiveOpponent_weak.zip - mõtleb ainult ühe käigu (valge käik) ette. Kui sinu programm seda eriti nõrka FiveOpponenti reeglina võidab, aga eelmisena toodud kahte-käiku-mõtlevat mitte, saad siiski praktikumitulemuseks 8 (kaheksa) punkti võimalikust kümnest.

NB! Kontrolli, et sinu programm ei mõtleks AK arvutiklasside masinates ühte käiku 10x10 laual kunagi üle ühe sekundi. Pikemat mõtlemist käsitletakse lihtsalt vigase töötamisena.

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 10 punkti.
Teise koha võitnud programmi autorid kumbki 5 punkti.

Võistlus ei ole kohustuslik. Kuidas sellest osa võtta: kolme päeva jooksul peale praktikumitähtaja möödumist tuleb teha oma programmist versioon, kus varem best_move funktsioonis sisaldunud kood kopeeritakse funktsioon best_opponent_move failis FiveOpponent.java. Viimane fail peab olema täiesti sõltumatu teistest programmi lähtekoodi-failidest (st peab ise kompileeruma).

Õppejõule tuleb siis nende kolme päeva jooksul saata emailiga järgmine info, kusjuures Subject real (emaili pealkiri) peab olema sõna FIVE:

autorite nimed, matriklinumbrid, emailid
programmi lähtekood (NB! FiveOpponent.java peab sisaldama sinu käiguvaliku-programmi)
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 10x10 kui 20x20 laual.
Programm peab suutma käia ka siis, kui etteantud laud on tühi (alustaja must).
Programm saab ette laua (vt praegust best_opponent_move) ja otsustab ise, kelle käik on, ning annab tagasi ühte integeri kodeeritult (vt praegust best_opponent_move) käigu sellele käijale (st suudab leida nii parima valge kui musta käigu, olenevalt, kelle käik on).

Seejärel korraldab õppejõud laekunud programmide vahel turniiri, kus edasi pääseb igast matshist parem. Kaks programmi pannakse omavahel mängima, vaheldumisi mustade ja valgetega, kuni üks programm jõuab teisest 2 punkti võrra ette (kaotus ja viik 0 punkti, võit 1 punkt). Mängitakse 10x10 laual. Kui kümne partiiga võitjat ei selgu, mängitakse edasi 20x20 laual. Kui seal ka kümne partiiga võitjat ei selgu, valitakse võitja loosiga.

Täiendavad detailid ilmuvad siia lehele hiljem.

Kuidas minimaxi ja seisuhinde arvutamist programmeerida

Alusta sellest, et tee valmis lihtne minimax (ilma alpha-betata) ja lihtne seisuhindaja, kus vaadatakse ainult seda, kas mõni osapooltest on võitnud: selleks saad kopeerida sisu funktsioonist getGameStatus (failis FiveLogic.java).

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 viiest laual (otsene võit)?
Loe kokku üleni lahtised neljased mõlema jaoks.
Loe kokku poollahtised neljased mõlema jaoks.
Loe kokku üleni lahtised kolmesed mõlema jaoks.
Võibolla ka: Loe kokku poollahtised kolmesed.
Võibolla ka: Loe kokku lahtised kahesed.

Seisuhinne arvuta kokku nendest parameetritest, pannes võimsamatele ähvardustele kõvema koefitsiendi (üleni lahtine neljane on praktiliselt juba võit, lahtine kolmene aga veel mitte). Mõistlik võib olla viimati käija värvi ja järgmisena käjia värvi ähvardustele erinevate koefitsientide panemine: järgmisena käija ähvardused on hullemad (kui ta juba kaotanud pole)!

Debugi täiustatud seisuhinne ära, mängides jälle ise vastu.

Tee katseid aja-arvestusega ja määra otsingusügavus selline, et AK klassides kunagi ei mõeldaks üle ühe sekundi (NB! 20x20 laual on otsisügavus ilmselt väiksem, kui 10x10 laual).

Nüüd peaks sinu programm olema piisavalt OK, võitmaks võrdlusprogrammi.

Ideid, kuidas programmi veel palju paremaks teha:

Vii sisse alpha-beta (modifitseeri minimaxi). Programm peaks leidma sama käigu, mis minimaxiga, aga rutem.
Sundkäikude puhul (neljase sulgemine, võibolla ka lahtise kolmese otsa sulgemine) ära otsi kõiki muid alternatiive läbi, vaid vaata ainult sundkäike.
Vali võimalikeks käikudeks ainult ruute, mis on mõne täidetud ruudu ligidal.
Tee seisuhindamist selliselt, et enne lõppsügavusele jõudmist tehakse vahepealse seisu seisuhinne ja antakse see lõppsügavusele ette. Lõppsügavuse seis erineb aga ainult ühe välja poolest, seega saab hinde arvutada nii, et vaatad läbi ainult viimase käigu ümbruskonna ja modifitseerid üks aste kõrgemal saadud seisuhinnet vastavalt.
Sundkäikude puhul, kus ainult üks valik, analüüsi sügavamale: unikaalne sundkäik ju ei laienda puud! Mh otsi sundkäikude ahelad lõpuni välja.
Loe läbi lisaviidetes antud artikkel: http://www.renju.nu/proof/Go-Moku.pdf