  Monte Carlo Tree Search (MCTS) is a sampling best-first method to search for
optimal decisions. The success of MCTS depends heavily on how the tree is built
and the selection process plays a fundamental role in this. One particular
selection mechanism that has proved to be reliable is based on the Upper
Confidence Bounds for Trees (UCT). The UCT attempts to balance exploration and
exploitation by considering the values stored in the statistical tree of the
MCTS. However, some tuning of the MCTS UCT is necessary for this to work well.
In this work, we use Evolutionary Algorithms (EAs) to evolve mathematical
expressions with the goal to substitute the UCT formula and use the evolved
expressions in MCTS. More specifically, we evolve expressions by means of our
proposed Semantic-inspired Evolutionary Algorithm in MCTS approach (SIEA-MCTS).
This is inspired by semantics in Genetic Programming (GP), where the use of
fitness cases is seen as a requirement to be adopted in GP. Fitness cases are
normally used to determine the fitness of individuals and can be used to
compute the semantic similarity (or dissimilarity) of individuals. However,
fitness cases are not available in MCTS. We extend this notion by using
multiple reward values from MCTS that allow us to determine both the fitness of
an individual and its semantics. By doing so, we show how SIEA-MCTS is able to
successfully evolve mathematical expressions that yield better or competitive
results compared to UCT without the need of tuning these evolved expressions.
We compare the performance of the proposed SIEA-MCTS against MCTS algorithms,
MCTS Rapid Action Value Estimation algorithms, three variants of the *-minimax
family of algorithms, a random controller and two more EA approaches. We
consistently show how SIEA-MCTS outperforms most of these intelligent
controllers in the challenging game of Carcassonne.
