Strategije drevesnega preiskovanja Monte CarloVodopivec, Tom (Avtor) Šter, Branko (Mentor) preiskovanjeplaniranjespodbujevalno učenjedrevesno preiskovanje Monte Carloigranje igerPo preboju pri igri go so metode drevesnega preiskovanja Monte Carlo (ang. Monte Carlo tree search – MCTS) sprožile bliskovit napredek agentov za igranje iger: raziskovalna skupnost je od takrat razvila veliko variant in izboljšav algoritma MCTS ter s tem zagotovila napredek umetne inteligence ne samo pri igrah, ampak tudi v številnih drugih domenah. Čeprav metode MCTS združujejo splošnost naključnega vzorčenja z natančnostjo drevesnega preiskovanja, imajo lahko v praksi težave s počasno konvergenco – to še posebej velja za temeljne algoritme MCTS, ki ne uporabljajo dodatnih izboljšav. Zaradi tega jih raziskovalci in programerji pogosto združujejo z ekspertnim znanjem, hevristikami in ročno izdelanimi strategijami. Kljub izrazitim dosežkom tako izboljšanih metod (primer je AlphaGo, ki je nedavno prekosil najboljšega človeškega igralca igre Go na svetu in s tem premagal ta velik izziv umetne inteligence), takšne domensko-specifične izboljšave zmanjšujejo splošnost številnih aplikativnih algoritmov. Izboljšati temeljne algoritme MCTS, brez izgube njihove splošnosti in prilagodljivosti, je težko in predstavlja enega aktualnih raziskovalnih izzivov. Ta disertacija uvaja nov pristop za nadgradnjo temeljnih metod MCTS in izpopolnjuje temeljno razumevanje tega področja v luči starejšega ter uveljavljenega področja spodbujevalnega učenja (ang. reinforcement learning). Povezava med drevesnim preiskovanjem Monte Carlo, ki ga skupnost uvršča med metode za preiskovanje in planiranje, ter spodbujevalnim učenjem je že bila nakazana v preteklosti, a še ni bila temeljito preučena in tudi še ni pomembno vplivala na širšo skupnost umetne inteligence. S to motivacijo v tem delu poglobljeno analiziramo povezavo med tema dvema področjema, tako da identificiramo in opišemo podobnosti ter razlike med njima. Uvajamo praktičen pristop razširitve metod MCTS s koncepti iz spodbujevalnega učenja: naše novo ogrodje, drevesno preiskovanje s časovnimi razlikami (ang. temporal difference tree search – TDTS), pooseblja novo družino algoritmov, ki delujejo po konceptih MCTS, obenem pa za učenje koristijo časovne razlike (ang. temporal differences) namesto vzorčenja Monte Carlo. To lahko razumemo kot posplošitev metod MCTS z učenjem s časovnimi razlikami in sočasno kot posplošitev klasičnih metod učenja s časovnimi razlikami z drevesnim preiskovanjem in ostalimi koncepti iz metod MCTS (kot so postopna širitev drevesa in uporaba privzete strategije). S pomočjo metod TDTS pokažemo, da uporaba uveljavljenih konceptov iz spodbujevalnega učenja v navezi z drevesnim preiskovanjem odpira možnosti za razvoj širokega spektra novih algoritmov, od katerih so klasične metode MCTS le ena izmed variant. V naših eksperimentih preizkusimo več tovrstnih algoritmov, osredotočimo pa se na razširitev algoritma UCT (ang. upper confidence bounds for trees) z algoritmom Sarsa(\lambda), ki je eden temeljnih algoritmov spodbujevalnega učenja. Naše meritve potrjujejo, da algoritmi TDTS dosegajo boljše rezultate na enostavnih igrah za enega igralca, klasičnih igrah za dva igralca in arkadnih video igrah: novi algoritmi ohranjajo robustnost in računsko ter pomnilniško zahtevnost, obenem pa konsistentno prekašajo algoritme MCTS. Naše ugotovitve zmanjšujejo razkorak med drevesnim preiskovanjem Monte Carlo in spodbujevalnim učenjem ter pozivajo k močnejšemu nadaljnjemu povezovanju teh dveh področij. Nazadnje, ta disertacija spodbuja k raziskovanju in uveljavljanju bolj enotnega pogleda na dve izmed temeljnih paradigem umetne inteligence – preiskovanje in učenje.20182018-01-12 12:40:07Doktorsko delo/naloga99313sl