6 ms·

MuGo: A minimalist Go engine modeled after AlphaGo

119 points by luu 10y ago

apetresc 10y ago
Cool. Some students at Rochester are also re-implementing AlphaGo based on DeepMind's paper in Nature: https://github.com/Rochester-NRT/RocAlphaGo https://github.com/Rochester-NRT/RocAlphaGo
GolDDranks 10y ago
How strong it is? Is there any pre-trained data available? IIRC, Monte Carlo Tree Search with "dumber" heuristics than NNs yielded amateur dan level AIs for the first time (somewhere around 2006?). Lately there has also been some AIs that bolt a NN in, and get around 1 stone stronger (which is still miles away from AlphaGo!). But since this is specifically modelled after AlphaGo, I wonder how it fares against other AIs.
cr0sh 10y ago
Something I'm finding interesting is how so many of these deep-learning neural nets use RELU for their activation function; RELU is known as a "lazy engineer's activation" function - very simple to implement, and despite looking like a hack, seems to work very well for many tasks. I tend to wonder - beyond "ease of implementation and good 'nuff" reasons - if there are other reasons to use RELU, over other activation functions like TANH or Sigmoid? I'm beginning to suspect that we may be seeing the "engineering side" of neural networks coming into play; that instead of using the more "biologically accurate" activation of the sigmoid function, we instead use RELU (and other ELU derivatives) because it works well, and is easier to understand? Much like how things progressed better in heavier-than-air flight once engineers realized that flapping wings weren't absolutely needed, and low-weight engines turning propellers, with fixed wings, worked better for flying than what nature uses...?
- xiphias 10y ago
  What's interesting is that Jeff Dean noted that ReLU was one of the big things why deep learning took off. Wikipedia summarizes tha advantages, but my guess is getting rid of the vanishing gradients problem: https://en.m.wikipedia.org/wiki/Rectifier_%28neural_networks%29?wprov=sfla1 https://en.m.wikipedia.org/wiki/Rectifier_%28neural_networks...
  - cr0sh 10y ago
    > Wikipedia summarizes tha advantages, but my guess is getting rid of the vanishing gradients problem Hmm - didn't think about that aspect, but that would be a big plus for backprop as I understand it! Thanks for the insight, and the link.
