go chess
While the chess human-computer show duell between the world champion Kramnik (human) and Deep Fritz (software) has reached its half time (three of the six matches have been played with two remis and one win of deep fritz) one can read every where that the computers becoming unchallenged winners is only a matter of time. With another (in western europe less known) board game the situation is still quite different: The best programs playing the game of go can only compete with stong human amatuers.
In the game of chess modern computers have the chance to compute and evaluate up to about 9 moves ahead (this means generating all possible moves together with all their possible answers together with all their possible following moves…and so on). This brute force approach together with sophisticated evaluation funtions (the part of the software that assigns a value to a given configuration on the board and thus judges how good or bad the computer “thinks” the position is) makes up the main part of the incredible strength of todays chess programs.
But it turned out that the strategies that make a computer program a good chess player basically fail to make a good go program. This has several reasons: First and foremost the number of possible moves is by magnitudes bigger than in chess games ( go is played on a 19 by 19 grid and in the beginning you can place your stones basically every where). Most of the moves are usually close to nonsense but this makes a brute force search though all possible moves slow and difficult. But then, writing a good evaluation function is much harder as well, since in go what a good position is depends more on your overall strategy than a programmer likes. Breaking things down to local considerations (“hey, the opponent played in the upper left corner, so lets focus on that part of the board only”) only works sometimes since the evaluation of a (seemingly) local configuration can sometimes only be decided by taking the whole boad into account.
So besides the standard techniques to manage the huge search tree (like tree pruning (this kind not that one) a go program needs clever heuristics (a fact that gives go programs more kind of a personality — and they are often said to resemble the playing style of their programmers). Here is a list of go programs
A good free candidate is of course gnu go and it is used by several go playing front ends.
So computer go programs are still relatively weak (not for me though but I count as a bloody beginner since I never found time to really get into it — for the last 15 years).
Luckily the game of go has a feature that lets unequal (in strengh) opponents play interesting matches against each other: the stronger player gives the weaker one a couple of stones head start.