Computer beating top human Go professional

by Frederic Friedel
3/10/2016 – Remember how in 1997 World Champion Garry Kasparov lost a match to IMB's Deep Blue? That was a watershed moment in computer history, but Artificial Intelligence has one last insurmountable barrier to cross: beat the best players in the world at the ancient Chinese game of Go. Played on a 19x19 grid the task seemed impossible – until today, when a five-game match has begun in Seoul, Korea. Watch it live.
YOUR PERSONAL CHESS COACH - Whether you’re taking your first steps into the world of club chess, or already playing at a tournament level: with FRITZ, you can train more efficiently, intelligently and with a more personalised approach than ever before.
FRITZ is more than just a chess engine – it’s a training revolution! Whether you’re taking your first steps into the world of club chess, or already playing at a tournament level: with FRITZ, you can train more efficiently, intelligently and with a more personalised approach than ever before.

Lee Sedol vs AlphaGo in Seoul

On Wednesday Lee Sedol, a 33-year-old master of the ancient Asian board game Go, sat down in the South Korean capital, Seoul, a five games against a computer. His opponent is Alphago, a program built by the Google subsidiary DeepMind. Lee, who has been a Go professional for 21 years, is currently ranked among the top three players in the world.

AlphaGo is a computer program developed by Google DeepMind, using a combination of machine learning and tree search techniques, combined with extensive training, both from human and computer play. This Nature paper, published in January 2016, describes the technical details behind a new approach to computer Go – one that combines Monte-Carlo tree search with deep neural networks, trained by supervised learning from human expert games, and by reinforcement learning from games of self-play. We will be providing more details in the near future.

In October 2015 AlphaGo became the first computer program to beat a professional Go player by winning 5-0 against three-times European Champion Fan Hui (2-dan pro).

Listen to Demis Hassabis, CEO of Google’s DeepMind, explain the background of this AI enterprise

The author of this report has known Demis for a long time – here's a small extract from a very readable report on the match in The Guardian:

What impact would a DeepMind victory have?

The chess world has had two decades to live with the fallout of Deep Blue’s victory over Kasparov. But Frederic Friedel, a computer chess pioneer and the founder of the news site ChessBase, argues that it’s possible to overstate the effect the victory had. “AlphaGo winning won’t change the world of Go. It’s like you’ve built a bicycle or a car that can go faster than Usain Bolt, and you say: ‘Look at how fast it is!,” does this mean the world ends for athletics? No, it doesn’t.”

Friedel, who first met Hassabis as “a cocky little kid who came for a dinner with Gary [Kasparov] and myself in London, and told us about some software he was developing”, does have a warning for Go players, though. “The advent of bicycles and motorbikes did not make athletes give up in despair: they just went on racing each other without these machines. But there is a grave difference to the chess analogy: a 200-metre runner cannot secretly use the assistance of a bicycle, but a chess player can most certainly get his moves surreptitiously from a computer.

“Cheating in chess is becoming a serious problem, and it will become more acute as technology progresses. That will change the game dramatically – not the fact that computers are stronger than humans.”

You may also want to listen to a radio interview the BBC World Service conducted with Friedel, which contains some provocative thoughts on artificial general intelligence (AGI). If you think Frederic's view are completely outlandish listen to Sam Harris on the subject (starting at 8:50 min).

The match in Seoul

A virtual encounter between Lee Se-dol and Demis Hassabis before the match [photo Yonhap/EPA]

Here is the schedule for the next four games – join the 1.5 million spectators that watched game one on YouTube. The $1 million dollar five-game challenge match is being staged in Seoul. Match commentary by Michael Redmond (9-dan pro) and Chris Garlock.

As we go into print – well, into HTML – AlphaGo has just won the second game, bringing the total score to 2-0 for the computer. The third game is on Saturday and well worth watching – listening to the commentators actually teaches you a lot about the game

Early comments

As mentioned above this is not the last you will be hearing about AlphaGo and DeepMind on our news page. But here are some quick reactions from two experts: first from Ken Thompson, who in the late 1970s and early 1980s built the first hardware chess machine, Belle, that won the computer chess world championship and became the first master-level machine in 1983. Ken, who abhors capitalisation and apostrophes like nature a vacuum, said: "i am very impressed. i didnt think it would happen in my lifetime."

John Nunn, on the other hand, wrote us: "I suspect that the 'hard for computers to master Go' thing is a bit of a myth. If the same effort had been put into computer Go as was put into chess, they would probably have reached this point a long time ago."

Tell us what you think. If you need more information visit the AlphaGo page on Google DeepMind – or consult these recent press stories on the match (you don't need to read all 13,000 of them). Finally this is where to watch the next three games of the match live on YouTube.

Topics: DeepMind, Go, Google
Editor-in-Chief emeritus of the ChessBase News page. Studied Philosophy and Linguistics at the University of Hamburg and Oxford, graduating with a thesis on speech act theory and moral language. He started a university career but switched to science journalism, producing documentaries for German TV. In 1986 he co-founded ChessBase.

Discuss

Rules for reader comments

 
 

Not registered yet? Register

King carrying rook King carrying rook 3/16/2016 08:38
@RaoulBertorello：

Chinese chess engine has defeated Chinese.

If you understand Chinese chess，should be clear：Only Very few of the Draw.

中国象棋程序已经胜了中国人类.

你如果懂中国象棋 棋谱，就应该清楚：只有极少数的和棋.

Weserberglander Weserberglander 3/13/2016 10:43
The time has come. In the twenties we will witness an earthquake that will leave no stone unturned. AI can already play chess games that are from another universe, soon it will revolutionize the medicine, will design a world which is no longer ruled by often self destructive human stone age instincts and compose new and even better Chopin sonatas. However: It's disgusting.
ceegebe ceegebe 3/12/2016 03:31
@ hydra00: Thanks a lot!
McUH McUH 3/12/2016 09:32
It is 3:0 now, so AI won. It was pretty convincing too, looked like it was controlling the flow of the game.
flachspieler flachspieler 3/12/2016 03:01
Computers are going to become stronger than humans in Go now.
This also means that time is ripe for "Freestyle Go". A Freestyle Go
player is a team with arbitrarily human computer structure. My
prediction: Even when Go computers alone will be 2 stones stronger
than the best human players (and that should happen earlier or later),
Freestyle Go teams will still be above them.
Regulus Guy Regulus Guy 3/11/2016 11:19
Much as I respect John Nunn's opinions, here I'm inclined to side with Ken Thomson - and let's remember that Thompson is a computer scientist by profession, which Nunn isn't. The deep learning technology central to AlphaGo depends on fairly recent breakthroughs that unexpectedly brought neural net methods back to the AI mainstream and showed they were a good deal more powerful than people had realized. The most obvious effect has been the massive improvement in speech recognition performance that's happened over the last 7-8 years. It's the same basic box of tricks.

Even given the improvements in deep learning that they've built on, AlphaGo is a fantastic piece of software engineering. The paper they published in Nature is impressive. These are extremely gifted people.

hydra00 hydra00 3/11/2016 06:39
@ ceegebe: The strongest (10x10) draughts programs, when pitted against each other, have a >95% draw rate. This is running on off the shelf hardware (e.g. hexa-cores). Furthermore, the time controls are quite fast (e.g. 5 sec/move on average). So you can imagine how the draw rate would easily creep beyond >99% on bigger hardware and/or slower time controls.

I won't go as far as to say the game can be solved using off the shelf hardware, but I'm fairly certain it can be solved given today's available hardware (supercomputers). It's just that there's no interest in doing so as it's more or less a foregone conclusion since checkers (8x8) is already solved and draughts is basically a larger version of checkers.
hydra00 hydra00 3/11/2016 06:35
@ timisis: You're correct, many people aren't aware of the power of the hardware that AlphaGo is running on. If it ends up winning convincingly (i.e. 4-1 or 5-0), the next question will be how long before the program can beat the world's #1 (~100 "elo" pts stronger than Lee Sedol) when running on non-exotic hardware (i.e. something that fits inside an ATX case).
hydra00 hydra00 3/11/2016 06:31
@ RaoulBertorello: I assume by higher complexity you mean "state-space" (number of legal positions). If so, xiangqi's state-space is about 7 orders of magnitude smaller than chess according to: https://en.wikipedia.org/wiki/Game_complexity

I believe the primary reason why xiangqi programs aren't any stronger than the world's best humans is simply because the draw barrier in xiangqi is much larger than it is in chess. You need either a much larger material advantage, or a positional advantage in order to have a forced win in xiangqi, than you do in chess. Likewise, shogi requires a much smaller material/positional advantage in order to win which explains why the draw rate in shogi is so low. This is why draughts programs (international checkers, 10x10) are super strong but yet when pitted against a top human almost every game is a draw (i.e. the draw barrier is very wide in draughts, but not as wide as it is in checkers (8x8)). I believe the same phenomenon exists in xiangqi.

Your thoughts?
ceegebe ceegebe 3/11/2016 05:22
What about Draughts? Please!
timisis timisis 3/11/2016 04:37
Curiously Nunn was never interested in machine intelligence, so the only reason he features here is that Friedel knows him well :) 1920 CPUs and 280 GPUs took to beat Lee Sedol, which is a larger count than Deep Blue's 20 years ago, so we may be talking about 100 times more computational power, it is not really an algorithm thing alone, not at all. Taken together, software and hardware, it is a landmark towards the inevitable Machine Takeover™.
zedware zedware 3/11/2016 06:43
IMB's should be IBM's
ChessPlease ChessPlease 3/11/2016 02:42
@KevinC Nunn is not 100% correct, and the problem wasn't lack of effort--software engineers lacked the algorithmic tools necessary to tackle something like Go until relatively recently. The traditional A.I. approaches such as those used in chess will not work in Go, and that is why this work is considered to be groundbreaking. To call it the, "...last insurmountable barrier A.I. has to cross" is stretching things a bit however.
fons fons 3/11/2016 01:11
@ Mr TambourineMan: That's a different discussion. I agree that superhuman artificial intelligence could be problematic.

@ Hawkman: That's not the significant thing about this; it's more about being a milestone for artificial intelligence (which is more than just calculation).

And as a chessplayer there's some schadenfreude to be had about Go no longer being able to claim to be "too hard" for computers. :D
AzingaBonzer AzingaBonzer 3/11/2016 12:44
@Hawkman: Next time, do some research before you speak. Go is one of those games that is *absolutely impossible* to play using brute force, at least with our computational capabilities. So however AlphaGo is beating the world Go champion, it's not doing so through pure calculation. I won't give away the actual method here; maybe then you'll have some incentive to look it up instead of sticking with your own ill-informed opinions.
mehmet gok mehmet gok 3/11/2016 12:36
"We can't solve problems by using the same kind of thinking we used when we created them." - Albert Einstein
Therefore, I am with Ken Thompson on this one rather than Dr. Nunn. Effort is not the solution but the paradigm shift is.
Hawkman Hawkman 3/11/2016 12:18
A computer can out calculate a human. Yawn. Except for games where there is some luck or bluffing involved such as card or dice games, this is really boring stuff.
RaoulBertorello RaoulBertorello 3/10/2016 11:05
@hydra00: it's exactly because of what you say, that is Chinese Chess engines and humans are apparently almost equal, or, better, there's no clear winner yet, in a game with higher complexity than Western (Indian) Chess, whereas in the latter engines are now out of reach of any human player. Should they have invested much more money than they did so far, then also Chinese Chess engines would be out of reach of everybody by now. The higher chances a human has at drawing a game in Chinese Chess against a computer is just a trompe l'oeil: it is still this way right because the engines are not yet enough developed to beat easily a human, and the engines are not yet enough developed because not enough money have been put in developing them. If the game is more complex, than a 'strong enough' computer would crash even more easily a human than it does in Western Chess.
Mr TambourineMan Mr TambourineMan 3/10/2016 10:36
fons. "Ideally in the future nobody has to work anymore" Yes. But.... What if we would have this future due to computers doing if for us. On wonder what if they'll, the computers, start thinking we could do theire job? You know soon they'll be smarter than us. And if so in there, the computers, World, we soon even be without a job. Like what we do with our horses. They, the horses, no longer do any jobs for us. Like them we will be Entertainment for computers and if we are lucky, depending on how we see things we end up in the Zoo department. Or as Friedel said the younger computers maybe start looking at us like religiouse people look up on the ape, we cant posibly comes from dumb humans or can we?
fons fons 3/10/2016 09:57
Not sure if Nunn is right. It took the development of neural networks, deep learning and a TON of hardware to make this happen. All things that were not available before.

@ johnmk:

Ideally in the future nobody has to work anymore. Isn't that the whole idea of progress? Or do we want to go backwards? People seem to forget this. Not quite going to happen in our lifetime, but that's where things are heading (and have been since forever).
Vernunft Vernunft 3/10/2016 09:02
Computers still can't play chess.
AzingaBonzer AzingaBonzer 3/10/2016 08:40
Nunn's comment is incorrect. There are certainly techniques that AlphaGo employs that were simply unavailable in the 1990's, both theoretically and computationally. AlphaGo came nearly two decades after Deep Blue by necessity, not due to lack of effort.
genem genem 3/10/2016 07:28
Next step - availability of an inexpensive Go program to run on my laptop computer. When?
hydra00 hydra00 3/10/2016 06:40
@ RaoulBertorello: How many xiangqi human vs. computer matches have there been in the past 5 yrs? I was under the impression that top xiangqi programs now (e.g. ggchess, cyclone) are just as strong as the world's best humans. It's just that the draw barrier in xiangqi is even wider than it is in chess (but not as wide as it is in say, checkers). So if there were a man vs. machine match in xiangqi, it would be quite boring as almost every game would end in a draw.

your thoughts?
Jarman Jarman 3/10/2016 05:49
@johnmk: People will stop doing some jobs and will turn their talents to new objectives. There's a tremendous amount of stuff for which humans are desperately needed - even where Google has a business presence: their "translator" is stil so laughably bad that one wonders why they even bother keeping it alive.
DJones DJones 3/10/2016 05:37
Without a UBI, relatively clean water and Low cost energy to support it all (fusion power?), the machines taking over our jobs, problem solving methods and other human activities is not a great thing in general. I agree johnmk. Inequality will just get worse and eventually there will be revolt against the elites who are pushing ever harder for a designer society.
KevinC KevinC 3/10/2016 05:32
@ChessPlease, Nunn is 100% correct, and your comparison to black holes is not a good one. Einstein predicted black holes in 1916, and the first one was discovered in 1971. You don't think that with computers today that they would not have discovered the first one sooner? They made the effort, but did not have the tools we have today, but programming strong Go computers has clearly not been a priority.
ChessPlease ChessPlease 3/10/2016 03:51
John Nunn is entitled to his opinion, even if that opinion happens to be totally wrong. What he said is sort of like saying, "Astronomers would have discovered evidence of black holes long ago if they'd only made more of an effort to look for them.". Apparently, he knows very little about machine learning, neural networks, or the fact that games with a higher branching factor than chess(but otherwise similar), are exponentially more difficult to calculate than chess using traditional methods.
johnmk johnmk 3/10/2016 03:12
People should not cheer this development. It may seem like a harmless game, but smarter computers will lead inevitably to more unemployment through automation. Neural networks can only accelerate this trend and don't believe anyone who says it won't happen. In this kind of economy, corporations look to cut costs and automation with robots is the easiest way to achieve it.
Real people need secure -- and dignified -- work. It is a real problem.
RaoulBertorello RaoulBertorello 3/10/2016 02:57
Comment by John Nunn remembers me what I told a colleague of mine eight (8) years ago when we were talking about chess engines: I told him the only reason why no Chinese Chess engine has ever won yet over a reigning human world Chinese Chess champion is that so far they have never invested the money necessary to develop a world class winner Chinese Chess engine, because evidently there has vener been Return On Investment in doing so as there was instead for Indian (western) chess, which is what moved IBM, the ROI being a worldwide advertising effect. Glad to know I think like Dr. John Nunn.
1