- bbctol 10y ago
  RELU is decidedly the more "biologically accurate" (or at least biologically inspired) compared to the sigmoid function. The idea put forth to originally justify RELUs was that neurons in the brain only have action potentials or lack thereof: the lowest level of activity a neuron can have is zero, and then you can ramp up frequency of action potentials from there, as opposed to the sigmoid's positive and negative symmetric curves. That said, a lot of the history of neural networks has been brief moments of biological inspiration followed by hacking and engineering that drifts further away from the biology the better it gets. The biggest example is backpropagation; despite how essential it's been to artificial neural networks, it really doesn't exist in the brain, at least not as simply as it does in code. For now, we're all still exploring, some looking towards biology, some towards abstract principles, and it remains to be seen if one provides consistently better results.
  - cr0sh 10y ago
    > The biggest example is backpropagation; despite how essential it's been to artificial neural networks, it really doesn't exist in the brain, at least not as simply as it does in code. Do you have any links to papers or such explaining "at least not as simply as it does in code"? EDIT: nvm, I followed the links in a wikipedia article on RELU to relevant PDFs... For a while now this is one area I have been questioning - that we do use backprop, and maybe there is something to be learned from nature that might (?) simplify how a NN is trained (then again, nature might be doing it in such a way that is more complex than can be engineered or practical)... > For now, we're all still exploring, some looking towards biology, some towards abstract principles, and it remains to be seen if one provides consistently better results. It might end up being a combination; at least, that seems the direction so far to a point. I want to thank you for your comments, though. I'm still learning this stuff (I'm working thru the Udacity Self-Driving Car Engineer Nanodegree), and you've given me some stuff to think about and explore further.
    - bbctol 10y ago
      Honestly, the current state of neural backpropagation research is still in flux and papers will be pretty technical. My background's in neuroscience, and the rough summary of what we know so far is: action potentials can travel backwards down a neuron, and they probably do so in vivo, but we don't know if this actually does anything. There's no mechanism we understand for passing information backwards through a synapse. In fact, the only reason people suspect this might be important, and not just an accidental effect, is because backpropagation has been important in developing artificial neural networks. Getting inspiration from nature is often useful (convolutional neural networks are loosely inspired by the way information is processed down the optic nerve) but for the specifics of neuron function, the brain is almost certainly doing things that are more complex than is practical to simulate. The brain contains hundreds of billions of neurons, and each one is orders of magnitude more complex than a node in an ANN, interacting with local and distant neurons through all kinds of separate but interlocking electrical, chemical, and long-term genetic actions.
- jimfleming 10y ago
  The reasons to use ReLUs are sparsity and improved gradient flow. ReLUs encourage sparsity because when the input to the ReLU is less than 0 as the activation becomes 0. This means some fraction of activations in a given layer will be omitted which can encourage better representations. They also have improved gradient flow because the gradients are zero or constant and thus don't suffer from vanishing/exploding gradients. In deep learning, I would _generally_ not look towards biology for the reasons behind why things are done as this is usually an after-the-fact explanation. When in doubt, blame the gradients.
  - ma2rten 10y ago
    LeakyReLUs work as well or better than ReLUs, so it can't be because of sparsity.
    - ekelsen 10y ago
      LeakyReLUs often have very small slopes on the negative side; this can help solve the problem of no gradients getting through a layer because the activations were all 0. But I would say it still has a sparsity effect on a trained network because of how small the slope usually is compared to one.
      - argonaut 10y ago
        That is not sparsity. In machine learning there is a very strong distinction between values that are exactly 0, and values that are close to zero (see: difference between L1 and L2 regularization).
        ekelsen 10y ago
        L1 regularization does not lead to values that are _exactly_ 0 either.
        makeset 10y ago
        Yes, it does. You might have been thrown off by the fact that L1 regularization is not L0 regularization, i.e. it doesn't explicitly limit the number of nonzero coefficients. Still, the linearity of L1 constraint boundaries creates spikes in directions with zero components, thus forcing constrained solutions to occur where many variables are driven to exactly zero. See here: https://en.wikipedia.org/wiki/Lasso_(statistics)#Geometric_interpretation https://en.wikipedia.org/wiki/Lasso_(statistics)#Geometric_i...
- sp332 10y ago
  https://smerity.com/articles/2016/google_nmt_arch.html https://smerity.com/articles/2016/google_nmt_arch.html section "V6: Residuals are the new hotness". You can think of each layer (or I guess a pair of layers) as trying to correct errors in the previous layer. If the previous layer is close enough, the next layer can output 0. This is more stable than a straight linear activation, where one layer might move up a bit as the next one moves down to compensate! ReLU lets the earlier layer fine-tune itself without the effect being undone by later layers.
  - cr0sh 10y ago
    Interesting! Thanks for the link!
- deepnotderp 10y ago
  Gradient flow due to chain rule is the reason. Also that last part is lecun a analogy ;
- deleted 10y ago
  [deleted]
tonetheman 10y ago
Super cool stuff
gcp 10y ago
This doesn't include the data set for the value network. This is critical, because producing that one requires implementing the full reinforcement learning. Even if you skip that and use the policy network, you still have the task of playing a few tens of million games. Learning a value network as big as AlphaGo from public data does not work: you overfit to hell. Which playout policy is this using? There doesn't seem to be any? Looks like it's just a neural network player. There's dozens of those already. You don't need to credit AlphaGo if you're only using policy networks for Go: The critical research for that was done at the University of Edinburgh.
AsyncAwait 10y ago
Sadly, it's not written in Go :-)
- marvy 10y ago
  To be fair, neither is AlphaGo :) But I admit that the pun is hard to resist.
brilee 10y ago
To give an update on status of project, I'm currently at the point where the policy net alone plays at 2-3kyu with a day or so of training. MCTS is implemented but Python is slow enough that I don't get significant Playouts. As a result I don't have insight into the scalability of my implementation. I'm currently working on code to play batches of games in parallel which should be of use both for RL and parallelized MCTS playouts.

