Games and AI Group

The Go for Go Project is a four year research projected on AI methods for Computer Go. It is funded by the Dutch Organization for Scientific Research, NWO (grand number 612.066.409). The project is mainly conducted by Guillaume Chaslot and Jahn-Takeshi Saito.

The two main fields of research are (1) Monte-Carlo Tree Search methods, and (2) Proof-Search methods.

Our program: Mango

Our Go-playing program, Mango, participated in numerous KGS tournaments and in the last Computer Olympiad.

Description of the project

Tactical search, machine learning, and scaling of methods successfully investigated on smaller Go boards are at the core of improving current computer Go programs. The four year project presented here will investigate such means in depth. The proposed working title is Go for Go - Global and local application of AI methods for the 19×19 Go Domain. The project is a framework for two Ph.D. students’ sub-projects AI Methods for Global Goals in the 19×19 Go domain and AI Methods for Local Goals in the 19×19 Go Domain. The sub-projects will profit from close interaction while at the same time centring around clearly delimited core topics.

In the field of combinatorial games investigated by AI research, Go constitutes a special case as it is among the most challenging objects in terms of search tree and state space complexity. It is expected to remain challenging for the foreseeable future. Over the past decade computer game playing has given valuable innovation in AI research as can be seen best in the field of search (cf. below). Computer Go has had its share in that advancement.

Improvement of Go playing systems and in the theoretical underpinnings have advanced hand in hand. Integration of novel AI techniques into Go playing programs has increased the strength of Go software as is evident in the case of Monte Carlo methods introduced to the combinatorial game domain in Go (Bouzy and Helmstetter [2003], Bouzy [2004]). Promising applications of machine learning to computer go have been continuously contributed (Abramson and Wechsler [2001], Enzenberger [2003], van der Werf et al. [2003], v.d. Werf et al. [2004]).

 

Research question

Global and local methods require to be improved and well-integrated in order to strengthen current programs. These methods include search, machine learning, and knowledge representation on both, the global and the local level. We therefore recognize as essential goals of our proposed endeavour the analysis of search and machine learning. The third main goal is founded on earlier work (v.d. Werf [2004]) which investigated AI techniques for the 9 × 9 Go domain. The project will aim at scaling promising results from that work to the much more complex 19 × 19 Go board. In this context, innovative search methods will be explored and machine learning techniques will be applied to new targets, offering novel insight for both AI sub-domains.

 

Classic Approach

Müller [2000] identifies two levels of search in the game of Go: Global strategic search and tactical goal oriented search. While global strategic search aims at finding the next move to play, tactical search deals with clearly described subproblems.
Virtually all Go programs rely on three basic mechanisms, namely feature detection, heuristic move suggestion, and heuristic move evaluation. Chen [2002] suggests that all Go programs can be classified by move generation to belong into one of four groups, but the three basic mechanisms are the foundation for all move generation types. Tactical search occurs at least in feature detection and heuristic move suggestion. Global search is the central way of co-ordinating results for move evaluation.

Monte Carlo methods have been studied extensively and contributed to increasing the strength of computer Go programs (Bouzy and Helmstetter [2003]). Simulated annealing within Monte Carlo Go has been proposed by Brügmann [1993]. It can improve the level of a Monte Carlo Go program significantly. Our belief is that this method can be extended and coupled with efficient tree search methods. Hence, this issue will be one of the main research axes. First studies for using Monte Carlo methods on tactical goals have given promising results (Cazenave and Helmstetter [2004]). The proof-number search family of algorithms (Allis [1994] and surveyed by Kishimoto [2005]) has developed rapidly and reached computer Go (Kishimoto [2005], Kishimoto and Müller [2005]). Neither approach requires more than minimal domain knowledge. We expect this fact to support an integration and render results scalable to other combinatorial games and possibly other AND/OR tree search problems. The project’s first goal is therefore to investigate further each approach and examine the integration of both into a new hybrid search tested on tactical search problems in Go.

By investigating the simulated annealing approach to Monte Carlo Go and the possibility of integrating Monte Carlo methods with proof number search, the program researches new search methods.

 

Machine Learning

