Monte Carlo Tree Search (MCTS) and its applications in board and card games are the center around which this thesis revolves. MCTS entered the field of Artificial Intelligence (AI) in 2006 when Rémi Coulom et al. combined tree search with Monte-Carlo evaluations which introduced independence from domain knowledge and a fine-grained control of the growth of the tree. The purpose of our study is the evaluation of the possibility of creating a MCTS-based AI that can perform as well as one of the strongest free and open source AI in playing the board game Nine Men’s Morris. Getting inspiration from the successful application of MCTS to a variety of board and card games, in this thesis we will try to evaluate the creation of such MCTS-based Nine Men’s Morris playing agent by evaluating its performances and trade-offs. Our results show that a Greedy strategy is the weakest of all and MiniMax the strongest and that the MCTS algorithm using 4096 number of playouts in the simulation steps is as strong as the 2-ply MiniMax while being less performant.

Monte Carlo Tree Search (MCTS) e le sue applicazioni nei giochi da tavola e nei giochi di carte sono il centro attorno al quale ruota questa tesi. MCTS ha fatto ingresso nel campo dell'Intelligenza Artificiale (IA) nel 2006 quando Rémi Coulom et al. hanno combinato l'albero di ricerca con le valutazioni di Monte-Carlo ed hanno permesso di introdurre indipendenza dalla conoscenza del dominio di applicazione e un controllo più dettagliato della crescita dell'albero. Lo scopo del nostro studio è valutare la possibilità di creare una IA basata su MCTS che può performare allo stesso modo della più forte ed open source IA nel giocare a Nine Men's Morris. Prendendo ispirazione dal successo con cui MCTS è stato applicato a svariati giochi in scatola e giochi di carte, in questa tesi proveremo a valutare la creazione di un agente basato su MCTS capace di giocare a Nine Men's Morris misurandone le prestazioni ed i compromessi. I nostri risultati mostrano che la strategia Greedy è la più debole di tutte le strategie e MiniMax la più forte e che l'algoritmo MCTS che usa 4096 iterazioni durante la fase di simulazione è tanto forte quanto il MiniMax a profondità 2 restando comunque poco performante.

Monte Carlo tree search applied to Nine Men’s Morris

ANDALORO, SERGIO
2015/2016

Abstract

Monte Carlo Tree Search (MCTS) and its applications in board and card games are the center around which this thesis revolves. MCTS entered the field of Artificial Intelligence (AI) in 2006 when Rémi Coulom et al. combined tree search with Monte-Carlo evaluations which introduced independence from domain knowledge and a fine-grained control of the growth of the tree. The purpose of our study is the evaluation of the possibility of creating a MCTS-based AI that can perform as well as one of the strongest free and open source AI in playing the board game Nine Men’s Morris. Getting inspiration from the successful application of MCTS to a variety of board and card games, in this thesis we will try to evaluate the creation of such MCTS-based Nine Men’s Morris playing agent by evaluating its performances and trade-offs. Our results show that a Greedy strategy is the weakest of all and MiniMax the strongest and that the MCTS algorithm using 4096 number of playouts in the simulation steps is as strong as the 2-ply MiniMax while being less performant.
ING - Scuola di Ingegneria Industriale e dell'Informazione
28-set-2016
2015/2016
Monte Carlo Tree Search (MCTS) e le sue applicazioni nei giochi da tavola e nei giochi di carte sono il centro attorno al quale ruota questa tesi. MCTS ha fatto ingresso nel campo dell'Intelligenza Artificiale (IA) nel 2006 quando Rémi Coulom et al. hanno combinato l'albero di ricerca con le valutazioni di Monte-Carlo ed hanno permesso di introdurre indipendenza dalla conoscenza del dominio di applicazione e un controllo più dettagliato della crescita dell'albero. Lo scopo del nostro studio è valutare la possibilità di creare una IA basata su MCTS che può performare allo stesso modo della più forte ed open source IA nel giocare a Nine Men's Morris. Prendendo ispirazione dal successo con cui MCTS è stato applicato a svariati giochi in scatola e giochi di carte, in questa tesi proveremo a valutare la creazione di un agente basato su MCTS capace di giocare a Nine Men's Morris misurandone le prestazioni ed i compromessi. I nostri risultati mostrano che la strategia Greedy è la più debole di tutte le strategie e MiniMax la più forte e che l'algoritmo MCTS che usa 4096 iterazioni durante la fase di simulazione è tanto forte quanto il MiniMax a profondità 2 restando comunque poco performante.
Tesi di laurea Magistrale
File allegati
File Dimensione Formato  
2016_09_Andaloro.pdf

accessibile in internet solo dagli utenti autorizzati

Descrizione: Thesis text
Dimensione 2.81 MB
Formato Adobe PDF
2.81 MB Adobe PDF   Visualizza/Apri

I documenti in POLITesi sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10589/126365