119 points by luu 10y ago

Cool. Some students at Rochester are also re-implementing AlphaGo based on DeepMind's paper in Nature: https://github.com/Rochester-NRT/RocAlphaGo https://github.com/Rochester-NRT/RocAlphaGo

GolDDranks 10y ago

How strong it is? Is there any pre-trained data available? IIRC, Monte Carlo Tree Search with "dumber" heuristics than NNs yielded amateur dan level AIs for the first time (somewhere around 2006?). Lately there has also been some AIs that bolt a NN in, and get around 1 stone stronger (which is still miles away from AlphaGo!). But since this is specifically modelled after AlphaGo, I wonder how it fares against other AIs.

cr0sh 10y ago

Something I'm finding interesting is how so many of these deep-learning neural nets use RELU for their activation function; RELU is known as a "lazy engineer's activation" function - very simple to implement, and despite looking like a hack, seems to work very well for many tasks. I tend to wonder - beyond "ease of implementation and good 'nuff" reasons - if there are other reasons to use RELU, over other activation functions like TANH or Sigmoid? I'm beginning to suspect that we may be seeing the "engineering side" of neural networks coming into play; that instead of using the more "biologically accurate" activation of the sigmoid function, we instead use RELU (and other ELU derivatives) because it works well, and is easier to understand? Much like how things progressed better in heavier-than-air flight once engineers realized that flapping wings weren't absolutely needed, and low-weight engines turning propellers, with fixed wings, worked better for flying than what nature uses...?

xiphias 10y ago
What's interesting is that Jeff Dean noted that ReLU was one of the big things why deep learning took off. Wikipedia summarizes tha advantages, but my guess is getting rid of the vanishing gradients problem: https://en.m.wikipedia.org/wiki/Rectifier_%28neural_networks%29?wprov=sfla1 https://en.m.wikipedia.org/wiki/Rectifier_%28neural_networks...
- cr0sh 10y ago
  > Wikipedia summarizes tha advantages, but my guess is getting rid of the vanishing gradients problem Hmm - didn't think about that aspect, but that would be a big plus for backprop as I understand it! Thanks for the insight, and the link.
