  A major challenge in decision making domains with large state spaces is to
effectively select actions which maximize utility. In recent years, approaches
such as reinforcement learning (RL) and search algorithms have been successful
to tackle this issue, despite their differences. RL defines a learning
framework that an agent explores and interacts with. Search algorithms provide
a formalism to search for a solution. However, it is often difficult to
evaluate the performances of such approaches in a practical way. Motivated by
this problem, we focus on one game domain, i.e., Connect-4, and develop a novel
evolutionary framework to evaluate three classes of algorithms: RL, Minimax and
Monte Carlo tree search (MCTS). The contribution of this paper is threefold: i)
we implement advanced versions of these algorithms and provide a systematic
comparison with their standard counterpart, ii) we develop a novel evaluation
framework, which we call the Evolutionary Tournament, and iii) we conduct an
extensive evaluation of the relative performance of each algorithm to compare
our findings. We evaluate different metrics and show that MCTS achieves the
best results in terms of win percentage, whereas Minimax and Q-Learning are
ranked in second and third place, respectively, although the latter is shown to
be the fastest to make a decision.
