Having an AI defeat the strongest human players (without cheating) isn't often the hard part, its making it fun, believable, interesting or, indeed, beatable (its no fun if you can never ever win) is often the hard part. A perfectly minmaxing AI that makes perfect decisions isn't very interesting to players. Outsmarting players in interesting ways is, well, interesting, but just always playing the best move in any given scenario (like what deep blue did with its search-based "AI") can create perfect play if the search space is within the bounds of time/memory of the AI, but that's not very interesting to play against or watch.