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.
Wooden houses wedged between concrete, crumbling brick facades with roofs gaping to the sky, and tiled art deco buildings down narrow alleyways: Taichung Central District’s (中區) aging architecture reveals both the allure and reality of the old downtown. From Indigenous settlement to capital under Qing Dynasty rule through to Japanese colonization, Taichung’s Central District holds a long and layered history. The bygone beauty of its streets once earned it the nickname “Little Kyoto.” Since the late eighties, however, the shifting of economic and government centers westward signaled a gradual decline in the area’s evolving fortunes. With the regeneration of the once
Even by the standards of Ukraine’s International Legion, which comprises volunteers from over 55 countries, Han has an unusual backstory. Born in Taichung, he grew up in Costa Rica — then one of Taiwan’s diplomatic allies — where a relative worked for the embassy. After attending an American international high school in San Jose, Costa Rica’s capital, Han — who prefers to use only his given name for OPSEC (operations security) reasons — moved to the US in his teens. He attended Penn State University before returning to Taiwan to work in the semiconductor industry in Kaohsiung, where he
On May 2, Chinese Nationalist Party (KMT) Chairman Eric Chu (朱立倫), at a meeting in support of Taipei city councilors at party headquarters, compared President William Lai (賴清德) to Hitler. Chu claimed that unlike any other democracy worldwide in history, no other leader was rooting out opposing parties like Lai and the Democratic Progressive Party (DPP). That his statements are wildly inaccurate was not the point. It was a rallying cry, not a history lesson. This was intentional to provoke the international diplomatic community into a response, which was promptly provided. Both the German and Israeli offices issued statements on Facebook
Perched on Thailand’s border with Myanmar, Arunothai is a dusty crossroads town, a nowheresville that could be the setting of some Southeast Asian spaghetti Western. Its main street is the final, dead-end section of the two-lane highway from Chiang Mai, Thailand’s second largest city 120kms south, and the heart of the kingdom’s mountainous north. At the town boundary, a Chinese-style arch capped with dragons also bears Thai script declaring fealty to Bangkok’s royal family: “Long live the King!” Further on, Chinese lanterns line the main street, and on the hillsides, courtyard homes sit among warrens of narrow, winding alleyways and
RSS