Gomoku-eng - Redigeerimiste ajalugu

Anier: /* Lisaviiteid */

2010-12-01T16:01:28Z

Lisaviiteid

←Vanem redaktsioon		Redaktsioon: 1. detsember 2010, kell 18:01
126. rida:		126. rida:
	* Study appendixes		* Study appendixes

	== ~~Lisaviiteid~~ ==		== Appendixes ==

	~~Loengus antud~~ info ~~ja viited~~: [[Media:Progpohi12.PPT\|Progpohi12.PPT]]		Lecture info and references: [[Media:Progpohi12.PPT\|Progpohi12.PPT]]

	~~Lisaks~~:		In addition:
	:http://en.wikipedia.org/wiki/Gomoku		:http://en.wikipedia.org/wiki/Gomoku
	:http://www.leepoint.net/notes-java/examples/games/five/five.html		:http://www.leepoint.net/notes-java/examples/games/five/five.html

Anier: /* How to implement minimax and the evalutaion function */

2010-12-01T16:01:00Z

How to implement minimax and the evalutaion function

←Vanem redaktsioon		Redaktsioon: 1. detsember 2010, kell 18:01
114. rida:		114. rida:
	Try do debug by plaing against it.		Try do debug by plaing against it.

	~~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~~).		Experiment with computation time and figure out an optimal search depth so it will never compute for more than 1 second. (NB! 20x20 board will probably have smaller search depth than 10x10)

	~~Nüüd peaks sinu programm olema piisavalt~~ OK, ~~võitmaks võrdlusprogrammi~~.		Yout program should be OK now, to win the benchmark opponent.

	~~Ideid, kuidas programmi veel palju paremaks teha~~:		Other ideas to make it better:

	* ~~Vii sisse~~ alpha-beta (~~modifitseeri minimaxi~~). ~~Programm peaks leidma sama käigu, mis minimaxiga, aga rutem~~.		* Implement alpha-beta (modify minimax). The program should find the same move faster.
	* ~~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~~.		* Don't loof for alternative moves if a move is forced (closing a set of four, open three, etc.)
	* ~~Vali võimalikeks käikudeks ainult ruute, mis on mõne täidetud ruudu ligidal~~.		* Compute turns near moves already made.
	* ~~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.		* Upon forced moves, where you have a single choice - search deeper. A unique forced move doesn't explode the search space. Try to search to the end of the search tree.
	* 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.		* Study appendixes
	* ~~Loe läbi lisaviited~~

	== Lisaviiteid ==		== Lisaviiteid ==

Anier: /* Kuidas minimaxi ja seisuhinde arvutamist programmeerida */

2010-12-01T15:55:38Z

Kuidas minimaxi ja seisuhinde arvutamist programmeerida

←Vanem redaktsioon		Redaktsioon: 1. detsember 2010, kell 17:55
93. rida:		93. rida:
	TBD		TBD

	== ~~Kuidas minimaxi ja seisuhinde arvutamist programmeerida~~ ==		== How to implement minimax and the evalutaion function ==

	~~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).		Begin by implementing a simple minimax (without alpha-beta) and an evaluation function that determines if either player has won. You can re-use getGameStatus() function from FiveLogic.java

	~~Debugi see programm ära, mängides talle ise vastu~~. ~~Tee katseid nii otsinguga sügavuseni kaks~~,		Debug the program by playing with it yourself. Experiment with search depths two, three, four, etc. Until search time gets too long. Explore if the program can detect one-turn win, two, etc. Can it block them.
	~~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~~:		Start improving the evaluation function with the main ideas:

	* ~~Kas on viiest laual~~ (~~otsene võit~~)?		* Detect sets of five (win)?
	* ~~Loe kokku üleni lahtised neljased mõlema jaoks.~~		* Fully open fours for both
	* ~~Loe kokku poollahtised neljased mõlema jaoks.~~		* Half open fours for both
	* ~~Loe kokku üleni lahtised kolmesed mõlema jaoks.~~		* Fully open threes for both
	* ~~Võibolla ka: Loe kokku poollahtised kolmesed.~~		* Maybe halfopen twos
	* ~~Võibolla ka: Loe kokku lahtised kahesed.~~		* Maybe open twos

	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)!		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~~.		Compute the evaluation value given these parameters giving a larger coefficient for a greater threat (Open set of four is practically a win, open three is soon to be). It might be reasobable to give different coefficients for both players. The player with the next turn will be assigned a greater threat.

			Try do debug by plaing against it.

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

