Home * Games * Go
220px-Go_board.jpg

The game of Go has attracted game researchers and programmers as an ambitious AI-challenge. Albert Zobrist was a pioneer, who wrote the first Go program in 1968 as part of his Ph.D. Thesis on pattern recognition [1]. Chess programmers, beside others, Rémi Coulom and Gian-Carlo Pascutto became successful Go programmers with their programs CrazyStone and Leela respectively. Competitive computer Go, as organized by the ICGA [2], is played on boards with 9x9 as well with default 19x19 grids.

Since Go lacks a simple evaluation function mainly based on counting material, attempts to apply similar techniques and algorithms as in chess were less successful. The breakthrough in computer Go was accomplished by Monte-Carlo tree search and deep learning.
19*19 Go board [3]

Progress

Monte-Carlo Go

After early trials to apply Monte Carlo methods to a Go playing program by Bernd Brügmann in 1993 [4], recent developments since the mid 2000s by Bruno Bouzy [5], and by Rémi Coulom, who coined the term Monte-Carlo Tree Search [6], in conjunction with UCT (Upper Confidence bounds applied to Trees) introduced by Levente Kocsis and Csaba Szepesvári [7], led to a breakthrough in computer Go [8].

CNNs

As mentioned by Ilya Sutskever and Vinod Nair in 2008 [9], convolutional neural networks are well suited for problems with a natural translation invariance, such as object recognition. Go has some translation invariance, because if all the pieces on a hypothetical Go board are shifted to the left, then the best move will also shift (with the exception of pieces that are on the boundary of the board). Many applications of neural networks to Go have already used convolutional neural networks, such as Nicol N. Schraudolph et al. [10], Erik van der Werf et al. [11], and Markus Enzenberger [12], among others.

In 2014, two teams independently investigated whether deep convolutional neural networks [13] could be used to directly represent and learn a move evaluation function for the game of Go. Christopher Clark and Amos Storkey trained an 8-layer convolutional neural network by supervised learning from a database of human professional games, which without any search, defeated the traditional search program Gnu Go in 86% of the games [14] [15] [16] [17] [18]. In their paper Move Evaluation in Go Using Deep Convolutional Neural Networks [19], Chris J. Maddison, Aja Huang, Ilya Sutskever, and David Silver report they trained a large 12-layer convolutional neural network in a similar way, to beat Gnu Go in 97% of the games, and matched the performance of a state-of-the-art Monte-Carlo Tree Search that simulates a million positions per move [20].

AlphaGo

In 2015, a team affiliated with Google DeepMind around David Silver, Aja Huang, Chris J. Maddison, and Demis Hassabis, supported by Google researchers John Nham and Ilya Sutskever, build a Go playing program dubbed AlphaGo [21], combining Monte-Carlo tree search with their 12-layer networks [22], the “policy network,” to select the next move, the “value network,” to predict the winner of the game. The neural networks were trained on 30 million moves from games played by human experts, until it could predict the human move 57 percent of the time. AlphaGo achieved a huge winning rate against other Go programs, and defeated European Go champion Fan Hui [23] in October 2015 with a 5 - 0 score [24] [25]. On March 9 to 15, 2016, AlphaGo won a $1M 5-game challenge match in Seoul versus Lee Sedol with 4 - 1 [26] [27] [28].

During The Future of Go Summit from May 23 to 27, 2017 in Wuzhen, China, AlphaGo won a three-game match versus current world No. 1 ranking player Ke Ji. After the Summit, AlphaGo is now retired from competitive play while DeepMind continues AI research in other areas [29].

Quotes

Quote by Gian-Carlo Pascutto in 2010 [30]:
There is no significant difference between an alpha-beta search with heavy LMR and a static evaluator (current state of the art in chess) and an UCT searcher with a small exploration constant that does playouts (state of the art in go).

The shape of the tree they search is very similar. The main breakthrough in Go the last few years was how to backup an uncertain Monte Carlo score. This was solved. For chess this same problem was solved around the time quiescent search was developed.

Both are producing strong programs and we've proven for both the methods that they scale in strength as hardware speed goes up.

So I would say that we've successfully adopted the simple, brute force methods for chess to Go and they already work without increases in computer speed. The increases will make them progressively stronger though, and with further software tweaks they will eventually surpass humans.

Computer Olympiads


See also

Search

Learning

Misc

Videos on Go


Selected Publications

[31] [32]

1960 ...

1970 ...

1980 ...

1990

1991
1992
1993
1994

1995 ...

1996
1997
1998
1999

2000 ...

2001
2002
2003
2004

2005 ...

2006
2007
2008
2009

2010 ...

2011
2012
2013
2014

2015 ...

2016
2017

Forum Posts

2005 ...

2010 ...

2015 ...

2017

External Links

Computer Go Archives

Computer Go Pages

Misc

Go Challenge

AlphaGo


