Tehisintellekt õpib mängima

Õpieesmärgid

Selle peatüki läbimise järgselt oskad:

• Hinnata mängimaõppimise olulisust tehisintellekti arenguloos
• Õpetada ise tehisintellektile trips-traps-trulli mängimist Minimax algoritmiga
• Selgitada kuidas piitsa ja prääniku meetod aitab tehisintellekti agentidel paremini mängida

Mängude roll tehisintellekti arengus

Tehisintellekti (TI) arengu jooksul on mängude mängima õpppimisel olnud oluline roll mitmel põhjusel, mis ulatuvad teaduslikust uudishimust kuni praktiliste rakendusteni.

• Kontrollitud keskkond:

  Mängud pakuvad kontrollitud keskkonda, kus saab testida ja täiustada algoritme, mis lahendavad keerulisi probleeme.

  Erinevalt pärismaailmast on see keskkond ohutu ja kuluefektiivne, lubades TI-l katsetada, ebaõnnestuda ja õppida miljonite simulatsioonide kaudu ilma reaalsete tagajärgedeta.

• Keerukad strateegilised ülesanded:

  Mängud, nagu male, Go või StarCraft II, esindavad keerukaid strateegilise otsustamise ülesandeid, mis nõuavad pikaajalist planeerimist, kohanemisvõimet ja loovust.

  Need omadused on ülekantavad paljudesse reaalmaailma rakendustesse, näiteks isesõitvatesse autodesse, logistika optimeerimisse, meditsiinisüsteemidesse ja küberjulgeolekusse.

• Tehisintellekti arendamine:

  Mängud on ideaalsed stiimulõppe ja sügavõppe algoritmide arendamiseks, mis võimaldavad tehisintellektil õppida läbi katsetamise ja tagasiside.

  Mängud on loomulik viis inimese ja masina suhtlemiseks ning nende kaudu saab uurida, kuidas paremini kujundada intuitiivseid ja tõhusaid kasutajaliideseid.

See teeb mängudest mitte ainult teadusliku uurimistöö vahendi, vaid ka praktilise viisi, kuidas valmistada tehisintellekti ette reaalsete probleemide lahendamiseks.

Tehisintellektile mängude õpetamise tehnilise protsessi etapid

1. Keskkonna määratlemine

• Mängu valik: Valitakse mäng, mida tehisintellekt hakkab mängima. See võib olla lauamäng, videomäng või mõni muu mängulaadne keskkond.
• Keskkonna modelleerimine: Määratletakse, kuidas tehisintellekt suhtleb mängukeskkonnaga. See hõlmab mänguseisude esitust, võimalikke tegevusi ja tasustamissüsteemi (näiteks punktid või võit/kaotus). Mänguseisude esitus võib olla erinev: näiteks pildid (pikslid), numbrilised väärtused (nt malelaual malendid) või sümbolid.

• Mängureeglite formaliseerimine: Kõik mängureeglid tuleb täpselt määratleda ja programmeerimiskeelde tõlkida. See hõlmab lubatud käike, võidutingimusi ja erijuhtumeid.
• Seisundiruumi analüüs: Hinnatakse kõikvõimalike mänguseisude arvu ja keerukust. Näiteks males on umbes 10^43 võimalikku seisu, mis mõjutab oluliselt õppimisstrateegiat.
• Tegevusruumi määratlemine: Defineeritakse kõik võimalikud tegevused, mida tehisintellekt saab igas seisus sooritada.

2. Algoritmi valik

• Stiimulõppe algoritmi valik: Valitakse sobiv stiimulõppe algoritm, nagu Q-õpe, sügav Q-õpe (DQN), või mõni teine sügavõppele põhinev algoritm (nt. Policy Gradient Methods, Actor-Critic Methods). Algoritmi valik sõltub mängu keerukusest, andmete hulgast ja soovitud tulemustest.
• Närvivõrgu arhitektuuri valik: Kui kasutatakse sügavat õppimist, tuleb valida sobiv närvivõrgu arhitektuur. Näiteks võib kasutada konvolutsioonilisi närvivõrke (CNN), mis on eriti head piltide analüüsimiseks, kuna nad suudavad tuvastada mustreid ja objekte pildis. Või hoopis korduvaid närvivõrke (RNN), mis sobivad jadade analüüsimiseks, näiteks mängu ajalugu või sõnade järjekord.
• Mudelite võrdlus: Erinevate arhitektuuride ja algoritmide testimine väiksema andmestikuga, et valida sobivaim lähenemine.

3. Õppimisprotsess

• Andmete kogumine: Tehisintellekt mängib mänge ja kogub kogemusi. Alguses võib see olla juhuslik avastamine (exploration) või põhineda lihtsatel, juba õpitud parimatel strateegiatel (exploitation). Saadud kogemused kogutakse kokku ja salvestatakse. Liiga palju avastamist võib olla ebaefektiivne, kui agent proovib liiga palju juhuslikke ja uusi asju, selle asemel et kasutada juba teadaolevaid toimivaid strateegiaid.

  Samas, kui tehisintellekt keskendub liigselt juba õpitud strateegiate kasutamisele, võib ta kinni jääda lokaalselt optimaalsetesse lahendustesse, olles rahul "piisavalt hea" strateegiaga ja jättes potentsiaalselt paremad lahendused leidmata, kuna ta ei uuri piisavalt alternatiivseid võimalusi.

• Preemiate määramine: Määratakse preemiad või karistused vastavalt tehisintellekti tegevustele. Näiteks võidu korral antakse suur preemia, kaotuse korral karistus. Süsteem õpib tegevuse ja tulemuse vahelisi seoseid. Preemiate määramine on sageli kõige keerulisem osa, kuna see peab kajastama mängu eesmärke ja mängija soove. Preemiaid saab anda ka erinevatel ajapunktidel (nt vahetulemused, viivitatud preemiad).

• Stiimulõppe algoritmi rakendamine: Kasutatakse kogutud andmeid ja preemiaid, et treenida tehisintellekti mudelit. Sügava õppimise korral tähendab see närvivõrgu parameetrite uuendamist, et minimeerida viga ennustatud ja tegelike väärtuste vahel.

4. Iteratiivne täiustamine ja optimeerimine

• Iteratiivne mängimine ja õppimine: Tehisintellekt jätkab mängimist ja õppimist, parandades oma strateegiaid kogemuse põhjal.
• Mudeli hindamine: Perioodiliselt hinnatakse tehisintellekti sooritust, võrreldes seda varasemate tulemustega või inimeste sooritusega. Kasutatakse testimist, et hinnata mudeli jõudlust.
• Parameetrite häälestamine: Vajadusel muudetakse algoritmi või närvivõrgu kaalusid, et parandada õppimise efektiivsust. See hõlmab ka hüperparameetrite (nt õppimiskiirus, võrgu suurus) reguleerimist.
• Optimeerimistehnikad:
  • Gradientlaskumine: Optimeerimisalgoritm, mis aitab leida närvivõrgu parameetrite väärtusi, mis minimeerivad kaofunktsiooni.
  • Kaofunktsioon: Mõõdab erinevust ennustuste ja tegelike väärtuste vahel.

5. Kasutuselevõtt ja edasiarendamine

• Lõplik mudel: Kui tehisintellekt saavutab soovitud taseme, võib selle kasutusele võtta praktilisteks rakendusteks.
• Jätkuv täiustamine: Kuigi tehisintellekt on saavutanud teatud taseme, võib jätkata selle täiustamist uute tehnikate või optimeerimismeetoditega.

Selline on mängude õpetamise üldine protsess, mis võib varieeruda sõltuvalt konkreetsest mängust ja valitud lähenemisviisist.

Mänguõppe algoritmid

Tehisintellektile mängude mängima õpetamine on olnud TI arengu üks olulisemaid verstaposte alates 1950. aastatest. Mänguõppe algoritmid jagunevad kahte põhikategooriasse: otsingupõhised ja õppivad algoritmid.

• Otsingupõhised algoritmid nagu Minimax ja Monte Carlo puuotsing (MCTS) analüüsivad igal käigul võimalikke tulevikustsenaariumeid, valides parima tegevuse ilma varasematest mängudest õppimata.

  Need sobivad hästi täieliku informatsiooniga mängudele, kus kõik reeglid on teada ja mänguseisud selgelt määratletud, kuid takerdub keerukamates mängudes niinimetatud kombinatoorse plahvatuse ees, kus käiguvariantide arv muutub hoomamatult suureks.

• Õppivad algoritmid seevastu paranevad kogemuse põhjal. Enamik neist põhineb stiimulõppel – agent teeb mängus otsuseid, saab tagasisidet preemia või karistuse (piitsa ja prääniku) vormis ning õpib maksimeerima pikaajalisi tulemusi.

  Selle asemel, et toetuda toorele arvutusjõule, arendavad algoritmid nagu Q-õpe ja Policy Gradient kogemuse kaudu välja mängulise „intuitsiooni“. Mängides miljoneid kordi ja saades tagasisidet tasude ja karistuste näol, õpib agent iseseisvalt ära võidustrateegiad isegi keskkondades, mille reeglid on talle tundmatud.

