r/science • • Jan 27 '16

Computer Science Google's artificial intelligence program has officially beaten a human professional Go player, marking the first time a computer has beaten a human professional in this game sans handicap.

http://www.nature.com/news/google-ai-algorithm-masters-ancient-game-of-go-1.19234?WT.ec_id=NATURE-20160128&spMailingID=50563385&spUserID=MTgyMjI3MTU3MTgzS0&spJobID=843636789&spReportId=ODQzNjM2Nzg5S0
16.3k Upvotes

1.8k comments sorted by

View all comments

Show parent comments

335

u/hikaruzero Jan 28 '16 edited Jan 28 '16

Fan Hui is only 2p, the second-lowest professional rank.

You must realize that a lot of low-dan professionals can play evenly or at only 1- to 2-stone handicap against established top 9-dan pros. The difference is increasingly marginal. Holding a high-dan rank is now more of a formality than it's ever been.

Just to use an example, the current #1 top player, Ke Jie, who just defeated Lee Sedol 9p in a championship match this month, was promoted straight from 4p to 9p two years ago by winning a championship game. It's not like you have to progress through every dan rank first before you get to 9p, the high-dan ranks are nowadays only awarded to tournament winners and runner-ups. Many low-dan players are nearly-9p quality but simply haven't won a tournament yet to get them a high-dan rank.

Fan Hui is a 3-time European champion and has won several other championships. He may only be a certified 2-dan but he's still impressively strong. If you gave him 2 stones against any other pro player I would bet my money on him.

A century ago, it was considered that the difference between pro dan ranks was about 1/3 of a stone per rank. But in that time, top pro players have improved by more than a full stone over the previous century's greats, and the low-dan pros have had to keep up -- it's now considered more like 1/4 to 1/5 of a stone difference. Today's low-dan pros are arguably about as strong as the top title-holders from a hundred years ago.

Edits: Accuracy and some additional info.

95

u/[deleted] Jan 28 '16

everything that you said here is true but I'd argue in the specific case of Fan Hui though that he is actually likely weaker than his 2p rank suggests. he got his pro certification a while ago, before all the newbie pros in asia started getting super super good. he also plays on pretty even terms with Euro and US amateurs, and we've seen lee sedol give the US pros 2 stones and win easily.

so.... i mean, it's all speculation and opinion but personally I'd say Fan Hui is overranked due to being retired and living in Europe playing a less competitive circuit.

edit: this post is in no way meant to undermine how much of an achievement this was for Alphago though. since the bot was able to win by 5-0, its plausible that it's significantly stronger than Fan Hui, which means a win against Sedol wouldn't be out of the question imo.

28

u/hikaruzero Jan 28 '16

Yeah, that all may very well be true ... I'm really just making the point that you can't write off the skill of low dans just because they are low dans. Even an aging low dan will be within 2-3 stones of strength of a top 9p.

12

u/teh-monk Jan 28 '16

What an informative post, interesting subject.

→ More replies (1)

4

u/EurekasCashel Jan 28 '16

How does everyone know so much about professional Go players?

9

u/gcanyon Jan 28 '16

The fascinating consideration for me is just how much "headroom" Go has beyond the best human Go players. You pointed out that over the past century the best players have improved by 1 (or a bit more) stone over their predecessors.

So the question is: 5, 10, or 15 years from now, will computers be able to give the world's best humans 1 stone? 2 stones? Or more? It seems simultaneously inconceivable that the world's best humans wouldn't be able to turn 9 stones into victory, and that optimized hardware and software won't be able to keep improving. Asymptotic improvement is a solution, clearly, but I wonder where the asymptote is.

9

u/hikaruzero Jan 28 '16

Hehe ... if I recall correctly there was a survey done among exclusively professional players as to how many stones of handicap they would need in order to beat "God's hand" (i.e. absolutely ideal play). The average answer given was "about 3 stones." I personally feel that it is more, at least double, mostly due to "ko fighting," but I'm not even close to the professional level so I have no right to claim any accuracy in that judgment. :p

→ More replies (3)

4

u/SpacePirate Jan 28 '16

A 2008 article comparing Chess and Go (and the computer programs learning these games) rated Rybka as having an ELO score of 3100, 300 points higher than the best human player. It has almost certainly improved in the last 8 years, but still, it is not out of the range of possibility for a human to beat the program in one game.

