×

48
49

DL, M, MF, R"Mastering the Game of Go without Human Knowledge", Silver, Schrittwieser & Simonyan et al 2017 (deepmind.com)

submitted by [deleted]

[deleted]

all 23 comments
sorted by:
best

[–]gwern 33 points34 points  (17 children)

Highlights:

  • AlphaGo Fan < AlphaGo Sedol < Master < Zero; extremely high ELO rating for Zero:

    The raw neural network, without using any lookahead, achieved an Elo rating of 3,055. AlphaGo Zero achieved a rating of 5,185, compared to 4,858 for AlphaGo Master, 3,739 for AlphaGo Lee and 3,144 for AlphaGo Fan. Finally, we evaluated AlphaGo Zero head to head against AlphaGo Master in a 100­game match with 2­h time controls. AlphaGo Zero won by 89 games to 11 (see Extended Data Fig. 6 and Supplementary Information)

    ...However, it was useful to test different versions of AlphaGo against each other under handicap conditions. Using names of major versions from Zero paper, AlphaGo Master > AlphaGo Lee > AlphaGo Fan, each version defeated its predecessor with 3 handicap stones...

  • pure selfplay, no initialization from expert games

  • no hand-engineered features, just the board state

  • architecture:

    • batchnormed residual layers instead of plain CNN/FCs
    • value & policy networks merged
    • switching to resnets and merging appear to give additive gains

  • full MCTS is used in training but not in play; during play, simple tree search

    • MCTS is however used to provide additional supervision: the policy-value network is now being optimized during policy-gradient self-play by the MCTS finetuning of the probability of playing each move + the ultimate winner. (So if moves A/B/C are evaluated as 33/33/33% by the NN, then several thousand MCTS rollouts indicate it's more likely to be 20/40/40%, it's backpropped to reduce A & increase B/C.)

  • training & computation time is massively reduced by all of the above:

    Surprisingly, AlphaGo Zero outperformed AlphaGo Lee after just 36 h. In comparison, AlphaGo Lee was trained over several months. After 72 h, we evaluated AlphaGo Zero against the exact version of AlphaGo Lee that defeated Lee Sedol, under the same 2h time controls and match conditions that were used in the man–machine match in Seoul (see Methods). AlphaGo Zero used a single machine with 4 tensor processing units (TPUs)29, whereas AlphaGo Lee was distributed over many machines and used 48 TPUs. AlphaGo Zero defeated AlphaGo Lee by 100 games to 0 (see Extended Data Fig. 1and Supplementary Information)...We subsequently applied our reinforcement learning pipeline to a second instance of AlphaGo Zero using a larger neural network and over a longer duration. Training again started from completely random behaviour and continued for approximately 40 days.Over the course of training, 29 million games of self­play were generated. Parameters were updated from 3.1 million mini­batches of 2,048 positions each. The neural network contained 40 residual blocks. The learning curve is shown in Fig. 6a. Games played at regular intervals throughout training are shown in Extended Data Fig. 5 and in the Supplementary Information

    Nature summary:

    Merging these functions into a single neural network made the algorithm both stronger and much more efficient, said Silver. It still required a huge amount of computing power — four of the specialized chips called tensor processing units, which Hassabis estimated to be US$25 million of hardware. But its predecessors used ten times that number. It also trained itself in days, rather than months. The implication is that “algorithms matter much more than either computing or data available”, said Silver.

    (This is in line with the computation/training improvements outlined by Hassabis in post-Ke Jie talks.)

    • sample-efficiency: one point that seems to be missing from the usual 'Zero reinvents all human Go research in a few days' is that Zero is also doing this at apparently much greater sample-efficiency than previous AGs, and, of course, humanity. Go pros start playing in early childhood full time in special-purpose Go academies and will play possibly 100s of thousands of games total in a lifetime, Go is played by tens of millions of people, etc, and the sum total of that expertise is passed in ~4m games by Zero.

  • Zero rediscovers many of the usual joseki... and discards some of them after training for a while with them: Extended Figure 2 pg11. For example, Knights Move Pincer is discovered ~40h, skyrockets in popularity, and then is discarded and largely disappears by 65h. Presumably the self-play learned a weakness in it.

  • Fan Hui is still working with DM according to Wired, and analyzing particularly good moves:

    Google has already used the company’s algorithms to cut data-center cooling bills. The recent financial filing listed the company’s first revenues, £40 million from services provided to other parts of Alphabet. Hassabis says the ideas in AlphaGo Zero could be applied to work on understanding climate, or proteins in the body. Machine-learning research from Google and others has also shown promise for extracting more ad dollars from consumers. AlphaGo Zero is also set to give back to the community DeepMind's project has shaken up. New ideas from its predecessors like that jaw-dropping move against Lee Sedol have invigorated the game. Fan Hui, the first professional player beaten by AlphaGo, now works with DeepMind and says AlphaGo Zero can inject further creativity into one of the world’s oldest board games. “Its games look a lot like human play but it also feels more free, perhaps because it is not limited by our knowledge,” Fan says. He’s already christened one tactic it came up the “zero move,” such is its striking power in the early stages of a game. “We have never seen a move like this, even from AlphaGo," he says.

  • from the Silver/Schrittweiser AmA:

    • the AlphaGo program is done:

      AlphaGo is retired! That means the people and hardware resources have moved onto other projects on the long, winding road to AI :)...We have stopped active research into making AlphaGo stronger. But it's still there as a research test-bed for DeepMinders to experiment with new ideas and algorithms... [on what would happen if continued to train since it hadn't converged fully] I guess it's a question of people and resources and priorities! If we'd run for 3 months, I guess you might still be wondering what would happen after, say, 6 months :)

      As we said in May, the Future of Go Summit was our final match event with AlphaGo.

    • there will not be release of the codebase (or, presumably, trained models):

      We've open sourced a lot of our code in the past, but it's always a complex process. And in this case, unfortunately, it's a prohibitively intricate codebase.

    • there will probably be a release of the 'teaching' tool:

      When are you planning to release the Go tool that Demis Hassabis announced at Wuzhen?

      Work is progressing on this tool as we speak. Expect some news soon : )

[–]gwern 12 points13 points  (3 children)

Open questions:

  • what happened to the special 'adversarial' agent intended to confuse AlphaGo, the library of hard board positions, running on 1 TPU, and the periodic-bootstrapping training regime mentioned by Hassabis or Silver months ago? https://www.reddit.com/r/reinforcementlearning/comments/6d2qf6/n_alphago_master_details_from_david_silver_talk/ https://www.reddit.com/r/reinforcementlearning/comments/66tg7g/demis_hassabis_april_2017_talk_on_alphago/
  • how much of an improvement does the tree search supervision inside each game provide?

  • why is their self-play so stable? Why is Zero possible? The single biggest question goes unanswered. (I've asked in the AmA.)

    Deep RL, and self-play in particularly, is notorious for massive instability (see just recently the methodology paper noting massive instability run-to-run for various ALE agents and irreproducibility issues.) The ELO performance curve is rock-solid. This is despite apparently lacking any of the usual stabilization mechanisms - eg they aren't self-playing against a wide suite of snapshots. (pg8, 'evaluator' & 'self-play' imply that there is only ever 1 NN being played against itself.) The paper doesn't address stability issues other than the very brief "To achieve these results, we introduce a new reinforcement learning algorithm that incorporates lookahead search inside the training loop, resulting in rapid improvement and precise and stable learning." And indeed, the training is stable and they don't mention anything like going through loops of learning josekis/defeating josekis/forgetting josekis/reinventing them... Why?

    • Is the tree search supervision singlehandedly enough to eliminate all instability and so they don't bother providing any ablation tests like they did resnets/dual-nets since it can't be trained at all without it? If so, why is this change so incredibly powerful that it can preserve knowledge of tactics/strategy indefinitely without any forgetting? Is it because it provides supervision on all possible moves, essentially 'distilling' the knowledge by forcing down the probabilities of all bad moves rederived by the tree search, turning them into Hinton's "dark knowledge"?
    • Can tree search fix instability in other settings as well? (eg backgammon would be a simple test case where we know self-play with checkpoints works and tree search is definitely feasible.) Could learned deep models stabilize training in ALE and elsewhere?

[–]gwern 16 points17 points  (0 children)

So to followup on tree search/stability: Silver, and Anthony (who independently reinvented it in Anthony et al 2017, see above), both say that the tree search is the special ingredient which stabilizes self-play! It Just Works. Silver further notes that they tried a large number of variants of pure self-play, but they all diverged or failed (as expected) until the tree-supervised variant.

Relevant Silver quotes from the AmA:

AlphaGo Zero uses a quite different approach to deep RL than typical (model-free) algorithms such as policy gradient or Q-learning. By using AlphaGo search we massively improve the policy and self-play outcomes - and then we apply simple, gradient based updates to train the next policy + value network. This appears to be much more stable than incremental, gradient-based policy improvements that can potentially forget previous improvements.

... [re Anthony's independent research] Thanks for posting your paper! I don't believe it had been published at the time of our submission (7th April). Indeed it is quite similar to the policy component of our learning algorithm (although we also have a value component), see discussion in Methods/reinforcement learning. Good to see related approaches working in other games.

...Creating a system that can learn entirely from self-play has been an open problem in reinforcement learning. Our initial attempts, as for many similar algorithms reported in the literature, were quite unstable. We tried many experiments - but ultimately the AlphaGo Zero algorithm was the most effective, and appears to have cracked this particular issue.

...In some sense, training from self-play is already somewhat adversarial: each iteration is attempting to find the "anti-strategy" against the previous version.

...One big challenge we faced was in the period up to the Lee Sedol match, when we realised that AlphaGo would occasionally suffer from what we called "delusions" - games in which it would systematically misunderstand the board in a manner that could persist for many moves. We tried many ideas to address this weakness - and it was always very tempting to bring in more Go knowledge, or human meta-knowledge, to address the issue. But in the end we achieved the greatest success - finally erasing these issues from AlphaGo - by becoming more principled, using less knowledge, and relying ever more on the power of reinforcement learning to bootstrap itself towards higher quality solutions.

Relevant Anthony comment:

I’ve been working on almost the same algorithm (we call it Expert Iteration, or ExIt), and we too see very stable performance. Why is a really interesting question. ... I believe the stability is a direct result of using tree search. My best explanation is that: An RL agent may train unstably for two reasons: (a) It may forget pertinent information about positions that it no longer visits (change in data distribution) (b) It learns to exploit a weak opponent (or a weakness of its own), rather than playing the optimal move.

  1. AlphaGo Zero uses the tree policy in the first 30 moves to explore positions. In our work we use a NN trained to imitate that tree policy. Because MCTS should explore all plausible moves, an opponent that tries to play outside of the data distribution that the NN is trained on will usually have to play some moves that the MCTS has worked out strong responses to, so as you leave the training distribution, the AI will gain an unassailable lead.
  2. To overfit to a policy weakness, a player needs to learn to visit a state s where the opponent is weak. However, because MCTS will direct resource to exploring towards s, it can discover improvements to the policy at s during search. MCTS finds these improvements will be found before the neural network is trained to try to play to s. In a method with no look-ahead, the neural network learns to reach s to exploit the weakness immediately. Only later does it realise that Vpi(s) is only large because the policy pi is poor at s, rather than because V*(s) is large.

This is a major breakthrough for self-play. I thought Anthony was cool, but Silver demonstrates that it scales to staggeringly large & complex NNs & domains.

[–]thebackpropaganda 2 points3 points  (1 child)

Do you have any references for instability of self-play? From my limited exposure to the Markov Games literature, it seems they consider perfect-information zero-sum 2-player game as a solved problem, and are busy developing convergent algorithms for general-sum multiplayer games.

I'd imagine that self-play in zero-sum 2-player games is convergent, because any strategy that works well against a good player is also good against weaker players, i.e. the transitivity property does hold. If it doesn't hold in general, it might be provable that it hold for Go.

[–]gwern 2 points3 points  (0 children)

I think it's folklore and mentioned in Sutton & Barto that most of the guarantees go out of the window as soon as you use nonlinear function approximators and especially deep nets. Deep RL, without any self-play, is notoriously unstable (see the methodology paper for some recent discussion of this). GANs have a more than superficial similarity to actor-critic architectures, and we know how stable those are. And Silver says above, "Our initial attempts [at pure self-play Go], as for many similar algorithms reported in the literature, were quite unstable." (and one would think he would know). I dunno what the MG people have solved but if they have, it would be nice if they could write a superhuman Go agent for the rest of us.

[–]sanxiyn 1 point2 points  (0 children)

I also thought it as "distilling search", nice to find that I am not alone.

[–]sorrge 0 points1 point  (3 children)

four of the specialized chips called tensor processing units, which Hassabis estimated to be US$25 million of hardware

25 million for 4 chips?

Excellent summary, thank you. I didn't understand your last sentence about ALE. Tree search is not feasible in ALE, is it? Or did you to learn a model of a game first and then use that for tree search?

[–]gwern 3 points4 points  (1 child)

25 million for 4 chips?

They are very big custom chips. Take a look at the photos sometime.

Or did you to learn a model of a game first and then use that for tree search?

Precisely. I'm thinking of, very roughly, papers like: "Learning model-based planning from scratch", Pascanu et al 2017; "Imagination-Augmented Agents for Deep Reinforcement Learning", Weber et al 2017 (blog); "Path Integral Networks: End-to-End Differentiable Optimal Control", Okada et al 2017; "Value Prediction Network", Oh et al 2017; "Prediction and Control with Temporal Segment Models", Mishra et al 2017; "Neural Network Dynamics for Model-Based Deep Reinforcement Learning with Model-Free Fine-Tuning", Nagabandi et al 2017; "Model-based Adversarial Imitation Learning", Baram et al 2016; "Learning Generalized Reactive Policies using Deep Neural Networks", Groshev et al 2017; "Deep Visual Foresight for Planning Robot Motion", Finn & Levine 2016.

[–]inconditus 1 point2 points  (0 children)

What do you mean that the custom chips are "big"? They're actually quite small: https://www.nextplatform.com/2017/05/17/first-depth-look-googles-new-second-generation-tpu/

25 million might include R&D costs, or maybe they're referring to 4 pods worth?

[–]BullockHouse 0 points1 point  (0 children)

I'm really curious how well learned environment models would work for replicating this success for general-purpose tasks.

If this can be made to work, it would be a good candidate for "the cake" in Yann Lecunn's metaphor. The cake is the environment model! It learns unsupervised, and directly benefits the quality of the RL policies via greedy tree searches.

[–]forgotmyrealpw 0 points1 point  (7 children)

thanks!

How is the elo rating even measured? Elo ratings were computed from evaluation games between different players, using 0.4 s per search (see Methods).

I can't find the methods online.

So how do they know they are not optimizing Zero to more effectively exploit a particular weakness of their reference engine(s) rather than really increasing general playing strength? Especially at 0.4s per ply a MCTS engine doesn't really do much.

How do you randomize openings?

[–]gwern 2 points3 points  (5 children)

So how do they know they are not optimizing Zero to more effectively exploit a particular weakness of their reference engine(s) rather than really increasing general playing strength? Especially at 0.4s per ply a MCTS engine doesn't really do much.

You would expect to see lots of fluctuations in the training curve and cycles in the joseki graphs if it was exhibiting the usual self-play pathologies. They show it maintains expert move prediction performance. And it crushes all the previous versions in the long time-control (2h) matches, which ought to be more than enough time for earlier AGs to do adequate MCTS and expose any vulnerabilities. Not to mention precedent: no particular holes were found in AG Lee or Master despite playing Lee, Ke Jie, a bunch of pros in blitz matches online, the multi-format tournament, or analysis of released self-play games. Zero is presumably not (yet) perfect but any holes must be very hard to find.

[–]sanxiyn 0 points1 point  (4 children)

Re: hole. Lee's win looked like a bug to me. (As in, having a clear and simple fix.) Do we know whether it was, and if it was what it was?

[–]gwern 2 points3 points  (3 children)

I don't know if it was a bug. Weren't the commentators like Redmond very impressed by the subtlety and power of Lee's move? And obviously he couldn't repeat it.

[–]sanxiyn 3 points4 points  (2 children)

As I understand, consensus post-mortem analysis is that while Lee's move was subtle, it actually does not work. That is, AlphaGo made a mistake after the move, and if it responded correctly Lee would have big loss.

[–]gwern 0 points1 point  (1 child)

Oh, I hadn't heard that. In any case, see Silver's final comment in the AmA: apparently AGs pre-Zero did suffer from a systematic problem he calls 'delusions', but nothing they did was able to fix the occasional delusion (so no 'clear and simple fix'), and it took solving pure self-play to eliminate 'delusions' in general.

[–]sanxiyn 3 points4 points  (0 children)

I re-discovered the analysis in the most official source, the commentary published by DeepMind, here. Page 21 has the mainline of refutation AlphaGo should have played.

[–]sanxiyn 0 points1 point  (0 children)

Methods start in page 7. Elo computation is in page 9, section "Evaluation".

Re: opening randomization, do you mean training or testing? Training opening randomization is in page 8, section "Self-play". "For the first 30 moves of each game, the temperature is set to 1; this selects moves proportionally to their visit count in MCTS, and ensures a diverse set of positions are encountered. For the remainder of the game, an infinitesimal temperature is used."

[–]gwern 2 points3 points  (0 children)

Followup paper is amazing (discussion)

AG Zero can be used to learn chess and defeats Stockfish after 4 hours of training: "Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm", Silver et al 2017 https://arxiv.org/abs/1712.01815

The game of chess is the most widely-studied domain in the history of artificial intelligence. The strongest programs are based on a combination of sophisticated search techniques, domain-specific adaptations, and handcrafted evaluation functions that have been refined by human experts over several decades. In contrast, the AlphaGo Zero program recently achieved superhuman performance in the game of Go, by tabula rasa reinforcement learning from games of self-play. In this paper, we generalise this approach into a single AlphaZero algorithm that can achieve, tabula rasa, superhuman performance in many challenging domains. Starting from random play, and given no domain knowledge except the game rules, AlphaZero achieved within 24 hours a superhuman level of play in the games of chess and shogi (Japanese chess) as well as Go, and convincingly defeated a world-champion program in each case.

[–]vee3my 0 points1 point  (3 children)

Would anyone be interested in trying to reconstruct, at least in principle, what exactly alpha go zero is doing? I am reading the paper quite carefully and it is a bit lacking in details at times.

[–]piotr001 3 points4 points  (2 children)

They say Alphago Zero has "prohibitively intricate codebase" so it won't be easy to rewrite. Besides the 4 TPU learning hardware is hard to emulate. TPUs (92 tflops) are handwavy 8.5x faster than GPU 1080 (11traflops). So on 4 gpus we would need 26 days to train to the level of alphago lee. (according to this blog post it takes 3 days to train to the level of alphago lee: https://deepmind.com/blog/alphago-zero-learning-scratch/).

But I'm new-bee here, so I maybe be mistaken. So If anyone have a realistic plan how to get this implemented I would love to help. :)

[–]vee3my 1 point2 points  (1 child)

super - we may try on a smaller board to begin with; replaying correctly the logic of the paper would already be cool, and I could teach it too!

[–]piotr001 1 point2 points  (0 children)

Fair enough let me go through the paper again and we talk over a messenger next week maybe I manage to help somehow :)