Iti0210lab63: erinevus redaktsioonide vahel

Allikas: Lambda
Mine navigeerimisribale Mine otsikasti
← Vanem muudatus
PriitJ (arutelu | kaastöö)
1416 muudatust
Resümee puudub
PriitJ (arutelu | kaastöö)
1416 muudatust
 
(ei näidata sama kasutaja 6 vahepealset redaktsiooni)
3. rida: 3. rida:
== Sissejuhatus ==
== Sissejuhatus ==


[[Image:Ifi0120lab6_alg.png|right|207px|algseis]]
[[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] ]]


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


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].
== Kasutajaliides ==


Teeme lihtsa programmi, mis seda mängu inimese vastu mängib. Kasutame mängu mängimiseks Monte Carlo puuotsingut.
Kasutajaliides võib olla nii tekstipõhine kui graafiline. Mängimine võiks tekstipõhise liidesega välja näha umbes nii:


== Nõuded ==
<pre>
...
 
|      |
|      |
|      |
|      |
|  O  |
| OXXXO |
|0123456|
To move: X
Your move? 2


[[Image:Ifi0120lab6_not.png|right|207px|notatsioon]]
|       |
|      |
|      |
|  O    |
|  XO  |
| OXXXO |
|0123456|
To move: X
Your move?


# 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.
</pre>
# 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>
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.
...


current state:
Näites on võimalikud käigud (kuhu oma nupp kukutada) nummerdatud 0-6.
To move: bear
Bear position: C3
Hunters are at: B1 C1 D1
available moves: [('C3', 'B3'), ('C3', 'D3'), ('C3', 'C2'), ('C3', 'C4')]


== Mängimine puhta Monte Carlo meetodiga ==


Your move? ('C3', 'B3')
Puhas Monte Carlo meetod teeb lihtsalt mingi arvu (''N'' iga käigu kohta) juhuslikke mänge ja valib käigu, millega kõige rohkem võite saavutati.
current state:
To move: bear
Bear position: B3
Hunters are at: B1 C2 D1
available moves: [('B3', 'C3'), ('B3', 'B2'), ('B3', 'B4'), ('B3', 'A3')]


<pre>
def pure_mc(pos, N=200):
    # kõik käigud algseisus
    my_side = pos["to_move"]
    initial_moves = moves(pos)
    # loendurid iga käigu jaoks
    win_counts = dict((move, 0) for move in initial_moves)


Your move?
    for move in initial_moves:
</pre>
        for i in range(N):
            # mängi juhuslikult seis kuni lõpuni
            res = simulate(pos, move, my_side)
            if res == WIN:
                win_counts[move] += 1
            elif res == DRAW:
                win_counts[move] += 0.5


[[Image:Ifi0120lab6_mini.png|right|207px|pisi]]
    # leia suurima võitude arvuga käik, tagasta


    # ...
</pre>


Funktsioon tekstipõhise liidesega mängimiseks:


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.
<pre>
def play_game(pos, player_side = "X"):
    playing = True
    while playing:
        if pos["to_move"] == player_side:
            # prindi info seisu kohta
            dump_pos(pos)
            movestr = input("Your move? ")
            # tõlgi kasutaja tekst oma sisemisse käiguformaati (kui vaja)
            move = parse_move(movestr)
        else:
            move = pure_mc(pos)


== Mängimine puhta Monte Carlo meetodiga ==
        pos = make_move(pos, move)
        # kontrolli kas mäng sai läbi
        if is_over(pos):
            playing = False
</pre>


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


<pre>
<pre>
 
play_game(starting_pos)
</pre>
</pre>


Toodud kooditükid on näide, ehk siis võib kasutada ka teistsuguseid lahendusi. Kui antud näidet kasutada, tuleb realiseerida kõik puuduolevad funktsioonid: <code>moves(), make_move(), simulate(), dump_pos(), parse_move(), is_over()</code>.


