I've been having a write's block recently so this month I'll be publishing an article written by my good friend Gareth Davies, Mathematics Ph.D by Oxford University. It's a very interesting read and I hope you guys enjoy it as much as I did. Without further ado...

Building computers that can play Go is seen by some as the ultimate challenge in artificial intellegence (AI for short). Although some tasks are thought to be far /more/ difficult for a computer to do well, the inability of computers to play Go represents a fundamental shortcoming of current programming techniques. The reason for this is that Go is a game of "perfect information". Unlike games with dice which contain elements of chance and games with chards which contain hidden information, all the information in Go is available to both players at all times. Furthermore, the rules of Go are exceptionally simple (particulaly the Tromp-Taylor logical rules of Go; my favourite ruleset). The fact that such a game, so logical and digital in its nature, should be dominated by humans is, at the outset, most surprising. As I mentioned before, it was research into AI which led me to discover Go in the first place and it was the fact that computers were unable to play well which initially fascinated me with it.The primary obstacle to proficient computer play is the size of the board. Computers do well at many other games of perfect information by using an algorithm called minimax. The idea is to simply read everything blindly, using the immense speed of computers to compensate for their lack of feeling for the game. In a game like chess (which is played on an 8x8 board and presents the player with a limited number of moves on each turn) computers caught up to the top human level in May of 1997 when IBM's Deep Blue defeated the then world champion Garry Kasparov in a six game match. For even simpler games such as checkers the lines of perfect play have been calculated.The approach of minimax has been applied to Go: 4x4 Go is strongly solved (the correct komi is known and the computer can play perfectly against any opponent); 5x5 Go is weakly solved (the lines of perfect play are known but you might catch the computer out by starting with a strange move). 7x7 Go is squarely in the relm of minimax and computers demonstrated their dominance against the top professionals as, in June this year, MoGoTW won 20/20 such games against professional players. With 9x9 Go we already see the problem with the traditional approach. There are so many possibilites for each move that a blind brute-force approach, while very strong, falls behind the best human play.Of course, if we extrapolate from the above then it becomes clear that computers will never (absolutely never) rival humans on the 19x19 board using the blind brute-force approach. Instead, programmers have to devise new algorithms to cope with the game. After all, a human doesn't play Go by blind brute-force.Gnugo took the approach of backing up some blind brute-force with many set sequences, a life-and-death encyclopedia, some pattern matching, and, most importantly, an algorithm to identify groups on the board and roughly eval!uate their tactical stability and strategic importance. This approach was refined a lot and I believe up to 2005 when Many Faces of Go was about 15 stones weaker than the then 1-dan professionals.In September of 2007 a paper was published outlining a completely new algorithm for playing Go, now called the Monte-Carlo algorithm. The idea is rather clever. On its turn the computer will consider a move X by selecting it at random, simulating hundreds of games from that point with both players playing randomly (recording the result in each case), and then assigning a score to X depending on how many of the simulated games were won by Black. It does this for a series of different X and then selects that which has the best score. Almost at once, on modern hardware, this algorithm was able to outperform the strongest Go playing programs and the program "MoGo" was born (although it was still more than 9 stones weaker than that the top players; Catalin beat MoGo with 9 stones in 2008).The last few years have been an exciting time for computer Go. The Monte-Carlo approach was strong but early attempts of combining it with set patterns and dictionaries spawned engines that were actually /weaker/ than pure Monte-Carlo engines. One of the most successful steps forward was the idea of maintaining a database of 3x3 Go patterns and assigning a play on the central point a score to represent the believed quality of the shape. Once Monte-Carlo engines were told to less often consider empty-triangles and such they shot up by a couple of stones. There have also been some developments in the way a program continues to analyse and refine it's view of the strongest moves by dynamic tree pruning but at this point things become a little advanced. Of course, there are computer programs out there which may be using even more advanced techniques but the source code of such programs is kept secret from the public (Zen, MoGoTW, Many Faces of Go) so I do not know more.In Bordeaux the winner of the computer tournament, Zen (being driven by a modest 6 modern desktop computers), defeated Kozo Hayashi 6p taking only a 5 stone handicap!As was remarked earlier, there is no feasible way for computers to ever compete with humans using the minimax algorithm but there is definitely scope for computers to reach and surpass the strongest human players as new algorithms are discovered and improved. There is some work being done on genetic algorithms (so computer programs which evolve) and learning algorithms. How long it will take for computers to catch up to humans is anyone's guess but "never" seems very unlikely to me.

Kyoung-nang Kang
from U.K.