bbctol 10y ago
RELU is decidedly the more "biologically accurate" (or at least biologically inspired) compared to the sigmoid function. The idea put forth to originally justify RELUs was that neurons in the brain only have action potentials or lack thereof: the lowest level of activity a neuron can have is zero, and then you can ramp up frequency of action potentials from there, as opposed to the sigmoid's positive and negative symmetric curves. That said, a lot of the history of neural networks has been brief moments of biological inspiration followed by hacking and engineering that drifts further away from the biology the better it gets. The biggest example is backpropagation; despite how essential it's been to artificial neural networks, it really doesn't exist in the brain, at least not as simply as it does in code. For now, we're all still exploring, some looking towards biology, some towards abstract principles, and it remains to be seen if one provides consistently better results.
- cr0sh 10y ago
  > The biggest example is backpropagation; despite how essential it's been to artificial neural networks, it really doesn't exist in the brain, at least not as simply as it does in code. Do you have any links to papers or such explaining "at least not as simply as it does in code"? EDIT: nvm, I followed the links in a wikipedia article on RELU to relevant PDFs... For a while now this is one area I have been questioning - that we do use backprop, and maybe there is something to be learned from nature that might (?) simplify how a NN is trained (then again, nature might be doing it in such a way that is more complex than can be engineered or practical)... > For now, we're all still exploring, some looking towards biology, some towards abstract principles, and it remains to be seen if one provides consistently better results. It might end up being a combination; at least, that seems the direction so far to a point. I want to thank you for your comments, though. I'm still learning this stuff (I'm working thru the Udacity Self-Driving Car Engineer Nanodegree), and you've given me some stuff to think about and explore further.
  - bbctol 10y ago
    Honestly, the current state of neural backpropagation research is still in flux and papers will be pretty technical. My background's in neuroscience, and the rough summary of what we know so far is: action potentials can travel backwards down a neuron, and they probably do so in vivo, but we don't know if this actually does anything. There's no mechanism we understand for passing information backwards through a synapse. In fact, the only reason people suspect this might be important, and not just an accidental effect, is because backpropagation has been important in developing artificial neural networks. Getting inspiration from nature is often useful (convolutional neural networks are loosely inspired by the way information is processed down the optic nerve) but for the specifics of neuron function, the brain is almost certainly doing things that are more complex than is practical to simulate. The brain contains hundreds of billions of neurons, and each one is orders of magnitude more complex than a node in an ANN, interacting with local and distant neurons through all kinds of separate but interlocking electrical, chemical, and long-term genetic actions.
jimfleming 10y ago
The reasons to use ReLUs are sparsity and improved gradient flow. ReLUs encourage sparsity because when the input to the ReLU is less than 0 as the activation becomes 0. This means some fraction of activations in a given layer will be omitted which can encourage better representations. They also have improved gradient flow because the gradients are zero or constant and thus don't suffer from vanishing/exploding gradients. In deep learning, I would _generally_ not look towards biology for the reasons behind why things are done as this is usually an after-the-fact explanation. When in doubt, blame the gradients.
- ma2rten 10y ago
  LeakyReLUs work as well or better than ReLUs, so it can't be because of sparsity.
  - ekelsen 10y ago
    LeakyReLUs often have very small slopes on the negative side; this can help solve the problem of no gradients getting through a layer because the activations were all 0. But I would say it still has a sparsity effect on a trained network because of how small the slope usually is compared to one.
    - argonaut 10y ago
      That is not sparsity. In machine learning there is a very strong distinction between values that are exactly 0, and values that are close to zero (see: difference between L1 and L2 regularization).
      - ekelsen 10y ago
        L1 regularization does not lead to values that are _exactly_ 0 either.
        makeset 10y ago
        Yes, it does. You might have been thrown off by the fact that L1 regularization is not L0 regularization, i.e. it doesn't explicitly limit the number of nonzero coefficients. Still, the linearity of L1 constraint boundaries creates spikes in directions with zero components, thus forcing constrained solutions to occur where many variables are driven to exactly zero. See here: https://en.wikipedia.org/wiki/Lasso_(statistics)#Geometric_interpretation https://en.wikipedia.org/wiki/Lasso_(statistics)#Geometric_i...
sp332 10y ago
https://smerity.com/articles/2016/google_nmt_arch.html https://smerity.com/articles/2016/google_nmt_arch.html section "V6: Residuals are the new hotness". You can think of each layer (or I guess a pair of layers) as trying to correct errors in the previous layer. If the previous layer is close enough, the next layer can output 0. This is more stable than a straight linear activation, where one layer might move up a bit as the next one moves down to compensate! ReLU lets the earlier layer fine-tune itself without the effect being undone by later layers.
- cr0sh 10y ago
  Interesting! Thanks for the link!
deepnotderp 10y ago
Gradient flow due to chain rule is the reason. Also that last part is lecun a analogy ;
deleted 10y ago
[deleted]

tonetheman 10y ago

Super cool stuff

gcp 10y ago

This doesn't include the data set for the value network. This is critical, because producing that one requires implementing the full reinforcement learning. Even if you skip that and use the policy network, you still have the task of playing a few tens of million games. Learning a value network as big as AlphaGo from public data does not work: you overfit to hell. Which playout policy is this using? There doesn't seem to be any? Looks like it's just a neural network player. There's dozens of those already. You don't need to credit AlphaGo if you're only using policy networks for Go: The critical research for that was done at the University of Edinburgh.

AsyncAwait 10y ago

Sadly, it's not written in Go :-)

marvy 10y ago
To be fair, neither is AlphaGo :) But I admit that the pun is hard to resist.

brilee 10y ago

To give an update on status of project, I'm currently at the point where the policy net alone plays at 2-3kyu with a day or so of training. MCTS is implemented but Python is slow enough that I don't get significant Playouts. As a result I don't have insight into the scalability of my implementation. I'm currently working on code to play batches of games in parallel which should be of use both for RL and parallelized MCTS playouts.