== Vajalikud asjad ==
== Vajalikud asjad ==
63. rida: 100. rida:
'''Mänguseisu sisemine esitus'''
'''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.
Lähtu sellest, et oleks võimalikult lihtne käike leida ja seda kontrollida, kas 4 nuppu on ritta saadud.
 
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'''
'''Käikude ja seisude genereerimine'''


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


'''Simulatsioon'''
'''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.
Simulatsioon peab tegema järjest juhuslikke käike, kuni mäng on lõppenud ning tagastama, kas tulemus oli võit, viik või kaotus. Viikide eraldi arvestamine on vajalik selleks, et programm üritaks vältida kaotust ka olukordades, kus ta võitu ei näe.


'''Lõppseisu ära tundmine'''
== Nõuded ==


Siin mängus on lõppseis see, kus karu enam liikuda ei saa. Ehk siis, on karu kord, aga tal pole ühtegi käiku.
* 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õiduprotsendid


'''Seisu väärtus'''
== Lisaülesanne ==


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:
Ei ole kohustuslik ja ei anna lisapunkte.


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


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.
[https://www.chessprogramming.org/images/d/d2/Uct-poster-erdmann.png poster]
 
<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 ==
[[Category:Iti0210]]
 
== 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]

Viimane redaktsioon: 24. veebruar 2021, kell 12:25

Otsing mängupuul

Sissejuhatus

Connect Four, autor Silver Spoon, CC-BY-SA 3.0

"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 võib olla nii tekstipõhine kui graafiline. Mängimine võiks tekstipõhise liidesega välja näha umbes nii: 

...

|       |
|       |
|       |
|       |
|   O   |
| OXXXO |
|0123456|
To move: X
Your move? 2

|       |
|       |
|       |
|  O    |
|  XO   |
| OXXXO |
|0123456|
To move: X
Your move?


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.

Mängimine puhta Monte Carlo meetodiga

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

def pure_mc(pos, N=200):
    # kõik käigud algseisus
    my_side = pos["to_move"]
    initial_moves = moves(pos)
    # loendurid iga käigu jaoks
    win_counts = dict((move, 0) for move in initial_moves)

    for move in initial_moves:
        for i in range(N):
            # mängi juhuslikult seis kuni lõpuni
            res = simulate(pos, move, my_side)
            if res == WIN:
                win_counts[move] += 1
            elif res == DRAW:
                win_counts[move] += 0.5

    # leia suurima võitude arvuga käik, tagasta

    # ...

Funktsioon tekstipõhise liidesega mängimiseks: 

def play_game(pos, player_side = "X"):
    playing = True
    while playing:
        if pos["to_move"] == player_side:
            # prindi info seisu kohta
            dump_pos(pos)
            movestr = input("Your move? ")
            # tõlgi kasutaja tekst oma sisemisse käiguformaati (kui vaja)
            move = parse_move(movestr)
        else:
            move = pure_mc(pos)

        pos = make_move(pos, move)
        # kontrolli kas mäng sai läbi
        if is_over(pos):
            playing = False

Ja testime: 

play_game(starting_pos)

Toodud kooditükid on näide, ehk siis võib kasutada ka teistsuguseid lahendusi. Kui antud näidet kasutada, tuleb realiseerida kõik puuduolevad funktsioonid: moves(), make_move(), simulate(), dump_pos(), parse_move(), is_over().

Vajalikud asjad

Mänguseisu sisemine esitus

Lähtu sellest, et oleks võimalikult lihtne käike leida ja seda kontrollida, kas 4 nuppu on ritta saadud.

Käikude ja seisude genereerimine

Leia käigule mingi sisemine esitus (kasvõi number 0-6) 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, viik või kaotus. Viikide eraldi arvestamine on vajalik selleks, et programm üritaks vältida kaotust ka olukordades, kus ta võitu ei näe.

Nõuded

  • 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õiduprotsendid

Lisaülesanne

Ei ole kohustuslik ja ei anna lisapunkte.

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

poster

Pärit leheküljelt "http://www.lambda.ee/w/index.php?title=Iti0210lab63&oldid=18528"