Iti0210lab63

Otsing mängupuul

Sissejuhatus

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 [1].

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

Nõuded

notatsioon

1. 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.
2. Algseisus on karu käik.
3. Programm kasutab Monte Carlo puuotsingu algoritmi ja peaks oskama ükskõik kumba poolt mängida.
4. Mängulaua võib ise valida. Juhendis on toodud ajalooline mängulaud ja lihtsustatud 3x3 mängulaud.
5. 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:

...

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? 

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.

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 ("A1", "A2")) 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

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.

        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)

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.

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.

poster