Large-Scale Optimization for Evaluation Functions with Minimax Search

• Published in: The Journal of artificial intelligence research 2014-01, Vol.49, p.527-568
• Main Authors: Hoki, K., Kaneko, T.
• Format: Article
• Language: English
• Subjects: Artificial intelligence; Chess; Iterative methods; Minimax technique; Optimization; Parameters; Searching
• ISSN: 1076-9757; 1076-9757; 1943-5037
• DOI: 10.1613/jair.4217

This paper presents a new method, Minimax Tree Optimization (MMTO), to learn a heuristic evaluation function of a practical alpha-beta search program. The evaluation function may be a linear or non-linear combination of weighted features, and the weights are the parameters to be optimized. To control the search results so that the move decisions agree with the game records of human experts, a well-modeled objective function to be minimized is designed. Moreover, a numerical iterative method is used to nd local minima of the objective function, and more than forty million parameters are adjusted by using a small number of hyper parameters. This method was applied to shogi, a major variant of chess in which the evaluation function must handle a larger state space than in chess. Experimental results show that the large-scale optimization of the evaluation function improves the playing strength of shogi programs, and the new method performs signicantly better than other methods. Implementation of the new method in our shogi program Bonanza made substantial contributions to the program's rst-place nish in the 2013 World Computer Shogi Championship. Additionally, we present preliminary evidence of broader applicability of our method to other two-player games such as chess.