Interesting ideas. I wonder if the perfect AI would study its opponent's moves and learn to move just as they would, then it would be like the human is playing against themselves.
It would be really hard ... because it involves studying your intentions rather than your moves.
In chess this is doable (the intent is clearer after the fact, and the possible moves are more limited), but think about CStrike for example ... how is your algorithm going to realize that you're protecting a gate because you don't want your opponents to sneak behind your teammates? Even simple questions become hard ... say you're attacking X1 just as a distraction, while your teammates are attacking X2 ... a team uses slight variations of some tactic, it's mostly never the same (different men in charge, different hotspots, switching between X1 and X2, etc ...). Gathering useful statistics about it requires lots of played games and lots of resources, and I don't think it's doable on your average gamer's hardware.
This is the reason it's difficult to come up with fun AI for head-to-head fighting games: once you get past the thin veneer of mastering the moves, they're entirely about mindgames. A FSM-based CPU opponent does not have a thought process a human player can predict and exploit, nor the ability to avoid repeated mistakes.
I believe this applies to many other types of games as well, but games with many split-second paper-scissors-rock decisions suffer the most. A computer can be programmed to scout out and react to a carrier buildup in Starcraft, but cannot easily be programmed to outguess a jab/throw mixup in Street Fighter.
My vague recollection is that RPS is the subject of AI competitions. You can't "beat" random selection, but you can't lose to it either. So if you want to win a tournament, you have to try to guess what your opponents will do, assuming that they too want to win, and are guessing your actions.
