Go has fallen to computer domination?

[Rein Halbersma]

The October '15 version had 40 search threads, 1202 CPUs and 176 GPUs at its disposal. For a company with Google's resources, this was merely a test run. With this much prestige on the line, expect one or even two orders of magnitude more computing power being thrown at the Lee Sedol match.

I don't know how MCTS scales, but those last couple of hundreds of ELO points should be well within reach. They must have done the math and concluded that they have a very good shot. Otherwise, even with Facebook with a competing project, why else would Google even consider doing the match so soon?

In fact what you say is plausible. The improvement from network and training alone are almost guaranteed to bring additional at least 100 Elo points. And looking at the scaling numbers, an order of magnitude hardware improvement another 200 Elo points. Basically, if they come with the same hardware, I would bet on Lee Sedol, if they come with 10x hardware the safer bet is on AlphaGo. Pretty amazing it would be, these super-pros were completely "untouchable" even by other good pros, never mind a funny amateur toy machine.

I looked at the rating vs resources tables in their appendix a bit, and with their current neural networks, just scaling resources for the MCTS alone won't get them beyond 3200 ELO. There are strong diminishing returns (1.6 times resources gives half the previous rating gain). They will need to learn significantly better networks (policy and value) and scale their resources to make those competitive in the MCTS.

[IanO]

I have to say I was very surprised by these news as most go players were. I remembered Zen became 6d on kgs just recently. But actually it happened 4 years ago already. Now a few days after the news of the alphago it got to 7d. So basically the surprise has a lot to do with the slowness of software improvement. Alphago just skipped a few levels.

The timing of this is most unfortunate! A month earlier, and Zen's achievement of a stable 7d rank on KGS would be a major event!

On the computer go mailing list, Hideki Kato gave us a few tidbits about Zen's strength advance:

It took
almost 4 years from 6d to 7d. One good thing is that Zen19X is
running on not a clsuter but just a dual-Xeon (2 x 12 core)
server.

