Factorization Ranking Model for Fast Move Prediction in the Game of Go

• Author / Creator

  Xiao, Chenjun

• In this thesis, we investigate the move prediction problem in the game of Go by proposing a new ranking model named Factorization Bradley Terry (FBT) model. This new model considers the move prediction problem as group competitions while also taking the interaction between features into account. A FBT model is able to provide a probability distribution that expresses a preference over moves. Therefore it can be easily compiled into an evaluation function and applied in a modern Go program. We propose a Stochastic Gradient Decent (SGD) algorithm to train a FBT model using expert game records, and provide two methods for fast computation of the gradient in order to speed up the training process. We also investigate the problem of integrating feature knowledge learned by the FBT model in Monte Carlo Tree Search (MCTS). Experimental results show that our FBT model outperforms the state-of-the-art fast move prediction system of Latent Factor Ranking, and it is useful in improving the performance of MCTS.

• Subjects / Keywords

  • Computer Go
  • Move Prediction
  • Machine Learning
  • Ranking Model

• Graduation date

  Fall 2016

• Type of Item

  Thesis

• Degree

  Master of Science

• DOI

  https://doi.org/10.7939/R38C9R87M

• License

  This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.