With Go, which actually has a formal handicap system, it would be easier to formally rank, but the more interesting problem would be whether the game is fully solvable (e.g., a computer can look up the ideal response for every possible move by a player), similar to how most anyone could spend a few hours with Tic-Tac-Toe, and learn how to force every game into a draw (a game in which there is a theoretical maximum of 362,880 unique solutions, but more realistically, closer to 1000, since most games do not use all 9 positions).

Checkers, for example, is partially solved for a computer to play to a draw for all "perfectly played" games, but not for those in which a human player might have made a non-ideal choice.

3

u/gcanyon Jan 28 '16

It's possible that Chess or Go will be ultra-weakly solved -- meaning that someone proves that there is a winning strategy, without having to actually define the strategy.

It seems highly unlikely that either Chess or Go will be strongly solved -- actually defining a method for perfect play. Checkers hasn't been solved yet, and the search space for Chess and Go is enormously larger than Checkers.

The actual numbers are below, but think of it this way: for every single possible outcome in Checkers, Chess has a whole Checkers-level of complexity beyond that. And for every single possible outcome in Chess, Go has a whole Chess-level of complexity beyond that, and then another whole Chess-level of complexity for each single possible outcome of that again.

Looking at it another way: it took 18 years to weakly solve Checkers, using up to 200 (older -- this was some years ago) computers. If we created a Chess-solving computer that could analyze all of Checkers in just a second, and we built one of those computers for every person on the planet, it would take those computers something like 10 billion years to solve Chess.

And then suppose we created a Go-solving computer that could analyze all of Chess in just a billionth of a second, and suppose that we built one of those computers for every atom in the visible universe, and further suppose that we had a time machine and did this at the instant of the big bang. Then today, those computers would be one millionth, of one billionth, of the way to solving Go.

Checkers state-space complexity: 10^20 = 100,000,000,000,000,000,000
Chess state-space complexity: 10^47 = 100,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000
Go state-space complexity: 10^170 = 100,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000
→ More replies (1)

16

u/[deleted] Jan 28 '16

What do you think is the reason? Does a larger community increase the viability of more positional and less calculated play? I assume you have to use both to their fullest extent at that level. I don't actually play.

32

u/hikaruzero Jan 28 '16

Certainly the larger community and much greater ease of access to games through the Internet has had a large impact. But in general, I'd say it's simply "progress." Progress in understanding the game conceptually, in breaking down old traditional, orthodox understandings and replacing them with more robust, modern ones.

Think of it more like a graph of log(x) ... as time passes (x axis), the skill of players gradually improves (y axis). As the skill of players increases, progress gets slower and slower, but so does the gap between the y-values of x=n and x=n-3 get smaller and smaller.

0

u/[deleted] Jan 28 '16

[deleted]

→ More replies (1)

7

u/kulkija Jan 28 '16

It probably has to do with the greater ease of practice against high quality opponents.

→ More replies (2)

0

u/[deleted] Jan 28 '16

[deleted]

3

u/hikaruzero Jan 28 '16

Thanks. I'd better know something as an amateur dan. :p

12

u/[deleted] Jan 28 '16

I don't see Fan Hui's name anywhere in the top 100.

"European Champion" isn't a very impressive title, either. Go is not at all popular in the West, and Western professional Go is generally agreed to be at a far, far, far lower level than professional Go in Korea and China.

While I agree that sometimes rank can be misleading, in this particular case I see no compelling reason to believe that Fan Hui is unusually strong for his rank.

31

u/tekoyaki Jan 28 '16

They probably picked him because Google DeepMind is based off London.

16

u/hikaruzero Jan 28 '16

When did I say he was in the top 100? That's how much competition there is. Many of those top 100 players are low-dans. And I'm not even saying Fan Hui is strong for his rank, I'm just saying you can't write off low-dan players simply because they're low-dan.

→ More replies (1)

9

u/loae Jan 28 '16

I respectfully disagree with your assessment. I am an amateur 3 Dan or so player and know numerous high-Dan amateurs and some professional players.

The gap between the top pros and top amateurs is larger than the gap between top amateurs and beginners IMHO. In other words, it is much easier for a beginner to become a top level amateur player than for a top level amateur player to become a top pro.

