Iti0210lab6

Minimax ja alpha-beta

Sissejuhatus

Loe läbi "Dots and Boxes" mängu kirjeldus ja reeglid (kuni sisukorrani, strateegia jne pole vajalik).

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.

Nõuded

1. Kasutajaliides on tekstipõhine
2. Mängulaud on 2x2 (s.t. 9 punkti) või 3x3 (16 punkti)
3. Inimene alustab alati
4. Programm kasutab kas minimax või alpha-beta algoritmi

Mängu mängimine võiks välja näha umbes nii:

...

Your move? (2,5)
current state:
* --- *     * 
      |      
*     *     * 
|           |
*     *     * 
available moves: {(4, 5), (5, 6), (1, 4), (8, 9), (2, 3), (3, 6), (7, 8), (5, 8)}


Your move? (1,4)
current state:
* --- *     * 
|  X  |      
* --- *     * 
|           |
*     * --- * 
available moves: {(2, 3), (3, 6), (5, 6), (7, 8), (5, 8)}


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 üks pool võidab, peale seda kuvab programm, kes võitis ja lõpetab.

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):

• 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.
• Implementeeri ise [AIMA] õpiku Figure 5.3 või 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.

Mitu käiku järjest

minimax ja selle edasiarendused eeldavad, et käike tehakse kordamööda. Selles mängus see tingimata nii ei ole. Kõige lihtsam viis on käsitleda ühe mängija järjestikuseid käike nii, et teine mängija teeb "tühja käigu" - seis ei muutu, aga mängujärg antakse jälle vastasele. See võimaldab puuotsingus minimax väärtusi või alpha ja beta rajasid korrektselt edasi anda.

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.