Attacking SameGame using Monte-Carlo Tree Search : Using randomness as guidance in puzzles

Abstract: Since the birth of the computer, the creation of algorithms to beat humans in games has been a hot topic, algorithms that if successful often have vast implications. For some games and problems however, it has been notoriously difficult for computers to perform well. But in 2006 an algorithm known as Monte-Carlo Tree Search (MCTS) was invented that boosted the performance of computers in some of the difficult two-player games, e.g. computer Go. Around the same time researchers started to look into how MCTS could be applied to single-player domains, one of them was the puzzle of SameGame. This thesis will continue the work on SameGame to further improve algorithms, ideas and knowledge on how to attack puzzles using MCTS. We mainly used a test set consisting of 250 randomly generated SameGame instances to evaluate the performance of various techniques. Doing this we managed to devise - among many things - a number of MCTS variations dynamically updating their explorative factor, leading not only to a clear improvement in performance but also mitigating the task of manually tuning parameters for the programmer. By combining ideas that empirically proved themselves successful in isolation, an algorithm matching (and sometimes outperforming) the performance of the previous NMCTS algorithm while using only a fraction of the resources was created, and on a different well known test set two competitive scores of 78936 and 80146 points were achieved. The results suggest that there are still many ways in which MCTS for single-player domains may be improved, and many unexplored lines of thought remain. This work's contribution lies not in a single algorithmic idea tuned to perfection, but in the survey of several ideas and their combination, providing a solid foundation for future research to build upon.