Iti0210lab6

Alpha-beta otsing

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

Nõuded

notatsioon

1. Kasutajaliides on tekstipõhine
2. 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.
3. Algseisus on karu käik
4. 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)