nips nips2004 nips2004-122 nips2004-122-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: David H. Stern, Thore Graepel, David MacKay
Abstract: Go is an ancient oriental game whose complexity has defeated attempts to automate it. We suggest using probability in a Bayesian sense to model the uncertainty arising from the vast complexity of the game tree. We present a simple conditional Markov random field model for predicting the pointwise territory outcome of a game. The topology of the model reflects the spatial structure of the Go board. We describe a version of the Swendsen-Wang process for sampling from the model during learning and apply loopy belief propagation for rapid inference and prediction. The model is trained on several hundred records of professional games. Our experimental results indicate that the model successfully learns to predict territory despite its simplicity. 1
[1] Thore Graepel, Mike Goutrie, Marco Kruger, and Ralf Herbrich. Learning on graphs in the game of Go. In Proceedings of the International Conference on Artificial Neural Networks, ICANN 2001, 2001.
[2] David Fotland. Knowledge representation in the many faces of go. ftp://www.joy.ne.jp/welcome/igs/Go/computer/mfg.tex.Z, 1993. URL:
[3] Nicol N. Schrauldolph, Peter Dayan, and Terrance J. Sejnowski. Temporal difference learning of position evaluation in the game of go. In Advances in Neural Information Processing Systems 6, pages 817–824, San Fransisco, 1994. Morgan Kaufmann.
[4] Markus Enzenberger. The integration of a priori knowledge into a Go playing neural network. URL: http://www.markus-enzenberger.de/neurogo.html, 1996.
[5] John Lafferty, Andrew McCallum, and Fernando Pereira. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proc. Int. Conf. on Machine Learning, 2001.
[6] Fabio Gagliardi Cozman. Generalizing variable elimination in Bayesian networks. In Proceedings of the IBERAMIA/SBIA 2000 Workshops, pages 27–32, 2000.
[7] R. H. Swendsen and J-S Wang. Nonuniversal critical dynamics in Monte Carlo simulations. Physical Review Letters, 58:86–88, 1987.
[8] Robert G. Edwards and Alan D. Sokal. Generalisation of the Fortuin-KasteleynSwendsen-Wang representation and Monte Carlo algorithm. Physical Review Letters, 38(6), 1988.
[9] Yair Weiss. Belief propagation and revision in networks with loops. Technical report, AI Lab Memo, MIT, Cambridge, 1998.
[10] A. L. Zobrist. Feature Extractions and Representations for Pattern Recognition and the Game of Go. PhD thesis, Graduate School of the University of Wisconsin, 1970.