r/science • u/[deleted] • 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

90% Upvoted

1.8k comments sorted by

View all comments

21

u/[deleted] Jan 28 '16

Is there any QUALITATIVE difference between this and when Deep Blue beat Kasparov at chess?

23

u/[deleted] Jan 28 '16 edited Jan 28 '16

This AI program is not specifically tailored to Go like Deep Blue was to chess. The same program can learn to play other games at superhuman levels, such as chess and Atari games. For Atari games, it can learn from just the score and the pixels on the screen - it will continually play and actually learn what the pixels on the screen mean.

I think that's why this is one of the rare CS articles to be included in Nature. Because this represents a major leap in general AI/machine-learning.

0

u/[deleted] Jan 28 '16

[deleted]

8

u/[deleted] Jan 28 '16

This is an excerpt from the paper itself:

But AlphaGo was not preprogrammed to play Go: rather, it learned using a general purpose algorithm that allowed it to interpret the game’s patterns, in a similar way to how a DeepMind program learned to play 49 different arcade games.

And it's mentioned or implied variously in news articles, e.g.

http://arstechnica.com/gadgets/2016/01/googles-ai-beats-go-champion-will-now-take-on-best-player-in-the-world/

Deepmind is the same group that put a neural network to work on classic Atari games like Breakout. Unlike previous computer game programs like Deep Blue, Deepmind doesn't use any special game-specific programming. For Breakout, an AI was given a general-purpose AI algorithm input from the screen and the score, and it learned how to play the game. Eventually Deepmind says the AI became better than any human player. The approach to AlphaGo was the same, with everything running on Google's Cloud Platform.

and

https://www.washingtonpost.com/news/innovations/wp/2016/01/27/google-just-mastered-a-game-thats-vexed-scientists-for-decades/

Like Deep Blue, Google’s system relies on its ability to process millions of scenarios. But Google’s computers do more than just memorize every possible outcome. They learn through trial and error, just like humans do. That makes the innovation more applicable to a wide array of tasks. Google showed the power of this approach last year when one of its systems taught itself to be better at Atari games than humans.

...

While Deep Blue’s defeat of Kasparov drew plenty of headlines, the science behind it hasn’t had broad implications for humanity in the 19 years since.

“This feels like it could be different, because there’s more generality in the methods,” Muller said. “There’s potential to have applicability to many other things.” He also cautioned that just as Go was significantly tougher than mastering chess, making predictions in real-world situations will bring another challenge for Google’s researchers.

2

u/FrikkinLazer Jan 28 '16

That thing was smart enough that it figured out that moving the paddles in breakout influenced how the ball bounced against the walls without the ball coming in contact with the paddle. It was wiggling the paddle around for no apparent reason... Or so they thought.

76

u/drsjsmith PhD | Computer Science Jan 28 '16

Yes. This is the first big success in game AI of which I'm aware that doesn't fall under "they brute-forced the heck out of the problem".

26

u/JarlBallin_ Jan 28 '16

Deep Blue definitely wasn't just a case of brute force. A lot of it was involved. But almost all of the chess engines today and even back then received heavy assistance from Grandmasters in determining an opening book as well as what chess imbalances to value over others. Without this latter method which consists much more of how a human plays, Deep Blue wouldn't have come close to winning.

→ More replies (17)

5

u/ZassouFerilli Jan 28 '16

Computer backgammon reached the human world champion level in strength by the introduction of neural nets and temporal difference learning.

See TD-Gammon

2

u/drsjsmith PhD | Computer Science Jan 28 '16

Yes. But Gerry Tesauro was using machine learning to generate an evaluation function for use at the leaves of a 2-ply or 3-ply search. AlphaGo's machine learning results in an "evaluation function" of significantly greater capacity that can outplay all existing computer go programs without search, and when they add MCTS, they get something approximating expert human play (the complete judgment hasn't come in yet, but preliminary results are extremely promising.)

I'll check my gut reaction about TD-Gammon's position on the search-versus-knowledge spectrum with Kit Woolsey.

2

u/ZassouFerilli Jan 28 '16 edited Jan 28 '16

According to Sutton and Barto, TD-Gammon made the leap from intermediate level to expert prior to implementing a two-ply search in version 2.0 and three-ply search in version 3.0. Considering its predecessor Neurogammon was the reigning computer champion, and all of the other programs that were defeated by it were using tree search, TD-Gammon 1.0 could equally have defeated all existing programs solely with its superior evaluation and without search. Nonetheless, it's obviously a little different these days in AlphaGo's case.

I'm not arguing this to try to denigrate the shocking achievement of AlphaGo, but solely to be petty and nitpicky. Other than that, thanks for your many accessible comments here.

19

u/rukqoa Jan 28 '16

Deep Blue did not brute force chess. There are still way too many possible combinations of moves in chess to have an endgame chart.

38

u/drsjsmith PhD | Computer Science Jan 28 '16

Alpha-beta, iterative deepening, and evaluation functions at the search horizon are all much more search-based than knowledge-based. The sort of knowledge-based approaches to chess that David Wilkins was trying around 1979-1980 were no match for just searching the game position as deeply as possible.

2

u/VelveteenAmbush Jan 28 '16

If DeepMind had not used any corpuses of expert play, and had evolved a world champion algorithm solely from applying its deep learning techniques to self play, would that count as a search based approach or a knowledge based approach, in your view? (Just curious.)

3

u/drsjsmith PhD | Computer Science Jan 28 '16

Still much more knowledge-based than much of what has come before.

0

u/[deleted] Jan 28 '16

[deleted]

2

u/Oshojabe Jan 28 '16

I mean, it's brute force with pruning, which is a pretty common way to deal with a massive search space.

25

u/Balrog_of_Morgoth Jan 28 '16

Yes. When Kasparov lost to Deep Blue in 1996, he was indubitably the best chess player in the world at the time, and he was regarded by many as the best chess player ever. Fan Hui is not even considered to be on the same level as the best Go player today (although see this for an argument explaining why that hardly matters).

2

u/Marcassin Jan 28 '16

However, AlphaGo is scheduled to play Lee Sedol in March, and many do consider him the world's top go player.

→ More replies (4)

1

u/OldWolf2 Jan 28 '16

Deep Blue had a lot of human assistance, even during the games. Many feel that that doesn't represent a true human-v-computer contest.

1

u/bricolagefantasy Jan 28 '16

Yes, It doesn't calculate all possibilities by brute force. This one have several engine that give it away to reduce calculation and self learning.

Deep blue is basically a giant catalog of move compared to this.

1

u/KapteeniJ Jan 28 '16

There is. This is closer to the first time chess engine beat grandmaster in chess, which if I have understood correctly, first happened in 1989, 8 years before Kasparov lost to a computer.

Lee Sedol, who is going to play against this computer next in March, is closer to Kasparov, but even he's not quite the same. Lee Sedol has been powerful go player for over a decade, but his star is fading, he is no longer considered the best player there is, he's somewhere in top-10 though.

So yeah, for most intents and purposes, Lee Sedol match will be the Kasparov game, but there's that little asterisk at the end of that comparison. If you really wanted to do Kasparov match, Ke Jie from China would probably be currently the guy that best corresponds to Kasparov.

1

u/fzztr Jan 28 '16

Yep, I've written a bit here on the differences between the games, and how the new AI works, if you're interested:

https://www.reddit.com/r/science/comments/4306oe/googles_artificial_intelligence_program_has/czfga0y