Viimane redaktsioon: 8. oktoober 2018, kell 09:25

Alpha-beta otsing

Sissejuhatus

"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. Seejuures on oluline, et programm kasutataks alpha-beta puuotsingut või mingit selle edasiarendust.

Nõuded

Kasutajaliides on tekstipõhine
Kasutame piltidel toodud algseisu ja mängulaua tähistust ("A1"..."E5"). Käiku tähistame näiteks B1-A1, 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 alpha-beta algoritmi ja peaks oskama ükskõik kumba poolt mängida

Mängu mängimine võiks 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. Näites ei ole mänguseisu visualiseeritud ja see ei ole ka kohustuslik.

Lahenduse võimalikud variandid (vali üks):

aima-python paketi games moodul ja games.Game klass. See töötab üsna sarnaselt search.Problem klassiga ning samas moodulis on üsna palju vajalikku juba ära implementeeritud. Juhendi lõpus on mõned näited selle paketi kasutamisest.
Implementeeri ise [AIMA] õpiku Figure 5.7 toodud algoritm
Leia sobivad kooditükid või pseudokood Internetist.

Ükskõik millise variandi valid, pööra tähelepanu, et ülalpool toodud nõuded oleks täidetud. Ühelt poolt need lihtsustavad ülesannet, aga teiselt poolt kitsendavad - kusagilt üle võetud lahendus vajab ikkagi tõenäoliselt ümber tegemist ja kohandamist.

Elementaarsed asjad

Elementaarse osa tegemisest ülesande kaitsmise juures piisab.

Mänguseisu sisemine esitus

Mängulaud vastab struktuurilt graafile, seega oleks loogiline seda ka graafina esitada. Selleks on mitmeid võimalusi, lähtu sellest, mida mängimiseks 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. Paljudes mängudes tehakse ka tabel, kust mänguvälja koordinaadi järgi saab leida selle sisu. Siin mängus on seda aga raske õigustada. Seega:

kus on karu
kus on jahimehed
kelle käik on

Käikude ja seisude genereerimine

See kuulub iga mänguprogrammi juurde. Tavaliselt on käikude genereerimine ja käigu põhjal uue seisu tegemine kaks eraldi funktsiooni. Õpiku Figure 5.7 pseudokoodis Actions() ja Result().

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. Õpiku algoritmis vastab sellele kohale TerminalTest() funktsioon.

Otsingu sügavuse piiramine

Otsingupuu on selles mängus lõpmatu, kuna nuppe saab lihtsalt edasi-tagasi nihutada. Esialgu tegeleme selle probleemiga nii, et piirame otsingu sügavuse ära (v.t. [AIMA] 5.4.2).

Seisu väärtus

Tähistame võiduseisu väärtuse mingi suure numbrigaWIN. Kõige primitiivsem seisuhinnang, mis täidaks nii õpiku Utility() kui Eval() funktsiooni ülesannet, oleks selline:

kui programm on jahimees, ja karu on lõksus, siis +WIN
kui programm on karu ja karu on lõksus, siis -WIN
muidu 0.

Nüüd peaks mängu juba olema võimalik testida, eeldusel, et meil on tehtud sisend/väljund ning implementeeritud ülejäänud alpha-beta otsing standardsel kujul (kas õpikust, mingi muu eeskuju alusel või olemasolev games.py moodulist).

Kasuta kõrval näidatud väikest mängulauda, et veenduda, et käikude tegemine, võidukäigu leidmine, jne toimiks. Tõnäoliselt on meil puudu veel üks vajalik element - nimelt on võimalik, et programm näeb korraga mitut käiku, mis võidule viivad. Kuna kõigi nende väärtus on sama (+WIN või -WIN), siis ei oska ta neil kuidagi vahet teha ning võib valida ühekäigulise võidu asemel käigu, mis karu minema päästab - ta näeb, et paari käigu pärast suudaks ta niikuinii võita.

Täiendame programmi veel ühe elemendiga - mida hiljem mängus võiduseis esineb, seda väiksem ta väärtus on. Näiteks kui käigu number on K, siis võiduseisu skoor on WIN-K. Karu poolt vaadates tuleb see (-1)-ga läbi korrutada. Nüüd peaks programm väikese mängulauaga hakkama saama. Kui ta ka suuremal hästi mängib, tore, aga kui mitte, pole ka midagi katki - antud mäng ei ole arvuti jaoks nii triviaalne kui näiteks trips-traps-trull.

Paremini mängimine