Anier: /* Võistluse tulemused */

2010-12-01T15:49:38Z

Võistluse tulemused

←Vanem redaktsioon		Redaktsioon: 1. detsember 2010, kell 17:49
90. rida:		90. rida:
	The teacher will make a tournament between the submitted programs in playoff format. Losing player will fall out. The programs will play for white and black players in rotation until one program leads by 2 points (loss and tie is 0 points, 1 point for win). 10 games will be played - if winner cannot be determined, it will be chosen randomly.		The teacher will make a tournament between the submitted programs in playoff format. Losing player will fall out. The programs will play for white and black players in rotation until one program leads by 2 points (loss and tie is 0 points, 1 point for win). 10 games will be played - if winner cannot be determined, it will be chosen randomly.

	== ~~Võistluse tulemused~~ ==		== Tournament results ==
	TBD		TBD

Anier: /* Tournament and extra points */

2010-12-01T15:49:27Z

Tournament and extra points

←Vanem redaktsioon		Redaktsioon: 1. detsember 2010, kell 17:49
76. rida:		76. rida:
	* precompiled class files		* precompiled class files

	~~Sisulised nõuded~~:		Principal demands:

	* ~~Teie programmi mõtlemiskomponendid peavad olema üleni teie enda kirjutatud~~. ~~Artikleid lugeda ja teisi programme uurida tohib, neid otse kopeerida aga mitte~~.		* The AI has to written by you. You can research articles and study other programs.
	* ~~Kui õppejõul tekib eelmise punkti osas kahtlus, siis ta uurib autoritelt asja edasi, ning kahtluse püsimisel diskvalifitseerib kahtlase programmi võistluselt~~.		* The teacher can ask additional questions if in suspicion and can disqualify the submission.

	~~Tehnilised nõuded~~:		Technical demands:

	* ~~Programm ei tohi AK arvutiklassides ühtegi käiku mõelda kauem, kui ühe sekundi~~.		* The progam can't compute a turn longer than 1 second.
	* ~~Programm peab suutma mängida nii~~ 10x10 ~~kui~~ 20x20 ~~laual~~.		* Should be able to play on 10x10 and 20x20 boards.
	* ~~Programm peab suutma käia ka siis, kui etteantud laud on tühi~~ (~~alustaja must~~).		* Program should be able to make a turn if the board is empty (black starts).
	* ~~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)~~.		* Program will be given a board and should be able to decide, whos turn it is. Then return an encoded integer representing the move for next players turn.

	~~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~~		The teacher will make a tournament between the submitted programs in playoff format. Losing player will fall out. The programs will play for white and black players in rotation until one program leads by 2 points (loss and tie is 0 points, 1 point for win). 10 games will be played - if winner cannot be determined, it will be chosen randomly.
	~~ka kümne partiiga võitjat ei selgu~~, ~~valitakse võitja loosiga~~.

	== Võistluse tulemused ==		== Võistluse tulemused ==

Anier – 1. detsember 2010, kell 15:40

2010-12-01T15:40:39Z

Uus lehekülg