Kaasaegsed läbimurded mänguõppes on saavutatud erinevate lähenemiste kombineerimisel. Näiteks AlphaGo ja AlphaZero ühendavad MCTS-i otsinguvõime närvivõrkude mustrituvastuse ja stiimulõppe pideva paranemisega. See hübriidne lähenemine on võimaldanud luua süsteeme, mis ületavad inimeste võimeid keerulistes strateegiamängudes nagu Go ja male.

Järgnevates alapeatükkides vaatleme põhjalikumalt iga algoritmi tööpõhimõtteid, tugevusi ja rakendusi, alustades klassikalistest otsingualgoritmidest ning liikudes edasi kaasaegsete õppivate süsteemideni.

Minimax

Minimax on otsustusalgoritm, mida kasutatakse tehisintellektis, mänguteoorias ja statistikateaduses. See on mõeldud optimaalse käigu leidmiseks kahe mängijaga, käigupõhistes ja täieliku informatsiooniga nullsummamängudes. Tuntumad näited sellistest mängudest on male, kabe, trips-traps-trull ja gomoku.

Algoritmi nimi tuleneb selle põhiprintsiibist: üks mängija (keda nimetame Max) püüab maksimeerida oma potentsiaalset kasu, samal ajal kui teine mängija (Min) püüab minimeerida Max'i kasu. Oluline eeldus on, et mõlemad mängijad mängivad alati enda jaoks parimal võimalikul viisil.

Kuidas see töötab?

Minimax algoritm modelleerib mängu mängupuuna, kus:

• Sõlmed (nodes) esindavad mänguseise.
• Servad (edges) ehk kahe sõlme vahelised ühendused esindavad võimalikke käike.
• Juursõlm (root node) on puu tipus asuv sõlm, meie praegune mänguseis.
• Lapsed (child nodes) on sõlmed, mis asuvad puus ühe taseme võrra madalamal kui tema vanem.
• Lehtsõlmed (leaf nodes) on puus ilma järglasteta sõlmed, antud juhul mängu lõppseisud (võit, kaotus või viik).

Puu on hierarhiline andmestruktuur, kus on üks juursõlm, mis on ühendatud oma laste või alamsõlmedega läbi servade. Sõlmed, millel ei ole lapsi, on lehed.

Minimax algoritmi tööprotsess on järgmine:

1. Mängupuu genereerimine: Algoritm loob (või kujutab ette) mängupuu kuni teatud sügavuseni või kuni mängu lõpuni.
2. Lõppseisude skoorimine: Iga lehtsõlme (lõppseisu) jaoks arvutatakse skoor ehk kasulikkuse väärtus (utility value) Max-mängija vaatenurgast. Näiteks:
   • +1: Max võidab
   • -1: Min võidab (Max kaotab)
   • 0: Viik
3. Tagasiulatuv analüüs (Backtracking): Algoritm liigub puus alt üles, lehtedest juure poole, ja määrab igale vahepealsele sõlmele väärtuse vastavalt sellele, kumma mängija käik on:

