Introducing Heuristic Function Evaluation Framework

Abstract

We propose a paradigm for evaluating game heuristic functions in which we define a set of metrics, each measuring an aspect of heuristic's performance, and use them to evaluate the heuristic function by comparing the function's output against a pre-computed benchmark containing a set of states from a game and ground-truth values of each of their moves. The advantage of our approach is that it is fast (once the benchmark is computed) and focused on specific user-defined questions. While the ideal benchmark dataset would have minimax action values, these values can sometimes be too difficult to obtain, so we investigate the possibility of generating datasets using the MCTS algorithm. We compare the performance of MCTS datasets for Connect Four to the game-theorical one, and identify a set of metric which can be reliably used with the MCTS dataset. Finally, we present two case studies, in which we show how our framework can be used to gain better understanding of a heuristic function's behavior.