Various inductive (Graepel et al. [2001]) and semi-inductive (Cazenave [2002]) learning methods have been applied to local life-and-death problems. Dahl and Halck [2000] have applied neural nets for feature detection in shape, group strength and territorial estimate and v.d. Werf et al. [2004] studied the latter subject in depth with encouraging results. However, as a recent survey suggests (Saito [2005], ch. 3), features such as connectivity and influence have remained untouched even though the fuzzy nature of these target concepts should indicate the applicability for robust learners such as neural nets for this task.
The sub-project treating applications of AI methods will therefore explore the possibilities of applying machine learning techniques and neural networks in particular to derive trained feature detection to enable better local tactical search. The quality of trained feature detection correlates to their reliability and speed enhancement over classical, often pattern-based feature detectors. Machine learning is a key issue in developing strong move prediction as well. It has been used for move prediction Enzenberger [2003], bye the way of neural networks v.d. Werf et al. [2004], supervised learning, and also reinforcement learning. These issues will be investigated in detail.

 

Integrating Search and Machine Learning Techniques into an operating 19 × 19 Go software

The ultimate test case for the suitability of the methods under investigation is constituted by developing an operating 19×19 Go playing software. The means developed by both sub-projects will be integrated into such a Go program by both Ph.D. students jointly. The surplus in performance gained by applying the newly devised technologies gives a practical measure of the utility achieved.

 

References

• Myriam Abramson and Harry Wechsler. Competitive reinforcement learning for combinatorial problems. INNS-IEEE International Joint Conference on Neural Networks (IJCNN 2001), 2001.
• L.V. Allis (1994). Searching for Solutions in Games and Artificial Intelligence. Ph.D. Thesis, University of Limburg, Maastricht, The Netherlands.
  
• B. Bouzy. Associating shallow and selective global tree search with Monte Carlo for 9x9 Go. Proceedings of 4th Computer and Games Conference, Ramat-Gan, 2004.
• B. Bouzy and B. Helmstetter. Monte Carlo Developments.  Proceedings of the Advances in Computer Games Conference (ACG-10), pages 159–174. Kluwer Academic, 2003.
  
• B. Brügmann. Monte Carlo Go. White paper, 1993.
  
• T. Cazenave. Metarules to improve tactical Go knowledge. In Joint Conference on Information Sciences, Durham, 2002.
  
• T. Cazenave and B. Helmstetter. Search for transitive connection. Information Sciences, 132(1):39-103, 2004.
  
• Keh-Hsun Chen. Knowledge and search in computer Go. In Game Programming Workshop, 2002.
• Fredrik A. Dahl and Ole Martin Halck. Minimax TD-learning with neural nets in a Markov game. In R. Lopez de Mantaras and E. Plaza, editors, Proceedings of the 11th European Conference on Machine Learning (ECML-00), pages 117–128, Barcelona, Spain, 2000. Springer.
  
• Markus Enzenberger. Evaluation in Go by a neural network using soft segmentation. Proceedings of the 10th Advances in Computer Games Conference, pages 97-108, 2003.
  
• Thore Graepel, Mike Goutrie, Marco Krüger, and Ralf Herbrich. Learning on graphs in the game of Go. In International Conference on Artificial Neural Networks (ICANN-01), Vienna, Austria, 2001.
  
• Akihiro Kishimoto. Correct and Effcient Search Algorithms in the Presence of Repetitions. PhD thesis, University of Alberta, 2005.
  
• Akihiro Kishimoto and Martin Müller. Dynamic decomposition search: A divide and conquer approach and its application to the one-eye problem in go. In In proceedings of the Computational Intelligence and Games Conference (CIG’05), pages 164-170, 2005.
  
• Martin Müller. Not like other games - why tree search in Go is di?erent. In Fifth Joint Conference on Information Sciences (JCIS), 2000.
  
• Jahn-Takeshi Saito. A pattern-based approach to monte carlo Go. Master’s thesis, Universität Osnabrück, April 2005.
  
• E.C.D. van der Werf, M.H.M. Winands, H.J. van den Herik, and J.W.H.M. Uiterwijk. Learning to predict life and death from Go records. In Wang, editor, Proceedings of the 7th Joint Conference on Information Sciences (JCIS 2003), pages 501-504, 2003.
  
• E.C.D. v.d. Werf, H.J. van den Herik, and J.W.H.M Uiterwijk. Learning to estimate potential territory in the game of Go. In proceedings of the 4th International Conference on Computers and Games (CG’04). Ramat-Gan, Israel, July 5-7, pages 501-504, 2004.
  
• E.C.D. v.d. Werf. AI techniques for the game of Go. PhD thesis, University of Maastricht, 2004.