Investigations with Monte Carlo Tree Search for finding better multivariate Horner schemes (abstract)

After the defeat of the human chess World Champion in 1997, many researchers turned their attention to the oriental game of Go. The minimax approach, so successful in chess, did not work in Go. Instead, around 2006 a new method was developed: MCTS (Monte Carlo Tree Search). The success of MCTS in Go caused researchers to apply the method to other domains. In this article we report on experiments with MCTS for finding improved orderings for multivariate Horner schemes, a basic method for evaluating polynomials. We report on initial results that typically improve existing methods by a factor of two. In addition, we continue with an investigation into two parameters that guide the MCTS search. It will be interesting to see if these insights can be transferred to other domains