ITI0011-2015:Gomoku

Tagasi kursuse lehele

Tähtaeg: 22. mai 2015.

Ülesanne täpsustub. Üldine osa on paigas. Kindlasti uueneb etteantud programm. Kuigi struktuur jääb samaks - kui alustad selle versiooniga, saad hiljem lihtsalt kopeerida oma koodi uuemasse versiooni.

Ülesande lühikirjeldus

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

Konkreetselt nõutakse, et sinu programm peab rõhuval enamikul juhtudel võitma õppejõu poolt etteantavat Gomoku võrdlusprogrammi, eeldades, et mõlemal on iga käigu jaoks aega üks sekund. 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.

Peate kirjutama StudentStrategy.getMove() sisu selliselt, et see mängiks piisavalt hästi. Võite sinna faili teha uusi meetodeid. Väliste librarite ja täiendavate klasside kasutamine ei ole lubatud! Ehk siis kogu koodi peate sellesse faili panema.

Kaitsma tulles peab strateegia töötama viimase versiooniga antud rakendusest. Üldiselt midagi olulist teie jaoks ei muutu. Üks konkreetne näide, mis võib muutuda, on ajapiirang. Hetkel füüsilist ajapiirangut rakenduses pole. Süsteem prindib välja tehtud käigud ja selleks kulunud aja. Kui käik võtab 1.1 sekundit, pole otseselt probleemi. Kui käik võtab 2 sekundit või kauem, tuleb miskit ette võtta.

Loe täpsemalt: #Punktide saamine, #Lähtekoodi seletus

Rakendus

Selleks, et ülesannet realiseerida, on teil ette antud GUI koos vastaste strateegiatega. Teie peate selles muutma ühte faili: StudentStrategy.java. See peatükk kirjeldab rakendust ja selle käimasaamist.

Viimane versioon 0.5 GUI-st: Meedia:Gomoku_v0.5.zip (seisuga 11. dets 2014)

Uuendused:

0.5:

• skoori arvestamine (mängijate võidud-viigid-kaotused loetakse kokku)
• esimese mängija käigu aja arvestamine hakkab sellest hetkest, kui laud jms objektid on loodud (ehk siis mõõdetakse reaalselt strateegia failis getMove() meetodi käivitusaega).

0.4:

• 2013. aasta turniiri võitja fix
• lisatud 20x20 laud
• OpponentStrong ja OpponentWeak tehtud lihtsamaks (teevad kiiremini käigu)
• veel mingeid bugifixe

0.3:

• 2013. aasta turniiri võitja (OpponentWinner)

0.2:

• Lisatud vastased OpponentWeak ja OpponentStrong
• Nimetatud vastased pole veel lõplikud. Küll võib arvestada, et 10p saamiseks peate vähemalt OpponentWeak'ist jagu saama. Võib juhtuda, et OpponentWeak ise muutub natuke lihtsamaks.

Käivitamine Eclipse'is

Zip-fail tuleb lahti pakkida näiteks workspace'i sisse (tekib workspace'i alla gomoku kaust). Nüüd eclipse'is file -> import -> General->Existing projects into Workspace -> nüüd valite kausta kettal ja finish. Peaks tekkima projekt nimega "gomoku".

Alternatiivne käivitamine

Kui eelmine meetod ei tööta, siis tuleb failid käsitsi kopeerida:

• Tõmba alla zip-fail
• tee Eclipse'is uus Java projekt
• kopeeri kõik zip-failis "gomoku/src" kaustas olevad failid loodud projekti "src" kausta (loodud projekti asukoha leiad näiteks projekti peal parem klikk - properties -> Resource, seal on "Location", mis näitab asukohta kettal).
• paki zip-failis olev "lib/strat_impl.jar" fail kuskile kettale lahti. Näiteks projekti alla loo uus kaust "lib" ja kopeeri sinna.
• projekti peal parem klikk - properties -> Java Build Path -> Libraries -> "Add External JARs" nupp (kui panid projekti alla, siis võta "Add JARs...")
• otsi avanevas dialoogis strat_impl.jar fail üles ja "OK" või "Open"

Nüüd peaks Main.java failist projekt käivitatav olema.

Andke teada, kui projekti importimine ei õnnestu.

---

IntelliJ IDE-l tundub olevat probleem meetodiga

     initializeGameStatusListener() 

Sest seal kasutuses lambda (täpne error siis):

     Lambda expressions are not supported at this language level.

Stacki juhendamisel läksin siis

     File -> Project Structure (Ctrl+Alt+Shift+S)

ning "Project" tabi alt sai muuta Language Levelit. IntelliJ-l on see vaikimisi 6 peal kuid lambdade jaoks peab 8-ks muutma nähtavasti.

---

Kui tekib JavaFX-iga viga, mis ütleb midagi keelatud klasside kohta, võib abi olla sellest: http://stackoverflow.com/questions/9266632/access-restriction-is-not-accessible-due-to-restriction-on-required-library#answer-9586411

