Invented over 2500 years ago in China, Go is a pastime beloved by emperors and generals, intellectuals and child prodigies. Like chess, it’s a deterministic perfect information game — a game where no information is hidden from either player, and there are no built-in elements of chance, such as dice.1 And like chess, it’s a two-person war game. Play begins with an empty board, where players alternate the placement of black and white stones, attempting to surround territory while avoiding capture by the enemy. That may seem simpler than chess, but it’s not. When Deep Blue was busy beating Kasparov, the best Go programs couldn’t even challenge a decent amateur. And despite huge computing advances in the years since — Kasparov would probably lose to your home computer — the automation of expert-level Go remains one of AI’s greatest unsolved riddles.
The Mystery of Go
Even in the West, Go has long been a favorite game of mathematicians, physicists, and computer scientists. Einstein played Go during his time at Princeton, as did mathematician John Nash. Seminal computer scientist Alan Turing was a Go aficionado, and while working as a World War II code-breaker, he introduced the game to fellow cryptologist I.J. Good. Now known for contributing the idea of an “intelligence exposition” to singularity theories — predictions of how machines will become smarter than people — Good gave the game a huge boost in Europe with a 1965 article for New Scientist entitled “The Mystery of Go.”
Good opens the article by suggesting that Go is inherently superior to all other strategy games, an opinion shared by pretty much every Go player I’ve met. “There is chess in the western world, but Go is incomparably more subtle and intellectual,” says South Korean Lee Sedol, perhaps the greatest living Go player and one of a handful who make over seven figures a year in prize money. Subtlety, of course, is subjective. But the fact is that of all the world’s deterministic perfect information games — tic-tac-toe, chess, checkers, Othello, xiangqi, shogi — Go is the only one in which computers don’t stand a chance against humans.
This is not for lack of trying on the part of programmers, who have worked on Go alongside chess for the last fifty years, with substantially less success. The first chess programs were written in the early fifties, one by Turing himself. By the 1970s, they were quite good. But as late as 1962, despite the game’s popularity among programmers, only two people had succeeded at publishing Go programs, neither of which was implemented or tested against humans.
Finally, in 1968, computer game theory genius Alfred Zobrist authored the first Go program capable of beating an absolute beginner. It was a promising first step, but notwithstanding enormous amounts of time, effort, brilliance, and quantum leaps in processing power, programs remained incapable of beating accomplished amateurs for the next four decades.
To understand this, think about Go in relation to chess. At the beginning of a chess game, White has twenty possible moves. After that, Black also has twenty possible moves. Once both sides have played, there are 400 possible board positions. Go, by contrast, begins with an empty board, where Black has 361 possible opening moves, one at every intersection of the 19 by 19 grid. White can follow with 360 moves. That makes for 129,960 possible board positions after just the first round of moves.
The rate at which possible positions increase is directly related to a game’s “branching factor,” or the average number of moves available on any given turn. Chess’s branching factor is 35. Go’s is 250. Games with high branching factors make classic search algorithms like minimax extremely costly. Minimax creates a search tree that evaluates possible moves by simulating all possible games that might follow, and then it chooses the move that minimizes the opponent’s best-case scenario. Improvements on the algorithm — such as alpha-beta search and null-move — can prune the chess game tree, identifying which moves deserve more attention and facilitating faster and deeper searches. But what works for chess — and checkers and Othello — does not work for Go.
Similarly inscrutable is the process of evaluating a particular board configuration. In chess, there are some obvious rules. If, ten moves down the line, one side is missing a knight and the other isn’t, generally it’s clear who’s ahead. Not so in Go, where there’s no easy way to prove why Black’s moyo is large but vulnerable, and White has bad aji. Such things may be obvious to an expert player, but without a good way to quantify them, they will be invisible to computers. And if there’s no good way to evaluate intermediate game positions, an alpha-beta algorithm that engages in global board searches has no way of deciding which move leads to the best outcome.
Not that it matters: Go’s impossibly high branching factor and state space (the number of possible board configurations) render full-board alpha-beta searches all but useless, even after implementing clever refinements. Factor in the average length of a game — chess is around 40 turns, Go is 200 — and computer Go starts to look like a fool’s errand.
Many Go players see the game as the final bastion of human dominance over computers. This view, which tacitly accepts the existence of a battle of intellects between humans and machines, is deeply misguided. In fact, computers can’t “win” at anything, not until they can experience real joy in victory and sadness in defeat, a programming challenge that makes Go look like tic-tac-toe. Computer Go matches aren’t the brain’s last stand. Rather, they help show just how far machines have to go before achieving something akin to true human intelligence. Until that day comes, perhaps it’s best to view the Densei-sen as programmers do.
Abstracted from http://www.wired.com/2014/05/the-world-of-computer-go/
Weiqi To Go 