Google's AlphaGo defeats Fan Hui 2p, 19x19, no handi, 5-0

[Mike Novack]

Also didn't see much mention that 5 informal games were played at the same time and the record for that was 3-2 in favor of alphago.
The informal games had 3 x30 byo-yomi time control. So when time gets tight it starts to struggle a bit.

This merits discussion. Unlike us, a machine isn't in "absolute time". In other words, if it has more computing crunch, effectively time slows down (a Turing machine can compute anything computable, but it would be doing it VERY slowly).

Now the actual machine being used here has a vast amount of crunch power compared to our home machine, huge even compared to the larger machines being used in the computer go tournaments. The result that it does worse compared to the human when at faster time controls implies that it NEEDS that much crunch to play at the pro level.

So I would NOT expect this breakthrough to affect go programs on our home machines any time soon (if ever). Current development on our small machines is for using less power while retaining adequate crunch to get the job done (the jobs that they are asked to do). Not toward developing more crunch, since so few users have any use for more crunch power. Remember, it's not just a matter of needing more battery capacity (and so weight) if the device uses more power but the problem of dissipating that much waste heat from a small device.

[Pippen]

Five minute simplified explanation of neural networks and why you would use GPUs for them:

Neural networks can be visualized as a graph consisting of nodes and edges (connections between nodes). The nodes are some sort of mathematical function like f(x)=m*x+b. That node would have three input edges (x, m and b) it and one output edge. The inputs and outputs are connected to other nodes or can be inputs/outputs to things outside the network.

A neural net will consist of many nodes arranged in interconnected layers. For example, part of a neural net for a go playing program might be a 19x19 grid of nodes, each with an input representing a point on a go board (0, 1 and 2 for empty, black and white). Those 361 nodes performing a mathematical function on individual numeric inputs can also be represented as a single node performing the same function on a 19x19 matrix.

So, actual neural network programs boil down to massive amounts of math on vectors, matrices and higher-dimensional arrays of numbers called tensors. Video games graphics is also a bunch of linear algebra and math on vectors and matrices. And we already have commodity specialized processors (GPUs) for doing exactly that, and they're many times more efficient at it than traditional CPUs.

What I do not understand: If there is a neural network then there is huge complexity of wires and firings, but someone has to make sure that this network has to produce a specific result in return, e.g. a good Go move. Can one conceptulize such a network or do they just play around with networks trial-and-error-wise?

[hyperpape]

So I would NOT expect this breakthrough to affect go programs on our home machines any time soon (if ever). Current development on our small machines is for using less power while retaining adequate crunch to get the job done (the jobs that they are asked to do). Not toward developing more crunch, since so few users have any use for more crunch power. Remember, it's not just a matter of needing more battery capacity (and so weight) if the device uses more power but the problem of dissipating that much waste heat from a small device.