The goal is to implement the artificial intelligence (AI) component for the [http://en.wikipedia.org/wiki/Gomoku Gomoku] game. You have to implement specific parts of the program, that compute the best possible move given a game status on board. The AI has to be able to perform at "resonable" level.

Specific demands follow. Your AI must win the AI provided by the teacher in majority of cases (e.g. 6 out of 10) provided both have computation time limited to 1 second.

It is guaranteed to be solvable, if:
* your program implements minimax algorithm correctly
* your game status evaluation function is reasonably simple (checks for sets of fices, open fours, half-open fours, open threes)

NB! The program should perform reasonably on both 10x10 and 20x20 boards.

== Programming in pairs ==

You can program this alone or in pair with other student. Paired assignment will award both studends maximum points if:
* Both students are presenting the program. Missing student gets no points.
* Both students understand the presented program code - including the parts implemented by other. The student that seems inadequate gets less or no points.

== Program framework ==

Your program has to be the refinement of the following code. Other alternatives - total makeovers or partially re-used GUI elements or classes are not accepted.

The framework consist of four files provided in the follwing ZIP file:

[[Media:Five.zip|Five.zip]]



The code compiles and works. But it performs poorly. The AI takes the first legal move found. You would have to re-implement the function best_move() (in file FiveLogic.java) to include minimax and a reasonable evaluation function. You can add methods and call them withing best_move(). No other parts of the code needs to be touched - including the GUI.

The provided code is based on the source code available here: http://www.leepoint.net/notes-java/examples/games/five/five.html

It is complemented with "program turn", auto-play, 20x20 board choice and a default board of 10x10 instead of 9x9.

== "auto" botton and benchmark AI ==

Pushing the "auto" button the program will play fully automatically - competition between best_move() (in file FiveLogic.java) and best_opponent_move (in file FiveOpponent.java). The human role is thereby the best_opponent_move().

The best_opponent_move() has poor performance also - it will also play on the first legal move available starting from botton-right.

The following ZIP file gives you the pre-compiled class file FiveOpponent.class that you would have to replace your compiled FiveOpponent.class with. You delete the FiveOpponent.class and FiveOpponent.java and replace them with FiveOpponent.class found on this page.

[[Media:FiveOpponent.zip|FiveOpponent.zip]]: unpack the ZIP containing the FiveOpponent.class

The give FiveOpponent will compute two turns ahead (white - his - turn, then black - the opponent, your program). Evaluation function enumerates sets of five, open fours, threes and twos. Plus half-open fours and threes. Then assigns coefficients to these sets. It doesn't include alpha-beta and any optimizations. Therefore it is rather slow.

Your program would have to win this FiveOpponent.class in majority of cases. (6 out of 10 games)

If you fail to beat the benchmark opponent you can choos to use even weaker opponent:

[[Media:FiveOpponent_weak.zip|FiveOpponent_weak.zip]]: unpack the zip to get the FiveOpponent.class

FiveOpponent_weak.zip will precompute one turn ahead (white's turn). If you can beat the weak opponent in majority of cases you will be awarded max. 8 points out of 10.

NB! Check that your program doesn't compute a turn on 10x10 board longer that 1 second. Else it will be considered as invalid algorithm.

== Tournament and extra points ==

'''NB! All authors will get 0 points upon detected plagiarism'''

There will be a tournament held between the AI-s submitted by students. The first two places get extra points:

* Winning team gets 10 extra points each.
* Second team gets 5 extra points each.

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

Tournament is not compulsory. How to participate: three days after the assigment deadline you have to assemble a version of the program where best_move() function is copied into best_opponent_move() function in FiveOpponent.java. It has to be completely independant of other parts of the program code - self compiling.

Given the three days you submit the code by email to the teacher. Write GOMOKU as the subject.

Provide:
* Author names, student ID-s and e-mails.
* Source code (NB! FiveOpponent.java needs to include yout best move computation)
* precompiled class files

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.

== Võistluse tulemused ==
TBD

== 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 lisaviited

== Lisaviiteid ==

Loengus antud info ja viited: [[Media:Progpohi12.PPT|Progpohi12.PPT]]

Lisaks:
:http://en.wikipedia.org/wiki/Gomoku
:http://www.leepoint.net/notes-java/examples/games/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/