Siin kirjeldatavaid tehnikaid võib katsetada vastavalt huvile ja motivatsioonile, kohustuslikud nad ei ole. Enamus tehnikaid on suhteliselt tüüpilised paljude lauamängude (ja sarnaste asjade) alpha-beta otsinguga tehtud lahenduste juures.

`games.Game` klassi kasutamise näited ja vihjed

Esmalt tuleb teha oma mängu klass:

import games

class BearGame(games.Game):                                                     
    def __init__(self):
        # algseis jne initsialiseerimine

    def to_move(self, state):
        # otsusta, kuidas karu ja jahimeeste poolt tähistada ja tagasta, kumb pool käigul on
                                                                                
    def actions(self, state):
        # kõik seisus võimalikud käigud
                                                                                
    def result(self, state, action):
        # uus seis peale käigu tegemist

    def utility(self, state, side):
        # mis on seisu väärtus antud poole jaoks (ei võrdu alati
        #   sellega, kelle käik antud seisus on)
        # täidab ka eval() funktsiooni rolli

    def terminal_test(self, state):
        # siin peaks ära tundma, kas karu on lõksu aetud

Game klass sisaldab ka play_game() meetodit, millega saab mängu mängida. Käikude jne testimiseks võid proovida ka ilma otsinguta mängida:

bg = BearGame()

bg.play_game(games.query_player,
              games.random_player)

Esimene parameeter on, kes karu poolt mängib (kuna nõuete järgi karu alustab), teine, kes mängib jahimehi. Näites olevad abifunktsioonid küsivad vastavalt käiku inimeselt või teevad juhusliku käigu. Kui parameetrid ära vahetad, saad teist poolt mängida.

Otsingut kasutades tuleks kindlasti kohe ka sügavus ära piirata:

def alphabeta_depth8(game, state):
    return games.alphabeta_cutoff_search(state, game, d=8)

bg.play_game(games.query_player,
              alphabeta_depth8)

@@ 1. rida: / 1. rida: @@
-= Minimax ja alpha-beta =
+= Alpha-beta otsing =
 == Sissejuhatus ==
