Evolving UCT alternatives for general video game playing

Artificial General Intelligence (AGI) and Monte Carlo Tree Search (MCTS) applied to video games is the context where this thesis takes place. Since 2014 when the first General Video Game AI competition was run, a contest for AGIs, MCTS-based agents have shown their superiority. The objective of this work is to show how to evolve effective MCTS heuristics for a specific game solely using game-play results and how these new heuristics, with none or limited domain information provided, can surpass the performance of a standard implementation of MCTS. The results show how adding more informations available to the heuristic can dramatically increase its performance. But more interestingly, they show how the heuristics can synthesize in a clear and neat formula the objectives of the game chosen.

Questa tesi si sviluppa nel contesto della Artificial General Intelligence (AGI) e della Monte Carlo Tree Search (MCTS) applicati ai video giochi. Sin dal 2014 quando la prima competizione di General Video Game AI fu disputata, una sfida tra diverse intelligenze artificiali generiche, agenti basati su MCTS hanno dimostrato la loro superiorità. L'obbiettivo di questo lavoro è mostrare come sia possibile evolvere euristiche efficaci per MCTS per un gioco specifico, utilizzando solamente gli esiti del gioco diretto e come queste nuove euristiche, con nessuna o poche informazioni sul dominio, possano sorpassare le prestazioni di una implementazione standard di MCTS. I risultati mostrano come aggiungere più informazioni a disposizione dell'euristica possa incrementare drasticamente le sue prestazioni. Ma è ancora più interessante come queste euristiche possano sintetizzare in una formula chiara e ordinata gli obiettivi del gioco scelto.