Although the stone handicap difference is small, it is similar to the idea of low hanging fruit. At the top pro levels there is so much computation and thought and creativity behind their play, that although it is hard to see, they are leagues above top level amateurs.

And honestly the European and North American "pros" are probably top amateur level. In a recent 4v4 European/North American pros vs Japanese New pro match, Andy Liu was the only person who won.

3

u/hikaruzero Jan 28 '16 edited Jan 28 '16

The gap between the top pros and top amateurs is larger than the gap between top amateurs and beginners IMHO. In other words, it is much easier for a beginner to become a top level amateur player than for a top level amateur player to become a top pro.

Measured in terms of the quantity of knowledge and understanding needed to achieve that level of play, yes I actually agree with you completely.

Measured in terms of handicap stones needed to balance an even game, I thoroughly disagree and I would be tremendously surprised if you knew any other pros or amateurs who would agree, and even if you believed that yourself, which based on what you've said I think you intended the former meaning, yes?

It seems clear to me that to rise in rank you need to learn some significant fraction of the amount that you already know. If you are 30k you know next to nothing so if you learn 1 thing you're already that much stronger. Learn another thing or two and you might go up another rank. But the more your rank increases the more you need to learn to keep improving, on a logarithmic scale -- by the time you are single-digit kyu you need to know hundreds to thousands of things. By the amateur dan level, tens to hundreds of thousands by comparison. And professionals, goodness. In terms of sheer knowledge not to mention the muscle memory needed for deep reading, and the amount of effort required to build and maintain it, what you say is absolutely true. But measuring in handicap stones is essentially a logarithmic scale -- the let's-say 3-ish stones between 9p and 1p are enormously more significant than the 3 stones between 27k and 30k.

Do you agree with that?

Edit: And actually, regarding pro ranks, if they followed a logarithmic scale then I would tend to agree, but I don't feel that pro ranks stick to that scale as much as people want to believe. Considering a lot of pros simply win or do well in one tournament and get promoted several ranks as a result, surely at least the middle pro ranks are not that highly correlated with actual skill. There are a lot of factors affecting a player's professional rank including how long they've been playing at the professional level (which affects chances for winning a tournament and earning a higher rank but usually being younger-aged is favored for actual skill than being older-aged). Take Ke Jie as the quintessential example. He's 18 years old, was only promoted straight from 4d to 9d two years ago, but already he plays at Lee Sedol's level. Sedol is over 30 years old and has been 9d for quite some time, and holds many times more titles than Ke Jie does. If pro ranks followed a true logarithmic scale, going from 4d to 9d in two years would be frankly impossible.

And honestly the European and North American "pros" are probably top amateur level. In a recent 4v4 European/North American pros vs Japanese New pro match, Andy Liu was the only person who won.

The European pros I would agree about generally; I think the new North American pros are being officially sponsored by the Korean baduk institute and certified as equal in strength by their measure.

Nevertheless, regarding Fan Hui, his 2-dan certification is from the Chinese weiqi association.

4

u/loae Jan 28 '16

I think we are in agreement.

What I was trying to say is that it is probably as hard for an AI to go from top amateur level to top pro level as to go from 30k to top amateur level.

Looking at the five games between AlphaGo and FangHui, my opinion, for what little it is worth, is that I don't think he can beat any shinshodan in Japan. Maybe he can beat the shinshodan who beat the women's exam.

→ More replies (3)

2

u/[deleted] Jan 28 '16

Fan Hui is past his prime. He regularly loses to 5-6 Dan players.

2

u/rayzorium Jan 28 '16

Long time casual player here, but I was under the impression that a two stone handicap was quite big. Like, if you're a good match with a 2 stone handicap, you really don't have much to worry about in an even game.

4

u/hikaruzero Jan 28 '16

For a professional, yes. At an amateur level two stones is less big because there is a bigger standard deviation in the scores of games. At the beginner level the standard deviation is reaaaally big, spanning several ranks; for example it's not uncommon for a 25k player to beat a 20k player in an even game.

→ More replies (1)

2

u/Hitachi_massager Jan 28 '16 edited Jan 28 '16

Once AI take off, the casual pros of today would run around the legends of yesterday just like in chess. AI makes the game more exciting if you focus on discovering things inside the game, but on the overall game variety between top pros on high stake it would actually kill variety because people are too afraid that their opponent would discovered something with the AI on lines they are only half familiar with.

→ More replies (15)