They said that a non distributed version of the program can beat Crazy Stone, Zen and one other program quite reliably (https://news.ycombinator.com/item?id=10982973). Of course, the non-distributed version is still a beefy server class machine, but that's also true of how the strongest versions of those programs have run.

[qianyilong]

So I would NOT expect this breakthrough to affect go programs on our home machines any time soon (if ever). Current development on our small machines is for using less power while retaining adequate crunch to get the job done (the jobs that they are asked to do). Not toward developing more crunch, since so few users have any use for more crunch power. Remember, it's not just a matter of needing more battery capacity (and so weight) if the device uses more power but the problem of dissipating that much waste heat from a small device.

They did mention however a scaled down version. The full version does a mix of rollouts and a neural network that estimates the value of each move but running just the value network without the rollouts they were estimating at amateur 5d with a 15,000 factor decrease in computation time. So it most definitely will affect our local computers. That version might even manage to make it on our mobile devices. Neural networks are blazing fast to evaluate but slow to train(in the paper I believe that the value network was trained using 50 GPUs for a week) but once trained(which only needs to happen once) it could be shipped elsewhere and definitely run with very few resources.

Edited:misread their graph 5 dan not 5-7. in particular page 11 of the paper for the graph in question.

[uPWarrior]

What I do not understand: If there is a neural network then there is huge complexity of wires and firings, but someone has to make sure that this network has to produce a specific result in return, e.g. a good Go move. Can one conceptualize such a network or do they just play around with networks trial-and-error-wise?

That is what "training" a network is all about. You need to learn the correct weights for your "wires", so that your nodes only fire when the right inputs are present.

There are many ways in which this can be done, hence the use of pro databases or self-playing. Deep learning has quite some black magic going on, in the sense that many things are done by experience rather than by mathematical rigor. Also, there are many kinds of artificial neural networks and I haven't read the paper so I don't know which one they used. This explanation is just how simple feed-forward networks (i.e. no cycles) with back-propagation work, but hopefully it gives you an idea of the possibilities.

Lets pretend that you have a network which has not been trained at all.
You start by showing it a game position, encoding the game state in whatever way you want at the input layer. This is done, maybe, by having one node (i.e. neuron) for each of the 361 positions of the board and giving each one a signal along an edge (synapse, wire, whatever you want to call it) connected to it representing whether it has a black stone, a white stone, or whether it is empty. You then look at the output layer to see whatever random thing this untrained network outputed as result.
The trick is: you have the "right" answer because you know which move was played in the real game. Therefore, you can slowly adjust the weights of all the wires connected to your output layer so that your output layer is closer to the answer you want, and similarly for all the layers before the output layer, all the way until you reach the input layer. Imagine doing this for 300 million positions in high-dan KGS or pro games and, once again hopefully, the network will start imitating this moves. The network is not big enough to "memorize" all the positions and corresponding outputs (this is what we usually call overfiting), so in order to give the correct answers, the network will have to have identified whatever these positions that output the same move have in common.

There are many ways in which self-playing could also lead to improvement. For instance, a naive way would be to slightly perturb the weights of the current network and then make both versions play many games against each other. Whichever network wins could be further refined.

[Bill Spight]

Perhaps they bought the BiGo database which already has loads of KGS games.
http://bigo.baduk.org/assistant_databases.html

I'm sure a company owned by Google gets access to things it wants to get access to.

They probably already had all the SGF files in a basement inside Area 51.

[Elom]

Google's AlphaGo defeats Fan Hui 2p, 19x19,

Wow, that's impressive. I wonder what the handi is...

5-0

Okay, I understand how it could make news, but I'm not so sure it's quite the level google were hoping for or anything especially new...

Oh, wait

*read thrice*...

Even so, I don't think it's quite the simple thing to jump to the level of a Top active Professional yet. While I understand that it has been commented that white was clearly stronger (in those games), indicating that white is well above a 1p level, you can be clearly above 1p level and clearly below top pro level. Therefore, Alpha go can be at any pro level, and as the programmers themselves cannot simply look at the games and conclude, it seems to be a matter of probability on their part? While I seem to get the impression a few of the team believe they have come so tantalisingly close to finally surpassing Go, I wouldn't be so confident as to be disappointed with losing to Lee 9p.

[fwiffo]

If you're interested in how neural networks work, the tutorials for Tensorflow are actually pretty accessible for anyone with basic programming skill (they are in Python).

I don't know the details about what tools Deepmind used here, but Tensorflow is used by machine learning teams at Google.

[DrStraw]

They probably already had all the SGF files in a basement inside Area 51.

Pretty soon they may have all the POSSIBLE sgf files in their basement.

[DrStraw]

What I do not understand: If there is a neural network then there is huge complexity of wires and firings, but someone has to make sure that this network has to produce a specific result in return, e.g. a good Go move. Can one conceptulize such a network or do they just play around with networks trial-and-error-wise?

A very, very simple analogy:

A baby is born with no knowledge of the world around it. Initially it actions are random. But it gets a positive response from crying when it is hungry, in the form of food. So the crying mechanism gets reinforced. Next time it is hungry it is more likely to cry than to not cry.

[Pippen]

Ok, some dummy questions:

1. When we speak about neural networks, do we speak about hardware (neural network-like wires) or software that simulates those networks on a normal computer with v. Neumann architecture?
2. If somebody develops a normal computer chip he basically has to go to the drawboard first and draw all the NAND, NOR,...-gates to make sure that some input gets some output he wishes and never some input breaks the machine down. Is this the same approach with neural networks, just that all those gates are more dependant from each other and need more calibration to function smoothly in comparison to a normal architecture where everything functions straightforward right from the beginning?

[uPWarrior]

Ok, some dummy questions:

1. When we speak about neural networks, do we speak about hardware (neural network-like wires) or software that simulates those networks on a normal computer with v. Neumann architecture?
2. If somebody develops a normal computer chip he basically has to go to the drawboard first and draw all the NAND, NOR,...-gates to make sure that some input gets some output he wishes and never some input breaks the machine down. Is this the same approach with neural networks, just that all those gates are more dependant from each other and need more calibration to function smoothly in comparison to a normal architecture where everything functions straightforward right from the beginning?

Artificial neural networks are only software.

In your brain, there are synapses that allow a neuron to pass a signal to a different neuron. These are created during your life, but particularly during brain development. A neuron "fires" when it receives a sufficiently strong signals from neurons connected to it.

An artificial neural network tries to emulate this behavior, but it is only software. Instead of creating synapses, we usually model that through a weight between two neurons - "a strong weight corresponds to a strong synapse".
Therefore, the structure (i.e. neurons) itself is not enough - you also need to know how strongly they are connected. This is what the training part tries to figure out.

[emeraldemon]

Here is what An Younggil 8p says about AlphaGo at the end of his review:

White's play in the second half of the game was excellent, and I couldn't find any serious mistakes from White.

AlphaGo's style seems to be slightly territorial, but well balanced. It's good at haengma and tesuji, but its play is not yet perfect.

As we can see, it made several questionable moves and mistakes, but its play in the second half of the game was much more accurate and refined than the in the first.

AlphaGo's games throughout this match were very impressive, and I never expected that a computer Go program could play such strong and smooth moves.

It's so surprising and shocking, and I look forward to watching the match between Lee Sedol 9p and AlphaGo in March 2016.

When AlphaGo faces Lee, we will be able to see more clearly just how strong it is, and how much it has improved since October 2015 (when this game was played).

[emeraldemon]

It's interesting to me that An Younggil says AlphaGo is strongest in the second half of the game. Maybe we will see games where Lee Sedol takes a lead early from strong opening, but then AlphaGo tries to claw its way back.

[Cassandra]

I remember some comments by Ôhashi Hirofumi 6p on professional (tournament) games that had an "unusual", centre-oriented opening.

It seemed to me that -- after 60 to 80 moves or so -- the position reached cannot be clearly distinguished from a position that derives from "normal" opening play (with the exception of one or two seemingly "misplaced" stones).

This would imply that there will be much more similar (may be partial) positions to learn from in "later" stages of the games than during the opening stage, when the board is relative empty.