Go

Go is a two-player board game that originated in China around 2000 B.C. The earliest written references to the game are from the earliest Chinese work narrative history, Zuo Zhuan ( Chronicles of Zuo), which describes a man in 548 B.C. who played the game. The game spread to Japan, where it became popular in the thirteenth century. Two players alternately place black and white stones on intersections of a 19x19 playing board. A stone or a group of stones is captured and removed if it's tightly surrounded by stones of the opposing color. The objective is to control a larger territory than one's opponent.
Go is complex for many reasons, including its large game board, multifaceted strategies, and huge numbers variations in possible games. After taking symmetry into account here, there are 32,940 opening moves, of which 992 are considered to be strong ones. The number of possible board configurations is usually estimated to be one of the order 10^172, with about 10^768 possible games. Typical games between talented players consist of about 150 moves, with an average of about 250 choices per move. While powerful chess software is capable of defeating top chess players, the best Go program often lose to skillful children.
Go-playing computers find it difficult to "look ahead" in the game to judge outcomes because many more reasonable moves must be considered in Go than in chess. The process of evaluating favorability of a proposition is also quite difficult because a difference of a single unoccupied grid point can affect large group of stones.
In 2006, two Hungarians researchers reported that an algorithm called UCT (for Upper Confidence bounds applied to Trees) could compete with professional Go players, but only on 9x9 boards. UCT helps the computer focus its search on the most promising move.