A data-driven approach for making a quick evaluation function for Amazons

Abstract

Amazons is a two player game, which is more complex than Chess, but not as complex as Go. That makes it a natural test bed for computer game research. Traditionally in computer Amazons research an algorithm called alpha-beta pruning, or a variation thereof, is used to search for the best move to play. Kloetzer et al. (2007) introduced Monte Carlo tree search as an alternative search algorithm. Monte Carlo tree search works by simulating many random progressions of the game. It performs better when more random games are considered. The more simulations, the better. Naively one might think that the best evaluation function yields the best results. This is not necessarily true. More advanced evaluation functions typically use more time than simpler evaluation functions, which leads to fewer simulations and thus poorer results. There is an interesting balance to strike: the evaluation function should be reliable, yet not take much time to compute.

In this thesis artificial neural networks are trained in order to act as an evaluation function. Neural networks may take long to train, but once trained they are able to quickly map inputs to outputs. Even if the quality of the evaluation is less then traditional evaluation functions, they may increase the performance of Monte Carlo tree search because they allow for many more simulations.