What does the future hold for Human-Computer Go?

On August 7th, 2008, a Go playing computer called "MoGoTitan" beat Myungwan Kim, an 8-dan professional, in a game of Go on a 19x19 board. The computer program ran on an 800-processor supercomputer with 15 Teraflops of computing capacity. MoGoTitan received a 9-stone handicap in order to give the computer a fair chance of winning. Before the game, the only question in the Go community was how many handicap stones the human would have to give the computer in order to give it a fair chance of winning. MoGoTitan made history by being the first supercomputer ever to defeat a human professional with a 9-stone handicap.

The headline in the AGA e-Journal read "Computer Beats Pro at U.S. Go Congress". It has been widely repeated on the internet, and the general public seems to be getting the impression that it's all over for us humans when it comes to playing against 15 Teraflop supercomputers. But this is not the case. With no changes in the algorithm and with computers getting faster and cheaper by the day, it's entirely possible that it will take longer than 10 years for a supercomputer to beat a 9-dan professional (the highest rank) in an even game on a 19x19 board.

Consider this:

1. Besides the three blitz games Myungwan Kim played with MogoTitan, Myungwan Kim had no way to judge the strength of his opponent. In fact, the computer played considerably stronger than it had in the blitz games, and Myungwan Kim underestimated his opponent in at least one critical point in the game.


2. Mogo uses a Monte Carlo algorithm to estimate the likelihood of winning with each possible move. This has led to a major breakthrough in being able to parallelize the game on multiple processors. However, it's possible that there are strategic moves which are difficult to find purely at random, and humans may be able to capitalize on this potential weakness.


3. A 9-stone handicap grants control of the entire board to the computer, and forces the human to try to take away as much of the board as possible. This means that the computer doesn't have to play through the opening of the game, where strategic thinking is at its most abstract. The computer may hit a wall around a 2 or three stone handicap, as the subtle strategies used in the opening become more important.

The question has never been whether computers would one day be able to beat a top professional in an even game of Go. We all know that this day will one day come. The fascinating thing about the game of Go is that, while the number of possibilities is enormous, human reasoning is able to cut through the number of possibilities very quickly. Strategy trumps brute force calculation. I admit it, I'm one of those people who knows there is something special about Go that requires more than just brute force. I think it's interesting to note that MoGoTitan used up 55 minutes, while Myungwan Kim used up about 13 minutes. This means that in a faster game, Myungwan Kim would have the upper hand.

So, the question has been: what major advance in computer intelligence will be required to defeat a human on a 19x19 board? After the impressive performance of MoGoTitan on August 7th, I'm sad to say that the answer may be "none". However, it hasn't happened yet. Beating a human with a 9-stone handicap is many times easier than beating a human in an even game.

I do hope that MoGo continues to make progress. I will be watching closely to see whether weaknesses in the Monte Carlo algorithm begin to surface. I will be happy if these weaknesses manifest themselves. I will be sad if they don't, and a 9-dan professional is defeated by a supercomputer before any major advances in computer intelligence.

However, even if that does happen, human Go players will still rise from the ashes. Why? Because: 1) 19x19 is an arbitrary board size, and Go can be played about the same way on any odd-numbered board size, with no limit, and 2) MoGo is still brute-forcing the game of Go, and human players do not. This is the reason that Go has resisted brute force approaches in the past.

It is said that while there are more possible games of Chess than there are grains of sand on the beach, there are more possible games of Go than there are atoms in the universe. Go is played on a 19x19 board with 361 possible first moves. After that, 360 possible removes remain, then 359, 358, and so on. So, the number of possible Go games is something like 361 * 360 * 359 * 358, and so on all the way down to one. This number is 361 factorial (expressed as 361!). It's a really big number. 769 digits. So, let's say it's something around 10 to the 768th power.

If we added just two lines to the board to make the size 21x21, then the number of possible games would be more like 441 factorial. That means the game would be more complex by a factor of (441! / 361!), or about 10 to the 208th power. That's about a googol, squared. To a human, the difference of two lines is very minor. To a brute force engine, it's an enormous change in bounds that will make a huge difference in the amount of coverage of the game tree, and put the humans back on top.

So, hooray for MoGo and the developers behind it! I applaud your efforts, and I hope you continue to make progress! But at the end of the day, don't be surprised if the Go board just gets a little larger as a result.

21x21 Go, anyone?