A video game AI that is fun to play against is a good AI. AI War for example. The enemy is fun to play against because it has a strong element of predictability, so it isn't necessarily smart in the most conventional sense, but it is really good because you can stack behaviors on top of behaviors until you need to pause the game for 30 minutes just to come up with a plan that accounts for every reaction the AI will produce.