References

  1. ^ Albert Zobrist (1970). Feature Extraction and Representation for Pattern Recognition and the Game of Go. Ph.D. thesis , University of Wisconsin, also published as technical report, pdf
  2. ^ Go at the Computer Olympiad
  3. ^ Go (Spiel) from Wikipedia.de
  4. ^ Bernd Brügmann (1993). Monte Carlo Go. pdf
  5. ^ Bruno Bouzy (2005). Associating domain-dependent knowledge and Monte Carlo approaches within a go program. Information Sciences, Heuristic Search and Computer Game Playing IV
  6. ^ Rémi Coulom (2006). Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search. CG 2006, pdf
  7. ^ Levente Kocsis, Csaba Szepesvári (2006). Bandit based Monte-Carlo Planning. ECML-06, LNCS/LNAI 4212, pdf
  8. ^ Sylvain Gelly, Marc Schoenauer, Michèle Sebag, Olivier Teytaud, Levente Kocsis, David Silver, Csaba Szepesvári (2012). The Grand Challenge of Computer Go: Monte Carlo Tree Search and Extensions. Communications of the ACM, Vol. 55, No. 3, pdf preprint
  9. ^ Ilya Sutskever, Vinod Nair (2008). Mimicking Go Experts with Convolutional Neural Networks. ICANN 2008, pdf
  10. ^ Nicol N. Schraudolph, Peter Dayan, Terrence J. Sejnowski (1994). Temporal Difference Learning of Position Evaluation in the Game of Go. Advances in Neural Information Processing Systems 6
  11. ^ Erik van der Werf, Jos Uiterwijk, Eric Postma, Jaap van den Herik (2002). Local Move Prediction in Go. CG 2002
  12. ^ Markus Enzenberger (2003). Evaluation in Go by a Neural Network using Soft Segmentation. Advances in Computer Games 10, pdf
  13. ^ Convolutional neural network from Wikipedia
  14. ^ Christopher Clark, Amos Storkey (2014). Teaching Deep Convolutional Neural Networks to Play Go. arXiv:1412.3409
  15. ^ Deep learning for… Go by Erik Bernhardsson, December 11, 2014
  16. ^ Teaching Deep Convolutional Neural Networks to Play Go by Hiroshi Yamashita, The Computer-go Archives, December 14, 2014
  17. ^ Why Neural Networks Look Set to Thrash the Best Human Go Players for the First Time | MIT Technology Review, December 15, 2014
  18. ^ Teaching Deep Convolutional Neural Networks to Play Go by Michel Van den Bergh, CCC, December 16, 2014
  19. ^ Chris J. Maddison, Aja Huang, Ilya Sutskever, David Silver (2014). Move Evaluation in Go Using Deep Convolutional Neural Networks. arXiv:1412.6564v1
  20. ^ Move Evaluation in Go Using Deep Convolutional Neural Networks by Aja Huang, The Computer-go Archives, December 19, 2014
  21. ^ AlphaGo | Google DeepMind
  22. ^ David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, Demis Hassabis (2016). Mastering the game of Go with deep neural networks and tree search. Nature, Vol. 529
  23. ^ Fan Hui at Sensei's Library
  24. ^ Game Over? AlphaGo Beats Pro 5-0 in Major AI Advance « American Go E-Journal, January 27, 2016
  25. ^ Official Google Blog: AlphaGo: using machine learning to master the ancient game of Go by Demis Hassabis, January 27, 2016
    Google DeepMind: Ground-breaking AlphaGo masters the game of Go, YouTube Video
  26. ^ DeepMind - YouTube Channel
  27. ^ Video Interview with Rémi Coulom on AlphaGo, February 2016
  28. ^ Artificial intelligence: Google's AlphaGo beats Go master Lee Se-dol, BBC News, March 12, 2016
  29. ^ AlphaGo’s Designers Explore New AI After Winning Big in China by Cade Metz, Wired, May 27, 2017
  30. ^ Re: Chess vs Go // AI vs IA by Gian-Carlo Pascutto, June 02, 2010
  31. ^ Computer Go Bibliography, University of Alberta
  32. ^ Computer Go Bibliography by Michael Reiss
  33. ^ GoTools - TsumeGo Solving Software
  34. ^ Gobble
  35. ^ Mathematical Go from Sensei's Library
  36. ^ Nici Schraudolph’s go networks, review by Jay Scott
  37. ^ EZ-GO at Sensei's Library
  38. ^ Tsumego at Sensei's Library
  39. ^ steganography from Wikipedia
  40. ^ The Shodan Go Bet
  41. ^ Re: Teaching Deep Convolutional Neural Networks to Play Go by Erik van der Werf, The Computer-go Archives, December 15, 2014
  42. ^ Capturing race from Wikipedia
  43. ^ Franz-Josef Dickhut from Wikipedia, Rémi Coulom
  44. ^ codecentric go challenge 2014: Interviews with Franz-Josef Dickhut and Rémi Coulom - codecentric Blog by Raymond Georg Snatzke, October 1, 2014
  45. ^ codecentric go challenge 2014: Final Interviews - codecentric Blog by Raymond Georg Snatzke, November 27, 2014 (German)
  46. ^ How Facebook’s AI Researchers Built a Game-Changing Go Engine | MIT Technology Review, December 04, 2015
  47. ^ Combining Neural Networks and Search techniques (GO) by Michael Babigian, CCC, December 08, 2015
  48. ^ AlphaGo Zero: Learning from scratch by Demis Hassabis and David Silver, DeepMind, October 18, 2017
  49. ^ The Mystery of Go, the Ancient Game That Computers Still Can’t Win by Alan Levinovitz, Wired, May 12, 2014
  50. ^ Wired Article on Computer GO by Edmund Moshammer, CCC, May 13, 2014
  51. ^ World #1 Go Player Ke Jie accepts Google Alpha Go Match.. by AA Ross, CCC, June 07, 2016
  52. ^ Ke Jie from Wikipedia

What links here?


Up one Level