The Chinese game of Go has proven to be a tough challenge to those in the artificial intelligence field.  Advanced AI has been developed for many other games, with perhaps the most famous being chess. However, Go is in a different league all-together. The number of possible moves in the game is immense and dwarfs that of chess, with Go containing five times the number of board positions.

Wikipedia best illustrates the immense complexity of the game with the following description:

It has been claimed that Go is the most complex game in the world due to its vast number of variations in individual games. Its large board and lack of restrictions allow great scope in strategy and expression of players' individuality. Decisions in one part of the board may be influenced by an apparently unrelated situation in a distant part of the board. Plays made early in the game can shape the nature of conflict a hundred moves later.

The game complexity of Go is such that describing even elementary strategy fills many introductory books. In fact, numerical estimates show that the number of possible games of Go far exceeds the number of atoms in the known universe.

Computer programs attempting to play Go have only performed well in handicapped matches, either by restricting the number of squares used in the game or by allowing the computer a number of free starting moves.

One of the core obstacles in developing a successful AI is that up to this point it has been infeasible to brute force a win against a good player because the machine would have consider more than 300 billion combinations just to anticipate four moves ahead.

Human players have been more successful at the game because Go masters do not perform this brute force technique, but rather have an intuitive sense of the board.  Unfortunately for computer scientists, this intuitive sense is difficult, if not impossible, to codify.

All is not lost however, for as time marches ever forward so does the speed of computer hardware and the efficacy of software algorithms.  Several Go programs are under active development, with each using lessons learned from past failures.

These programs utilize a version of the Monte Carlo Tree Search algorithm called the UCT.  Since the advent of the UCT, Go programs have been rapidly improving as the Taipei Times explains:

UCT works on the idea of playing out games over and over again, choosing moves at random, but it is biased to what’s been successful before. It does this while still allowing alternative lines to be explored.
...
MCTS is in its infancy, but the rate of performance improvement is pretty rapid.” He thinks a machine to beat all humans could appear in four to five years.

The Go site 'Sensei's library' explores some of the more technical details of the UCT and also provides source code for those of you interested in developing your own Go engine.  A partial technical description of UCT:

A Monte Carlo (MC) program searches for moves that have high win rates, calculated from playing out at least a few hundred random games.

A basic MC program would simply collect statistics for all children of the root node, but MC evaluation of these moves will not converge to the best move. It is therefore necessary to do a deeper search.

The UCT-method (which stands for Upper Confidence bounds applied to Trees) is a very natural extension to MC-search, where for each played game the first moves are selected by searching a tree which is grown in memory, and as soon as a terminal node is found a new move/child is added to the tree and the rest of the game is played randomly. The evaluation of the finished random game is then used to update the statistics of all moves in the tree that were part of that game.

The UCT-method solves the problem of selecting moves in the tree such that important moves are searched more often than moves that appears to be bad. One way of doing this would be to select the node with the highest winrate 50% of the time and select a random move otherwise.

Even with the UCT it may be quite a while before unhandicapped computers will be able to consistently beat a master Go player.  The best of the best computer programs still require move and board handicapping, but they are much stronger than programs developed just five years ago.

For those of you interested the world of computer Go, check out the sites of the programs mentioned in the Times article:

• The Many Faces of Go: 2008 World computer Go 19x19 and 9x9 champion.
• MoGo: Gold medal winner of the 2007 Computer Game Olympiad for Go
• Go++: Winner of the 9th KGS Computer Go Tournament