This version uses DCNN (Yamato's original implementation),
which improves the plays in early stages a lot (maybe better
global evaluation than the use of B-T model due to the aparture
size?) and lets Zen play sicker and less offensive (better
compensation of the bias of MoGo-type local-priortized
simulations?).

This version beats the previous with 80% and is improved more
than 200 Elo on CGOS.
http://www.yss-aya.com/cgos/19x19/bayes.html
where the new version is Zen-10.8-1c (3306) and the previous is
Zen-1c-2.8G (3078; ver. 10.4). Either uses one core of an i7
5960X. *Zen-10.8-2c (3505) uses two cores and gets 200 more
Elo.

*The version run on KGS is 10.9 which has the number of handcap
stones in the input layer but looks almost no effects .

Some explanation for those who normally follow computer chess rating lists. The computer go server (CGOS) is just an online go server that computer go authors can join to play automated matches with other programs. Thus, the hardware used is under control of the authors. The hardware and program versions are quite diverse compared to the uniform platforms used in the major computer chess rating lists. As far as I can tell, computer go has no rating list equivalent to those in computer chess, making it difficult to compare and track progress.

On the other hand, up to now computer go is still under the level of top amateur dans, so go program ranks on go servers like KGS are a legitimate strength measure (albeit very low resolution).

[bob]

This is likely a "I hope to be first" gamble. Nobody remembers the second computer to beat the world champion, only the first. I remain skeptical of this stuff, however, but we will see.

sceptical that the computer will win, ? or on the whole point of doing man vs computer?

That the NN approach will work as well as expected, particularly for chess where the number of patterns is huge since the game is so different from go where squares only have 3 states.

[duncan]

This is likely a "I hope to be first" gamble. Nobody remembers the second computer to beat the world champion, only the first. I remain skeptical of this stuff, however, but we will see.

sceptical that the computer will win, ? or on the whole point of doing man vs computer?

That the NN approach will work as well as expected, particularly for chess where the number of patterns is huge since the game is so different from go where squares only have 3 states.

the number of positions in chess is I think about 10 ^43. any estimate about number of patterns ?

[syzygy]

Nobody remembers the second computer to beat the world champion, only the first. I remain skeptical of this stuff, however, but we will see.

First was Genius. Second was Deep something, right?

[Laskos]

The October '15 version had 40 search threads, 1202 CPUs and 176 GPUs at its disposal. For a company with Google's resources, this was merely a test run. With this much prestige on the line, expect one or even two orders of magnitude more computing power being thrown at the Lee Sedol match.

I don't know how MCTS scales, but those last couple of hundreds of ELO points should be well within reach. They must have done the math and concluded that they have a very good shot. Otherwise, even with Facebook with a competing project, why else would Google even consider doing the match so soon?

In fact what you say is plausible. The improvement from network and training alone are almost guaranteed to bring additional at least 100 Elo points. And looking at the scaling numbers, an order of magnitude hardware improvement another 200 Elo points. Basically, if they come with the same hardware, I would bet on Lee Sedol, if they come with 10x hardware the safer bet is on AlphaGo. Pretty amazing it would be, these super-pros were completely "untouchable" even by other good pros, never mind a funny amateur toy machine.

I looked at the rating vs resources tables in their appendix a bit, and with their current neural networks, just scaling resources for the MCTS alone won't get them beyond 3200 ELO. There are strong diminishing returns (1.6 times resources gives half the previous rating gain). They will need to learn significantly better networks (policy and value) and scale their resources to make those competitive in the MCTS.

That speed-up at the last factor of 1.6 is probably marred by error margins, I would take the large span of the last 764 -> 1920 CPU cores (~2.5 factor) as reference, which brings 89 Elo points. The estimate to 10 fold more CPU would give at least 150 Elo points, and they might improve on that.

Being very weak at Go, I tried to rely on Crazy Stone analysis for the 5 official games. It's very rough, as Crazy Stone is 1000 Elo points weaker than both players, but from my experience in chess, even a weak engine often gives reasonable evals of games between much stronger opponents. Here is the evolution of each game from black point of view. The eval shown is the percentage black has to win.







The first thing which strikes compared to many other analyses I saw is that AlphaGo seems systematically outplaying Fan Hui. Only in some openings-early midgame Fan Hui managed to do some fighting back, but in the second part of the games AlphaGo seems really a wall. This somehow confirms some pros who say the bot is very strong later in the game.

[bob]

This is likely a "I hope to be first" gamble. Nobody remembers the second computer to beat the world champion, only the first. I remain skeptical of this stuff, however, but we will see.

sceptical that the computer will win, ? or on the whole point of doing man vs computer?

That the NN approach will work as well as expected, particularly for chess where the number of patterns is huge since the game is so different from go where squares only have 3 states.

the number of positions in chess is I think about 10 ^43. any estimate about number of patterns ?

Not a clue. The problem is that with chess, the state space is really large since each square can be one of 13 values. IE roughly 13 ^ 64 possibilities. In go the action is all about clusters of stones, while in chess, pieces don't have to be clustered to work together.

I'm hardly a NN expert, but we did do a research project here quite a few years ago dealing with target tracking. IE trying to take successive RADAR sweeps and figure out which objects on each of the two sweeps match. Not so easy when one can occlude another, speeds can change between sweeps, it was a computationally challenging problem and we had a couple here interested in using ANNs to see if it could be solved. Final answer was "way too slow" and "needs an infinite amount of training"...

It might well work for chess, but as I said, I remain skeptical. Be interesting to see how this works for go, when this match happens. I remember the days of "Deep Blue has solved chess" hysteria, now we know it wasn't even close.

[matthewlai]

This is likely a "I hope to be first" gamble. Nobody remembers the second computer to beat the world champion, only the first. I remain skeptical of this stuff, however, but we will see.

sceptical that the computer will win, ? or on the whole point of doing man vs computer?

That the NN approach will work as well as expected, particularly for chess where the number of patterns is huge since the game is so different from go where squares only have 3 states.

the number of positions in chess is I think about 10 ^43. any estimate about number of patterns ?

Not a clue. The problem is that with chess, the state space is really large since each square can be one of 13 values. IE roughly 13 ^ 64 possibilities. In go the action is all about clusters of stones, while in chess, pieces don't have to be clustered to work together.

I'm hardly a NN expert, but we did do a research project here quite a few years ago dealing with target tracking. IE trying to take successive RADAR sweeps and figure out which objects on each of the two sweeps match. Not so easy when one can occlude another, speeds can change between sweeps, it was a computationally challenging problem and we had a couple here interested in using ANNs to see if it could be solved. Final answer was "way too slow" and "needs an infinite amount of training"...

It might well work for chess, but as I said, I remain skeptical. Be interesting to see how this works for go, when this match happens. I remember the days of "Deep Blue has solved chess" hysteria, now we know it wasn't even close.

Size of the input space is not a problem. 13^64 is many orders of magnitude smaller than most problems we work on with neural nets (eg. HD videos).

Complexity of the mapping between input and output space is. I am not convinced that that's more complex in chess than it is in go.

ANNs can be very fast nowadays on GPUs, when designed by machine learning experts. Many non-ML people try ANNs and discount them for being slow/inaccurate, when it's really the design of the network that is sub-optimal. When you have sub-optimal input representation for example, you'll need a much larger network to disentangle the inputs, and that would require a lot more training and a lot more computational power.

Unfortunately, contrarily to popular beliefs, we are still not at a stage where we can just feed anything to a general ANN and expect good result and good performance. There would be no need for machine learning people otherwise!

Machine learning has also been probably the fastest developing field in the past few years. There has been a few big breakthrough papers published every year for the past few years, and then there are also many really cool things behind closed doors. State of the art ANNs nowadays are nothing like ANNs of early 2010s.

[Astatos]

So Matthew why you didn't manage to make Giraffe work?

[matthewlai]

So Matthew why you didn't manage to make Giraffe work?

Giraffe most certainly did work.