Computers are very good at the game of Go —
There’s an attraction between computer programmers and the Asian game of Go. I think there’s a lot to like about the game — it has very simple rules, high complexity (it’s “deeper” than chess) and pleasing symmetry and aesthetics. I think the real reason programmers are so drawn to it might be a little more self-involved, though: being good at things that computers aren’t good at tends to make programmers happy, and computers are terrible at Go.1
Or at least, that’s the folk knowledge that’s been true for most of my life. Computers have always been worse than an average amateur with a few years of experience, and incomparably bad to true professionals of the game. Someone I was talking to brought up the ineptitude of computers at Go a few days ago, talking about new ideas for CAPTCHAs: “just make the human solve Go problems”, they said, and you’re done; computers can’t do that, right?
So, I’ve enjoyed this feeling of technological superiority to computers as much as anyone, and it hurts me a little to say this, but here I go: the idea that computers are bad at Go is not remotely true anymore. Computers are excellent at Go now. To illustrate this, there’s some history we should go into:
Back in 1997 — the year that Deep Blue beat chess world champion Garry Kasparov for the first time — Darren Cook asked Computer Go enthusiasts for predictions on when computers will get to shodan (a strong amateur level) and when they’ll beat World Champion players. John Tromp, an academic researcher and approximately shodan-level amateur, noticed the optimism of the guesses and wondered aloud whether the bets would continue to be optimistic if money were on the line, culminating in:
John Tromp: “I would happily bet that I won’t be beaten in a 10 game match before the year 2011.”
Darren Cook took the bet for $1000, and waited until 2010 before conducting the match against the “Many Faces of Go” program: Tromp won by 4 games to 0. That seemed to settle things, but the challenge was repeated last month, from January 13th-18th 2012, and things happened rather differently. This time Tromp was playing a rising star of a program named Zen19, which won first place at the Computer Go Olympiad in 2009 and 2011. The results are in, and:
Zen19 won by 3 games to 1. (For more reading on the challenge, see David Ormerod’s page or Darren Cook’s.)
Beating an amateur shodan-level player is shocking by itself — that’s my strength too, and I wasn’t expecting a computer to be able to beat me anytime soon — but that isn’t nearly the limit of Zen19’s accomplishments: its progress on the KGS Go server looks something like this:
To put the 5-dan rank in perspective: amongst the players who played American Go Association rated games in 2011, there were only 105 players that are 6-dan and above.2 This suggests that there are only around 100 active tournament players in the US who are significantly stronger than Zen19. I’m sure I’ll never become that strong myself.3
Being able to gain four dan-level ranks in three years is incredible, and there’s no principled reason to expect that Zen19 will stop improving — it seems to have aligned itself on a path where it just continues getting better the more CPU time you throw at it, which is very reminiscent of the story with computer chess. Even more reminiscent (and frustrating!) is the technique used to get it to 5-dan. Before I explain how it works, I’ll explain how an older Go program worked, using my favorite example: NeuroGo.
NeuroGo dates back to 1996, and has what seems like a very plausible design: it’s a hierarchical set of neural networks, containing a set of “Experts” that each get a chance to look at the board and evaluate moves. It’s also possible for an expert to override the other evaluators — for example, a “Life and Death Expert” module could work out whether there’s a way to “kill” a large group, and an “Opening Expert” could play the first moves of the game where balance and global position are most important. This seems to provide a nice balance to the tension of different priorities when considering what to play.
Zen19, on the other hand, incorporates almost no knowledge about how to make strong Go moves! It’s implemented using Monte Carlo Tree Search, as are all of the recent strong Go programs. Monte Carlo methods involve, at the most basic level, choosing between moves by generating many thousands of random games that stem from each possible move and picking the move that leads to the games where you have the highest score; you wouldn’t expect such a random technique to work for a game as deep as Go, but it does. This makes me sad because while I wasn’t foolish enough to believe that humans would always be better at Go than computers, I did think that the process of making a computer that is very good at Go might be equivalent to the process of acquiring a powerful understanding of how human cognition works; that the failure of brute-force solutions to Go would mean that we’d need a way to approximate how humans approach Go before we’d start to be able to beat strong human players reliably by implementing that same approach in silico.
Update: “bitti” comments below that Zen19 is choosing which move to play based on maximizing win probability, not maximizing score.
I think that programs like Zen19 have actually learned even less about how to play good Go than computer chess programs have learned about how to play good chess; at least the chess programs contain heuristics about how to play positionally and how to value different pieces (in the absence of overriding information like a path to checkmate that involves sacrificing them). This lack of inbuilt Go knowledge shows up in Zen19’s games — it regularly makes moves that look obviously bad, breaking proverbs about good play and stone connectivity, leaving you scratching your head at how it’s making decisions. You can read a commented version of one of its wins against Tromp at GoGameGuru, or you could even play against it yourself on KGS.
Update: Matthew Woodcraft comments below that Zen19 does contain significant domain knowledge about Go. It’s hard to know exactly how much; it’s closed-source.
Zen19 is beating extremely strong amateurs, but it hasn’t beaten professionals in games with no handicap yet. That said, now that we know that Zen19 is using Monte Carlo strategies, the reason why it seems to be getting stronger as it’s fed more CPU time is revealed: these strategies are the most obviously parallelizable algorithms out there, and for all we know this exact version of Zen19 could end up becoming World Champion if a few more orders of magnitude of CPU time were made available to it.
Which would feel like a shame, because I was really looking forward to seeing us figure out how brains work.
1: I think this is probably why I’ve never been interested in puzzles like Sudoku; I can’t escape the feeling of “I could write a Perl script that does this for me”. If I wouldn’t put up with such manual labor in my work life, why should I put up with it for fun?
2: Here is the query I used to come up with the 105 number.
3: In fact, KGS ranks are stronger than the same-numbered AGA rank, so the correct number of active players in the US who are stronger than Zen19 may be even smaller. Being stronger than US players isn’t the same as being stronger than professional players, though — there are many players that are much stronger than amateur 5-dan in Asia, because there are high-value tournaments and incentives to dedicating your life to mastering Go there that don’t exist elsewhere.