---

Kui sul on tekkinud mõni probleem ja oled selle ära lahendanud, palun saada email: ago.luberg @ ttu.ee . Saan siis selle ka siia lisada.

Lisapunktid

Kes leiab mõne vea ja selle jaoks ka koodiparanduse antud rakenduses, võib teenida lisapunkte. Ka on oodatud kõiksugu ettepanekud parendamise osas (kasutajamugavus, väljanägemine, töökindlus, turvalisus jms).

Punktide saamine

Aja jooksul tekib siia lehele erineva tugevusega vastased, kellest peate jagu saama. Vastaseid on 3:

• Nõrgema vastase (OpponentWeak) alistamine annab minimaxiga annab 8p,
• Tugeva alistamine (OpponentStrong) minimaxiga annab 10p
• Eelmise aasta võitja alistamine annab minimaxiga 13p.

Minimaxi asemel võib olla ka alpha-beta või mõni muu variant minimaxist, mis kärbib otsingupuud.

Kui võidate nõrgemat vastast kasutama minimax algoritmi, võite saada kuni 5p. Eeldus on, et mängija siiski suudab tuvastada erinevaid olukordi (seda kontrollib õppejõud käsitsi tema vastu mängides).

Punktid lähevad arvesse juhul, kui võidate vastast vähemalt 60% juhtudest. Ehk siis kaitsmisel paneme teie koodi mängima vastasega ja teeme 10 mängu. Et saada 10 punkti, peab teie kood tugevamat vastast vähemalt kuues mängus võitma. 8 punkti saamiseks peab teie kood nõrgemat vastast vähemalt 6 mängus võitma.

Osaline võitmine

Juhul, kui teie kood ei võida 60% juhtudest, aga mängib vähemalt keskmiselt paremini vastasest (arvestatuna sedasi, et kaotus on 0p, viik 1p, võit 2p. Summeerime punktid kokku ning tulemus peab olema üle 50%), on tulemuseks punktisumma, mis korrutatakse läbi mängupunktide %-ga.

Ehk siis, kui teie programm võidab nõrgemat vastast 10-st mängust 2 korda ja 7 korda mängib viiki, siis oleks teie mängude punktisumma 2*2 + 7*1 = 11. Maksimaalne võimalik oleks 20 punkti (10*2). Seega oleks teie punktisumma 8 p * 55% = 4.4 (ümardatuna 4). Kui võidate näiteks 4 mängu ja 6 teete viiki, oleks mängude punktisumma 4*2 + 6*1 = 14. Ülesande eest oleks punktisumma: 8 p * 70% = 5.6 (ümardatuna 6).

Võistlus ja lisapunktid

NB! Plagiaadi esitamisel saavad selle kõik autorid ülesande eest 0 punkti

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: 22. maiks (k.a) tuleb saata viimane versioon StudentStrategy.java failist (mida võib soovi korral veel täiendada) õppejõu emaili peale.

Võistlusel võib osaleda kahekesi.

Õppejõule tuleb saata emailiga järgmine info, kusjuures Subject real (emaili pealkiri) peab olema sõna GOMOKU:

• autorite nimed, matriklinumbrid, emailid
• StudentStrategy.java 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.
• 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 seisu ja käigul oleva mängija (ehk siis selle mängija, kellena teie strateegia mängib). Vt täpsemat juhendit sektsioonist #Lähtekoodi_seletus #Lähtekoodi_seletus
• Programm ei tohi kasutada võrguühendust
• Programm ei tohi kasutada väliseid teeke (või siis kui kopeerite lähtekoodina StudentStrategy.java sisse).
• Programm võib kasutada erinevaid lõimeid (thread), kuigi peab arvestama, et arvuti, milles turniir toimub, ei pruugi olla kasutada rohkem kui ühte. Seega, te ei saa eeldada, et teil on multiprotsessoriga arvuti.
• Et välistada suurte andmebaaside kaasapanemist, peab lähtekoodi faili suurus olema maksimaalselt 1 MB (mis tegelikult on päris suur maht, ehk siis ühtteist te sinna saate soovi korral panna).
• Programm ei tohi tekitada mängimise ajal faile kettale (küll aga võib kasutada mälu "piiramatult", arvestades, et mälu võib olla limiteeritud mõnesaja megabaidiga).
• Võistlus kahe vastase vahel toimub reeglina ühe programmi käivitamise jooksul. See tähendab seda, et kui vastased mängivad 10 mängu, siis kõik need mängud käivitatakse sama sessiooni jooksul. StudentStrategy objekt instantsieeritakse igal mängul. Küll aga saate staatiliste muutujatega salvestada infot läbi erinevate mängude. Seega on teil võimalik näiteks õppida eelmistest mängudest.

