KDnuggets Home » News » 2016 » Feb » News, Features » Google’s Great Gains in the Grand Game of Go ( 16:n04 )

Google’s Great Gains in the Grand Game of Go

The game of Go has long stumped AI researchers, and, as such, solving it was thought to be years off. That is, until Google solved it earlier this week. Or did it?

For some time, the big players in artificial intelligence (AI) (notably Google and Facebook) have been trying to solve the ancient Chinese game of Go. Go is a 2500 year old board game played by two players alternating the placement of their pieces on the (traditionally) 19x19 game board. The goal is to avoid having your pieces surrounded by your opponent's, while simultaneously attempting to surround your opponent's pieces with your own. Absurdly simple in theory, Go has continuously proven a formidable challenge for AI researchers.

Go board

The recipe for success in the game of Go includes lots of practice, as well as the abilities for both subtle pattern recognition and nuanced decision making for dealing with these potentially sparse or incomplete patterns. The complexity of gameplay had led many to believe that it would be a decade or longer before Go was solved.

To the surprise of many, Google announced earlier this week that it had, in fact, "mastered Go."

A Bit About AlphaGo

Google DeepMind built its AlphaGo system using deep learning techniques and Monte Carlo tree search. Described in the published paper, the outlined architecture actually uses a pair of deep neural networks, one for next move prediction and the other for outcome prediction based on different board arrangements. A major difference beteeen AlphaGo and, for example, Deep Blue, the chess-playing computer that holds the distinction of being the first AI to beat a reigning chess champion in Garry Kasparov, is that Deep Blue had hard-coded rules and utilized brute-force techniques in its search space; AlphaGo learns over time the best moves to make in particular situations.

To demonstrate why brute force is not an option in Go, the exact number of legal positions in the game, using a regulation 19x19 board, is a number that is 171 digits in length, a number which was only determined in early 2016. For 2500+ years players of Go didn't even have an idea of how many legal positions were on the playing surface. Because of this and other issues related to combinatorics, Go has long been a source of great interest for mathematics research.

(Did you know that there are more possible legal Go positions than there are estimated atoms in the universe?)

Chinese Go stones

It should be pointed out that earlier this week, Facebook also published a paper on its Go progress, which follows a pattern-matching approach and employs a deep neural network architecture as well.

Why Go?

But why even attempt to solve Go? In reality, this is just another in an increasingly-challenging series of human games queued up for AI to solve; it just so happens that it is one of the crown jewels. There is nothing about the game specifically, beyond the challenge of solving it, that would invite the attention and trouble of large companies pouring time, money, and energy into this effort. Is there?

Digressing momentarily, it is argued that Go is more challenging for computers to learn than, for example, chess, for 2 major reasons:

  1. Each turn provides many more potential moves
  2. Measuring a player's advantage at any given time is very difficult to do

Comparing the first point to chess, for example, we know that at any given chess board configuration any piece can move in only certain sequences, providing a finite set of moves to measure success against. Similarly, only a relatively small number of moves can be made by the opponent in the resulting state. Go allows a player to set their next piece at any legal position on the board, which can then be countered by the opponent laying their next piece at any other legal position on the board, and so on; the potential set of outcomes is not dependent on a small number of legal positional changes. Instead, the position of the next piece is chosen depending upon the existing and emerging patterns of both the player and their opponent, a fluid situation.

For both of these reasons, the pattern recognition ability is much more important in Go than in chess (or a number of other games). In order to maximize its pattern recognition capabilities, AlphaGo uses generalizable techniques that, it is hoped, can be applied to real world situations, and perhaps to the development of a "general AI" (think SkyNet; no don't, I'm kidding). It is for these resulting generalizable techniques which may lead to general AI that Go is so aggressively pursued by Google and Facebook (as well as by others).

This isn't an all-or-nothing scenario either; incremental attempts at solving smaller versions of Go, using restricted board sizes, have been attempted (and achieved) over the years. Of course, approaches to these solutions are vastly different than those required for much larger and more complicated game spaces, and so the chances of 5x5 Go strategies being generalizable are slim to none.


Is Go Really Solved?

So, is Go really solved? The truth is, we don't yet know.

And to be fair, Google has said that its system has mastered Go (not solved), which is both responsible and seemingly cautiously optimistic.

What we do know is that AlphaGo beat Fan Hui, the European Go champion, five games to zero. It's not that this isn't a spectacular achievement for a computational Go; this is far better than any previous attempt has fared.

However, as good at Go as Fan Hui may be (and with all due respect to him and his accomplishments), it's a bit like the up-and-coming rookie readily beating the second or third tier champion at some sport (Hui is very good, but he is not ranked among top players in the world, most of whom compete in South East Asia). Sure, the rookie is good (very good, even), but until they play against top tier opponents their true level of competitive skill will never be known. If AlphaGo wants to prove its chops, it will have to do so in the big leagues.

And it will do just that in March. AlphaGo plans to play Lee Sedol, one of the world’s best players of Go, in a tournament in Seoul, South Korea. Its performance in this matchup will effectively determine if it is the cream of the crop in Go (or very close), or if it is ranked #200 in the world. To be clear, given that millions of people play Go worldwide and have for millenia, neither scenario is a catastrophe; though I think most would agree that one of the two options is clearly more desirable.

Tempering our expectations is Jonathan Schaeffer, computer scientist at the University of Alberta, and designer of the program that solved checkers, who says:

This is not yet a Deep Blue moment. The real achievement will be when the program plays a player in the true top echelon. Deep Blue started regularly beating grandmasters in 1989, but the end result was eight years later.

We will leave you with what Fan Hui himself had to say after playing AlphaGo, which is likely the greatest compliment that the system could receive.

I know AlphaGo is a computer, but if no one told me, maybe I would think the player was a little strange, but a very strong player, a real person.

March will give us a much better idea of just how significant Google's latest accomplishment is.