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

Allikas: Lambda
Mine navigeerimisribale Mine otsikasti
← Vanem muudatus
Resümee puudub
 
(ei näidata sama kasutaja 19 vahepealset redaktsiooni)
1. rida: 1. rida:
Ü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.
(2005 aasta ülesandevariandi [[Praktikumitöö: mõtlemismäng 2005 | leiad siit]].)


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:
<b>NB! See ülesanne on arhiivimaterjal, mitte reaalne laboriülesanne! Seda ülesannet ei tule programmeerida.</b>


* kui sinu programm kasutab korrektselt minimaxi
Ü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]. Erinevalt Ecki programmist peab sinu programm suutma inimmängija vastu ise mängida (ja mitte lootusetult halvasti).
* 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.
"Kabe" all mõeldakse antud ülesandes [http://en.wikipedia.org/wiki/English_draughts Inglise (ameerika) kabet] 64-ruudulisel laual.


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


== Kahekesi programmeerimine ==
Mida nõutakse:


Viis nuppu ritta ülesannet võib programmeerida kas üksi või kahekesi. Kahekesi programmeerimise puhul saab kumbki täispunktid, tingimusel, et:
* 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.


* 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 ==
Mida ei nõuta, aga mis ei ole ka keelatud:


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


Etteantud kood koosneb neljast failist selles zip failis:
== Esialgseid, üldisi soovitusi  ==


vt ka: [[loengus tehtud kabe toorik]]


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


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.
Etteantud lähtekood baseerub siin lehel varem viidatud lähtekoodile  http://www.leepoint.net/notes-java/45examples/55games/five/five.html
* Lisa lihtnuppudele kaalud: mida lähemal vastase viimasele reale, seda parem.
 
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.
Tee katseid aja-arvestusega ja määra otsingusügavus selline, et AK klassides kunagi ei mõeldaks üle ühe sekundi.


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):
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!
<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 7  (seitse)
punkti.
 
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 ==
== Võistlus ja lisapunktid ==
61. rida: 46. 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:
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
Võistlus ei ole kohustuslik. Kuidas sellest osa võtta: ...
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 <b>FIVE</b>:
Õppejõule tuleb 2006 aasta jooksul (2007 on juba hilja!) saata emailiga järgmine info, kusjuures Subject real (emaili pealkiri) peab olema sõna <b>KABE</b>:


* autorite nimed, matriklinumbrid, emailid
* autorite nimed, matriklinumbrid, emailid
* programmi lähtekood (NB! FiveOpponent.java peab sisaldama sinu käiguvaliku-programmi)
* programmi lähtekood
* programmi valmiskompileeritud class failid  
* programmi valmiskompileeritud class failid  


83. rida: 66. rida:


* Programm ei tohi AK arvutiklassides ühtegi käiku mõelda kauem, kui ühe sekundi.
* 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.
Täiendavad detailid ilmuvad siia lehele hiljem.


== Kuidas minimaxi ja seisuhinde arvutamist programmeerida ==
== Kasulikke linke ==
 
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 llahtised 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/English_draughts inglise kabe reeglid] ja [http://en.wikipedia.org/wiki/Checkers kabe  üldiselt]
:http://en.wikipedia.org/wiki/Gomoku
:*[http://math.hws.edu/javanotes/c8/s5.htm  õpikus toodud apleti] [http://math.hws.edu/javanotes/source/Checkers.java kood]: peab kasutama aluskoodina!
:http://www.leepoint.net/notes-java/45examples/55games/five/five.html
:* http://www.ocf.berkeley.edu/~yosenl/extras/alphabeta/alphabeta.html
: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
:* http://web.archive.org/web/20040607185428/www.cs.vu.nl/~victor/thesis.html
:http://www.cs.ualberta.ca/~chinook/

Viimane redaktsioon: 14. november 2007, kell 14:28

(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

Pärit leheküljelt "http://www.lambda.ee/w/index.php?title=Praktikumitöö:mõtlemismäng&oldid=7812"