How far are we from "use AI to play multiplayer games against you in a more interesting way than "traditional game AI" (cheating via godmode vision, outright juiced stats, high inherent apm, etc.)?

What would be fun would be an RTS where the computer learns new strategies and counters and where the only "cheating" is it matches your APM (if not inherently limited by the game, more like a 4X than an RTS) so it was actually strategy/tactics which wins.

And the game doesn't have to actually be "win every time", but "plays in an interesting way"; e.g. for a game like HoI, more accurately simulating historical nations.