-Loe läbi "Dots and Boxes" mängu [https://en.wikipedia.org/wiki/Dots_and_Boxes kirjeldus ja reeglid] (kuni sisukorrani, strateegia jne pole vajalik).
+[[Image:Ifi0120lab6_alg.png|right|207px|algseis]]
-Teeme lihtsa programmi, mis seda mängu inimese vastu mängib. Seejuures on oluline, et programm kasutataks minimax stiilis (s.t. võib olla ka mingi alpha-beta variant) puuotsingut.
+"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. Seejuures on oluline, et programm kasutataks alpha-beta puuotsingut või mingit selle edasiarendust.
 == Nõuded ==
+[[Image:Ifi0120lab6_not.png|right|207px|notatsioon]]
 # Kasutajaliides on tekstipõhine
-# Mängulaud on 2x2 (s.t. 9 punkti) või 3x3 (16 punkti)
+# Kasutame piltidel toodud algseisu ja mängulaua tähistust (''"A1"..."E5"''). Käiku tähistame näiteks B1-A1, mis tähendab et väljal B1 asuv nupp, olgu see siis jahimees või karu, liigub väljale A1.
-# Inimene alustab alati
+# Algseisus on karu käik
-# Programm kasutab kas minimax või alpha-beta algoritmi
+# Programm kasutab alpha-beta algoritmi ja peaks oskama ükskõik kumba poolt mängida
 Mängu mängimine võiks välja näha umbes nii:
@@ 19. rida: / 25. rida: @@
 ...
-Your move? (2,5)
 current state:
-* --- *     *
+To move: bear
-      |
+Bear position: C3
-*     *     *
+Hunters are at: B1 C1 D1
-|           |
+available moves: [('C3', 'B3'), ('C3', 'D3'), ('C3', 'C2'), ('C3', 'C4')]
-*     *     *
-available moves: {(4, 5), (5, 6), (1, 4), (8, 9), (2, 3), (3, 6), (7, 8), (5, 8)}
-Your move? (1,4)
+Your move? ('C3', 'B3')
 current state:
-* --- *     *
+To move: bear
-|  X  |
+Bear position: B3
-* --- *     *
+Hunters are at: B1 C2 D1
-|           |
+available moves: [('B3', 'C3'), ('B3', 'B2'), ('B3', 'B4'), ('B3', 'A3')]
-*     * --- *
-available moves: {(2, 3), (3, 6), (5, 6), (7, 8), (5, 8)}
 Your move?
-...
 </pre>
-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 üks pool võidab, peale seda kuvab programm, kes võitis ja lõpetab.
+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. Näites ei ole mänguseisu visualiseeritud ja see ei ole ka kohustuslik.
-Näites on kõik punktid tähistatud numbritega (1-9) ja kriipsu tõmbamiseks sisestatakse kaks punkti. Nii ei pea tegema, aga see tundub üsna mõistlik.
 Lahenduse võimalikud variandid (vali üks):
-* [https://github.com/aimacode/aima-python aima-python] paketi <code>games</code> moodul ja <code>games.Game</code> klass. See töötab üsna sarnaselt <code>search.Problem</code> klassiga ning samas moodulis on üsna palju vajalikku juba ära implementeeritud.
+* [https://github.com/aimacode/aima-python aima-python] paketi <code>games</code> moodul ja <code>games.Game</code> klass. See töötab üsna sarnaselt <code>search.Problem</code> klassiga ning samas moodulis on üsna palju vajalikku juba ära implementeeritud. Juhendi lõpus on mõned näited selle paketi kasutamisest.
-* Implementeeri ise [''AIMA''] õpiku ''Figure 5.3'' või ''Figure 5.7'' toodud algoritm
+* Implementeeri ise [''AIMA''] õpiku ''Figure 5.7'' toodud algoritm
 * Leia sobivad kooditükid või pseudokood Internetist.
 Ükskõik millise variandi valid, pööra tähelepanu, et ülalpool toodud nõuded oleks täidetud. Ühelt poolt need lihtsustavad ülesannet, aga teiselt poolt kitsendavad - kusagilt üle võetud lahendus vajab ikkagi tõenäoliselt ümber tegemist ja kohandamist.
-== Ideed lahenduse jaoks ==
+== Elementaarsed asjad ==
+Elementaarse osa tegemisest ülesande kaitsmise juures piisab.
+'''Mänguseisu sisemine esitus'''
+Mängulaud vastab struktuurilt graafile, seega oleks loogiline seda ka graafina esitada. Selleks on mitmeid võimalusi, lähtu sellest, mida mängimiseks 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. Paljudes mängudes tehakse ka tabel, kust mänguvälja koordinaadi järgi saab leida selle sisu. Siin mängus on seda aga raske õigustada. Seega:
+* kus on karu
+* kus on jahimehed
+* kelle käik on
+'''Käikude ja seisude genereerimine'''
+See kuulub iga mänguprogrammi juurde. Tavaliselt on käikude genereerimine ja käigu põhjal uue seisu tegemine kaks eraldi funktsiooni. Õpiku ''Figure 5.7'' pseudokoodis ''Actions()'' ja ''Result()''.
+'''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. Õpiku algoritmis vastab sellele kohale ''TerminalTest()'' funktsioon.
+'''Otsingu sügavuse piiramine'''
-* kui esitad olekut ''tegemata'' käikude kaudu, siis muutub käikude genereerimine <code>actions()</code> meetodis lihtsamaks
+Otsingupuu on selles mängus lõpmatu, kuna nuppe saab lihtsalt edasi-tagasi nihutada. Esialgu tegeleme selle probleemiga nii, et piirame otsingu sügavuse ära (v.t. ''[AIMA]'' 5.4.2).
-* mängu saab mängida ka nii, kui pole märgitud, kes millise kriipsu tegi, seega visualiseerimist saab lihtsustada kui näitad mõlema mängija kriipse ühtemoodi
-* Kui kasutad <code>games.Game</code> klassi, siis seal leiduv <code>play_game()</code> meetod sunnib mängijaid käike tegema kordamööda ja meie mängus see ei ole nii. Aga sellest saab teha oma versiooni, mis kontrolliks näiteks mängu olekust, kelle käik parajasti on.
+'''Seisu väärtus'''
-* kui su otsing on mingil põhjusel liiga aeglane, siis piira rekursiooni sügavus ära ning tagasta lõppseisu asemel mingi vahepealne hinnang seisule (vt [''AIMA''] 5.4). Sel juhul on oluline ka järgmine punkt.
-* <code>utility()</code> funktsioon peaks vahet tegema, kas tegu on lõppseisuga või mitte. Lõppseisus võitmine on palju olulisem kui mingis vahepealses olekus hea skoori omamine.
+Tähistame võiduseisu väärtuse mingi suure numbriga<code>WIN</code>. Kõige primitiivsem seisuhinnang, mis täidaks nii õpiku ''Utility()'' kui ''Eval()'' funktsiooni ülesannet, oleks selline:
+* kui programm on jahimees, ja karu on lõksus, siis +WIN
+* kui programm on karu ja karu on lõksus, siis -WIN
+* muidu 0.
+[[Image:Ifi0120lab6_mini.png|right|207px|pisi]]
+Nüüd peaks mängu juba olema võimalik testida, eeldusel, et meil on tehtud sisend/väljund ning implementeeritud ülejäänud alpha-beta otsing standardsel kujul (kas õpikust, mingi muu eeskuju alusel või olemasolev <code>games.py</code> moodulist).
+Kasuta kõrval näidatud väikest mängulauda, et veenduda, et käikude tegemine, võidukäigu leidmine, jne toimiks. Tõnäoliselt on meil puudu veel üks vajalik element - nimelt on võimalik, et programm näeb korraga mitut käiku, mis võidule viivad. Kuna kõigi nende väärtus on sama (+WIN või -WIN), siis ei oska ta neil kuidagi vahet teha ning võib valida ühekäigulise võidu asemel käigu, mis karu minema päästab - ta näeb, et paari käigu pärast suudaks ta niikuinii võita.
+Täiendame programmi veel ühe elemendiga - mida hiljem mängus võiduseis esineb, seda väiksem ta väärtus on. Näiteks kui käigu number on K, siis võiduseisu skoor on WIN-K. Karu poolt vaadates tuleb see (-1)-ga läbi korrutada. Nüüd peaks programm väikese mängulauaga hakkama saama. Kui ta ka suuremal hästi mängib, tore, aga kui mitte, pole ka midagi katki - antud mäng ei ole arvuti jaoks nii triviaalne kui näiteks trips-traps-trull.
+== Paremini mängimine ==
+[[Iti0120lab6lisa|Siin kirjeldatavaid tehnikaid]] võib katsetada vastavalt huvile ja motivatsioonile, kohustuslikud nad ei ole. Enamus tehnikaid on suhteliselt tüüpilised paljude lauamängude (ja sarnaste asjade) alpha-beta otsinguga tehtud lahenduste juures.
+== <code>games.Game</code> klassi kasutamise näited ja vihjed ==
+Esmalt tuleb teha oma mängu klass:
+<pre>
+import games
+class BearGame(games.Game):
+    def __init__(self):
+        # algseis jne initsialiseerimine
+    def to_move(self, state):
+        # otsusta, kuidas karu ja jahimeeste poolt tähistada ja tagasta, kumb pool käigul on
+    def actions(self, state):
+        # kõik seisus võimalikud käigud
+    def result(self, state, action):
+        # uus seis peale käigu tegemist
+    def utility(self, state, side):
+        # mis on seisu väärtus antud poole jaoks (ei võrdu alati
+        #   sellega, kelle käik antud seisus on)
+        # täidab ka eval() funktsiooni rolli
+    def terminal_test(self, state):
+        # siin peaks ära tundma, kas karu on lõksu aetud
+</pre>
+<code>Game</code> klass sisaldab ka <code>play_game()</code> meetodit, millega saab mängu mängida. Käikude jne testimiseks võid proovida ka ilma otsinguta mängida:
+<pre>
+bg = BearGame()
+bg.play_game(games.query_player,
+              games.random_player)
+</pre>
+Esimene parameeter on, kes karu poolt mängib (kuna nõuete järgi karu alustab), teine, kes mängib jahimehi. Näites olevad abifunktsioonid küsivad vastavalt käiku inimeselt või teevad juhusliku käigu. Kui parameetrid ära vahetad, saad teist poolt mängida.
+Otsingut kasutades tuleks kindlasti kohe ka sügavus ära piirata:
+<pre>
+def alphabeta_depth8(game, state):
+    return games.alphabeta_cutoff_search(state, game, d=8)
+bg.play_game(games.query_player,
+              alphabeta_depth8)
+</pre>

Iti0210lab6: erinevus redaktsioonide vahel

Viimane redaktsioon: 8. oktoober 2018, kell 09:25

Sisukord

Alpha-beta otsing

Sissejuhatus

Nõuded

Elementaarsed asjad

Paremini mängimine

`games.Game` klassi kasutamise näited ja vihjed

Navigeerimismenüü

Iti0210lab6: erinevus redaktsioonide vahel

Viimane redaktsioon: 8. oktoober 2018, kell 09:25

Alpha-beta otsing

Sissejuhatus

Nõuded

Elementaarsed asjad

Paremini mängimine

games.Game klassi kasutamise näited ja vihjed

Navigeerimismenüü

Otsing

`games.Game` klassi kasutamise näited ja vihjed