7
$\begingroup$

Recently researchers at Google DeepMind published a paper, where they described a Go playing system that beat the best current computer programs and the human European champion.

I had a quick look at that paper, and it seems it is using many interesting ideas from previous papers. What did they do differently that allowed them to achieve this spectacular improvement?

$\endgroup$
  • 1
    $\begingroup$ Go playing programs had been quietly progressing into new territory with machine learning techniques for a few years. The Google team have pushed it further, but the improvement is not IMO as radical as it seems (many people will be comparing it with the "common knowledge" from 10 years ago that Go was too hard for computers). For example, some Go playing programs did beat Google's player in testing. Also, look at progress on the wikipedia page: en.wikipedia.org/wiki/Computer_Go#2000s . . . $\endgroup$ – Neil Slater Jan 30 '16 at 20:47
6
$\begingroup$

The existing programs before AlphaGo were based on:

1) Convolutional neural networks (CNN), trained on a database of existing games.

OR

2) Monte Carlo tree search (MCTS)


AlphaGo is based on a combination of:

A) reinforcement learning: train networks by letting versions of CNN's (see above) play against eachother.

AND

B) MCTS using moves generated by step A)

On top of that, the performance was improved even further by using distributed computing with large amounts of CPU's and GPU's.

So the novelty was the combination of the above techniques A) and B).

$\endgroup$
  • $\begingroup$ I'm not really aware of CNN programs that existed before AlphaGo. Do you have examples? CNN's as you describe in (A) are simply a drop in replacement for traditional machine learning models to do the same thing. (B) was also done exactly as you describe in previous engines, so neither of these are novelties. The novelty is simply applying CNN's in place of old machine learning models within the existing framework of Monte Carlo Tree Search. $\endgroup$ – Imran Apr 1 '16 at 18:02
  • $\begingroup$ @Neil Slater +1. I edited my answer to emphasize more the combination of both techniques. Thanks. $\endgroup$ – Rolf Schorpion Jun 24 '18 at 8:53
1
$\begingroup$

Nothing in the components they used is novel. All approaches have been explored. Checking their references you will notice many researchers doing similar work. The novelty was the pipeline they followed and the combination of model-free and model-based Reinforcement Learning approaches. I will try to give you a non technical different perspective on what they captured.

Model-free approaches usually attempt to approximate functions such as Value functions (representing how good it is to be in a particular state - board configuration - in terms of future reward) or parametrized policy functions (probabilities of selecting an action given a state. Briefly, your model gains some kind of 'intuition' on which moves are relative good - something similar to the intuition professional Go players have, when they declare that they do a move because it 'feels' good. This is very important at the early stage of the game when planning is inefficient to use.

Model-based approaches attempt to simulate every single possible trajectory of the game in the form of a decision tree. Thus they are useful for planning (before you actually make a move in the game you check and evaluate all possible contingencies and then you decide which move to take from your current position). The MCTS is such an algorithm, creates a decision tree over possible future courses of the game from the current board position, and evaluates these heuristics according to some criteria. The best algorithms in Go so far were based in this algorithm (and is considered as a RL algorithm).

So in terms of novelty, with few words: combination of planning and intuition, which means combination of MCTS algorithm with function approximators for evaluation of the simulated game trajectories. In this case they used very deep convolutional neural nets for the 'intuition' part. In addition to this, the whole model is data-driven as it was first trained on human expert moves (this could be useful in applications in many other domains apart from gaming). If you examine every single component, there is nothing novel...but the whole process to combine effectively all these elements and achieve Mastery in that complex domain is something novel. Hope it helps!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.