It's a bit of a game design problem too, since you may want to optimize for how "fun" the AI is to play against. There are patterns of behavior that can be equivalently challenging, but greatly varying in terms of how interesting or enjoyable they are to play against.

I.e. there are various chess bots that can be assigned personality dimensions like aggressiveness, novelty, etc.