Praktikumitöö:mõtlemismäng: erinevus redaktsioonide vahel

Redaktsioon: 29. november 2006, kell 16:52

(2005 aasta ülesandevariandi leiad siit.)

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

"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

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

@@ 1. rida: / 1. rida: @@
 (2005 aasta ülesandevariandi [[Praktikumitöö: mõtlemismäng 2005 | leiad siit]].)
-Ülesandeks on lisada etteantud [http://en.wikipedia.org/wiki/Gomoku 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:
+Ülesandeks on kirjutada talutavalt mängiv kabeprogramm. <b>Programmi võib kirjutada ja esitada kas üksi või kahekesi</b>. Kabeprogramm <b>peab</b> baseeruma D.Ecki mittemõtlevale kabeprogrammile [http://math.hws.edu/javanotes/c8/s5.html | sellest peatükist]: kasuta alusena [http://math.hws.edu/javanotes/source/Checkers.java seda  lähtekoodi].
-* kui sinu programm kasutab korrektselt minimaxi
+"Kabe" all mõeldakse antud ülesandes [[http://en.wikipedia.org/wiki/English_draughts Inglise (ameerika) kabet]] 64-ruudulisel laual.
-* 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.
+== Konkreetsed nõuded ==
-NB! Sinu programm peab suutma mõistliku headusega mängida nii 10x10 kui 20x20 laual.
+Mida nõutakse:
-== Kahekesi programmeerimine ==
+* Esimene nõue oli juba kirjas: Sinu programm peab baseeruma [http://math.hws.edu/javanotes/source/Checkers.java | 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.
-Viis nuppu ritta ülesannet võib programmeerida kas üksi või kahekesi. Kahekesi programmeerimise puhul saab kumbki täispunktid, tingimusel, et:
+Mida ei nõuta, aga mis ei ole ka keelatud:
-* 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 ==
+* 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).
-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:
+== Esialgseid, üldisi soovitusi  ==
-<b>[[Media:Five.zip|Five.zip]]</b>
+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.
-<!-- <b>[http://www./lambda.ee/images/c/c9/Five.zip  Five.zip ]</b>  -->
+Seejärel asu täiustama seisuhindajat. Peamised ideed:
-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.
+* 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.
-Etteantud lähtekood baseerub siin lehel varem viidatud lähtekoodile   http://www.leepoint.net/notes-java/45examples/55games/five/five.html
+Tee katseid aja-arvestusega ja määra otsingusügavus selline, et AK klassides kunagi ei mõeldaks üle ühe sekundi.
-Võrreldes viimasega on lisatud masina käik, autoplay rezhiim ja 20x20 laua valik, samuti on vaikimisi lauasuuruseks võetud 10x10, mitte aga 9x9.
+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!
-== "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):
-<b>[[Media:FiveOpponent.zip|FiveOpponent.zip]]</b>:  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:
-<b>[[Media:FiveOpponent_weak.zip|FiveOpponent_weak.zip]]</b>:  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 ==
@@ 63. rida: / 44. rida: @@
 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.
+* Esikoha võitnud programmi autorid kumbki 15 punkti.
-* Teise koha võitnud programmi autorid kumbki 5 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: kolme päeva jooksul peale
@@ 71. rida: / 53. rida: @@
 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 <b>FIVE</b>:
+Õppejõule tuleb siis nende kolme päeva jooksul saata emailiga järgmine info, kusjuures Subject real (emaili pealkiri) peab olema sõna <b>KABE</b>:
 * autorite nimed, matriklinumbrid, emailid
-* programmi lähtekood (NB! FiveOpponent.java peab sisaldama sinu käiguvaliku-programmi)
+* programmi lähtekood
 * programmi valmiskompileeritud class failid
@@ 85. rida: / 67. rida: @@
 * 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 mängida nii mustade kui valgetega.
-* 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
+Seejärel korraldab õppejõud laekunud programmide vahel turniiri, kus edasi pääseb igast matshist parem.
-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
-== Lisaviiteid ==
-Loengus antud info ja viited: [[Media:Progpohi12.PPT|Progpohi12.PPT]]
-Parim viis-nuppu-ritta programmeerimise artikkel: http://www.renju.nu/proof/Go-Moku.pdf
-Lisaks:
-:http://en.wikipedia.org/wiki/Gomoku
-:http://www.leepoint.net/notes-java/45examples/55games/five/five.html
-:http://www.ocf.berkeley.edu/~yosenl/extras/alphabeta/alphabeta.html
-:http://web.archive.org/web/20040607185428/www.cs.vu.nl/~victor/thesis.html
-:http://www.cs.ualberta.ca/~chinook/

Praktikumitöö:mõtlemismäng: erinevus redaktsioonide vahel

Redaktsioon: 29. november 2006, kell 16:52

Konkreetsed nõuded

Esialgseid, üldisi soovitusi

Võistlus ja lisapunktid

Navigeerimismenüü

Otsing