Iti0210lab14

Hüvitisega õppimine

Sissejuhatus

Rakendame hüvitisega õppimist (reinforcement learning) seamängule, millega puutusime kokku 4. praktikumis. Reeglid uuesti:

• 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.

Rakendame Q-Learning algoritmi. Lihtne selgitus Q-Learning algoritmi kohta.

Treeni oma algoritm, lastes tal mängida iseenda vastu ja niiviisi seamängu strateegia täiesti iseseisvalt avastada. Seejärel katseta dummy_ai vastu, mitu korda näiteks 100 mängust sinu algoritm võidab. Et võrdlus aus oleks, pane 50% mängudest alustajaks oma algoritm ja 50% dummy_ai. Et mõista, kuidas Q-learning töötab, vaatame ka õpitud Q-tabelit.

Q-Learning seamängu jaoks

Kõigepealt, mis on olek ja mis on tegevus?

Lihtne soovitus oleks võtta olekuks praegused punktid (AI-l 0-100 ja vastasel 0-100) ning "käes" olevad punktid. Tegevus on loomulikult ROLL ja PASS, muid valikuid pole.

Juhuslikkus seamängus

Kuigi seamäng on lihtne, siis juhuslikkus teeb iseseisva õppimise raskeks. Näiteks, AI võib teha 3 korda järjest samas seisus õige käigu, aga iga kord ebaõnne tõttu kaotada. Seega õpib ta hoopis, et käik oli halb.

Juhuslikkuse vastu võitlemine:

1. Õpime aeglaselt. Paneme learning rate parameetri, ehk alpha, üsna väikese.
2. Üldistame. Paneme sarnased olekud kokku üheks olekuks. Kui AI satub samasse olekusse palju kordi, siis erandlikud juhused ei mängi enam nii suurt rolli.

Näidis, kuidas punktidest olekuid saada. Selle koodiga tekib 11x11x11 olekut.

def state_idx(ai_points, opp_points, rolled):
    ap = min(ai_points//10, 10)    # ai points: 0-9, 10-19, ..., 90-99, 100
    op = min(opp_points//10, 10)
    r = min(rolled//5, 10)         # rolled: 0-4, 5-9, ..., 45-49, 50+
    return (ap, op, r)

Edasi on juba maitse asi, kas kasutada lihtsalt kogu kolmikut indeksina, või teha mitmemõõtmeline massiiv. Kuna õpitakse Q[s, a] tabelit, siis juurde tuleb veel üks dimensioon - tegevus, ROLL või PASS.

Käigu valimine

Primitiivne meetod (greedy): oletame, et seis on 30 punkti AI-l, 90 punkti vastasel. Käes on 0 punkti. Vaatan tabelist, kumb tegevus on suurema skooriga, Q[state_idx(30,90,0)][PASS] või Q[state_idx(30,90,0)][ROLL].

Erinevaid võimalusi katsetav meetod (epsilon-greedy): väike tõenäosus epsilon, et valitakse juhuslik käik.

Õppimine

Oletame, et tegevus on tehtud ja teada uus_olek ning ka parim võimalik skoor, mida uuest olekust võimalik saavutada max_Q = max(Q[uus_olek][PASS], Q[uus_olek][ROLL]) . Lisaks tasu R mis on 0, v.a. juhul kui keegi just võitis või kaotas.

Seamängu puhul peame kindlasti kasutama alpha parameetrit, mis ütleb, kui palju me iga uue kogemusega vana teadmist unustame ja uut juurde võtame:

Q[vana olek][tegevus] += alpha * (R + gamma * max_Q - Q[vana olek][tegevus])

Treenimine ja testimine

"Q-õppimise" algoritm seamängu jaoks - iga kord, kui on AI käik, tee need tegevused:

1. Õpi eelmise käigu tulemusest (mängu alguses tuleb see samm vahele jätta)
2. Vali uus käik
3. Jäta olek enne käiku ja valitud käik meelde.

Sellisel juhul pole vahet, kas kahe käigu vahel veeretatakse lihtsalt korra täringut või teeb vastane terve pika käikude seeria. AI saab iseenda vastu mängida, kui kasutad mõlema poole käikude valimiseks ql_ai meetodit (vt. allpool), aga treenimise mõttes on mõistlik, kui käsitled programmikoodis ühte poolt õppiva AI-na ja teist poolt lihtsalt treeningpartnerina. Siis on teoorias võimalik treenida suvalise programmi või isegi inimese vastu.

Kasuta testraamistikku, mida kasutasid 4. praktikumi jaoks. Tee see ümber nii, et kaks programmi saaksid omavahel mängida.

Kuna Q-tabelit tuleb meeles pidada, siis oleks meie õppiva AI puhul mõistlik kasutada objektorienteeritud lähenemist:

class QLearner:
    def __init__(self):
        self.Q = {}
        self.gamma = 0.8    # discount factor
        self.alpha = 0.05   # learning rate

    def ql_ai(self, turn, rolled, my_points, opp_points):
        # compatibility parameters:
        #   turn - can be ignored
        # useful parameters:
        #   rolled, my_points, opp_points - the current state, to determine
        #                                  action: PASS or ROLL

    def update(self, s, action, reward, s_prim):
        # s - old state (my points, opp points, rolled)
        # action - action taken from state s
        # reward - 0 usually, 100 if I won, -100 if I lost
        # s_prim - new state. What happened after my action was taken

Kui oled mõned korrad (100-1000) QLearner-it iseenda vastu treeninud, lase tal vahepeal ~100 mängu testiks dummy_ai vastu mängida, siis treeni edasi jne. Võiduprotsent võiks alguses tõusta ja pidama jääda kusagile 0.5 juurde. Kui see juhtub, on su programm iseseisvalt mängu selgeks õppinud. Meeldetuletuseks, dummy_ai oli selline:

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

Mida õpiti

Kui programm on treenitud, võta Q-tabelist välja osa, mis vastab strateegiale juhul, kui vastasel on 50 punkti. Lisa see oma aruandesse, umbes sellisel kujul:

AI punkte \ käes	0-4	5-9	...	50+
0-9	5 / 5	5 / -10	...	-90 / 90
10-19	7 / 8	-19 / 4	...	-80 / 99
...	...	...	...	...
100	100 / 100	100 / 100	...	100 / 100

Siin näites on ROLL/PASS skoorid pandud ühte ruutu. Aruanne peaks olema kompaktne (1lk) ja loetav, data dump siia ei sobi.

Lisaülesanne

Ideid katsetamiseks (seda osa pole kohustuslik teha):

1. Tee graafik, kuidas võiduprotsent dummy_ai vastu muutub. Selleks vaheldumisi treeni, siis tee testmänge. Parem kui testmängude ajal on õppimine välja lülitatud.
2. Kuidas see graafik muutub parameetrite alpha, gamma, epsilon muutmisel?
3. Võib proovida treenida ka dummy_ai või minimax algoritmi vastu.