The game Connect Four is a pretty neat little game, which was solved back in 1988 by two different individuals: James Allen and Victor Allis. It makes a pretty nifty benchmark too, called Fhourstones. My modern desktop evaluates over 10 million positions per second, and can solve the entire game in about 3 minutes. Pretty cool.