Iti0210lab62 - Redigeerimiste ajalugu

PriitJ: /* Lisaülesanne */

2019-03-02T08:28:50Z

Lisaülesanne

←Vanem redaktsioon		Redaktsioon: 2. märts 2019, kell 10:28
152. rida:		152. rida:
	Selle osa tegemine ei ole kohustuslik. Muuda <code>pig_game</code> funktsiooni või tee ise sobiv lahendus nii, et <code>dummy_ai</code> ja <code>minimax_ai</code> saaks omavahel mängida. Lase neil mängida näiteks 100 või suurem arv mänge ning pea arvet võitude ja kaotuste üle.		Selle osa tegemine ei ole kohustuslik. Muuda <code>pig_game</code> funktsiooni või tee ise sobiv lahendus nii, et <code>dummy_ai</code> ja <code>minimax_ai</code> saaks omavahel mängida. Lase neil mängida näiteks 100 või suurem arv mänge ning pea arvet võitude ja kaotuste üle.

	Kui oled ''expectiminimax''-i õigesti teinud, võiks see "dummy" strateegia vastu rohkem võite saada kui kaotusi. Õppejõu katsetus: 10000 mängu, võiduprotsent 54%.		Kui oled ''expectiminimax''-i õigesti teinud, võiks see "dummy" strateegia vastu rohkem võite saada kui kaotusi. <!--Õppejõu katsetus: 10000 mängu, võiduprotsent 54%.-->

PriitJ: /* Sissejuhatus */

2019-02-28T17:34:07Z

Sissejuhatus

