One of my coworkers today (who knows I play Go) mentioned to me that he saw an article on digg stating that there had been some new breakthrough in Go-playing computer technology, bringing computers much closer to professional-level play. He couldn’t remember any details of the article, but with a bit of digging (no pun intended), I managed to locate the article he had read.
Two Hungarian scientists have come up with an algorithm that helps computers pick the right move in Go, played by millions around the world, in which players must capture spaces by placing black-and-white marbles on a board in turn.
“We are not far from reaching the level of a professional Go player,” Levente Kocsis of the Hungarian Academy of Sciences computing lab Sztaki said.
I happen to be subscribed to a computer Go mailing list, where researchers from around the world discuss the current state-of-the-art in artificial intelligence with relation to the Go world. Unfortunately, I hadn’t been following along recently, so I hadn’t seen the article before my coworker pointed it out to me. Intrigued, I wondered if there really was some cool new algorithm that had been discovered, or if it was simply another incremental step in the quest to get halfway-decent Go-playing computer programs.Sure enough, when I got home and started pawing through the mailing list archives, one of the first posts was lamenting how the article had completely butchered Kocsis’ quote. From a Yahoo article on the same subject:
“On a nine by nine board we are not far from reaching the level of a professional Go player,” said Levente Kocsis at the Hungarian Academy of Sciences’ computing lab SZTAKI.
Aha! This is a considerably different statement. Go is played on a 19×19 board. Beginners will often start with a 9×9 board, and then move up to a 13×13 board, before playing on the full-size board. But 9×9 Go, while structurally the same game, is considerably less deep and considerably easier for a computer to process. How much easier?
Well, 6×6 Go is completely solved—or, in other words, computers have calculated the exact sequences of moves that will result in the highest score possible. 7×7 Go has allegedly been solved within the past few years, but nobody (to my knowledge) has exhaustively proven that the sequences they discovered are, in fact, the optimal lines of play.
9×9 Go is only slightly larger than 7×7 Go, but it is so exponentially more difficult that professional Go players routinely trounce the world’s best 9×9 Go programs. As Kocsis’ quote says, we haven’t yet reached the point where computers play 9×9 Go at a professional level. We may be getting close (mostly, in my opinion, due to faster computers—not any special new algorithms), but we haven’t reached it yet.
13×13 is even further from 9×9 than 9×9 is from 7×7. And, predictably, computers do exponentially worse at 13×13, getting crushed by strong amateur players. By the time you get all the way up to 19×19, the world’s best computers are still only about my level. New algorithms or no, we still have a long way to go before Go-playing computer programs are even interesting to watch, much less solid opponents for the world’s best amateurs.
Entries (RSS)