If you wanted to beat the best software in the world at a classic board game, there was only one left for you — the strategy game Go. It has long been considered the last bastion of human gaming superiority, holding out against the onslaught of computational brute force and artificial intelligence techniques, while draughts, Othello, backgammon and chess have all fallen.
But to be a human winner at Go, you’re going to have to get good, very good, in a hurry as the end, with computers ruling, is in sight.
In February, the software MoGo, developed at the University of Paris-Sud, achieved what was once thought impossible: it won two games, on a 19x19 board, against professional Go players. (It did benefit from a handicap — in effect, a number of free turns at the start of the game.) The same month, a program called Many Faces of Go, with a seven-turn handicap, beat a professional in a game played during the general meeting of the Association for the Advancement of Artificial Intelligence. (See the human-computer Go challenges Web page at bit.ly/Go28.)
The wins did require a lot of computing power, however. MoGo was running on 640 cores of the Huygens supercomputer in Amsterdam; Many Faces of Go on a 32-core 3.2GHz Xeon, eight quad cores networked together.
Next month the bar is likely to rise again as programmers fine-tune their code for the annual International Computer Games Association tournament, the computer olympiad, in Pamplona, Spain (bit.ly/Go26).
Yet even a few years ago Go looked like an impossible computing task: the “search space” for each move was too big. At each turn, especially in the beginning, there are hundreds of possible places to play (the board has 361 points, compared to chess’s 64), and deciding on which will turn out better a number of moves ahead — a comparatively simple task in chess and draughts — turns into a morass, with hundreds of almost-equal possibilities and a few hundred moves over which to compare them. Standard “minimax” methods that work for chess (picking the move that gives your opponent the fewest high-value moves in future) don’t work in Go.
What’s changed has been the development of the UCT algorithm (bit.ly/Go24), a special case of the Monte Carlo Tree Search (MCTS) algorithm. UCT first appeared in 2006 applied to small 9x9 Go boards, and now academics, and professional Go programmers, are extending and refining its techniques. It has led to a revolution in Go program development.
David Fotland, the US-based commercial developer behind Many Faces of Go (bit.ly/go222), says the results represent a major leap. But he’s realistic about the achievement. “My machine can beat a good amateur, but not a great amateur.”
Last year he spent six months incorporating UCT into his software, combined with his traditional Go algorithm (“the new algorithm has some blind spots”), and won that year’s computer olympiad. At the event every program incorporating UCT beat all the ones using traditional methods.
Go pieces are called stones, are black or white, and identical. Playing alternately, the object is to use one’s stones to surround as many blank intersections (called “territory”) as possible. Games typically have a couple of hundred moves.
The Go rating scale for amateurs starts at 35 kyu, and moves towards 0: the highest level is 1 kyu. The next amateur rank is 1 dan, up to 7 dan. Above them are professionals, who start at pro 1 dan going up to pro 9 dan, the highest level possible.
“Handicapping” allows weaker competitors to play on a level footing with stronger ones: each difference in grading is given as one stone’s start. Thus a 20-kyu player would get nine stones in a game against an 11-kyu player.
GAME OF CHANCE
Many Faces of Go’s result puts it at about a 1-dan amateur ranking. David Silver, who’s researching Go for his PhD at the University of Alberta, says that: “Anyone who would have suggested this [could happen] a couple of years ago would have been laughed out of town.”
Silver contributed to MoGo in 2007, developing UCT, which led to the first victories against human pro players on 9x9 boards. But when he started his PhD, pre-UCT, he was discouraged from studying the game by the head of the university’s games research group. Too many good minds had been wasted on it, and the research was doomed to failure, it was thought.
For the past 30 years, Go programs have evaluated positions by using handcrafted heuristics based on human knowledge of shapes, patterns and rules. However, professional Go players often play moves according to intuitive feelings that are hard to quantify. Encoding their knowledge into machine-understandable rules has proved to be a dead end.
UCT works on the idea of playing out games over and over again, choosing moves at random, but it is biased to what’s been successful before. It does this while still allowing alternative lines to be explored.
Now, Silver says: “I feel very fortunate doing research during this revolutionary period. MCTS is in its infancy, but the rate of performance improvement is pretty rapid.” He thinks a machine to beat all humans could appear in four to five years.
Yet humans haven’t lost all their tricks. As the human vs computer Go challenges Web page notes: “In every case where each player [computer and human] won at least one game, the human lost the first game played and won the rest. This may be because of experience gained in the first game, or because of techniques learned from discussions with the other players.” But the randomization the UCT algorithm brings may make that result less likely.
Fotland thinks the UCT-based work responds to a certain amount of processor supercharging, but then plateaus. “There is a certain kind of large-scale fighting in Go that requires a kind of thinking the algorithm not good at. [The ranking] 1 dan amateur is where people start being good at these large-scale fights.”
His rival Mick Reiss, the commercial programmer behind Go++ (bit.ly/AnJ9s), released his version incorporating UCT in Japan this month. His publisher says it matches the Japanese commercial version of Many Faces of Go in strength.
Reiss doesn’t think UCT is the total answer. Of pure UCT-based programs, he says: “A lot of them play in a wacky way, which doesn’t really work. Because it’s so different to what Go players are used to, in the early games they get beaten. Once they get a bit of practice they get their revenge.”
The highest level of his own program is based on a combination of the old-style Go approach and the UCT program. “It does less of the strangeness of the pure UCT programs. It plays in a more conventional way.”
Fotland is still circumspect about when computers will dominate Go. “I’d say 20 years. There’s got to be several algorithm breakthroughs, and 20 years of Moore’s law (bit.ly/Go224).”
And then? The end of an era? Certainly. But the end of playing Go? Thankfully, as the evidence shows, we still enjoy the simple pleasure of just playing games.
In late October of 1873 the government of Japan decided against sending a military expedition to Korea to force that nation to open trade relations. Across the government supporters of the expedition resigned immediately. The spectacle of revolt by disaffected samurai began to loom over Japanese politics. In January of 1874 disaffected samurai attacked a senior minister in Tokyo. A month later, a group of pro-Korea expedition and anti-foreign elements from Saga prefecture in Kyushu revolted, driven in part by high food prices stemming from poor harvests. Their leader, according to Edward Drea’s classic Japan’s Imperial Army, was a samurai
Located down a sideroad in old Wanhua District (萬華區), Waley Art (水谷藝術) has an established reputation for curating some of the more provocative indie art exhibitions in Taipei. And this month is no exception. Beyond the innocuous facade of a shophouse, the full three stories of the gallery space (including the basement) have been taken over by photographs, installation videos and abstract images courtesy of two creatives who hail from the opposite ends of the earth, Taiwan’s Hsu Yi-ting (許懿婷) and Germany’s Benjamin Janzen. “In 2019, I had an art residency in Europe,” Hsu says. “I met Benjamin in the lobby
April 22 to April 28 The true identity of the mastermind behind the Demon Gang (魔鬼黨) was undoubtedly on the minds of countless schoolchildren in late 1958. In the days leading up to the big reveal, more than 10,000 guesses were sent to Ta Hwa Publishing Co (大華文化社) for a chance to win prizes. The smash success of the comic series Great Battle Against the Demon Gang (大戰魔鬼黨) came as a surprise to author Yeh Hung-chia (葉宏甲), who had long given up on his dream after being jailed for 10 months in 1947 over political cartoons. Protagonist
A fossil jawbone found by a British girl and her father on a beach in Somerset, England belongs to a gigantic marine reptile dating to 202 million years ago that appears to have been among the largest animals ever on Earth. Researchers said on Wednesday the bone, called a surangular, was from a type of ocean-going reptile called an ichthyosaur. Based on its dimensions compared to the same bone in closely related ichthyosaurs, the researchers estimated that the Triassic Period creature, which they named Ichthyotitan severnensis, was between 22-26 meters long. That would make it perhaps the largest-known marine reptile and would