Exploring GnuGo's Evaluation Function with a SVM

Christopher Fellows, Yuri Malitsky, Gregory WojtaszczykAAAI 2006

Abstract

This study investigates the automation of weight tuning in the GnuGo engine using Support Vector Machines (SVMs). By leveraging expert-designed heuristics as input features, the researchers demonstrate that a machine learning model can effectively replicate complex hand-tuned rules. Furthermore, the SVM-based approach identified optimized weight configurations that allowed the engine to solve tactical puzzles previously beyond its capabilities, proving that statistical models can refine human domain knowledge.

Introduction

In the era preceding deep reinforcement learning, the game of Go represented a significant challenge for artificial intelligence due to its vast branching factor and the difficulty of position evaluation. Unlike Chess, where piece values provide a clear metric, Go relies on a complex network of influences. Traditional engines like GnuGo relied on thousands of lines of hand-tuned heuristics, often adjusted through human trial and error. This research addresses whether these manual "rules of thumb" can be replaced by a supervised learning approach that learns optimal weights from expert play.

Methods

The authors integrated the SVM-light implementation with the GnuGo engine to automate evaluation. The process involved:

  1. Feature Extraction: Instead of raw board states, the model used GnuGo’s internal "move generators." These generators assign "reasons" to moves, which were converted into a vector of 13 characteristic values.
Table of the 13 characteristic values used as features for the SVM model.
  1. Normalization and Classification: Data for each board position was normalized by comparing the "correct" move against candidate moves. A linear SVM with a "hard margin" (penalty parameter $C = 1,000$) was employed to find a hyperplane that strictly separated correct moves from incorrect ones in the training data.
  2. Weight Application: The weights derived from the SVM were then reintegrated into GnuGo to serve as the new evaluation function.

Results and Key Insights

The SVM demonstrated a remarkable ability to mimic and improve upon GnuGo's existing logic.

  • Perfect Replication: On a training set of 187 problems (7,000 data points), the SVM achieved perfect separation, selecting the correct move in every instance.
  • Generalization: When tested on 2,000 professional game positions, the SVM-weighted engine solved 314 problems, nearly matching the original GnuGo’s 316. This indicates the model captured the engine's core logic without overfitting.
  • Weight Volatility and Optimization: The SVM revealed that human tuners might have significantly undervalued certain features. For example, when training on specific tactical puzzles, the importance of "Max Pos Shape" increased from 4.05 to 44.5.
Comparison of feature weights between the original GnuGo engine and various SVM-trained models.

By adjusting these weights, the SVM enabled the engine to solve "cut/connect" and "escape capture" problems that were previously unsolvable by the hand-tuned version.

Conclusion

The study concludes that a linear SVM can effectively approximate the complex, hand-tuned evaluation functions of traditional Go engines. While the linear kernel has limitations in capturing non-linear logic (like if-else heuristics), it provides a robust framework for balancing domain knowledge with mathematical optimization. Future research could explore non-linear kernels, such as RBF, to capture more intricate feature interactions.

Summary updated

BibTeX
@inproceedings{fellows2006exploring,
  author = {Christopher Fellows and Yuri Malitsky and Gregory Wojtaszczyk},
  title = {{Exploring GnuGo's Evaluation Function with a SVM}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure