11 ms·

Alpha Go Zero: How and Why It Works

354 points by Mageek 9y ago

partycoder 9y ago
Go has been studied for hundreds of years. In many cases, by people who study the game since their childhood and work on it as a full-time occupation. The consequence of Alpha Go Zero is that it can, in a matter of days, disregard and surpass all human knowledge about the game. Maximizing a score margin has been equated for a long time with maximizing your probability of winning. Alpha Go doesn't play like that... it's a substantial paradigm shift. If you see the early commentaries you will see that human players were initially saying Alpha Go moves were mistakes because they were slow and wasted opportunities to get more territory, to then realize that Alpha Go was actually winning.
- ImSkeptical 9y ago
  I think people have always understood the difference between maximising probability of victory versus score. Even in amateur games you'll get the feeling "I could fight here, and it would be complicated, but I might get a huge advantage, or I could just play safe and keep my advantage."
- aurelianito 9y ago
  Even kyus like myself play more conservatively when winning. Alphago just takes this to the extreme but it is common on most levels of play (from single digit kyus to the best professional players).
EGreg 9y ago
I wonder how the STYLE of Alpha Go Zero is regarded by human experts. Is it far different from AlphaGo? Why bother learning from AlphaGo if they can learn from AlphaGo Zero? Did they unleash a second "Master" program? I am wondering if the "better" strategy moves are now super wacky and weird and break all theory.
- danielvf 9y ago
  At least initial reports are that alphaGo Zero is more human-like than Master. Zero packs even more of the inhuman ability to pick the most critical part of the board for each move, but less weird looking stuff. In fact, one of the obvious differences between AlphaGo Zero and top human players, is much more play on safe opening spots, which has been out of fashion among human pros for a hundred years or so.
  - zone411 9y ago
    Interesting. It may be possible that while the style of play of Master is able to exploit the errors of human players easily and score convincing victories by many stones, Zero is closer to playing Go perfectly, even if it means winning by one stone. There is a chance that Zero would not score such convincing victories over humans as Master but is much less exploitable. If a strong player plays obvious novices (and humans are now at a level of novices compared to these programs), it doesn't have to worry about taking more unsound risks.
  - gizmo686 9y ago
    >At least initial reports are that alphaGo Zero is more human-like than Master. Empirically, this is not correct. The original AlphaGo achieved a 57% accuracy at predicting expert moves. I can't find an exact number, but based on the graph in the nature article, AlphaGo Zero has a less than 50% accuracy at predicting human moves. Eyeballing the graph, it looks like the supervized learning variant of AlphaGo Zero scored <55% at predicting human moves. Better than reinforcement learning AlphaGo Zero, but still worse then the original AlphaGo. Of course, it is not clear that ability to predict the move humans will play is the best metric to measure how human like a computer plays. It is just the only objective metric we have. Although, if this were an actual research question, we could probably come up with better metrics. https://storage.googleapis.com/deepmind-media/alphago/AlphaGoNaturePaper.pdf https://storage.googleapis.com/deepmind-media/alphago/AlphaG... https://www.nature.com/nature/journal/v550/n7676/pdf/nature24270.pdf https://www.nature.com/nature/journal/v550/n7676/pdf/nature2...
    - 9y ago
javajosh 9y ago
"On a long enough timeline, everything is a discrete game." (With apologies to _Fight Club_) Personally, I look forward to the day when the software I own works for me to the extent of optimizing the decisions I make during the day, even many mundane ones. Properly executed, such a system could make a big difference in my quality of life. I believe that a big piece that is missing is a solid life-model, a life-representation, that can be optimized. Once that is defined, an RNN or MCS can optimize it and I can reap the benefits.
- StavrosK 9y ago
  Complete with creepy predictions like "Predicted optimal life path: $120,000 net worth, 63 year life span".
- ben_w 9y ago
  If it is optimising all your decisions, even the mundane ones, is it really your life any more? If it plugged into your brainstem and took over, by definition nobody else would notice the difference (you always did what it said anyway, or you’d be suboptimal), so why not just flood the 20 watt carbon-based neural network with bliss drugs and let the silicon-based neural network be the person instead?
  - shard 9y ago
    Or just replace the brain completely with the computer, like in Greg Egan's jewel stories. http://will.tip.dhappy.org/blog/Compression%20Trees/.../book/by/Greg%20Egan/Learning%20To%20Be%20Me/ http://will.tip.dhappy.org/blog/Compression%20Trees/.../book...
  - zzzzzzzza 9y ago
    well if you chose and modified the representation of the world yourself, and set it so it would be making decisions based on a heuristic you provided it, then at the end of the day, it is not so different from how our biological circuits work, to the extent we have control over them
  - kbenson 9y ago
QML 9y ago
What makes this different from a minimax algorithm with alpha-beta pruning?
- GolDDranks 9y ago
  Minimax algorithm with alpha-beta pruning is an exhaustive search algorithm. MCTS is a probabilistic algorithm that optimises for converging faster for a partial "good enough" result. Introducing MCTS for Go playing programs in 2006 brought upon a revolution in playing strength. For the first time Go programs stood a chance against a dan-level amateur.
- deleted 9y ago
  [deleted]
- Mageek 9y ago
  The branching factor for games like Go is too high. Alpha Go Zero uses a stochastic policy to focus its attention on useful branches. This policy is optimized alongside the predicted value for each node.
- gwern 9y ago
  Aside from MCTS being a different tree search method, there is no 'closing of the loop'. In regular MCTS, it is far from unheard of to do the random playouts with instead some 'heavier' heuristic to make the playouts a little better estimators of the node value, but the heavy playouts do not do any kind of learning, the heuristic you start with is what you end with; what makes this analogous to policy iteration (hence the names for the Zero algorithm of 'tree iteration' or 'expert iteration') is that the refined estimates from the multiple heavy playouts are then used to improve the heavy playout heuristic (ie. a NN which can be optimized via backpropagation in a supervised learning of board position -> value). Then in a self-play setting, the MCTS continually refines its heavy heuristic (the NN) until it's so good that the NN+MCTS is superhuman. Then at play time you can drop the MCTS entirely and just use the heavy heuristic to do a very simple tree search to choose a move (which I think might actually be a minimax with a fixed depth but I forget).
