Go has fallen to computer domination?

Discussion of anything and everything relating to chess playing software and machines.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Uri Blass
Posts: 8948
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: Go has fallen to computer domination?

Post by Uri Blass » Mon Feb 01, 2016 11:00 am

Laskos wrote:
matthewlai wrote:
Rein Halbersma wrote:
matthewlai wrote:
Rein Halbersma wrote:
matthewlai wrote:
Astatos wrote:So Matthew why you didn't manage to make Giraffe work?
Giraffe most certainly did work.
OK, so if you would feed the Giraffe NN-eval into a MCTS framework, would it scale to Stockfish-level peformance? (bridging around 1000 ELO IIRC).
Probably not. Chess and go are different problems that require different algorithms.
Then we have different definitions of "work". I think the question by Giorgos meant: "why didn't you manage to make Giraffe competitive with Stockfish?"

IIRC, the AlphaGo eval takes around 3ms to compute, which is about 3-4 orders of magnitude slower than a fast chess eval. An accurate eval is not enough, it needs to be fast enough as well.
Well, by "work" I meant play a reasonable game of chess. I didn't see any mentioning of Stockfish, and it seems strange to say that an engine only works if it's competitive with Stockfish. That obviously requires a lot more work than what can be done by 1 guy in 4 months, with a radically different approach, even if the approach is correct.
From human point of view, Giraffe and AlphaGo are comparable achievements. On a 4 core i7 Giraffe plays IM level Chess. On a similar 4 core i7 with 2 GPU, AlphaGo plays Go at very strong amateur level comparable to Chess IM. In both cases, on an i7 they are in the first several thousands players in strength among millions of casual players and many thousands dedicated players, and are just below the level of Chess GM and Go Pro. AlphaGo is probably a bigger achievement only because other approaches in Go don't work well.
How do you compare?
There are 1628 chess ployers in the world with fide rating 2450 or higher

How many go human players are better than AlphaGo on a 4 core i7?

Astatos
Posts: 18
Joined: Thu Apr 10, 2014 3:20 pm

Re: Go has fallen to computer domination?

Post by Astatos » Mon Feb 01, 2016 11:02 am

Giraffe project terminated because NN in Chess couldn't match conventional programming. There is no double meaning here. My question is whether a new approach similar to AlphaGo can make a comeback for chess programs as well and if not what are the differences apart of the different number of states for each square?

duncan
Posts: 12031
Joined: Mon Jul 07, 2008 8:50 pm

Re: Go has fallen to computer domination?

Post by duncan » Mon Feb 01, 2016 11:37 am

syzygy wrote:
bob wrote: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?
given the right time controls nearly any one can beat komodo
http://www.top-5000.nl/matches/1994.htm

During the Intel Grand Prix in London 1994 Kasparov was eliminated in the 1st round by Chess Genius, a computer program from the UK written by Richard Lang running on just a Pentium 166 Mhz.

Although the game was about speed chess (25m) a shock went through the chess world and it was news in all the mainstream media.

Uri Blass
Posts: 8948
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: Go has fallen to computer domination?

Post by Uri Blass » Mon Feb 01, 2016 11:49 am

bob wrote:
syzygy wrote:
bob wrote: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?
No, first was deep blue. Not counting blitz games. We were rolling GMs up and spitting them out in the early 80's at blitz...
First to beat the world champion include also blitz games and 25 minutes per game is fast time control but not blitz.

I believe Genius was the first to beat the world champion.

User avatar
Evert
Posts: 2929
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: Go has fallen to computer domination?

Post by Evert » Mon Feb 01, 2016 12:35 pm

Astatos wrote:Giraffe project terminated because NN in Chess couldn't match conventional programming. There is no double meaning here.
How the hell do you expect a new program, developed over 4 months and using new techniques, to do better than finely tuned conventional programs that have been in development for years?

matthewlai
Posts: 793
Joined: Sun Aug 03, 2014 2:48 am
Location: London, UK
Contact:

Re: Go has fallen to computer domination?

Post by matthewlai » Mon Feb 01, 2016 2:34 pm

Astatos wrote:Giraffe project terminated because NN in Chess couldn't match conventional programming. There is no double meaning here. My question is whether a new approach similar to AlphaGo can make a comeback for chess programs as well and if not what are the differences apart of the different number of states for each square?
I have explained the termination of the Giraffe project in another thread. And no, it wasn't because it couldn't match conventional programming.

I'm always open to the idea that someone else knows more about what I think than I do, though.
Disclosure: I work for DeepMind on the AlphaZero project, but everything I say here is personal opinion and does not reflect the views of DeepMind / Alphabet.

bob
Posts: 20923
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Go has fallen to computer domination?

Post by bob » Mon Feb 01, 2016 5:42 pm

Uri Blass wrote:
bob wrote:
syzygy wrote:
bob wrote: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?
No, first was deep blue. Not counting blitz games. We were rolling GMs up and spitting them out in the early 80's at blitz...
First to beat the world champion include also blitz games and 25 minutes per game is fast time control but not blitz.

I believe Genius was the first to beat the world champion.
Most only consider tournament time controls. As I said, GMs were falling to computers at blitz in the early 1980's. Korchnoi, Gutman (his second in the WCC cycle then, Ivanov, I'd have to look through old paper files to find out how many GMs fell to Cray Blitz back then. That had become the norm at blitz.

But not 40/2hr type games. Not until 1997. Not to mention 1 game vs a match either...

bob
Posts: 20923
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Go has fallen to computer domination?

Post by bob » Mon Feb 01, 2016 5:44 pm

Laskos wrote:
Rein Halbersma wrote:
Laskos wrote:
Rein Halbersma wrote:
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.

Image
Image
Image
Image
Image

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.
Is there empirical evidence concerning time scaling for monte-carlo players (such as go)? The 70+ elo for doubling is specifically derived based on existing chess programs using traditional alpha/beta, not MCTS.

User avatar
Laskos
Posts: 10949
Joined: Wed Jul 26, 2006 8:21 pm
Full name: Kai Laskos

Re: Go has fallen to computer domination?

Post by Laskos » Mon Feb 01, 2016 6:03 pm

Uri Blass wrote:
How do you compare?
There are 1628 chess ployers in the world with fide rating 2450 or higher

How many go human players are better than AlphaGo on a 4 core i7?
AFAIK there are some 1000-2000 true Pro Go players, and AlphaGo on 4 cores + 2 GPU is just below this level. Therefore Giraffe in Chess and AlphaGo in Go perform at similar human level on a home PC. It doesn't mean the task to build an AI of this level is of the same difficulty.

User avatar
Laskos
Posts: 10949
Joined: Wed Jul 26, 2006 8:21 pm
Full name: Kai Laskos

Re: Go has fallen to computer domination?

Post by Laskos » Mon Feb 01, 2016 6:11 pm

bob wrote:
Is there empirical evidence concerning time scaling for monte-carlo players (such as go)? The 70+ elo for doubling is specifically derived based on existing chess programs using traditional alpha/beta, not MCTS.
IIRC the scaling of MCTS Go bots like Crazy Stone is even better than with traditional Chess engines, almost linear to 16 or so cores, very good to 32. The gain from 1 to 32 cores (5 doublings) can exceed 500 ELO points in self-games. The strongly diminishing returns occur only with clusters of many machines. This is what I remember from reading some data.

Post Reply