←Vanem redaktsioon		Redaktsioon: 28. veebruar 2019, kell 19:34
13. rida:		13. rida:
	Seega on tegu mänguga, kus tuleb otsustada, kui palju riskida. Minimax algoritmi mõttes on siin mõlemal poolel kaks võimalikku käiku - "veereta veel" või "anna käik vastasele". Lisaks, kuna üks mängija võib veeretada mitu korda järjest, siis puus ei ole selgeid MIN ja MAX tasandeid - üks mängija võib teha mitu otsust järjest. Kuna meil on tegemist ka juhuslikkusega, siis kasutame ''expectiminimax'' algoritmi (õpik [''AIMA''] 5.5). See lisab otsingupuusse ka juhuslikkuse sõlmed (''chance nodes'').		Seega on tegu mänguga, kus tuleb otsustada, kui palju riskida. Minimax algoritmi mõttes on siin mõlemal poolel kaks võimalikku käiku - "veereta veel" või "anna käik vastasele". Lisaks, kuna üks mängija võib veeretada mitu korda järjest, siis puus ei ole selgeid MIN ja MAX tasandeid - üks mängija võib teha mitu otsust järjest. Kuna meil on tegemist ka juhuslikkusega, siis kasutame ''expectiminimax'' algoritmi (õpik [''AIMA''] 5.5). See lisab otsingupuusse ka juhuslikkuse sõlmed (''chance nodes'').

	Kasutajaliidesele jne pole vaja rõhku panna. Oluline osa tööst on kasutada käigu (otsus, kas veeretada või anda kord vastasele) leidmiseks ''expectiminimax'' algoritmi. Ülesande lahendamise eelduseks on, et saad juba enam-vähem aru, kuidas töötab minimax: [''AIMA''] õpikust osad 5.1, 5.2 ja 5.4. Suhteliselt asjaliku kirjelduse, kuidas ''minimax'' otsingupuud läbib, [https://www.cs.cornell.edu/courses/cs312/2002sp/lectures/rec21.htm leiad ka siit].		Kasutajaliidesele jne pole vaja rõhku panna. Oluline osa tööst on kasutada käigu (otsus, kas veeretada või anda kord vastasele) leidmiseks ''expectiminimax'' algoritmi. Ülesande lahendamise eelduseks on, et saad juba enam-vähem aru, kuidas töötab minimax: [''AIMA''] õpikust osad 5.1, 5.2 ja 5.4. Suhteliselt asjaliku kirjelduse, kuidas ''minimax'' otsingupuud läbib, [https://www.cs.cornell.edu/courses/cs312/2002sp/lectures/rec21.htm leiad ka siit], võid vaadata ka harjutustunnis tehtud [[Media:Iti0120lab62_ttt.txt\|minimax demo]].

	== Ettevalmistus ==		== Ettevalmistus ==

PriitJ: /* Sissejuhatus */

2019-02-27T11:11:55Z

Sissejuhatus

←Vanem redaktsioon		Redaktsioon: 27. veebruar 2019, kell 13:11
13. rida:		13. rida:
	Seega on tegu mänguga, kus tuleb otsustada, kui palju riskida. Minimax algoritmi mõttes on siin mõlemal poolel kaks võimalikku käiku - "veereta veel" või "anna käik vastasele". Lisaks, kuna üks mängija võib veeretada mitu korda järjest, siis puus ei ole selgeid MIN ja MAX tasandeid - üks mängija võib teha mitu otsust järjest. Kuna meil on tegemist ka juhuslikkusega, siis kasutame ''expectiminimax'' algoritmi (õpik [''AIMA''] 5.5). See lisab otsingupuusse ka juhuslikkuse sõlmed (''chance nodes'').		Seega on tegu mänguga, kus tuleb otsustada, kui palju riskida. Minimax algoritmi mõttes on siin mõlemal poolel kaks võimalikku käiku - "veereta veel" või "anna käik vastasele". Lisaks, kuna üks mängija võib veeretada mitu korda järjest, siis puus ei ole selgeid MIN ja MAX tasandeid - üks mängija võib teha mitu otsust järjest. Kuna meil on tegemist ka juhuslikkusega, siis kasutame ''expectiminimax'' algoritmi (õpik [''AIMA''] 5.5). See lisab otsingupuusse ka juhuslikkuse sõlmed (''chance nodes'').

	Kasutajaliidesele jne pole vaja rõhku panna. Oluline osa tööst on kasutada käigu (otsus, kas veeretada või anda kord vastasele) leidmiseks ''expectiminimax'' algoritmi. Ülesande lahendamise eelduseks on, et saad juba aru, kuidas töötab minimax: [''AIMA''] õpikust osad 5.1, 5.2 ja 5.4. Suhteliselt asjaliku kirjelduse, kuidas ''minimax'' otsingupuud läbib, [https://www.cs.cornell.edu/courses/cs312/2002sp/lectures/rec21.htm leiad ka siit].		Kasutajaliidesele jne pole vaja rõhku panna. Oluline osa tööst on kasutada käigu (otsus, kas veeretada või anda kord vastasele) leidmiseks ''expectiminimax'' algoritmi. Ülesande lahendamise eelduseks on, et saad juba enam-vähem aru, kuidas töötab minimax: [''AIMA''] õpikust osad 5.1, 5.2 ja 5.4. Suhteliselt asjaliku kirjelduse, kuidas ''minimax'' otsingupuud läbib, [https://www.cs.cornell.edu/courses/cs312/2002sp/lectures/rec21.htm leiad ka siit].

	== Ettevalmistus ==		== Ettevalmistus ==

PriitJ: /* Sissejuhatus */

2019-02-27T11:07:05Z

Sissejuhatus

←Vanem redaktsioon		Redaktsioon: 27. veebruar 2019, kell 13:07
9. rida:		9. rida:
	* kui mängija veeretab 1, siis läheb kord vastasele ja mängija kaotab kõik selle korra jooksul veeretatud punktid.		* kui mängija veeretab 1, siis läheb kord vastasele ja mängija kaotab kõik selle korra jooksul veeretatud punktid.

	[[Image:~~Ifi0120lab62_eminimax~~.png\|right\|expectiminimax puu]]		[[Image:Ifi0120lab62_chance.png\|right\|expectiminimax puu]]

	Seega on tegu mänguga, kus tuleb otsustada, kui palju riskida. Minimax algoritmi mõttes on siin mõlemal poolel kaks võimalikku käiku - "veereta veel" või "anna käik vastasele". Lisaks, kuna üks mängija võib veeretada mitu korda järjest, siis puus ei ole selgeid MIN ja MAX tasandeid - üks mängija võib teha mitu otsust järjest. Kuna meil on tegemist ka juhuslikkusega, siis kasutame ''expectiminimax'' algoritmi (õpik [''AIMA''] 5.5). See lisab otsingupuusse ka juhuslikkuse sõlmed (''chance nodes'').		Seega on tegu mänguga, kus tuleb otsustada, kui palju riskida. Minimax algoritmi mõttes on siin mõlemal poolel kaks võimalikku käiku - "veereta veel" või "anna käik vastasele". Lisaks, kuna üks mängija võib veeretada mitu korda järjest, siis puus ei ole selgeid MIN ja MAX tasandeid - üks mängija võib teha mitu otsust järjest. Kuna meil on tegemist ka juhuslikkusega, siis kasutame ''expectiminimax'' algoritmi (õpik [''AIMA''] 5.5). See lisab otsingupuusse ka juhuslikkuse sõlmed (''chance nodes'').

PriitJ: /* Expectiminimax */

2019-02-27T11:06:37Z

Expectiminimax

←Vanem redaktsioon		Redaktsioon: 27. veebruar 2019, kell 13:06
104. rida:		104. rida:
	Nüüd teeme lisaks <code>dummy_ai</code>-le ka otsingupõhise "AI". Õpikus on algoritm antud rekursiivse funktsioonina:		Nüüd teeme lisaks <code>dummy_ai</code>-le ka otsingupõhise "AI". Õpikus on algoritm antud rekursiivse funktsioonina:

	[[Image:~~Ifi0120lab62_chance~~.png\|ekraanitõmmis õpikust lk 178]]		[[Image:Ifi0120lab62_eminimax.png\|ekraanitõmmis õpikust lk 178]]

	Ka meil on mõistlik see rekursiivsena teha. Algoritmis on 4 osa:		Ka meil on mõistlik see rekursiivsena teha. Algoritmis on 4 osa:

PriitJ: /* Lisaülesanne */

2019-02-27T11:01:21Z

Lisaülesanne

←Vanem redaktsioon		Redaktsioon: 27. veebruar 2019, kell 13:01
152. rida:		152. rida:
	Selle osa tegemine ei ole kohustuslik. Muuda <code>pig_game</code> funktsiooni või tee ise sobiv lahendus nii, et <code>dummy_ai</code> ja <code>minimax_ai</code> saaks omavahel mängida. Lase neil mängida näiteks 100 või suurem arv mänge ning pea arvet võitude ja kaotuste üle.		Selle osa tegemine ei ole kohustuslik. Muuda <code>pig_game</code> funktsiooni või tee ise sobiv lahendus nii, et <code>dummy_ai</code> ja <code>minimax_ai</code> saaks omavahel mängida. Lase neil mängida näiteks 100 või suurem arv mänge ning pea arvet võitude ja kaotuste üle.

	Kui oled ''expectiminimax''-i õigesti teinud, võiks see "dummy" strateegia vastu rohkem võite ~~saama~~ kui kaotusi. Õppejõu katsetus: 10000 mängu, võiduprotsent 54%.		Kui oled ''expectiminimax''-i õigesti teinud, võiks see "dummy" strateegia vastu rohkem võite saada kui kaotusi. Õppejõu katsetus: 10000 mängu, võiduprotsent 54%.

PriitJ: Uus lehekülg: '= Otsingu kasutamine mängu mängimiseks = == Sissejuhatus == Strateegiamängudes, nagu male, ''go'' jne on võimalik hea käigu leidmiseks kasutada sügavutiotsingu varianti n...'

2019-02-27T11:00:30Z

Uus lehekülg: '= Otsingu kasutamine mängu mängimiseks = == Sissejuhatus == Strateegiamängudes, nagu male, ''go'' jne on võimalik hea käigu leidmiseks kasutada sügavutiotsingu varianti n...'

Uus lehekülg

= Otsingu kasutamine mängu mängimiseks =

== Sissejuhatus ==

Strateegiamängudes, nagu male, ''go'' jne on võimalik hea käigu leidmiseks kasutada sügavutiotsingu varianti nimega minimax. Meie proovime mängida mängu, kus on ka juhuslik element: [https://en.wikipedia.org/wiki/Pig_(dice_game) seamäng]. Lühidalt:
* mängitakse selleni, kes saab enne 100 punkti. Alguses on mõlemal mängijal 0 punkti.
* mängija võib veeretada ühte täringut mitu korda järjest, senikaua kuni ta ei veereta 1. Tulemused liidetakse kokku.
* kui mängija otsustab, et soovib veeretatud punktid alles hoida, liidetakse need tema kogusummale ja kord läheb vastasele.
* kui mängija veeretab 1, siis läheb kord vastasele ja mängija kaotab kõik selle korra jooksul veeretatud punktid.

[[Image:Ifi0120lab62_eminimax.png|right|expectiminimax puu]]

Seega on tegu mänguga, kus tuleb otsustada, kui palju riskida. Minimax algoritmi mõttes on siin mõlemal poolel kaks võimalikku käiku - "veereta veel" või "anna käik vastasele". Lisaks, kuna üks mängija võib veeretada mitu korda järjest, siis puus ei ole selgeid MIN ja MAX tasandeid - üks mängija võib teha mitu otsust järjest. Kuna meil on tegemist ka juhuslikkusega, siis kasutame ''expectiminimax'' algoritmi (õpik [''AIMA''] 5.5). See lisab otsingupuusse ka juhuslikkuse sõlmed (''chance nodes'').

Kasutajaliidesele jne pole vaja rõhku panna. Oluline osa tööst on kasutada käigu (otsus, kas veeretada või anda kord vastasele) leidmiseks ''expectiminimax'' algoritmi. Ülesande lahendamise eelduseks on, et saad juba aru, kuidas töötab minimax: [''AIMA''] õpikust osad 5.1, 5.2 ja 5.4. Suhteliselt asjaliku kirjelduse, kuidas ''minimax'' otsingupuud läbib, [https://www.cs.cornell.edu/courses/cs312/2002sp/lectures/rec21.htm leiad ka siit].

== Ettevalmistus ==

Proovime kõigepealt mängu niisama mängida. Siin on lihtne Pythoni implementatsioon:

<pre>
import random

AI = 0
PLAYER = 1

ROLL = 0
PASS = 1

def pig_game(ai_func):
rolled = 0
turn = PLAYER
player_points = ai_points = 0

while player_points < 100 and ai_points < 100:
print("Your points", player_points,
"AI points", ai_points,
"holding", rolled)

if turn == PLAYER:
decision = ROLL
if rolled > 0:
s = input("Do you want to keep rolling (Y/n)? ")
if len(s) > 0 and s[0].lower() == "n":
decision = PASS

if decision == PASS:
rolled = 0
turn = AI
else:
dieroll = random.randint(1, 6)
print("You rolled...", dieroll)
if dieroll == 1:
player_points -= rolled # lose all points again
rolled = 0
turn = AI
else:
rolled += dieroll
player_points += dieroll

else:
decision = ai_func(turn, rolled, ai_points, player_points)
if decision == PASS:
print("-- AI decides to pass.")
rolled = 0
turn = PLAYER
else:
dieroll = random.randint(1, 6)
print("-- AI rolled...", dieroll)
if dieroll == 1:
ai_points -= rolled # lose all points again
rolled = 0
turn = PLAYER
else:
rolled += dieroll
ai_points += dieroll

if player_points >= 100:
print("You won!")
elif ai_points >= 100:
print("AI won.")
</pre>

Vaja on ka mingit "tehisintellekti", mis vastase osa mängiks. Üks variant võiks olla selline:

<pre>
def dummy_ai(turn, rolled, my_points, opp_points):
if rolled < 21:
return ROLL
else:
return PASS
</pre>

<code>dummy_ai</code> implementeerib suhteliselt agressiivse strateegia, mis mänguseisule tähelepanu ei pööra, aga üritab iga kord vähemalt 21 punkti veeretada. "AI" funktsioonile on antud mõned parameetrid, mida edaspidi vaja läheb: mängu seis punktide kujul, lisaks kelle kord on (<code>turn</code>) ning kui palju mängija on praeguse korra jooksul punkte kogunud (<code>rolled</code>).

Mängu saad käima panna nii:

<pre>
pig_game(dummy_ai)
</pre>

== Expectiminimax ==

Nüüd teeme lisaks <code>dummy_ai</code>-le ka otsingupõhise "AI". Õpikus on algoritm antud rekursiivse funktsioonina:

[[Image:Ifi0120lab62_chance.png|ekraanitõmmis õpikust lk 178]]

Ka meil on mõistlik see rekursiivsena teha. Algoritmis on 4 osa:
# rekursiooni lõpetamise tingimus: kui keegi on võitnud, või me ei taha otsinguga sügavamale minna, tuleks tagastada seisu numbriline väärtus (<code>Utility</code>), mida suurem seda parem "AI" jaoks.
# MAX-sõlm: kui on parajasti "AI" käik, peaks ta leidma, kumb käik annab kõrgema skoori - veeretamine või lõpetamine, s.t. kutsuma välja rekursiivse otsingu mõlema juhtumi jaoks.
# MIN-sõlm: vastase käigu korral tuleb leida madalaim võimalik skoor, kuna peame eeldama (kartma), et vastane mängib nii hästi kui suudab.
# Juhuslik sõlm: iga kord, kui keegi otsustab veeretada, tuleb siin käsitleda kõik 6 võimalikku tulemust - muuta seisu nii nagu täringuveere seda teeks ning hinnata iga juhtumit rekursiivse otsinguga. Tulemustest võtta keskmine.

Algoritmi jaoks võid kasutada seda toorikut. Arvesta, et otsingu esimesel tasemel (otsingupuu juur) tuleb leida ja tagastada, milline käik on parem. Edaspidi tuleb arvutada ja tagastada ainult skoori. Tavaliselt on mänge mängivates programmides esimene ja järgmised tasemed ka eraldi funktsioonidena tehtud.

<pre>
def minimax_ai(turn, rolled, my_points, opp_points):
# this is the top level of search
# we search all possible moves
# (PASS and ROLL in case of the Pig game)
# and pick the one that returns the highest minimax estimate
</pre>

Ning rekursiivne osa:
<pre>
def exp_minimax(turn, chance, rolled, my_points, opp_points, depth):
# update remaining depth as we go deeper in the search tree
depth = depth - 1

# case 1a: somebody won, stop searching
# return a high value if AI wins, low if it loses.

# case 1b: out of depth, stop searching
# return game state eval (should be between win and loss)

# case 2: AI's turn (and NOT a chance node):
# return max value of possible moves (recursively)

# case 3: player's turn:
# return min value (assume optimal action from player)

# case 4: chance node:
# return average of all dice rolls
</pre>

Lisatud on parameetrid <code>chance</code> - kas tegu on juhuslikkuse sõlmega ja <code>depth</code>, mis piirab otsingu sügavust - kui see muutub 0-ks, peaks otsingu lõpetama. Miks on vaja eraldi arvet pidada, kelle käik ja kas tegu ''chance node''-ga? Põhjus selles, et peale täringu veeretamist ei lähe mänguõigus tingimata vastasele üle, seega tuleb meeles pidada, kes parajasti veeretab.

Seamängus on mänguseis väga lihtne ning seda võib edasi anda kolme numbrilise väärtusega: "AI" punktid, vastase punktid ning kui palju hetkel veeretav mängija on kogunud. Kui soovid, võid edasi anda ka viimase täringuveeretuse tulemuse, kui arvad, et see võiks seisu hinnangut mõjutada.

== Lisaülesanne ==

Selle osa tegemine ei ole kohustuslik. Muuda <code>pig_game</code> funktsiooni või tee ise sobiv lahendus nii, et <code>dummy_ai</code> ja <code>minimax_ai</code> saaks omavahel mängida. Lase neil mängida näiteks 100 või suurem arv mänge ning pea arvet võitude ja kaotuste üle.

Kui oled ''expectiminimax''-i õigesti teinud, võiks see "dummy" strateegia vastu rohkem võite saama kui kaotusi. Õppejõu katsetus: 10000 mängu, võiduprotsent 54%.