Playing Nine Men's Morris with Monte Carlo Tree Search and a Neural Network

Stanojkovska, Iva (avtor), Šter, Branko (mentor)

As the use of AI increases, so does our curiosity and ideas of what can be achieved with it. We, as humans, have certain limitations when it comes to memory, planning and decision-making. We don’t have the capability to plan significantly far into the future and make choices that would guarantee, or at least maximize success, even for simpler things like board games. A simple game, like Tic Tac Toe, is still within our limits, but if you turn to chess or Go, the possible states and moves for these games would not be comprehensible to a human brain. This is where computer algorithms step in. One of the most promising methods for successful decision making is the Monte Carlo tree search, which is the basis for the algorithm developed for this thesis. We will focus on the game of Nine Men’s Morris - which is neither an overly simple game like Tic Tac Toe nor as complex as chess or Go. In this thesis, we will explore a possible way of utilizing Monte Carlo Tree Search in combination with neural networks to develop an algorithm to play Nine Men’s Morris, based on the computer program Alpha Zero.

• Jezik: Angleški jezik
• Ključne besede: artificial intelligence, Monte Carlo tree search, convolutional neural networks, reinforcement learning, Alpha Zero, nine men's morris
• Vrsta gradiva: Diplomsko delo/naloga
• Tipologija: 2.11 - Diplomsko delo
• Organizacija: FRI - Fakulteta za računalništvo in informatiko
• Leto izida: 2025
• PID: 20.500.12556/RUL-167753
• COBISS.SI-ID: 230547459
• Datum objave v RUL: 10.03.2025

Sekundarni jezik

• Jezik: Slovenski jezik
• Naslov: Igra Mlin z drevesnim preiskovanjem Monte Carlo in nevronsko mrežo

Izvleček

Z vse večjo rabo umetne inteligence raste tudi naša radovednost in ideje o tem, kaj lahko dosežemo z njo. Ljudje imamo določene omejitve, ko gre za spomin, načrtovanje in odločanje. Nimamo sposobnosti načrtovanja daleč v prihodnost in sprejemanja odločitev, ki bi zagotovile oz.\ maksimizirale uspeh, ob upoštevanju vseh možnosti, tudi za nekaj tako preprostega kot igra. Preprosta igra, kot so Križci in krožci (Tic Tac Toe), je morda še vedno znotraj naših zmožnosti, pri kompleksnejših igrah kot sta npr. šah ali Go, pa je možnih stanj in potez za človeške možgane preprosto preveč. Tukaj nastopijo računalniški algoritmi. Ena najbolj obetavnih metod uspešnega odločanja je drevesno preiskovanje Monte Carlo, ki je osnova za algoritem, uporabljen v diplomskem delu. Osredotočili se bomo na igro mlin, ki je zahtevnejša kot Tic Tac Toe, a hkrati še vedno preprostejša kot šah ali Go. V diplomskem delu bomo raziskali možen način uporabe drevesnega preiskovanja Monte Carlo v kombinaciji z nevronskimi mrežami za razvoj algoritma za igranje igre mlin, ki temelji na računalniškem programu Alpha Zero.

• Ključne besede: umetna intelignca, drevesno preiskovanje Monte Carlo, konvolucijske nevronske mreže, spodbujevano učenje, igra mlin