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 alati 2x2 (s.t. 9 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.