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.
RSS