Computer Go reference bots

Interested in Computer Go? Then you probably already know about Don Dailey's excellent work on providing a number of Monte Carlo reference implementations. So far, he has managed to implement it in two three different languages (Java, C and some language called Vala).

The announcement is here and the Java bot is available here. It's not the prettiest Java code out there, but Don is a C programmer (I think) so he is excused. It was very interesting and educating to study the code. I've been reading a lot of the Monte Carlo Computer Go papers but I've always felt as if I've missed something fundamental since my understanding of how it works felt too... simple.

Now that I've seen the code I can say, with confidence, that it *is* quite simple. Implementing a Monte Carlo method, that is. Getting a decent (let alone, good) AI-player for 19x19 Go seems quite far from simple.

CrazyStone vs Aoba Kaori

Yet another Computer Go program wins a handicap game (8 stones) against a professional Go player. Earlier today, CrazyStone (running on a PC with 8 processors) played Aoba Kaori (4P) at the FIT2008 conference (here are some photos) and won by resignation.

In a couple of weeks, MoGo plays Myungwan Kim (again) at the Cotsen Go Tournament. It will be interesting to see whether or not they can repeat the success from the US Go Congress. I have a feeling that Kim will have adapted to MoGo's playing style.

MoGo beats Myungwan Kim (8P) at US Go Congress

From the AGA newsletter (via the ComputerGo mailing list):

COMPUTER BEATS PRO AT U.S. GO CONGRESS:
In a historic achievement, the MoGo computer program defeated Myungwan Kim 8P (l) Thursday afternoon by 1.5 points in a 9-stone game billed as “Humanity’s Last Stand?” “It played really well,” said Kim, who estimated MoGo’s current strength at “two or maybe three dan,” though he noted that the program – which used 800 processors, at 4.7 Ghz, 15 Teraflops on a borrowed European supercomputer – “made some 5-dan moves,” like those in the lower right-hand corner, where Moyogo took advantage of a mistake by Kim to get an early lead. “I can’t tell you how amazing this is,” David Doshay -- the SlugGo programmer who suggested the match -- told the E-Journal after the game.

“I’m shocked at the result. I really didn’t expect the computer to win in a one-hour game.” Kim easily won two blitz games with 9 stones and 11 stones and minutes and lost one with 12 stones and 15 minutes by 3.5 points. The games were played live at the U.S. Go Congress, with over 500 watching online on KGS. “I think there’s no chance on nine stones,” Kim told the EJ after the game. “It would even be difficult with eight stones. MoGo played really well; after getting a lead, every time I played aggressively, it just played safely, even when it meant sacrificing some stones. It didn’t try to maximize the win and just played the most sure way to win. It’s like a machine.”

The game generated a lot of interest and discussion about the game’s tactics and
philosophical implications. “Congratulations on making history today,” game organizer Peter Drake told both Kim and Olivier Teytaud, one of MoGo’s programmers, who participated in a brief online chat after the game. At a rare loss for words in a brief interview with the EJ after the game, Doshay wondered “How much time do we have left? We’ve improved nine stones in just a year and I suspect the next nine will fall quickly now.”

- reported by Chris Garlock

Amazing! Though, the last quote (by David Doshay) should probably be taken with a grain of salt.

[Update 2008-08-09] Apparently, David was misquoted.

Human-Computer 19x19 Go Showdown

From the Computer-Go mailing list:

On Thursday, August 7, at 1:00 PM (Pacific time), Kim MyungWan 8p will take on MoGo, the world’s strongest computer Go program. MoGo will connect remotely from France, where it will be running on a supercomputer boasting over 3,000 processor cores. The game will be broadcast on KGS.

Sweet! I guess I'll get an answer to some questions quite a bit sooner than I expected.

What would *you* do with a thousand cores?

Anwar Ghuloum's post Unwelcome advice has caused a bit of a stir recently. Probably not in the way he wanted though. The comments are full of questions and doubts about whether they (Intel) can back up their claims of soon-to-come-thousands-of-cores-processors. And, more importantly, if they *can* - programming in itself will be very different from how we do it today so it's meaningless to think about it in terms of how it's done now.

But, regardless of all that... More than a thousand cores in a single processor. What would *you* do with that? One area that I think looks particularly promising is Computer Go. That many cores may well be the tipping point of AI players in Go. Will they finally be able to move up into the (professional) Dan levels?

In the upcoming tournament at the European Go Congress (in Leksand, Sweden) they're provding hardware with 2 cores. If we ignore practical scaling problems for a minute, what would the effect of an additional 998 cores be? Many of the top players today (like MoGo and CrazyStone) rely on "easily" parallellizable statistical methods (see UCT and Monte Carlo methods for more info). And the more playouts you can perform within a given time the better the resulting play. At least in theory.

I may well be underestimating the problem. I know. But it would be very interesting to see how much of an improvement can be made by just adding more raw power.

Cracking Go?

The October issue of IEEE Spectrum has a very interesting article about Go AI players and whether or not one can be created that will beat the best human players. The article is written by Feng-Hsiung Hsu. He was one of the people in the team behind Deep Blue, the chess-playing program that beat Garry Kasparov in 1997, so I guess he knows what he's talking about.

I was a bit disappointed though, after having read the article, since I got the feeling that the solution was more or less the Deep Blue program running on faster hardware and having been enhanced using null-move pruning and caching results of life-and-death analysis. It all sounds a bit... too simple. Life-and-death analysis is tricky business indeed and it doesn't help at all when he basically says that all the leading Go programmers today are too narrow minded in what they do and that their approach(es) won't ever lead to any decent Go AI players.

Until he provides some more details about this I'm going to have to agree with Luke Biewald that he himself may very well have underestimated the problem. It will however be very interesting to see what they come up with in the next few years in the research efforts that Microsoft (where he works) sponsor.

More books arrived today!

When I started reading The Reasoned Schemer I realised that I had skipped The Seasoned Schemer. Not that that's not allowed or anything but I really felt that I needed to complete the series with it.

When I ordered it I also decided to give myself The Second Book of Go. I'm still rubbish at it though.