• Max-tasandil: Kui on Max-mängija kord käia, valib ta käigu, mis viib suurima skooriga alamsõlmeni. Seega saab praegune sõlm endale väärtuseks oma "laste" väärtustest maksimumi.
• Min-tasandil: Kui on Min-mängija kord käia, valib ta käigu, mis viib vähima skooriga alamsõlmeni (minimeerides Max'i kasu). Seega saab praegune sõlm endale väärtuseks oma "laste" väärtustest miinimumi.

1. Optimaalse käigu valik: Kui väärtused on jõudnud tagasi juursõlmeni, valib Max käigu, mis viib kõige kõrgema väärtusega harusse. See ongi Minimaxi poolt leitud optimaalne käik.

Lihtsustatult öeldes

Minimax püüab leida käigu, mis viib parima võimaliku tulemuseni kõige halvemas võimalikus stsenaariumis. See tähendab, et algoritm valib käigu, mis tagab parima tulemuse isegi siis, kui vastane teeb enda jaoks alati kõige paremad käigud.

Põhiomadused:

• Rekursiivne: Algoritmi on kõige lihtsam implementeerida rekursiivse funktsioonina.
• Sügavuti otsing (Depth-First Search): See uurib mängupuud sügavuti.
• Eeldab optimaalset vastast: Algoritmi efektiivsus sõltub eeldusest, et vastane ei tee vigu.
• Arvutusmahukas: Reaalsetes mängudes nagu male on mängupuu tohutult suur, mistõttu kasutatakse Minimaxi koos optimeerimistehnikatega, millest tuntuim on alfa-beeta kärpimine (Alpha-Beta Pruning), mis aitab vältida ilmselgelt halbade harude analüüsimist.

Q-õppe algoritm

Q-õpe (Q-learning) on üks stiimulõppe alusalgoritme, mis püüab ära õppida iga võimaliku tegevuse „kvaliteedi“ (Q-väärtuse) igas mänguseisus. See väärtus on ennustus, kui palju preemiat TI pikas plaanis saab, kui ta selles olukorras just selle käigu teeb.

Seda võib ette kujutada hiiglasliku tabelina (Q-tabelina), kus ridades on kõik mänguseisud ja veergudes kõik võimalikud käigud. Mängu käigus uuendab tehisintellekt pidevalt selle tabeli väärtusi. Kui mingi käik viib hea tulemuseni (saab tasu), suurendatakse selle käigu Q-väärtust.

Lõpuks õpib agent igas olukorras valima käigu, millel on tabelis kõige kõrgem väärtus. See sobib hästi väiksema hulga olekutega mängudele (nagu trips-traps-trull või labürint), kuid muutub ebapraktiliseks keerulistes mängudes nagu male, kus seisude arv on astronoomiline.

Sügav Q-õppe algoritm

DQN (Deep Q-Network ehk sügav Q-võrk) on Q-õppe edasiarendus, mis lahendab Q-tabeli suuruse probleemi. Selle asemel, et hoida väärtusi hiiglaslikus tabelis, kasutab DQN närvivõrku, et ennustada Q-väärtusi. Närvivõrk võtab sisendiks mänguseisu (näiteks ekraanipildi) ja väljastab hinnangu iga võimaliku käigu oodatava kasulikkuse kohta.

See lähenemine võimaldas tehisintellektil õppida mängima keerulisi mänge, näiteks vanu Atari videomänge, otse piksli-infost, saavutades inimtasemest paremaid tulemusi, kuna närvivõrk suudab leida mustreid ka väga keerulistes ja varem nägemata olukordades.

Policy Gradient

Policy Gradient meetodid on teine lähenemine stiimulõppele. Erinevalt Q-õppest, mis hindab käikude väärtust, õpib see algoritm otse strateegiat (policy) ehk kindlat käitumist. Strateegia ongi reeglistik, mis ütleb, kui tõenäoliselt peaks agent igas olukorras mingi kindla käigu tegema. Ja gradient on nagu nool, mis näitab, millises suunas peab agent oma poliitikat (ehk reegleid) muutma, mäng kulgeks tulemuslikumalt.

Algoritm töötab nii, et esialgu proovib agent tegevusi mõningase juhuslikkusega. Kui tegevuste jada viib hea tulemuseni (võiduni), muudetakse strateegiat nii, et neid tegevusi tehakse tulevikus tõenäolisemalt. Halva tulemuse korral vähendatakse nende tegevuste tõenäosust.

See on nagu lihasmälu treenimine: teed midagi, mis töötab, ja su keha õpib seda automaatselt kordama. See meetod on äärmiselt võimas, sest see suudab õppida väga keerulisi ja rafineeritud strateegiaid otse, ilma et peaks iga üksiku käigu väärtust hindama.

Monte Carlo puuotsing

Monte Carlo puuotsing (Monte Carlo Tree Search e. MCTS) on otsingualgoritm, mida kasutatakse keerukate mängude strateegiate analüüsimiseks. Selle abil simuleeritakse võimalikke mänguseise (otsingupuud) ja hinnatakse, millised käigud on tõenäoliselt parimad.

Algoritm töötab nelja sammuga: valitakse lubavas suunas käik, lisatakse uus seis puusse, mängitakse sealt juhuslik mäng lõpuni ja uuendatakse statistikat. Mida rohkem läbiproovitud situatsioone, seda täpsem hinnang. MCTS oli AlphaGo võidu võti - kombineerides seda närvivõrkudega suutis TI võita maailmameistrit Go mängus. Eelis on, et algoritm keskendub automaatselt paljulubavamatele käikudele ja ei raiska aega halbade variantide uurimisele.