On Google’s AlphaGo


I thought I’d get away from critiques and reviews and serious stuff like that for a week and talk about a cool (or scary) development in AI research. I won’t talk about the details, so don’t get scared off yet. This will be more of a high level history of what happened. Many of my readers are probably unaware this even exists.

Let’s start with the basics. Go is arguably the oldest game in existence. And despite appearances, it’s one of the simplest. Each player takes a turn placing a stone on the intersections of a 19×19 board. If you surround a stone or group of stones of your opponent, you capture them (remove them from the board). If you completely surround other intersections, that counts as your “territory.”

The game ends when both sides pass (no more moves can be made to capture or surround territory). The side that has more territory + captures wins. There’s no memorization of how pieces move. There’s no rules to learn (except ko, which basically says you can’t do an infinite loop causing the game to never end). It’s really that simple.

And despite the simplicity, humans have continued to get better and produce more and more advanced theory about the game for over 2,500 years.

Let’s compare Go to Chess for a moment, because most people in the West think of Chess as the gold standard of strategy games. One could study chess for a whole lifetime and still pale in comparison to the top Grand Masters. When Deep Blue beat Kasparov in 1997, it felt like a blow to humanity.

If you’re at all in touch with the Chess world, you will have succumb to the computer overlords by now. We can measure the time since Deep Blue’s victory in decades. The AI have improved so much since then that it is commonly accepted across the whole community that a human will never be able to win against a machine at Chess ever again.

A few years ago, we could at least have said, “But wait, there’s still Go.” To someone who doesn’t have much experience with Go, it might be surprising to learn that computers weren’t even close to winning against a human a few years ago.

Here’s the rough idea why. Chess can be won by pure computation of future moves. There is no doubt that humans use pattern recognition and positional judgment and basic principles when playing, but none of that stands a chance against a machine that just reads out every single combination of the next 20 moves and then picks the best one.

Go, on the other hand, has pattern recognition as a core element of the strategy. One might try to argue that this is only because the calculations are so large, no human could ever do them. Once we have powerful enough computers, a computer could win by pure forward calculation.

As far as I understand it, this is not true. And it was the major problem in making an AI strong enough to win. Even at a theoretical level, having the computer look ahead a dozen moves would generate more combinations than the number of atoms in the known universe. A dozen moves in Chess is half the game. A dozen moves in Go tells you nothing; it wouldn’t even cover a short opening sequence.

Go definitely has local sections of the game where pure “reading ahead” wins you the situation, but there is still the global concept of surrounding the most territory to consider. It’s somewhat hard to describe in words to someone unfamiliar with the game what exactly I mean here.

san-ren-sei-opening

Notice how on the right the black stones sort of surround that area. That could quickly turn into territory by fully surrounding it. So how do you get an AI to understand this loose, vague surrounding of an area? One could even imagine much, much looser and vaguer surrounding as well. Humans can instantly see it, but machines cannot and no amount of a calculating further sequences of moves will help.

For years, every winter break from college, I’d go home and watch famous and not-so-famous people easily win matches against the top AI. Even as late as 2014, it wasn’t clear to me that I’d ever see a computer beat a human. The problem was that intractable.

Along came Google. They used a machine learning technique called “Deep Learning” to teach an AI to develop these intuitions. The result was the AlphaGo AI. In March 2016, AlphaGo beat Lee Sedol, arguably the top Go player in the world. It was a five game sequence, and AlphaGo won 4-1. This gave humanity some hope that the top players could still manage a match here and there (unlike in Chess).

But then the AI was put on an online Go server secretly under the name “Master.” It has since played pretty much every single top pro in the world. It has won every single game with a record around 60-0. It is now believed that humans will never win against it, just like in Chess.

More theory has been developed about Go than any other game. We’ve had 2,500 years of study. We thought we had figured out sound basic principles and opening theory. AlphaGo has shaken this up. It will often play moves that look bad to a trained eye, but we’re coming to see that many of the basics we once thought of as optimal are not.

It’s sort of disturbing to realize how quickly the machine learned the history of human development and then went on to innovate it’s own superior strategies. It will be interesting to see if humans can adapt to these new strategies the AI has invented.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s