iGo for broke

by Kensatsukan Gaijin

This month, Artificial Intelligence (“AI”) achieved something once thought impossible - AlphaGo, a program developed by Google's DeepMind unit, defeated legendary Go player Lee Se-dol in Seoul, South Korea. AlphaGo made headlines in January when DeepMind – an artificial intelligence company that Google bought in 2014 – announced that its AI had defeated reigning European champion Fan Hui 5–0.  This victory marks a significant advancement in AI -  Go (in Japanese, “igo”) is something of a Holy Grail for AI developers, whose first global success in board games came in 1997 when IBM’s Deep Blue defeated then-world chess champion Gary Kasparov.


Why does it matter so much?  Well, here’s an explanation by Japanese Table founder John Berryman:


<<In 1997 we built a computer that could beat a the best chess player in the world, but even as of late last year the idea of building a Go AI that could beat a professional player was not anticipated in this decade. The difficulty with Go is that for each turn there are simply too many possible moves, so you can't use the approach used with chess of just looking at all possible moves going forward (well, all reasonable moved). Another problem with building a Go AI is that, unlike chess, it's difficult to look at the board during the middle of a game and get an idea of who has the better board position. Humans lean upon intuition to play Go and it was thought that an AI that could beat a human professional would have to exhibit a similar intuition.


Folks were rather astounded when AlphaGo beat a professional player back last fall. AlphaGo is built with the new "deep learning" neural network approaches that have been gaining a lot of academic interest recently. Basically they trained two networks. One was trained to look at a board and guess the next move that would be made. The other was trained to look at a board and determine who would win the match based upon the current board position. It turns out that this basically covers the two "difficult" things presented in the first paragraph. Once these two networks were good enough, they were used together in one program to build a Go AI. Basically, when it was the AI's turn to move, the first network was used to predict the evolution of the game for quite a large set of moves into the future (but it didn't have to try every possible move), and then for each future board position the AI would estimate the probability that it would win the game. Based upon all that simulation, the AI would then simply chose the next move that most likely lead to success.


The finally ingredient in making the AI so strong is that it started playing games with itself. When the first two networks were trained, they were trained with a database of tons and tons of matches from high level players (millions of matches). But when the full Go AI was assembled it was allowed to start playing games with itself - hundreds of millions. As it played it became better and better until in the recent match with #2 Go player, Sedol, it won 4 out of 5 matches.


It's truly a remarkable achievement in AI.>>


What makes Go such a great target of DeepMind and Google’s AI team is the nature of the game itself.  Created more than 2,500 years ago in China, Go has simple rules, but requires a mixture of complicated strategy and foresight.  The game begins with an empty board. There’s only one type of stone, unlike Chess that has six different pieces. The two players alternate turns, placing one of their stones on any vacant intersections of the lines at each turn. The stones are not moved once they’re played. However they may be “captured,” in which case they are removed from the board. You can capture stones by completely surrounding them, like this (white is one stone away from capturing the black stone in this example).  But the goal isn’t to capture as many stones as possible. The main object of the game is to use your stones to form territories and occupy the most space possible. Moreover, the sheer number of possible moves is what makes Go such a complicated game to learn. After the first two moves of a chess game, there are 400 possible next moves — in Go, there are close to 130,000.


And as Google gets better at reading and predicting human behavior, it will be able to apply its progress in AI to other areas. According to Brown University computer scientist Michael L. Littman, AlphaGo’s technology could be applied to Google’s self-driving cars, where the AI has to make decisions continuously, or in a problem-solving search capacity, like showing a gluten-free baking recipe. Smartphone assistants that are smart and contextual could be the next area of focus for DeepMind, as well as healthcare and robotics. DeepMind’s ability to sift through massive amounts of data and come up with the best possible next move could immensely help all of those industries.  






The Japan Times

The Verge