Iti0210lab63 - Redigeerimiste ajalugu

PriitJ: /* Nõuded */

2021-02-24T10:25:25Z

Nõuded

←Vanem redaktsioon		Redaktsioon: 24. veebruar 2021, kell 12:25
114. rida:		114. rida:

	* programm peab kasutama juhuslikul simulatsioonil põhinevat (Monte Carlo) algoritmi. Ei tohi olla minimax vms		* programm peab kasutama juhuslikul simulatsioonil põhinevat (Monte Carlo) algoritmi. Ei tohi olla minimax vms
	* lisaks koodile pane reposse ka näide (tekstifail sobib), kus mingi seisu puhul võimalikud käikud ja nende ~~võiduprotsentid~~		* lisaks koodile pane reposse ka näide (tekstifail sobib), kus mingi seisu puhul võimalikud käikud ja nende võiduprotsendid

	== Lisaülesanne ==		== Lisaülesanne ==

PriitJ: /* Lisaülesanne */

2021-02-24T10:23:52Z

Lisaülesanne

←Vanem redaktsioon		Redaktsioon: 24. veebruar 2021, kell 12:23
117. rida:		117. rida:

	== Lisaülesanne ==		== Lisaülesanne ==

			Ei ole kohustuslik ja ei anna lisapunkte.

	Uuri, kuidas töötab [https://youtu.be/UXW2yZndl7U UCT versioon Monte Carlo puuotsingust] ja proovi see realiseerida.		Uuri, kuidas töötab [https://youtu.be/UXW2yZndl7U UCT versioon Monte Carlo puuotsingust] ja proovi see realiseerida.

PriitJ: /* Nõuded */

2021-02-24T10:23:13Z

Nõuded

←Vanem redaktsioon		Redaktsioon: 24. veebruar 2021, kell 12:23
113. rida:		113. rida:
	== Nõuded ==		== Nõuded ==

	* programm peab kasutama ~~mingit varianti~~ Monte Carlo ~~puuotsingust (ehk siis, ei~~ tohi olla minimax vms)		* programm peab kasutama juhuslikul simulatsioonil põhinevat (Monte Carlo) algoritmi. Ei tohi olla minimax vms
	* ~~lisa aruandesse~~ mingi seisu puhul ~~näide võimalikest käikudest~~ ja nende ~~võiduprotsentidest~~		* lisaks koodile pane reposse ka näide (tekstifail sobib), kus mingi seisu puhul võimalikud käikud ja nende võiduprotsentid

	== Lisaülesanne ==		== Lisaülesanne ==

PriitJ: /* Sissejuhatus */

2021-02-24T10:19:38Z

Sissejuhatus

←Vanem redaktsioon		Redaktsioon: 24. veebruar 2021, kell 12:19
5. rida:		5. rida:
	[[Image:Ifi0120lab6_c4.gif\|right\|frame\|Connect Four, autor ''[https://commons.wikimedia.org/wiki/User:Silver_Spoon Silver Spoon]'', [https://creativecommons.org/licenses/by-sa/3.0/deed.en CC-BY-SA 3.0] ]]		[[Image:Ifi0120lab6_c4.gif\|right\|frame\|Connect Four, autor ''[https://commons.wikimedia.org/wiki/User:Silver_Spoon Silver Spoon]'', [https://creativecommons.org/licenses/by-sa/3.0/deed.en CC-BY-SA 3.0] ]]

	[https://en.wikipedia.org/wiki/Connect_four "Connect Four"] on mäng, kus mängijad kordamööda 7x6 raami mängunuppe kukutavad ja proovivad esimesena 4 oma nuppu saada ritta horisontaalis, vertikaalis või diagonaalile. Teeme lihtsa programmi, mis seda mängu inimese vastu mängib. Kasutame mängu mängimiseks Monte Carlo ~~puuotsingut~~.		[https://en.wikipedia.org/wiki/Connect_four "Connect Four"] on mäng, kus mängijad kordamööda 7x6 raami mängunuppe kukutavad ja proovivad esimesena 4 oma nuppu saada ritta horisontaalis, vertikaalis või diagonaalile. Teeme lihtsa programmi, mis seda mängu inimese vastu mängib. Kasutame mängu mängimiseks Monte Carlo meetodit.

	== Kasutajaliides ==		== Kasutajaliides ==

PriitJ – 9. märts 2020, kell 18:48

2020-03-09T18:48:10Z

←Vanem redaktsioon		Redaktsioon: 9. märts 2020, kell 20:48
121. rida:		121. rida:

	[https://www.chessprogramming.org/images/d/d2/Uct-poster-erdmann.png poster]		[https://www.chessprogramming.org/images/d/d2/Uct-poster-erdmann.png poster]

			[[Category:Iti0210]]

PriitJ: /* Kasutajaliides */

2019-10-17T00:40:28Z

Kasutajaliides

←Vanem redaktsioon		Redaktsioon: 17. oktoober 2019, kell 02:40
37. rida:		37. rida:


	Programm näitab mänguseisu, küsib käiku, seejärel teeb oma käigu ~~(või käigud)~~ ja näitab jälle mänguseisu. See tsükkel kordub, kuni mäng läbi saab.		Programm näitab mänguseisu, küsib käiku, seejärel teeb oma käigu ja näitab jälle mänguseisu. See tsükkel kordub, kuni mäng läbi saab.

	Näites on võimalikud käigud (kuhu oma nupp kukutada) nummerdatud 0-6.		Näites on võimalikud käigud (kuhu oma nupp kukutada) nummerdatud 0-6.

PriitJ – 17. oktoober 2019, kell 00:39

2019-10-17T00:39:58Z

Näita muudatusi

PriitJ – 16. oktoober 2019, kell 12:10

2019-10-16T12:10:59Z

←Vanem redaktsioon		Redaktsioon: 16. oktoober 2019, kell 14:10
89. rida:		89. rida:
	== Monte Carlo puuotsing ==		== Monte Carlo puuotsing ==

			Monte Carlo puuotsing (''MCTS'') ei uuri kõiki käike võrdselt, vaid üritab uurida puu harusid, kus on hetkel suurem võiduprotsent. Igas otsingu tsüklis valitakse üks puu "leht" ning tehakse sealt simulatsioon uue käiguga.

			<pre>
			A (2/5) A (3/6)
			/ \ \ ===> / \ \
			B(1/3) C(1/1) D(0/1) B(1/3) C(2/2) D(0/1)
			: \|
			E E(1/1)
			</pre>

			Vasakpoolses puus on 3 varianti, mida järgmiseks simulatsiooniks valida: seisud B, C ja D. Kuna C-l on parim võiduprotsent, valitakse see ning omakorda järglane E. Oletame et E lõppes võiduga, siis kasvatatakse puud mööda tagasi liikudes nii võitude kui katsete arvu (parempoolne puu). Kaotuse korral kasvaks ainult katsete arv.

	== Oluline optimisatsioon ==		== Oluline optimisatsioon ==

PriitJ: Uus lehekülg: '= Otsing mängupuul = == Sissejuhatus == algseis "Karujaht" on arvatavasti Vana-Roomast pärit mäng, kus kolm jahimeest peavad karu...'

2019-10-16T11:26:45Z

Uus lehekülg: '= Otsing mängupuul = == Sissejuhatus == right|207px|algseis "Karujaht" on arvatavasti Vana-Roomast pärit mäng, kus kolm jahimeest peavad karu...'

Uus lehekülg

= Otsing mängupuul =

== Sissejuhatus ==

[[Image:Ifi0120lab6_alg.png|right|207px|algseis]]

"Karujaht" on arvatavasti Vana-Roomast pärit mäng, kus kolm jahimeest peavad karu "kinni püüdma" - suruma ta sellisesse seisu, kus karul enam ühtegi käiku ei ole. Nupud paiknevad mängulaua joonte ristumiskohtades, näiteks nagu pildil olevas algseisus. Käike teevad pooled kordamööda ja käiguks on ühe nupu liigutamine mööda joont järgmisesse ristumiskohta.

Mängus ei ole karul võimalik võita, mängitakse selle peale, kas ja kui kiiresti ta kinni püütakse. Võimalik, et Vana-Roomas mängiti raha peale, kihla veeti selle peale, kas karu suudab näiteks 40 käiku vastu pidada [http://mlwi.magix.net/bg/beargames.htm].

Teeme lihtsa programmi, mis seda mängu inimese vastu mängib. Kasutame mängu mängimiseks Monte Carlo puuotsingut.

== Nõuded ==

[[Image:Ifi0120lab6_not.png|right|207px|notatsioon]]

# Kasutame mängulaua tähistust ridade ja veergudega (''"A1"..."E5"''). Käiku tähistame näiteks B1A1, mis tähendab et väljal B1 asuv nupp, olgu see siis jahimees või karu, liigub väljale A1.
# Algseisus on karu käik.
# Programm kasutab Monte Carlo puuotsingu algoritmi ja peaks oskama ükskõik kumba poolt mängida.
# Mängulaua võib ise valida. Juhendis on toodud ajalooline mängulaud ja lihtsustatud 3x3 mängulaud.
# Tekstipõhisest kasutajaliidesest piisab. Graafilise võib teha, kui sellele liiga palju aega ei kulu.

Mängu mängimine võiks tekstipõhise liidesega välja näha umbes nii:

<pre>
...

current state:
To move: bear
Bear position: C3
Hunters are at: B1 C1 D1
available moves: [('C3', 'B3'), ('C3', 'D3'), ('C3', 'C2'), ('C3', 'C4')]

Your move? ('C3', 'B3')
current state:
To move: bear
Bear position: B3
Hunters are at: B1 C2 D1
available moves: [('B3', 'C3'), ('B3', 'B2'), ('B3', 'B4'), ('B3', 'A3')]

Your move?
</pre>

[[Image:Ifi0120lab6_mini.png|right|207px|pisi]]

Programm näitab mänguseisu, küsib käiku, seejärel teeb oma käigu (või käigud) ja näitab jälle mänguseisu. See tsükkel kordub, kuni mäng läbi saab.

== Mängimine puhta Monte Carlo meetodiga ==

Puhas Monte Carlo meetod teeb lihtsalt mingi arvu (''N'') juhuslikke mänge ja valib käigu, millega kõige rohkem võite saavutati.

<pre>

</pre>

== Vajalikud asjad ==

'''Mänguseisu sisemine esitus'''

Mängulaud vastab struktuurilt graafile, seega oleks loogiline seda ka graafina esitada. Lähtu sellest, mida mängu programmeerimiseks vaja on: kiiresti leida, mis on mu käigud (või naaberväljad) kui ma asun näiteks väljal B4.

Mänguseisu ennast peaks kõige lihtsam olema kirjeldada selle kaudu, kus karu ja jahimehed parajasti seisavad. Seega:
* kus on karu
* kus on jahimehed
* kelle käik on

'''Käikude ja seisude genereerimine'''

Leia käigule mingi sisemine esitus (kasvõi tuple <code>("A1", "A2")</code>) ja tee funktsioon, mis igast seisust
legaalsed käigud genereerib. Teiseks on vaja funktsiooni, mis võtab seisu ja käigu ning annab uue seisu.

'''Simulatsioon'''

Simulatsioon peab tegema järjest juhuslikke käike, kuni mäng on lõppenud ning tagastama, kas tulemus oli võit või mitte. Siin võib olla kasulik ka käikude arvule piirang panna, kuna nuppe edasi-tagasi liigutades võib mäng lõpmatult kesta.

'''Lõppseisu ära tundmine'''

Siin mängus on lõppseis see, kus karu enam liikuda ei saa. Ehk siis, on karu kord, aga tal pole ühtegi käiku.

'''Seisu väärtus'''

Monte Carlo puuotsingus on vaja teada simulatsiooni lõpptulemus: kas võit või mitte. Jahimeeste puhul on selge, mis on võit, kuidas seda defineerida karu puhul? Kui simulatsiooni pikkus on piiratud näit. 20 käigule, siis:

== Monte Carlo puuotsing ==

== Oluline optimisatsioon ==

== Mida aruandesse lisada ==

Tulemustest aitab aru saada, kui lisad:

* mängulaud mida kasutasid
* mingi seisu puhul näide võimalikest käikudest ja nende võiduprotsentidest
* kas ja kuidas mõjutas tulemusi jahimeeste käikude korduste keelamine

== Lisaülesanne ==

Uuri, kuidas töötab UCT versioon Monte Carlo puuotsingust ja proovi see realiseerida.

[https://www.chessprogramming.org/images/d/d2/Uct-poster-erdmann.png poster]