Having a non-cheating bot beat a human is a major achievement.

(for some categories of games!)

I'm almost nitpicking here, but it's important to understand the distinction where when trying to build "human-like" AI that players feel are like the real thing, you also want to emulate human shortcomings. Sometimes it might not be cheating per the rules, but still be obviously outside the realm of current human capabilities.

e.g.: An AI opponent with perfect arithmetical abilities in a game like Scorched Earth: http://en.wikipedia.org/wiki/Scorched_Earth_(video_game)