yters 9y ago
Are there adversarial examples for Alpha Go Zero?
- robotresearcher 9y ago
  The NN played against itself.
- danielvf 9y ago
  What do you mean? AlphaGo Zero has played itself, and they have published 20 of those games.
  - Barrin92 9y ago
    the OP is referring to the use of a GAN, which is a different type of setup. GAN's were not used for alphaGo, as the article points out Deepmind uses reinforcement learning and MCTS.
    - nschucher 9y ago
      They're most likely referring to adversarial attacks where degenerate inputs are constructed that could cause AlphaGo Zero to perform sub-optimally or catastrophically fail (see OpenAI Research [0]). This is distinct from generative adversarial networks (GANs) or adversarial self-play (which I guess AlphaGo Zero is an example of). [0] https://blog.openai.com/adversarial-example-research/ https://blog.openai.com/adversarial-example-research/
- comex 9y ago
  It seems like it would be drastically harder to attack a Go-playing network compared to an image classifier, just because there’s so much less freedom in input. With an image, you can vary each pixel independently however you want. In a game of Go, on any given turn there are probably only a handful of moves that don’t amount to throwing away territory, which would probably be harmful enough to offset any gain by ‘confusing’ the AI. Not only that. the list of suitable moves depends on the AI’s choices in addition to its opponent’s, making the state space highly discontinuous. Who knows, though… maybe there’s some vulnerability so severe that you can spend half the game wasting your moves and win anyway, because the AI gets so confused that it stops playing with even basic competence. I guess that image classifiers giving 99.9% confidence to the wrong class also seems pretty ‘incompetent’… and it would be very cool to see. Another obstacle is that whereas an image classifier is basically a purely learned function, Monte Carlo tree search has a hard-coded element of applying potential moves to find new states to explore - always following the game’s rules correctly. If you go more than a few moves ahead, it has a relatively unpredictable choice of what states to explore; but as you get closer to the current move, I think it starts to look a bit more like brute force. So if you want the AI to make a really bad move - one that has severe consequences in the next few turns - you need to not just make the NN think it looks good, but that the game state still looks good even after you make any possible counterplay. Disclaimer: I don’t actually know much about either neural networks or Go.
gwern 9y ago
Some additional discussion: https://www.reddit.com/r/reinforcementlearning/comments/778vbk/mastering_the_game_of_go_without_human_knowledge/ https://www.reddit.com/r/reinforcementlearning/comments/778v... https://www.reddit.com/r/MachineLearning/comments/7apvr4/d_it_seems_like_alphago_zeros_biggest_successes/ https://www.reddit.com/r/MachineLearning/comments/7apvr4/d_i...
shghs 9y ago
The main reason AlphaGo Zero learns so much faster than its predecessors is because it uses temporal-difference learning.[1] This effectively removes a huge amount of the value network's state space for the learning algorithm to search through, since it bakes in the assumption that a move's value ought to equal that of the best available move in the following board position, which is exactly what you'd expect for a game like Go. A secondary reason for AlphaGo Zero's performance is that it combines both value and policy networks into a single network, since it's redundant to have two networks for move selection. These are the two biggest distinguishing characteristics of AlphaGo Zero compared to previous AlphaGos, and the OP doesn't discuss either of them. [1] https://en.wikipedia.org/wiki/Temporal_difference_learning https://en.wikipedia.org/wiki/Temporal_difference_learning
- gwern 9y ago
  > These are the two biggest distinguishing characteristics of AlphaGo Zero compared to previous AlphaGos, and the OP doesn't discuss either of them. David Silver disagrees. The most critical distinguishing characteristic is the expert/tree iteration which makes stable self-play possible at all.
  - cosminro 9y ago
    A lot of people reading the paper miss this. I guess it's not emphasized enough. In the first paper, the selfplay trained policy is about 1500 in elo rating, while darkforest2 a supervised trained policy from Facebook is around the same, if not better. So selfplay wasn't of much use the first time around. While in the AlphaZero paper the selfplay trained policy has about 3000 elo rating.
    - gwern 9y ago
      > A lot of people reading the paper miss this. I guess it's not emphasized enough. Yeah, it's hilariously underemphasized. 1 sentence, literally. Fortunately I was able to ask Silver directly and get confirmation that it's the tree iteration: https://www.reddit.com/r/MachineLearning/comments/76xjb5/ama_we_are_david_silver_and_julian_schrittwieser/dokh31z/ https://www.reddit.com/r/MachineLearning/comments/76xjb5/ama...
jacobkg 9y ago
Can this technique be used to write a strong chess engine?
- Choco31415 9y ago
  Yes. As described, all that’s needed is a way to imagine all possible moves from a game state, and check if a game state corresponds with win/tie/loss. That is possible in Tic-Tac-Toe, Chess, and Go.
  - Blazespinnaker 9y ago
    Surprisingly, they haven't done it though. Wonder why. Is it because of the number of different state changes that can occur from a particular position? Maybe Go is easier to solve than chess. It would be very interesting to see a computer improve on chess openings.
    - evandijk70 9y ago
      First of all, Go is not 'solved'. While the AI plays better than the best humans, it does not play perfectly (nor will any AI program in the forseeable future). If by 'solving' you mean, developing a strong AI program to play chess, I think the reason they haven't done it because chess is easier to solve than Go. The best computer chess engines are already a lot better than the best humans. Thus, there is not much to gain for Google by finding a new approach. There have been attempts to use similar approaches for chess, but they al seemed to perform worse than the traditional approach for chess. (Alpha-beta search with a hand-written evaluation function and null-move pruning). The differences between Go and Chess that might explain this are: - Chess has a smaller branching factor (the number of legal moves is around 40 in a typical position in chess, whereas it's over 100 in a typical position for Go) - A chess position is easier to evaluate. Simply counting the material already gives a decent evaluation in a lot of cases. This supplemented by hand-written rules gives a solid evaluation of a position - The average game of chess is shorter. A game of chess lasts between 20 and 80 moves, whereas a game of Go lasts around 200 games. This makes it a lot more feasible to extend the search far enough to oversee the consequences of each move in chess when compared to Go
