I think it's really important to realize is that a game AI isn't really there to try to win, or maybe even to "convincingly" beat you the same way a human is. Perhaps you could train an AI to make the game more "fun", but that's pretty hard to measure and people are so different. It's a really hard optimization process.

One commonality, it seems, is that players want to get better at the game. Perhaps, an AI that TEACHES the user to improve their play, and reduce errors would be an easier problem. So far we mostly do this using heuristics of gradually increasing difficulty, but it should really depend on what the player is weakest at... and what the user can improve at fastest! That is something nicely measurable, which you might use to train an AI.

Then, if/when people play against other human players they are as strong as they can be... often an FPS goal.