The Mystery of Go

Nice article on the progress of computer Go.

See also The Laskers and the Go master: "While the baroque rules of Chess could only have been created by humans, the rules of Go are so elegant, organic, and rigorously logical that if intelligent life forms exist elsewhere in the universe, they almost certainly play Go." (Edward Lasker, International Master and US Chess champion)

WIRED: ... 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. ... 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.

...

After the match, I ask Coulom when a machine will win without a handicap. “I think maybe ten years,” he says. “But I do not like to make predictions.” His caveat is a wise one. In 2007, Deep Blue’s chief engineer, Feng-Hsiung Hsu, said much the same thing. Hsu also favored alpha-beta search over Monte Carlo techniques in Go programs, speculating that the latter “won’t play a significant role in creating a machine that can top the best human players.”

Even with Monte Carlo, another ten years may prove too optimistic. And while programmers are virtually unanimous in saying computers will eventually top the humans, many in the Go community are skeptical. “The question of whether they’ll get there is an open one,” says Will Lockhart, director of the Go documentary The Surrounding Game. “Those who are familiar with just how strong professionals really are, they’re not so sure.”

According to University of Sydney cognitive scientist and complex systems theorist Michael Harré, professional Go players behave in ways that are incredibly hard to predict. In a recent study, Harré analyzed Go players of various strengths, focusing on the predictability of their moves given a specific local configuration of stones. “The result was totally unexpected,” he says. “Moves became steadily more predictable until players reached near-professional level. But at that point, moves started getting less predictable, and we don’t know why. Our best guess is that information from the rest of the board started influencing decision-making in a unique way.” ...

The current handicap accorded a computer against a professional player is 4 stones. In the story below the world chess champion and his brother are given 9 stones by the Japanese mathematician (shodan = lowest non-beginner or black belt).

Mr. Kitabatake one day told us that a Japanese mathematician was going to pass through Berlin on his way to London, and if we wanted to we could play a game with him at the Japanese Club. Dr. Lasker asked him whether he and I could perhaps play a game with him in consultation, and was wondering whether the master – he was a shodan – would give us a handicap.

“Well, of course,” said Mr. Kitabatake.
“How many stones do you think he would give us?" asked Lasker.
“Nine stones, naturally,” replied Mr. Kitabatake.
“Impossible!” said Lasker. “There isn’t a man in the world who can give me nine stones. I have studied the game for a year, and I know I understood what they were doing.”
Mr. Kitabatake only smiled.
“You will see,” he said.

The great day came when we were invited to the Japanese Club and met the master – I remember to this day how impressed I was by his technique – he actually spotted us nine stones, and we consulted on every move, playing very carefully. We were a little disconcerted by the speed with which the master responded to our deepest combinations. He never took more than a fraction of second. We were beaten so badly at the end, that Emanuel Lasker was quite heartbroken. On the way home he told me we must go to Japan and play with the masters there, then we would quickly improve and be able to play them on even terms. I doubted that very strongly, but I agreed that I was going to try to find a way to make the trip.