saagarjha 9y ago
If the author's here: some of the math formulas don't render correctly. In particular, 10^170 is parsed as 10^{1}70, and $5478$ shows up without TeX applied to it.
- Mageek 9y ago
  Thanks, fixed those
  - dmix 9y ago
    Another minor fix: > A new paper was released a few days detailing a new neural net I believe you mean "a few days ago"?
    - Mageek 9y ago
      kk
  - tromp 9y ago
    Another minor fix: the number of chess diagrams is at most 10^46, according to http://tromp.github.io/chess/chess.html http://tromp.github.io/chess/chess.html
- pgodzin 9y ago
  One stats with a randomly initialized set -> starts
naveen99 9y ago
someone posted an attempt at an open source implementation of alphagozero https://github.com/yhyu13/AlphaGOZero-python-tensorflow https://github.com/yhyu13/AlphaGOZero-python-tensorflow anyone try it yet ?
- xelxebar 9y ago
  There's also Leela Zero [1]. [1] https://github.com/gcp/leela-zero https://github.com/gcp/leela-zero
Blazespinnaker 9y ago
Mageek, any reason why they haven't applied this to chess yet?
- glinscott 9y ago
  MCTS has done very poorly on chess compared to alpha-beta. Chess has a high number of forcing moves in capture sequences, and it's been very difficult to evaluate positions that are not settled. Traditionally an algorithm called a quiescence search is used, but it relies on doing an evaluation at each node of the search, which would be prohibitive with the latency for a network evaluation. One of the things that amazed me the most about AlphaGo Zero was that they didn't do any tricks to minimize the latency of the network evaluation! Still, it's certainly worth a try, I'd be extremely interested to see what style of chess a self-trained MCTS chess version would have :).
- bluetwo 9y ago
  The founder of DeepMind was an internationally ranked chess prodigy, so that's a good question.
