According to a recent article, a computer program can now play a decent game of Go on a 9×9 grid. I really wasn’t sure this would ever happen. Andrew and I went to a talk about programming computers to play Go, about twelve years ago, and I remember that the programmers of two of the best computer Go programs were proud just because when their programs played each other, they usually played on the same portion of the board: apparently just figuring out what part of the board is worth fighting over is a hard problem, or at least hard to program.
I guess I should explain that in Go, two players take turns placing colored stones at the intersections of a grid, trying to control as much space as possible. If a group of one player’s stones are completely surrounded by the other player’s stones, the surrounded stones are removed from the board. You basically play until the board is full (well, not quite, but close enough). For more details, you can check wikipedia. For various reasons that were fairly clear when the programmers explained them, this is not an “easy” problem like chess.
In chess, there are maybe 20 possible moves at a given point in the game, and each leads to 20 choices for the other player, and so on. Each “I do this, he does that” is called a “move” —the “I do this” part or the “he does that” part is called a “half move” — so each move creates about 400 branches. A dedicated chess computer can evaluate several billion positions per second (isn’t modern technology amazing?), so in about 4 minutes it can investigate every single branch to a point 5 moves down the road (that’s 10 half-moves). At that point it can throw out 99.9999999% of the possibilities — like the ones that leave it down a piece with no compensation, or the ones that leave its opponent down a piece with no compensation (because its opponent wouldn’t choose those branches either) —- and can then spend another minute or so looking farther down the promising alleys, going as far as 20 half-moves in some cases. Back when computers were a lot slower — in the late 1980s, for example — programmers put a lot of effort into figuring out how to evaluate each position so they could “trim the tree” earlier, and there was a general sense that we would learn about chess, and about “artificial intelligence,” by working on the evaluation function. But “speed kills”, and although the evaluation function for a top chess computer is indeed fairly sophisticated, the main improvement in the programs has been to simply look deeper.
With Go, the biggest problem is that there is no obvious way to “trim the tree.” Oh, sure, there are a few situations in which, looking several half-moves down the road, you can tell that one player has “wasted” their moves because their pieces have been captured…but there aren’t very many of these. If players just plunk down pieces at random for a while, even a long while, the odds are pretty good that neither player will have any pieces actually captured, so the number of pieces on the board will still be equal. That means that the approach that was so successful in chess — just look at every possibility as far down the road as you can, and pick the possibility that gives you a material advantage (or other easily measured advantage) even if the other player plays optimally too — can’t work in Go, because there is no “easily measured advantage.”
I haven’t had a chance to read the paper describing the approach taken by the new Go program, “Bandit based Monte-Carlo Planning” by Levente Kocsis and Csaba Szepesvari, but it seems like it should be worth at least a glance.
Fascinating. I hope the guys set up a robot on one of the internet Go servers so I can have a go ;-) at the program. I just fired off an email to Kocsis asking just that.
However, I won't hold my breath until I've been whacked myself. Although programs have been getting stronger recently (esp. GnuGo), they are still far away from beating an amateur with 3 years experience. I find being close to pro strength hard to believe.
We are living in interesting times.
Phil,
Just to update this story: when I was in Taiwan, my friend's 8-year-old son beat me at go. It was a close game, but still . . . he was only 8 years old!
Indeed, the world of Go programs is moving fast these days. For instance there are some people also using probabilistic pattern matching for Go at Microsoft
http://research.microsoft.com/mlp/apg/learning_to…
Pierre
Ps: what is the syntax for links?
Good 9×9 board computer go players aren't really news. I've enjoyed the igowin software – this is a simple free program very easy to install and use. Moreover, the nice thing about go is that you can always handicap yourself to play with a computer that might be worse. But I was easily beaten with igo even without handicap.
There is a more extensive Wikipedia list of go programs.
Thore Graepel of Microsoft Research (and the Learning to Play Go project) says that Monte Carlo go is shodan (master) on 9×9. MoGo does use the UCT algorithm mentioned in the blog entry.
Note: 9×9 grid is the smallest kind, for quick 5 minute games…
19×19 is the full size game that people usually play and that is where computers are still at loss.
In other words: no, computers still can't play go.
While the article and paper are interesting, it is still premature to claim that computers can play Go. Monte Carlo methods have achieved certain levels of success with Go, but they are more or less just a faster, probablistic way of pruning/tree search. Monte Carlo methods do have their limitations in the Go domain, discussed somewhat extensively in a paper, "Monte Carlo Go Has a Way to Go" that was presented at AAAI 2006. See the following URL for the paper,
http://www.fun.ac.jp/~kishi/pdf_file/AAAI06Yoshim…
That said, it would be nice to find an actual research paper discussing how UCT stacks up to other Go-playing programs. The article linked merely says that they are "not far from reaching the professional level." Programs like GNUGo and Many Faces of Go are also not far from the professional level (I believe Many Faces of Go is only three or four "levels" away from professional play). So yeah, if anyone knows of an objective evaluation of this method in the Go domain, could you post a link to the paper?
I would like to reinforce what Aleks said above — the 9×9 game is very different from larger boards. For example, I can regularly trounce GNUGo on 13×13, but not on 9×9.
The reason for this is that the 9×9 board is much smaller, which plays to the computer's strength. The branching factor is much greater with larger boards.
Large boards play to the human strength — strategic thinking and an almost mystical internal intuition about what a move "means", rather than an analytical conclusion.
-Josh S-
This is a bit dated. The current "best" Monte Carlo/UCT go program on 19×19 boards is Sylvain Gelly's MoGo release 3. It routinely wins by 0.5 point (a win is a win is a win…) against GNU Go 3.7.10, and achieves 3 kyu or so against human players on KGS. However, on a faster computer with more internal memory and more time allotted per move, it may be better than that against human players. The claim is that the algorithm is perfectly scalable (like Archimedes level). I'm not so sure, but my confidence that a shodan computer player against people won't arrive in the next decade is less than it was. The number of positions, incidentally, is 3 ** (19*19) less one, because the empty board is not a game (no stone has been placed, so there's no contest.) Some of those positions are useless for Go (such as spelling out meri kurisumasu with go stones, etc.), which makes UCT interesting.