M-eval: A Multivariate Evaluation Function for Opening Positions in Computer Go
Jacques Basaldúa, Tai-Ning Yang, José Marcos Moreno-Vega · 2010
Recently, computer go has experienced great advance with the introduction of Monte-Carlo Tree Search (MCTS). Although MCTS programs are overall stronger than previous programs, their strength manifests mostly as the game advances. Strong human players applying established opening principles overtake current MCTS programs in the early moves of non-handicap 19×19 games. In this paper, the authors propose a method, M-eval, for implementing these opening principles in a program. M-eval is a multivariate evaluation function that provides a priori information for MCTS-based go programs. An initial vector made of k positive qualities both players wish to maximize is computed on a board position for each player. The initial vector is dimensionally reduced using non-negative matrix factorization to minimize informational loss. This reduction is done using the multivariate structure learned offline from a set of over 110,000 board positions from a database of master human games. The resulting R2encoding is converted by regression to a real value used as a priori information in MCTS. Games were played using the MCTS GoKnot/QYZ framework with M-eval enabled against the same program without M-eval. Results show valuable improvement both in territorial gain and number of wins.