The best AI I have seen is probably in WC3. However, I feel that in many games, it isn't the AI that is good, but rather that the computer players sort of cheat by having knowledge of everything in their environment; for example, they know (from the beginning) where the bases of other players are, instead of having to search like a human player. This gives them a huge edge - think of it as a human player playing against another with a map-hack, very unfair.