The Game Of 'GO' And How It Foils Computers

While most of the modern world is caught up in online video games there remain millions of us dedicated to good, old fashioned board games, including chess  and GO. While most people have heard of chess, relatively few know about Weiqi, the Chinese name for GO which dates back over 2,500 years. GO is played on a 19x19 grid though simplified forms of the game (in which players opt to invest less time) have smaller grids, e.g. 9 x 9.

Unlike chess, the object  in GO isn't to capture pieces but to control territory on the board, whether that's an actual game board or a computer display for computer 'GO'.  Also, unlike in chess where various colored chess pieces (as well as shapes) are in use, GO admits of only two colors - black and white- and these are always associated with the same shaped rounded pieces, called "stones".  Also unlike chess, one doesn't place a stone on an empty square or space but rather on an intersection of gird lines - which must be unoccupied, of course.

Players alternate moves, each placing a stone on an unoccupied intersection. Also unlike chess, a player can forego a move if it is not in his best interest. The goal is to control as much space on the board as possible without one's own pieces being surrounded - in which case they can be removed - and added to the opponent's score.

GO is, by the preceding description, a canonical minimalist game, with only one type of piece and a handful of rules. Never mind, in depth and complexity it supersedes chess. For a first move alone, facing an empty board or grid, there are some 361 possible moves. Even well into the same - such as depicted in the graphic - there are many more options than in the typical chess game.

Here are two other interesting aspects of the game: 1) Draws are impossible, unlike in chess, and 2) the first player to move doesn't have a significant advantage as in chess. In addition, opening sequences, like the Ruy Lopez in chess, don't repeat themselves as often. One would think, on the face of it, it would be as easy to design a decent computer game of GO as for chess but this hasn't been the case.

This is not to say some forms of computer game exist that are halfway decent and can at least give humans a decent work out. One of these is EZ-GO which I've played countless times, but too often ended up beating the computer. It simply lacks the nuanced moves - or what one could cite as the advanced move potential- that my Grandmaster Chess game exhibits. Playing at the 'grandmaster' level it is extremely difficult to snatch a win in the latter.

Why is it so difficult to put together a decent computer GO game? Some have conjectured (e.g. Chris Chabris, WSJ, 'Game On', Jan. 2-3, p. C4) that mastering it "requires more humanlike skills of pattern recognition and intuitive judgment".  This may be so, but anyone who's studied the basis of GO also knows there is a lot of graph theory that it involved. This is something that any decent computer ought to be able to emulate, and in fact, master thoroughly.

One current effort to come up with the GO 'goods' is being led by Facebook, and according to Chabris (ibid.):

"Facebook's GO program combines two fairly new computational technologies: deep convolutional neural networks which vaguely use brain-like algorithms to learn and recognize large scale patterns on the game board, and Monte Carlo tree search which is a form of 'thinking ahead' that works out detailed tactical sequences in specific areas."

He adds:

"According to Facebook's developers, this approach beats the best open source GO program more than 95 percent of the time".

Maybe so. But will there ever be a time when we come up with a computing marvel like 'Deep Blue' which beat chess grandmaster Garry Kasparov in 1997? We will have to wait and see if human ingenuity in designing computer GO will eventually be able to defeat a GO master.