GO and the man-machine match

Source: deepmind.com

A major step forward in game AI a month or so ago with Deepmind’s result published in Nature magazine! The machine beat the European GO champ 5-0! Looking forward to the match with the legend Lee Sedol starting tomorrow!

GO is a beautiful , complex board game. It has resisted the efforts of AI practitioners for quite a while now but there have been some pretty good advances made with clever Tree Search techniques – notably MCTS or Monte Carlo Tree Search. A simple way to talk about the complexity is with the typical number of legal moves to explore at each step – much bigger than in Chess. But probably equally importantly, it seems harder to articulate why an expert good move is good – seemingly more intuitive than analytical.

From my reading of  the Nature publication ( Silver, D. et al. Nature 529, 484–489 (2016)) , Deep mind’s program uses a combination of at least 4 key techniques & elegant ways to combine them:

1. Monte Carlo Tree Search (used by the top GO programs)
2. Deep Neural Nets  (to learn from a database of games)
3. Deep Reinforcement Learning ( to learn from games played by the AI with itself)
4. Domain Knowledge – some basic features were coded in for eg: whether a move at this position results in a Ladder capture or escape, Sensibleness – whether a move results in filling up an Eye, Number of Opponent stones that would be captured by a current move , Number of Own stones that would be captured, etc. Nuances related to Tree Search may also be construed as Domain Knowledge even if they are not as explicit as the basic features listed.

Additionally, the best version of the program uses a considerable amount of hardware with nearly 300 GPUs and a couple of thousand CPUs. Also see http://googleresearch.blogspot.com/2016/01/alphago-mastering-ancient-game-of-go.html

There are many interesting blogs that discuss the AlphaGo – Fan Hui series. Gary Marcus has one at https://backchannel.com/has-deepmind-really-passed-go-adc85e256bec  . An interesting piece with critical thinking is seen at http://www.milesbrundage.com/blog-posts/alphago-and-ai-progress.

What is most interesting to me here is the extent of Domain Knowledge related to GO that needs to be coded into the program. What are the concepts the program implicitly learns by playing itself or from the vast database? What may be a way to get the program to learn the concept behind Ladders or Sensibleness?

Who do we think we will the match – Lee Sedol or AlphaGo? I am not an expert at GO, so I wouldn’t hazard a guess. Reddit has a nice summary of what some expert GO players feel are the strengths and weaknesses of alphaGO. https://www.reddit.com/r/MachineLearning/comments/43fl90/synopsis_of_top_go_professionals_analysis_of/ Well, the program that beat Fan Hui has had several months to improve – both from machine learning and any improvements to the code itself, in addition to potentially using more powerful hardware.

I hope for a good fight. Who are you rooting for?