Õppejõud korraldab laekunud programmide vahel turniiri, kus edasi pääseb igast matšist 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.

Õppejõud jätab õiguse teha korralduse poolel muudatusi. Sõltuvalt esitatud tööde arvust, võib korraldada ka alagruppidega turniiri, kus kohe esimese mängu kaotamise korral välja ei kuku. Aga täpsemat infot saab jagada siis, kui on teada, palju osalejaid on.

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 võid vaadata praktikumides tehtud seisuhindamisi/minimaxi ja .

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 lisaviited #Lisaviited

Lähtekoodi seletus

Tuleb implementeerida interface'i: <source lang="java"> package gomoku;

/**

* @author Ago
*
* Interface for computer strategy.
*/

public interface ComputerStrategy { /** * Takes the game state and return the best move * @param board Board state * @param player Player indicator. Which player's * strategy it is. Possible values: SimpleBoard.PLAYER_*. * @return A location where to make computer's move. * * @see SimpleBoard * @see Location */ public Location getMove(SimpleBoard board, int player);

/** * Name will be shown during the play. * This method should be overridden to * show student's name. * @return Name of the player */ public String getName(); } </source>

Objekt, mis antakse "getMove" meetodile kaasa:

<source lang="java"> package gomoku;

/**

* Simple 2-dimensional presentation
* of the game board.
* Every cell in the board is represented
* by one integer, the Values are either
* PLAYER_BLACK, PLAYER_WHITE or EMPTY.
* This object also knows the size of the board
* and the last move (Location object).
* 
* @author Ago
* @see Location
*/

public class SimpleBoard {

/** * Cell value for black player's piece */ public static final int PLAYER_BLACK = 1;

/** * Cell value for white player's piece */ public static final int PLAYER_WHITE = -1;

/** * Empty cell value */ public static final int EMPTY = 0;

/** * The height of the board. * Indicates the number of rows. */ private int height = -1; /** * The width of the board. * Indicates the number of columns. */ private int width = -1;

private int[][] board;

/** * Returns the height (number of rows) * of the board. * @return Number of rows */ public int getHeight() { return height; }

/** * Returns the width (number of columns) * of the board. * @return Number of columns */ public int getWidth() { return width; }

/** * Returns 2-dimensional * array of integers with values * PLAYER_WHITE, PLAYER_BLACK or EMPTY. * The values correspond to * White player's piece, * Black player's piece, * or an empty cell accordingly. * @return */ public int[][] getBoard() { return board; }

/** * Constructor to instantiate the board. * @param simpleBoard 2-dimensional * array for the board. */ public SimpleBoard(int[][] simpleBoard) { height = simpleBoard.length; if (height > 0) width = simpleBoard[0].length; board = simpleBoard; } }

</source>

Teil tuleb "getMove" meetodis tagastada käigu asukoht Location objektina:

<source lang="java"> package gomoku;

/**

* @author Ago
* Location on the board, 0-based.
*/

public class Location { /** * Index of the row. */ private final int row; /** * Index of the column. */ private final int column;

public Location(int row, int column) { this.row = row; this.column = column; }

/** * @return Row index */ public int getRow() { return row; }

/** * @return Column index */ public int getColumn() { return column; }

@Override public String toString() { return String.format("(%d, %d)", row, column); } } </source>

Näidis random strateegia: <source lang="java"> /**

* A random strategy implementation
* for the gomoku game.
* @author Ago
*
*/

public class RandomStrategy implements ComputerStrategy {

@Override public Location getMove(SimpleBoard board, int player) { int[][] b = board.getBoard(); while (true) { // let's loop until we find an empty spot int row = (int)(Math.random() * board.getHeight()); int col = (int)(Math.random() * board.getWidth()); if (b[row][col] == SimpleBoard.EMPTY) { // if empty, let's return this location return new Location(row, col); } } }

@Override public String getName() { return "Random computer strategy"; }

} </source>

Tudeng peab täiendama järgmist klassi: StudentStrategy.java: <source lang="java"> package gomoku;

public class StudentStrategy implements ComputerStrategy {

@Override public Location getMove(SimpleBoard board, int player) { // let's operate on 2-d array int[][] b = board.getBoard(); for (int row = b.length - 1; row >= 0; row--) { for (int col = b[0].length - 1; col >= 0; col--) { if (b[row][col] == SimpleBoard.EMPTY) { // first empty location return new Location(row, col); } } } return null; }

@Override public String getName() { return "Tudengi nimi"; }

}

</source>

Praegune tudengi kood hakkab alt paremalt järjest nuppe mööda rida käima (kui on vaba koht).

Lisaviited

Loengu-/praktikumimaterjalid eelmisest aastast: Loeng minimax, alpha-beta, ITI0011:praktikum 13, ITI0011:praktikum 14

Lisaks:

• http://en.wikipedia.org/wiki/Gomoku
• 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/