Iti0210lab6

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 mängu raha peale, kihla veeti selle peale, kas karu suudab näiteks 40 käiku vastu pidada.

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

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.

Hästi 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.

Ideed lahenduse jaoks

• kui esitad olekut tegemata käikude kaudu, siis muutub käikude genereerimine actions() meetodis lihtsamaks
• 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 games.Game klassi, siis seal leiduv play_game() 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.
• 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.
• utility() 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.

games.Game klassi kasutamise näited ja vihjed

Trips-traps-trull on games moodulis juba valmis tehtud ja kasutab ka Game klassi. Käima tõmmatakse mäng nii:

import games

ttt = games.TicTacToe()
ttt.play_game(games.query_player,
              games.alphabeta_player)