Iti0210lab62

Otsingu kasutamine mängu mängimiseks

Sissejuhatus

Strateegiamängudes, nagu male, go jne on võimalik hea käigu leidmiseks kasutada sügavutiotsingu varianti nimega minimax. Meie proovime mängida mängu, kus on ka juhuslik element: seamäng. Lühidalt:

• mängitakse selleni, kes saab enne 100 punkti. Alguses on mõlemal mängijal 0 punkti.
• mängija võib veeretada ühte täringut mitu korda järjest, senikaua kuni ta ei veereta 1. Tulemused liidetakse kokku.
• kui mängija otsustab, et soovib veeretatud punktid alles hoida, liidetakse need tema kogusummale ja kord läheb vastasele.
• kui mängija veeretab 1, siis läheb kord vastasele ja mängija kaotab kõik selle korra jooksul veeretatud punktid.

Seega on tegu mänguga, kus tuleb otsustada, kui palju riskida. Minimax algoritmi mõttes on siin mõlemal poolel kaks võimalikku käiku - "veereta veel" või "anna käik vastasele". Lisaks, kuna üks mängija võib veeretada mitu korda järjest, siis puus ei ole selgeid MIN ja MAX tasandeid - üks mängija võib teha mitu otsust järjest. Kuna meil on tegemist ka juhuslikkusega, siis kasutame expectiminimax algoritmi (õpik [AIMA] 5.5). See lisab otsingupuusse ka juhuslikkuse sõlmed (chance nodes).

Kasutajaliidesele jne pole vaja rõhku panna. Oluline osa tööst on kasutada käigu (otsus, kas veeretada või anda kord vastasele) leidmiseks expectiminimax algoritmi. Ülesande lahendamise eelduseks on, et saad juba enam-vähem aru, kuidas töötab minimax: [AIMA] õpikust osad 5.1, 5.2 ja 5.4. Suhteliselt asjaliku kirjelduse, kuidas minimax otsingupuud läbib, leiad ka siit, võid vaadata ka harjutustunnis tehtud minimax demo.

Ettevalmistus

Proovime kõigepealt mängu niisama mängida. Siin on lihtne Pythoni implementatsioon:

import random

AI = 0
PLAYER = 1

ROLL = 0
PASS = 1

def pig_game(ai_func):
    rolled = 0
    turn = PLAYER
    player_points = ai_points = 0

    while player_points < 100 and ai_points < 100:
        print("Your points", player_points,
            "AI points", ai_points,
            "holding", rolled)

        if turn == PLAYER:
            decision = ROLL
            if rolled > 0:
                s = input("Do you want to keep rolling (Y/n)? ")
                if len(s) > 0 and s[0].lower() == "n":
                    decision = PASS

            if decision == PASS:
                rolled = 0
                turn = AI
            else:
                dieroll = random.randint(1, 6)
                print("You rolled...", dieroll)
                if dieroll == 1:
                    player_points -= rolled # lose all points again
                    rolled = 0
                    turn = AI
                else:
                    rolled += dieroll
                    player_points += dieroll

        else:
            decision = ai_func(turn, rolled, ai_points, player_points)
            if decision == PASS:
                print("-- AI decides to pass.")
                rolled = 0
                turn = PLAYER
            else:
                dieroll = random.randint(1, 6)
                print("-- AI rolled...", dieroll)
                if dieroll == 1:
                    ai_points -= rolled # lose all points again
                    rolled = 0
                    turn = PLAYER
                else:
                    rolled += dieroll
                    ai_points += dieroll

    if player_points >= 100:
        print("You won!")
    elif ai_points >= 100:
        print("AI won.")

Vaja on ka mingit "tehisintellekti", mis vastase osa mängiks. Üks variant võiks olla selline:

def dummy_ai(turn, rolled, my_points, opp_points):
    if rolled < 21:
        return ROLL
    else:
        return PASS