bluetwo 9y ago
Saw the AlphaGo movie at a festival recently. Been following the AlphaGo Zero developments, which leap-frog what was going on in the movie (although still very much worth seeing). One thing I was curious about is if Go would be considered solved, either hard or weakly solved, since AlphaGo Zero at this point doesn't seem to be able to be beat by any living human. Wikipedia does not list it as solved in either sense, and I was wondering if this was an oversight.
- gcb0 9y ago
  if alpha go is just an adversarial network to brute force states, then it is not solved (note I don't research alphaGo, and most of what I know about it is from HN comments)
  - ggghvggtff 9y ago
    Oh so you’re an internet idiot, who shits on other people’s hard work even if completely clueless about it —- what’s it like over there?
- gizmo686 9y ago
  Go still has not been Ultra-weakly solved (eg. we do not know who is supposed to win). If AlphaGo has weakly solved go, then it should either have a 100% win rate when playing against itself as white, or a 100% win rate when playing against itself as black.
  - nojvek 9y ago
    Or 100% rate of a draw. Like tic tac toe.
    - gamegoblin 9y ago
      Due to komi, a go game cannot be drawn. That is, the 2nd player is awarded some number of points for the disadvantage of moving 2nd, and that number of points typically has a fractional 0.5 in it to break ties. The most common komi values these days are 6.5 or 7.5, depending on ruleset.
deleted 9y ago
[deleted]
cgearhart 9y ago
I wonder how AlphaGo Zero would fare against the others if they were all using the same search algorithm, and I wonder how the search depth vs breadth changes in Zero compared to earlier variants.
nemo1618 9y ago
Would be really cool to see a generic framework for this, where you can plug in the rules of your discrete-deterministic-game-with-perfect-information and get a superhuman bot. Does something like this already exist?
- panic 9y ago
  Check out the field of general game playing: https://en.wikipedia.org/wiki/General_game_playing https://en.wikipedia.org/wiki/General_game_playing http://www.ggp.org http://www.ggp.org http://logic.stanford.edu/ggp/readings/retrospective.html http://logic.stanford.edu/ggp/readings/retrospective.html
- nojvek 9y ago
  If anyone's interested who understands alpha zero in depth. I would love to start a github project to implement a super not that players checkers, tic tac toe, chess, go etc and all related games on the browser via an openai like interface.
unpseudo 9y ago
They are two things a human brain does when playing chess or go: evaluating a position and mentally playing some positions (by doing a search tree). The AlphaGo neural network is able to do the first part (evaluating positions) but the search tree is still a hand crafted algorithm. Do they have plans to work on a version with a pure neural network? (i.e. a version which would be able to learn how to do a search tree.)
- nojvek 9y ago
  Who is to say that the human brain doesn't have a different cell type to do this kind of search. The neocortex is shaped in a different way than other neural cells so I imagine search and evaluation are different architectures. But you're right. A NN way to do Montecarlo search in GPUs would make things even simpler.
zeristor 9y ago
Are there any plans to do this for Chess? I imagine that this is an iteration of the Alpha Go engine, people working on this are very current with Alpha Go. If Chess is similar, then wouldn't DeepMind be able to bootstrap game knowledge. Perhaps this isn't a big goal, but Chess is Chess after all.
- deleted 9y ago
  [deleted]
- naveen99 9y ago
  There was a project for chess, called giraffe https://bitbucket.org/waterreaction/giraffe https://bitbucket.org/waterreaction/giraffe whose author shut it down after joining google deep mind: http://www.talkchess.com/forum/viewtopic.php?t=59003 http://www.talkchess.com/forum/viewtopic.php?t=59003 He thinks it's only a matter of time till machine learning beats hand crafted systems like stockfish even in chess. http://arxiv.org/abs/1509.01549 http://arxiv.org/abs/1509.01549
  - nojvek 9y ago
    Does alphazero beat stock fish purely by self play. That would be huge. Stock fish is the result of so many hand crafted optimizations over a large game play dataset.
    - thom 9y ago
      Intuitively you'd expect deep learning to improve on Stockfish's evaluation of positions, but perhaps not at the same level of throughput. I'm also intrigued as to whether a purely self-taught AI system can compare in the endgame to an engine with access to a 7-piece endgame tablebase, whose evaluation of those positions is obviously _perfect_.
falcor84 9y ago
As someone who has played many a game of Tic-Tac-Toe, I found the numerical examples really hard to follow. s(0,5) is obviously the winning move for the X player, but for some reason all examples seem to favor s(0,1).
- alkonaut 9y ago
  Winning move how? With which board? with O__ _X_ O_X Then X can't win in the next move and must choose (0,1) between the two O's the left column in order to not lose.
  - falcor84 9y ago
    D'oh, thanks. I suppose I just misread the oh's.
pmarreck 9y ago
> It is interesting to see how quickly the field of AI is progressing. Those who claim we will be able to see the robot overlords coming in time should take heed - these AI's will only be human-level for a brief instant before blasting past us into superhuman territories, never to look back. This final paragraph is just editorializing. A computer will never care about anything (including games like Go and domination of other beings) that it is not programmed to imitate care about, and will thus remain perennially unmotivated. Also, my intuition says that gradient descent is an ugly hack and that there HAS to be some better way (like a direct way) to get at the inverse of a matrix (not just in specific cases but in the general case!), but I digress, and not being a mathematician, perhaps someone has already proved somehow that a general method to directly and efficiently invert all possible matrices is impossible
- thomasahle 9y ago
  What do you mean with inverting a matrix? In the usual definition it is well studied and understood https://en.m.wikipedia.org/wiki/Invertible_matrix#Methods_of_matrix_inversion https://en.m.wikipedia.org/wiki/Invertible_matrix#Methods_of...
  - pmarreck 9y ago
    I just... Here's the deal. Most good math is elegant, it has a beauty about it. And as a programmer, good code has the same "feel." But when I took Andrew Ng's class, gradient descent felt... not beautiful at all... and just based on that beauty-seeking intuition, there MUST be a more elegant way to get directly at the inverse of a matrix (assuming it exists and is possible) than all of these... complicated expensive workarounds. And the pot at the end of that rainbow is you get the EXACT value that gradient descent is wasting all this time trying to snowboard down N-dimensional space to get to! I know I may be asking to make what may be a fundamentally-hard problem, easy... I'm just saying that I don't get the same, eh, "buzz" I get when I see a really cool solution for something (which I've often gotten from math, physics, programming, etc.). This is very hard to explain as it's probably irrational and thus I can't make a strong rational argument for it lol (admittedly!) I really love linear algebra, btw, so this should be right up my alley.
erikb 9y ago
I don't get what is new in the set of attributes that this article describes. Monte Carlo was already used in 2005 in AIs playing on KGS. Gradient Descent is a basic algorithm is a basic algorithm that I saw in an AI class in ~2008 as well. I bet both are even a lot older and well known by all experts. This is not what makes AlphaGo special or Zero successful. The curious thing about Zero is that usually with Gradient Descent you run a huge risk of running into a local maximum and then stop evolving because every evolution makes you not better than the current step. So one question is actually how they used these same old algorithms so much more efficiently, and the second question is how did they overcame the local maximum problem. Additionally there may be other problems involved that experts know better than me. But an explanation of basic algorthims can't be the answer.
- gwern 9y ago
  > The curious thing about Zero is that usually with Gradient Descent you run a huge risk of running into a local maximum and then stop evolving because every evolution makes you not better than the current step. No. The curious thing is that you can train a godawful huge NN with 40 layers via pure self-play with no checkpoints or baselines or pretraining or library of hard problems or any kind of stabilization mechanism, and it won't diverge but will learn incredibly rapidly and well and stably. As Silver says in the AmA, all their attempts at pure self-play ran into the usual divergence problems where the training explodes and engages in catastrophic forgetting, which is what the RL folklore predicts will happen if you try to do that. Local maximums are not the problem - the problem is the self-play can't even find a local maximum much less maintain it or improve it. > So one question is actually how they used these same old algorithms so much more efficiently, and the second question is how did they overcame the local maximum problem. Er, this is exactly what OP is all about: the Monte Carlo tree search supervision. That's how they used them.
  - psb217 9y ago
    If you read the AGZ paper closely, they actually use checkpoints during training. Specifically, during training they only perform updates to the "stable" set of parameters when the current "learning" set of parameters produces a policy which beats the stable set at least 55% of the time. The current stable parameters are what they use for generating the self-play data which they use to update the current "learning" parameters. I believe this is only mentioned in the supplementary material...
fspeech 9y ago
Given that AlphaGo Zero was trained on several million games of self plays, each game involving hundreds of steps, each step with 1600 MCTS simulations, the total number of board positions it has considered is on the order of trillions. While impressive it pales in comparison to the number of possible board positions of 10^170 (https://en.m.wikipedia.org/wiki/Go_and_mathematics https://en.m.wikipedia.org/wiki/Go_and_mathematics). So its amazing performance tells us that: 1. Possibly the elegant rule of the game cuts down the search space so much that there is a learnable function that gives us optimal MCTS supervision; 2. Or CNN approximates human visual intuition so well, so while Zero has not evaluated so many board positions it has evaluated all the positions that human has ever considered - so it remains possible that a different network could produce different strategies and be better than Zero.

354 points by Mageek 9y ago

Go has been studied for hundreds of years. In many cases, by people who study the game since their childhood and work on it as a full-time occupation. The consequence of Alpha Go Zero is that it can, in a matter of days, disregard and surpass all human knowledge about the game. Maximizing a score margin has been equated for a long time with maximizing your probability of winning. Alpha Go doesn't play like that... it's a substantial paradigm shift. If you see the early commentaries you will see that human players were initially saying Alpha Go moves were mistakes because they were slow and wasted opportunities to get more territory, to then realize that Alpha Go was actually winning.

ImSkeptical 9y ago
I think people have always understood the difference between maximising probability of victory versus score. Even in amateur games you'll get the feeling "I could fight here, and it would be complicated, but I might get a huge advantage, or I could just play safe and keep my advantage."
aurelianito 9y ago
Even kyus like myself play more conservatively when winning. Alphago just takes this to the extreme but it is common on most levels of play (from single digit kyus to the best professional players).

EGreg 9y ago

I wonder how the STYLE of Alpha Go Zero is regarded by human experts. Is it far different from AlphaGo? Why bother learning from AlphaGo if they can learn from AlphaGo Zero? Did they unleash a second "Master" program? I am wondering if the "better" strategy moves are now super wacky and weird and break all theory.

danielvf 9y ago
At least initial reports are that alphaGo Zero is more human-like than Master. Zero packs even more of the inhuman ability to pick the most critical part of the board for each move, but less weird looking stuff. In fact, one of the obvious differences between AlphaGo Zero and top human players, is much more play on safe opening spots, which has been out of fashion among human pros for a hundred years or so.
- zone411 9y ago
  Interesting. It may be possible that while the style of play of Master is able to exploit the errors of human players easily and score convincing victories by many stones, Zero is closer to playing Go perfectly, even if it means winning by one stone. There is a chance that Zero would not score such convincing victories over humans as Master but is much less exploitable. If a strong player plays obvious novices (and humans are now at a level of novices compared to these programs), it doesn't have to worry about taking more unsound risks.
- gizmo686 9y ago
  >At least initial reports are that alphaGo Zero is more human-like than Master. Empirically, this is not correct. The original AlphaGo achieved a 57% accuracy at predicting expert moves. I can't find an exact number, but based on the graph in the nature article, AlphaGo Zero has a less than 50% accuracy at predicting human moves. Eyeballing the graph, it looks like the supervized learning variant of AlphaGo Zero scored <55% at predicting human moves. Better than reinforcement learning AlphaGo Zero, but still worse then the original AlphaGo. Of course, it is not clear that ability to predict the move humans will play is the best metric to measure how human like a computer plays. It is just the only objective metric we have. Although, if this were an actual research question, we could probably come up with better metrics. https://storage.googleapis.com/deepmind-media/alphago/AlphaGoNaturePaper.pdf https://storage.googleapis.com/deepmind-media/alphago/AlphaG... https://www.nature.com/nature/journal/v550/n7676/pdf/nature24270.pdf https://www.nature.com/nature/journal/v550/n7676/pdf/nature2...
  - 9y ago

javajosh 9y ago

"On a long enough timeline, everything is a discrete game." (With apologies to _Fight Club_) Personally, I look forward to the day when the software I own works for me to the extent of optimizing the decisions I make during the day, even many mundane ones. Properly executed, such a system could make a big difference in my quality of life. I believe that a big piece that is missing is a solid life-model, a life-representation, that can be optimized. Once that is defined, an RNN or MCS can optimize it and I can reap the benefits.

StavrosK 9y ago
Complete with creepy predictions like "Predicted optimal life path: $120,000 net worth, 63 year life span".
ben_w 9y ago
If it is optimising all your decisions, even the mundane ones, is it really your life any more? If it plugged into your brainstem and took over, by definition nobody else would notice the difference (you always did what it said anyway, or you’d be suboptimal), so why not just flood the 20 watt carbon-based neural network with bliss drugs and let the silicon-based neural network be the person instead?
- shard 9y ago
  Or just replace the brain completely with the computer, like in Greg Egan's jewel stories. http://will.tip.dhappy.org/blog/Compression%20Trees/.../book/by/Greg%20Egan/Learning%20To%20Be%20Me/ http://will.tip.dhappy.org/blog/Compression%20Trees/.../book...
- zzzzzzzza 9y ago
  well if you chose and modified the representation of the world yourself, and set it so it would be making decisions based on a heuristic you provided it, then at the end of the day, it is not so different from how our biological circuits work, to the extent we have control over them
- kbenson 9y ago

QML 9y ago

What makes this different from a minimax algorithm with alpha-beta pruning?

GolDDranks 9y ago
Minimax algorithm with alpha-beta pruning is an exhaustive search algorithm. MCTS is a probabilistic algorithm that optimises for converging faster for a partial "good enough" result. Introducing MCTS for Go playing programs in 2006 brought upon a revolution in playing strength. For the first time Go programs stood a chance against a dan-level amateur.
deleted 9y ago
[deleted]
Mageek 9y ago
The branching factor for games like Go is too high. Alpha Go Zero uses a stochastic policy to focus its attention on useful branches. This policy is optimized alongside the predicted value for each node.
gwern 9y ago
Aside from MCTS being a different tree search method, there is no 'closing of the loop'. In regular MCTS, it is far from unheard of to do the random playouts with instead some 'heavier' heuristic to make the playouts a little better estimators of the node value, but the heavy playouts do not do any kind of learning, the heuristic you start with is what you end with; what makes this analogous to policy iteration (hence the names for the Zero algorithm of 'tree iteration' or 'expert iteration') is that the refined estimates from the multiple heavy playouts are then used to improve the heavy playout heuristic (ie. a NN which can be optimized via backpropagation in a supervised learning of board position -> value). Then in a self-play setting, the MCTS continually refines its heavy heuristic (the NN) until it's so good that the NN+MCTS is superhuman. Then at play time you can drop the MCTS entirely and just use the heavy heuristic to do a very simple tree search to choose a move (which I think might actually be a minimax with a fixed depth but I forget).

yters 9y ago

Are there adversarial examples for Alpha Go Zero?

robotresearcher 9y ago
The NN played against itself.
danielvf 9y ago
What do you mean? AlphaGo Zero has played itself, and they have published 20 of those games.
- Barrin92 9y ago
  the OP is referring to the use of a GAN, which is a different type of setup. GAN's were not used for alphaGo, as the article points out Deepmind uses reinforcement learning and MCTS.
  - nschucher 9y ago
    They're most likely referring to adversarial attacks where degenerate inputs are constructed that could cause AlphaGo Zero to perform sub-optimally or catastrophically fail (see OpenAI Research [0]). This is distinct from generative adversarial networks (GANs) or adversarial self-play (which I guess AlphaGo Zero is an example of). [0] https://blog.openai.com/adversarial-example-research/ https://blog.openai.com/adversarial-example-research/
comex 9y ago
It seems like it would be drastically harder to attack a Go-playing network compared to an image classifier, just because there’s so much less freedom in input. With an image, you can vary each pixel independently however you want. In a game of Go, on any given turn there are probably only a handful of moves that don’t amount to throwing away territory, which would probably be harmful enough to offset any gain by ‘confusing’ the AI. Not only that. the list of suitable moves depends on the AI’s choices in addition to its opponent’s, making the state space highly discontinuous. Who knows, though… maybe there’s some vulnerability so severe that you can spend half the game wasting your moves and win anyway, because the AI gets so confused that it stops playing with even basic competence. I guess that image classifiers giving 99.9% confidence to the wrong class also seems pretty ‘incompetent’… and it would be very cool to see. Another obstacle is that whereas an image classifier is basically a purely learned function, Monte Carlo tree search has a hard-coded element of applying potential moves to find new states to explore - always following the game’s rules correctly. If you go more than a few moves ahead, it has a relatively unpredictable choice of what states to explore; but as you get closer to the current move, I think it starts to look a bit more like brute force. So if you want the AI to make a really bad move - one that has severe consequences in the next few turns - you need to not just make the NN think it looks good, but that the game state still looks good even after you make any possible counterplay. Disclaimer: I don’t actually know much about either neural networks or Go.

gwern 9y ago

Some additional discussion: https://www.reddit.com/r/reinforcementlearning/comments/778vbk/mastering_the_game_of_go_without_human_knowledge/ https://www.reddit.com/r/reinforcementlearning/comments/778v... https://www.reddit.com/r/MachineLearning/comments/7apvr4/d_it_seems_like_alphago_zeros_biggest_successes/ https://www.reddit.com/r/MachineLearning/comments/7apvr4/d_i...

shghs 9y ago

The main reason AlphaGo Zero learns so much faster than its predecessors is because it uses temporal-difference learning.[1] This effectively removes a huge amount of the value network's state space for the learning algorithm to search through, since it bakes in the assumption that a move's value ought to equal that of the best available move in the following board position, which is exactly what you'd expect for a game like Go. A secondary reason for AlphaGo Zero's performance is that it combines both value and policy networks into a single network, since it's redundant to have two networks for move selection. These are the two biggest distinguishing characteristics of AlphaGo Zero compared to previous AlphaGos, and the OP doesn't discuss either of them. [1] https://en.wikipedia.org/wiki/Temporal_difference_learning https://en.wikipedia.org/wiki/Temporal_difference_learning

gwern 9y ago
> These are the two biggest distinguishing characteristics of AlphaGo Zero compared to previous AlphaGos, and the OP doesn't discuss either of them. David Silver disagrees. The most critical distinguishing characteristic is the expert/tree iteration which makes stable self-play possible at all.
- cosminro 9y ago
  A lot of people reading the paper miss this. I guess it's not emphasized enough. In the first paper, the selfplay trained policy is about 1500 in elo rating, while darkforest2 a supervised trained policy from Facebook is around the same, if not better. So selfplay wasn't of much use the first time around. While in the AlphaZero paper the selfplay trained policy has about 3000 elo rating.
  - gwern 9y ago
    > A lot of people reading the paper miss this. I guess it's not emphasized enough. Yeah, it's hilariously underemphasized. 1 sentence, literally. Fortunately I was able to ask Silver directly and get confirmation that it's the tree iteration: https://www.reddit.com/r/MachineLearning/comments/76xjb5/ama_we_are_david_silver_and_julian_schrittwieser/dokh31z/ https://www.reddit.com/r/MachineLearning/comments/76xjb5/ama...

jacobkg 9y ago

Can this technique be used to write a strong chess engine?

Choco31415 9y ago
Yes. As described, all that’s needed is a way to imagine all possible moves from a game state, and check if a game state corresponds with win/tie/loss. That is possible in Tic-Tac-Toe, Chess, and Go.
- Blazespinnaker 9y ago
  Surprisingly, they haven't done it though. Wonder why. Is it because of the number of different state changes that can occur from a particular position? Maybe Go is easier to solve than chess. It would be very interesting to see a computer improve on chess openings.
  - evandijk70 9y ago
    First of all, Go is not 'solved'. While the AI plays better than the best humans, it does not play perfectly (nor will any AI program in the forseeable future). If by 'solving' you mean, developing a strong AI program to play chess, I think the reason they haven't done it because chess is easier to solve than Go. The best computer chess engines are already a lot better than the best humans. Thus, there is not much to gain for Google by finding a new approach. There have been attempts to use similar approaches for chess, but they al seemed to perform worse than the traditional approach for chess. (Alpha-beta search with a hand-written evaluation function and null-move pruning). The differences between Go and Chess that might explain this are: - Chess has a smaller branching factor (the number of legal moves is around 40 in a typical position in chess, whereas it's over 100 in a typical position for Go) - A chess position is easier to evaluate. Simply counting the material already gives a decent evaluation in a lot of cases. This supplemented by hand-written rules gives a solid evaluation of a position - The average game of chess is shorter. A game of chess lasts between 20 and 80 moves, whereas a game of Go lasts around 200 games. This makes it a lot more feasible to extend the search far enough to oversee the consequences of each move in chess when compared to Go

saagarjha 9y ago

If the author's here: some of the math formulas don't render correctly. In particular, 10^170 is parsed as 10^{1}70, and $5478$ shows up without TeX applied to it.

Mageek 9y ago
Thanks, fixed those
- dmix 9y ago
  Another minor fix: > A new paper was released a few days detailing a new neural net I believe you mean "a few days ago"?
  - Mageek 9y ago
    kk
- tromp 9y ago
  Another minor fix: the number of chess diagrams is at most 10^46, according to http://tromp.github.io/chess/chess.html http://tromp.github.io/chess/chess.html
pgodzin 9y ago
One stats with a randomly initialized set -> starts

naveen99 9y ago

someone posted an attempt at an open source implementation of alphagozero https://github.com/yhyu13/AlphaGOZero-python-tensorflow https://github.com/yhyu13/AlphaGOZero-python-tensorflow anyone try it yet ?

xelxebar 9y ago
There's also Leela Zero [1]. [1] https://github.com/gcp/leela-zero https://github.com/gcp/leela-zero

Blazespinnaker 9y ago

Mageek, any reason why they haven't applied this to chess yet?

glinscott 9y ago
MCTS has done very poorly on chess compared to alpha-beta. Chess has a high number of forcing moves in capture sequences, and it's been very difficult to evaluate positions that are not settled. Traditionally an algorithm called a quiescence search is used, but it relies on doing an evaluation at each node of the search, which would be prohibitive with the latency for a network evaluation. One of the things that amazed me the most about AlphaGo Zero was that they didn't do any tricks to minimize the latency of the network evaluation! Still, it's certainly worth a try, I'd be extremely interested to see what style of chess a self-trained MCTS chess version would have :).
bluetwo 9y ago
The founder of DeepMind was an internationally ranked chess prodigy, so that's a good question.

bluetwo 9y ago

Saw the AlphaGo movie at a festival recently. Been following the AlphaGo Zero developments, which leap-frog what was going on in the movie (although still very much worth seeing). One thing I was curious about is if Go would be considered solved, either hard or weakly solved, since AlphaGo Zero at this point doesn't seem to be able to be beat by any living human. Wikipedia does not list it as solved in either sense, and I was wondering if this was an oversight.

gcb0 9y ago
if alpha go is just an adversarial network to brute force states, then it is not solved (note I don't research alphaGo, and most of what I know about it is from HN comments)
- ggghvggtff 9y ago
  Oh so you’re an internet idiot, who shits on other people’s hard work even if completely clueless about it —- what’s it like over there?
gizmo686 9y ago
Go still has not been Ultra-weakly solved (eg. we do not know who is supposed to win). If AlphaGo has weakly solved go, then it should either have a 100% win rate when playing against itself as white, or a 100% win rate when playing against itself as black.
- nojvek 9y ago
  Or 100% rate of a draw. Like tic tac toe.
  - gamegoblin 9y ago
    Due to komi, a go game cannot be drawn. That is, the 2nd player is awarded some number of points for the disadvantage of moving 2nd, and that number of points typically has a fractional 0.5 in it to break ties. The most common komi values these days are 6.5 or 7.5, depending on ruleset.

deleted 9y ago

[deleted]

cgearhart 9y ago

I wonder how AlphaGo Zero would fare against the others if they were all using the same search algorithm, and I wonder how the search depth vs breadth changes in Zero compared to earlier variants.

nemo1618 9y ago

Would be really cool to see a generic framework for this, where you can plug in the rules of your discrete-deterministic-game-with-perfect-information and get a superhuman bot. Does something like this already exist?

panic 9y ago
Check out the field of general game playing: https://en.wikipedia.org/wiki/General_game_playing https://en.wikipedia.org/wiki/General_game_playing http://www.ggp.org http://www.ggp.org http://logic.stanford.edu/ggp/readings/retrospective.html http://logic.stanford.edu/ggp/readings/retrospective.html
nojvek 9y ago
If anyone's interested who understands alpha zero in depth. I would love to start a github project to implement a super not that players checkers, tic tac toe, chess, go etc and all related games on the browser via an openai like interface.

unpseudo 9y ago

They are two things a human brain does when playing chess or go: evaluating a position and mentally playing some positions (by doing a search tree). The AlphaGo neural network is able to do the first part (evaluating positions) but the search tree is still a hand crafted algorithm. Do they have plans to work on a version with a pure neural network? (i.e. a version which would be able to learn how to do a search tree.)

nojvek 9y ago
Who is to say that the human brain doesn't have a different cell type to do this kind of search. The neocortex is shaped in a different way than other neural cells so I imagine search and evaluation are different architectures. But you're right. A NN way to do Montecarlo search in GPUs would make things even simpler.

zeristor 9y ago

Are there any plans to do this for Chess? I imagine that this is an iteration of the Alpha Go engine, people working on this are very current with Alpha Go. If Chess is similar, then wouldn't DeepMind be able to bootstrap game knowledge. Perhaps this isn't a big goal, but Chess is Chess after all.

deleted 9y ago
[deleted]
naveen99 9y ago
There was a project for chess, called giraffe https://bitbucket.org/waterreaction/giraffe https://bitbucket.org/waterreaction/giraffe whose author shut it down after joining google deep mind: http://www.talkchess.com/forum/viewtopic.php?t=59003 http://www.talkchess.com/forum/viewtopic.php?t=59003 He thinks it's only a matter of time till machine learning beats hand crafted systems like stockfish even in chess. http://arxiv.org/abs/1509.01549 http://arxiv.org/abs/1509.01549
- nojvek 9y ago
  Does alphazero beat stock fish purely by self play. That would be huge. Stock fish is the result of so many hand crafted optimizations over a large game play dataset.
  - thom 9y ago
    Intuitively you'd expect deep learning to improve on Stockfish's evaluation of positions, but perhaps not at the same level of throughput. I'm also intrigued as to whether a purely self-taught AI system can compare in the endgame to an engine with access to a 7-piece endgame tablebase, whose evaluation of those positions is obviously _perfect_.

falcor84 9y ago

As someone who has played many a game of Tic-Tac-Toe, I found the numerical examples really hard to follow. s(0,5) is obviously the winning move for the X player, but for some reason all examples seem to favor s(0,1).

alkonaut 9y ago
Winning move how? With which board? with O__ _X_ O_X Then X can't win in the next move and must choose (0,1) between the two O's the left column in order to not lose.
- falcor84 9y ago
  D'oh, thanks. I suppose I just misread the oh's.

pmarreck 9y ago

> It is interesting to see how quickly the field of AI is progressing. Those who claim we will be able to see the robot overlords coming in time should take heed - these AI's will only be human-level for a brief instant before blasting past us into superhuman territories, never to look back. This final paragraph is just editorializing. A computer will never care about anything (including games like Go and domination of other beings) that it is not programmed to imitate care about, and will thus remain perennially unmotivated. Also, my intuition says that gradient descent is an ugly hack and that there HAS to be some better way (like a direct way) to get at the inverse of a matrix (not just in specific cases but in the general case!), but I digress, and not being a mathematician, perhaps someone has already proved somehow that a general method to directly and efficiently invert all possible matrices is impossible

thomasahle 9y ago
What do you mean with inverting a matrix? In the usual definition it is well studied and understood https://en.m.wikipedia.org/wiki/Invertible_matrix#Methods_of_matrix_inversion https://en.m.wikipedia.org/wiki/Invertible_matrix#Methods_of...
- pmarreck 9y ago
  I just... Here's the deal. Most good math is elegant, it has a beauty about it. And as a programmer, good code has the same "feel." But when I took Andrew Ng's class, gradient descent felt... not beautiful at all... and just based on that beauty-seeking intuition, there MUST be a more elegant way to get directly at the inverse of a matrix (assuming it exists and is possible) than all of these... complicated expensive workarounds. And the pot at the end of that rainbow is you get the EXACT value that gradient descent is wasting all this time trying to snowboard down N-dimensional space to get to! I know I may be asking to make what may be a fundamentally-hard problem, easy... I'm just saying that I don't get the same, eh, "buzz" I get when I see a really cool solution for something (which I've often gotten from math, physics, programming, etc.). This is very hard to explain as it's probably irrational and thus I can't make a strong rational argument for it lol (admittedly!) I really love linear algebra, btw, so this should be right up my alley.

erikb 9y ago

I don't get what is new in the set of attributes that this article describes. Monte Carlo was already used in 2005 in AIs playing on KGS. Gradient Descent is a basic algorithm is a basic algorithm that I saw in an AI class in ~2008 as well. I bet both are even a lot older and well known by all experts. This is not what makes AlphaGo special or Zero successful. The curious thing about Zero is that usually with Gradient Descent you run a huge risk of running into a local maximum and then stop evolving because every evolution makes you not better than the current step. So one question is actually how they used these same old algorithms so much more efficiently, and the second question is how did they overcame the local maximum problem. Additionally there may be other problems involved that experts know better than me. But an explanation of basic algorthims can't be the answer.

gwern 9y ago
> The curious thing about Zero is that usually with Gradient Descent you run a huge risk of running into a local maximum and then stop evolving because every evolution makes you not better than the current step. No. The curious thing is that you can train a godawful huge NN with 40 layers via pure self-play with no checkpoints or baselines or pretraining or library of hard problems or any kind of stabilization mechanism, and it won't diverge but will learn incredibly rapidly and well and stably. As Silver says in the AmA, all their attempts at pure self-play ran into the usual divergence problems where the training explodes and engages in catastrophic forgetting, which is what the RL folklore predicts will happen if you try to do that. Local maximums are not the problem - the problem is the self-play can't even find a local maximum much less maintain it or improve it. > So one question is actually how they used these same old algorithms so much more efficiently, and the second question is how did they overcame the local maximum problem. Er, this is exactly what OP is all about: the Monte Carlo tree search supervision. That's how they used them.
- psb217 9y ago
  If you read the AGZ paper closely, they actually use checkpoints during training. Specifically, during training they only perform updates to the "stable" set of parameters when the current "learning" set of parameters produces a policy which beats the stable set at least 55% of the time. The current stable parameters are what they use for generating the self-play data which they use to update the current "learning" parameters. I believe this is only mentioned in the supplementary material...

fspeech 9y ago

Given that AlphaGo Zero was trained on several million games of self plays, each game involving hundreds of steps, each step with 1600 MCTS simulations, the total number of board positions it has considered is on the order of trillions. While impressive it pales in comparison to the number of possible board positions of 10^170 (https://en.m.wikipedia.org/wiki/Go_and_mathematics https://en.m.wikipedia.org/wiki/Go_and_mathematics). So its amazing performance tells us that: 1. Possibly the elegant rule of the game cuts down the search space so much that there is a learnable function that gives us optimal MCTS supervision; 2. Or CNN approximates human visual intuition so well, so while Zero has not evaluated so many board positions it has evaluated all the positions that human has ever considered - so it remains possible that a different network could produce different strategies and be better than Zero.