Well, it looks like 2007 will mark the year that checkers was finally solved.
A team at the University of Alberta has developed a computer that has solved checkers. The computer, called Chinook, can do no worse than draw an opponent. From the Nature article:
"The team directed Chinook so it didn't have to go through every one of the 500 billion billion (5 * 1020) possible moves. Not all losing plays needed to be analysed; instead, for each game position, Chinook needed to work out only a move that would allow it to win. In the end, only 1/5,000,000 of the moves were computed."
Jaap van den Herik, editor of the International Computer Games Journal, calls the achievement "a truly significant advance in artificial intelligence." He predicts that chess will be solved some time between 2060 and 2070 -- a game with a complexity tree of 10^46 (although some estimates place it as high as 10^123, which is insane -- that number of bits could define the entire universe in computational terms).
Given the success of Chinook and the ability to 'compress' its thinking, I believe chess is in danger of being solved well before van den Herik's prediction.
I expect this to happen sometime between 2035 and 2045 when computers really start to get scary -- on the scale of billions of times more powerful than all human minds combined.