Uporaba drevesnega preiskovanja Monte Carlo in strojnega učenja za učenje hevristične funkcije

FRLIC, KARIN (avtor), Sadikov, Aleksander (mentor)

Algoritem minimaks je eden najbolj razširjenih algoritmov za igranje iger med dvema igralcema. Pri tem se uporablja hevristična funkcija, ki ocenjuje, kako koristno je doseči neko stanje v igri za posameznega igralca. V diplomskem delu poskusimo tako funkcijo za igranje igre Hex ustvariti avtomatsko z uporabo različnih modelov nadzorovanega strojnega učenja. Učne primere za strojno učenje pridobimo s številnimi odigranimi igrami, ki jih simulira MCTS. Ugotovimo, da je igralec, ki za izbiro potez uporablja algoritem minimaks z α-β in naučeno funkcijo, slabši od igralca, ki igra samo z MCTS. Odkrijemo pa, da igralec, ki združi prednosti obeh omenjenih igralcev, igra bolje od MCTS.

• Jezik: Slovenski jezik
• Ključne besede: drevesno preiskovanje Monte Carlo, nadzorovano strojno učenje, algoritem minimaks, hevristična ocenjevalna funkcija, rezanje alfabeta, igra Hex
• Vrsta gradiva: Diplomsko delo/naloga
• Organizacija: FRI - Fakulteta za računalništvo in informatiko
• Leto izida: 2019
• PID: 20.500.12556/RUL-106123
• Datum objave v RUL: 30.01.2019

FRLIC, KARIN, 2019, Uporaba drevesnega preiskovanja Monte Carlo in strojnega učenja za učenje hevristične funkcije [na spletu]. Diplomsko delo. [Dostopano 31 marec 2025]. Pridobljeno s: https://repozitorij.uni-lj.si/IzpisGradiva.php?lang=slv&id=106123

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Using Monte Carlo tree search and machine learning to learn a heuristic function

Izvleček

Minimax algorithm is one of the most widely used algorithms for playing two-player games. It uses a heuristic function that estimates the benefits of reaching a given game state for both players. In this bachelor thesis we attempt to automatically construct that kind of a function for the game of Hex. Different models of supervised machine learning are trained on learning samples, generated by simulations of MCTS. As a result, the player that uses minimax with α-β and the learnt function performs worse than the player that uses pure MCTS. However, the player combining advantages of both players achieves better results than MCTS.

• Ključne besede: Monte Carlo tree search, supervised machine learning, minimax algorithm, heuristic evaluation function, alpha-beta pruning, the game of Hex