Design of artificial intelligence for mancala games

Mancala games are an important family of board games with a millennial history and a compelling gameplay. The goal of this thesis is the design of artificial intelligence algorithms for mancala games and the evaluation of their performance. In order to do so, we selected five of the main mancala games, namely Awari, Oware, Vai Lung Thlan, Ohvalhu and Kalah. Then, we designed and developed several artificial intelligence mancala players: a greedy algorithm, that makes the locally optimal choice; three different versions of the classic Minimax, that applies tree search, guided by an heuristic function that evaluates the state of the game; the more recent Monte Carlo Tree Search algorithm, that builds the search tree in an incremental and asymmetric manner by doing many simulated games, balancing between exploration and exploitation. We evaluated all the mancala algorithms we designed through an extensive series of experiments and discussed their pros and cons.

I mancala sono un'importante famiglia di giochi da tavolo grazie alla loro storia millenaria e alle meccaniche di gioco avvincenti. L'obiettivo di questa tesi è il design algoritmi di intelligenza artificiale per i mancala e l'analisi delle prestazioni in termini di percentuale di vittorie ottenute contro altri algoritmi. Per farlo, abbiamo scelto e implementato cinque tra i più importanti mancala, ovvero Awari, Oware, Vai Lung Thlan, Ohvalhu and Kalah. Abbiamo quindi progettato e sviluppato diversi algoritmi di intelligenza artificiale: un algoritmo greedy, ispirato alle tipiche strategie presentate nei libri di mancala; tre versioni differenti di Minimax, che applica una ricerca ad albero, guidato da una funzione euristica che valuta lo stato di gioco; il più recente Monte Carlo Tree Search, che costruisce l'albero di ricerca in modo incrementale ed asimmetrico simulando molte partite e bilanciando tra esplorazione e ottimizzazione. Abbiamo condotto una estesa serie di esperimenti per valutare la performance degli algoritmi di intelligenza artificiale sviluppati discutendone i pro e contro.