dummy_ai implementeerib suhteliselt agressiivse strateegia, mis mänguseisule tähelepanu ei pööra, aga üritab iga kord vähemalt 21 punkti veeretada. "AI" funktsioonile on antud mõned parameetrid, mida edaspidi vaja läheb: mängu seis punktide kujul, lisaks kelle kord on (turn) ning kui palju mängija on praeguse korra jooksul punkte kogunud (rolled).

Mängu saad käima panna nii:

pig_game(dummy_ai)

Expectiminimax

Nüüd teeme lisaks dummy_ai-le ka otsingupõhise "AI". Õpikus on algoritm antud rekursiivse funktsioonina:

Ka meil on mõistlik see rekursiivsena teha. Algoritmis on 4 osa:

1. rekursiooni lõpetamise tingimus: kui keegi on võitnud, või me ei taha otsinguga sügavamale minna, tuleks tagastada seisu numbriline väärtus (Utility), mida suurem seda parem "AI" jaoks.
2. MAX-sõlm: kui on parajasti "AI" käik, peaks ta leidma, kumb käik annab kõrgema skoori - veeretamine või lõpetamine, s.t. kutsuma välja rekursiivse otsingu mõlema juhtumi jaoks.
3. MIN-sõlm: vastase käigu korral tuleb leida madalaim võimalik skoor, kuna peame eeldama (kartma), et vastane mängib nii hästi kui suudab.
4. Juhuslik sõlm: iga kord, kui keegi otsustab veeretada, tuleb siin käsitleda kõik 6 võimalikku tulemust - muuta seisu nii nagu täringuveere seda teeks ning hinnata iga juhtumit rekursiivse otsinguga. Tulemustest võtta keskmine.

Algoritmi jaoks võid kasutada seda toorikut. Arvesta, et otsingu esimesel tasemel (otsingupuu juur) tuleb leida ja tagastada, milline käik on parem. Edaspidi tuleb arvutada ja tagastada ainult skoori. Tavaliselt on mänge mängivates programmides esimene ja järgmised tasemed ka eraldi funktsioonidena tehtud.

def minimax_ai(turn, rolled, my_points, opp_points):
    # this is the top level of search
    # we search all possible moves
    # (PASS and ROLL in case of the Pig game)
    # and pick the one that returns the highest minimax estimate

Ning rekursiivne osa:

def exp_minimax(turn, chance, rolled, my_points, opp_points, depth):
    # update remaining depth as we go deeper in the search tree
    depth = depth - 1

    # case 1a: somebody won, stop searching
    # return a high value if AI wins, low if it loses.

    # case 1b: out of depth, stop searching
    # return game state eval (should be between win and loss)

    # case 2: AI's turn (and NOT a chance node):
    # return max value of possible moves (recursively)

    # case 3: player's turn:
    # return min value (assume optimal action from player)

    # case 4: chance node:
    # return average of all dice rolls

Lisatud on parameetrid chance - kas tegu on juhuslikkuse sõlmega ja depth, mis piirab otsingu sügavust - kui see muutub 0-ks, peaks otsingu lõpetama. Miks on vaja eraldi arvet pidada, kelle käik ja kas tegu chance node-ga? Põhjus selles, et peale täringu veeretamist ei lähe mänguõigus tingimata vastasele üle, seega tuleb meeles pidada, kes parajasti veeretab.

Seamängus on mänguseis väga lihtne ning seda võib edasi anda kolme numbrilise väärtusega: "AI" punktid, vastase punktid ning kui palju hetkel veeretav mängija on kogunud. Kui soovid, võid edasi anda ka viimase täringuveeretuse tulemuse, kui arvad, et see võiks seisu hinnangut mõjutada.

Lisaülesanne

Selle osa tegemine ei ole kohustuslik. Muuda pig_game funktsiooni või tee ise sobiv lahendus nii, et dummy_ai ja minimax_ai saaks omavahel mängida. Lase neil mängida näiteks 100 või suurem arv mänge ning pea arvet võitude ja kaotuste üle.

Kui oled expectiminimax-i õigesti teinud, võiks see "dummy" strateegia vastu rohkem võite saada kui kaotusi.