The Mystery of Go

Wednesday, June 11th, 2014

In 1965 New Scientist published I.J. Good’s The Mystery of Go:

Go, the Japanese national pastime, was recently described by Ralph Fox, a Princeton professor of mathematics, as the most interesting game in the world. At any rate many expert chess players, including Emanuel Lasker, who was World Chess Champion for 28 years, have held that Go is more interesting than chess, and it is not easy to think of any third game that is a serious rival. Another, unrelated chess master, Edward Lasker, believes that Go will replace chess as the leading intellectual game of the Occident just as it has reigned supreme in the Orient for some four thousand years.

In Japan the game is known as I-go or Go, in China as Wei-k’i or Wei-Chi, in Korea as Patok. It is played by a high proportion of educated people in Japan, including many Geisha girls, and ability at Go is relevant to promotion in many firms.

[...]

The rules are basically so simple that perhaps a game very much like Go is played in many extra-terrestrial places, even within our own galaxy.

[...]

A weakness in chess is that there is too much knowledge about the openings, and it is constantly increasing. It is not good for a game if its mastery requires much rote learning. In Go, although play in the corners of the board is somewhat stereotyped among masters, one can become a competent Go player by occidental standards with very little knowledge of these so-called Joseki.

In chess, the parrots can be defeated by playing Randomised Chess, wherein the pieces on the back lines are permuted at random. Similarly, Randomised Go could be defined in terms of a random deletion of some of the vertices near the corners of the board. The corners could even be abolished by playing on a cylinder or an anchor ring: this could be done, without using a magnetic set, by identification of opposite sides of the ordinary board, either one pair of sides or both pairs. Another form of Go is that with more than two players, all against all, with one colour for each player. Since it is possible for players to form coalitions, this form of Go bears some resemblance to power politics and is liable to create an emotional scene.

But ordinary Go is fascinating enough for people with an IQ between 110 and 190 — in fact, too fascinating. Sometimes the game becomes an addiction, like smoking, food, drink, television, chess and women. It seems to appeal especially to scientists and mathematicians, because of the emergence of the Gestalt — a unity with a significant pattern — out of a collection of discrete entities and axioms.

Go on a computer? — In order to programme a computer to play a reasonable game of Go — rather than merely a legal game — it is necessary to formalise the principles of good strategy, or to design a learning programme. The prlnciples are more qualitative and mysterious than in chess, and depend more on judgment. So I think it will be even more difficult to programme a computer to play a reasonable game of Go than of chess.

The experienced player will often be unable to explain convincingly to a beginner why one move is better than another. A move might be regarded as good because it looks influential, or combines attack and defence, or preserves the initiative, or because if we had not played at that vertex the opponent would have done so; or it might be regarded as bad because it was too bold or too timid, or too close to the enemy or too far away. If these and other qualitative judgments. could be expressed in precise quantitative terms, then good strategy could be programmed for a computer; but hardly any progress has been made in this direction.

Indeed, hardly any progress was made in computer Go for decades after Good’s article came out, until Rémi Coulom’s Crazy Stone combined a tree search with Monte Carlo methods:

He christened the new algorithm Monte Carlo Tree Search, or MCTS, and in January of 2006, Crazy Stone won its first tournament. After he published his findings, other programmers quickly integrated MCTS into their Go programs, and for the next two years, Coulom vied for dominance with another French program, Mogo, that ran a refined version of the algorithm.

Although Crazy Stone ended up winning the UEC Cup in 2007 and 2008, Mogo’s team used man-machine matches to win the publicity war. Coulom felt the lack of attention acutely. When neither the public nor his university gave him the recognition he deserved, he lost motivation and stopped working on Go for nearly two years.

Coulom might have given up forever had it not been for a 2010 email from Ikeda Osamu, the CEO of Unbalance, a Japanese computer game company. Ikeda wanted to know if he’d be willing to license Crazy Stone. Unbalance controlled about a third of the million-dollar global market in computer Go, but Zen’s commercial version had begun to increase its market share. Ikeda needed Coulom to give his company’s software a boost.

The first commercial version of Crazy Stone hit the market in spring of 2011. In March of 2013, Coulom’s creation returned to the UEC Cup, beating Zen in the finals and — given a four-stone head-start — winning the first Densei-sen against Japanese professional Yoshio “The Computer” Ishida. The victories were huge for Coulom, both emotionally and financially. You can see their significance in the gift shop of the Japan Go Association, where a newspaper clipping, taped to the wall behind display copies of Crazy Stone, shows the pro grimly succumbing to Coulom’s creation.

Comments

  1. Rollory says:

    From the article:

    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.

    That about sums it up. Chess is a solvable problem and has in large part been solved (checkers has been completely solved). Go is also a solvable problem; the difference is that the computational ability required to solve it is orders of magnitude larger. Which does not make it impossible.

    Among the many SF short stories I read as a kid, I remember there was one (must have been from 1950s or so) where a race of alien robots was talking about how there was this planet that had to be avoided at all costs because there was a terribly infectious logic problem that tended to permanently crash any of their kind that encountered it because it was so engrossingly difficult, and the only information available was the names of the components: King, Queen, Rook, Bishop, Knight, Pawn.

    Today of course that story is laughably naive. Assuming technological civilization doesn’t collapse, there’s no reason Go can not eventually suffer the same fate as chess. It’s just a matter of doing the computations – because it is a solvable problem with a limited possibility space.

  2. Digitally recreating the entire universe is a solvable problem with a limited possibility space.

  3. Steve Johnson says:

    “At any rate many expert chess players, including Emanuel Lasker, who was World Chess Champion for 28 years, have held that Go is more interesting than chess, and it is not easy to think of any third game that is a serious rival.”

    I nominate poker or bridge.

    They represent another category of games:

    From a certain perspective go and chess are the same type of game — non-random, public information games. Poker and bridge are hidden information games with a random element (randomness and hidden information go together in a game for obvious reasons).

  4. Robb Seaton says:

    A weakness in chess is that there is too much knowledge about the openings, and it is constantly increasing.

    Bobby Fischer’s chess variant deals with this problem.

  5. Candide III says:

    There they go about Crazy Stone again. When it wins in at least a 4-game match against the same pro, rather than one-offs with different ones, then I’ll take notice. Crazy Stone’s “style”, such as it is, is sufficiently unlike any human that adjustments are required, and the authors of the program don’t give pros the opportunity. Of course the situation is hopeless from the game-theoretical business point of view, because both parties have no incentives to organize a real test. Program authors want good press releases to obtain further funding, professionals want the playing fees to keep rolling in. Professionals usually manage to lose by half a point when they play amateurs for money, and they seldom play amateurs seriously, at least in Japan. By the way, if you want really first-class Go pros these days, you go to South Korea and China, not Japan.

  6. Boonton says:

    Has checkers really been solved? What does that mean exactly?

  7. Candide III says:

    It means that there is an algorithm, runnable on existing hardware, that wins (if its opponent makes a mistake) or draws every time against any opponent.

  8. Isegoria says:

    Pseudopolymath notes that Go skills may not transfer well:

    My one intuition from playing a little Go in high school is that it teaches you recognize a non-winning position and abandon that before losses mount. Looking at Japan in WWII, playing the game doesn’t translate that skill to real life.

  9. Candide III says:

    “All I know now is that you came here with that stupid Duke who… Aiee-e-e! Woman! I care not if you kill me! He was honorable and brave, but it was stupid to put himself in the way of the Harkonnen fist!”

    Silence.

    Presently, Jessica said: “He had no choice, but we’ll not argue it.”

Leave a Reply