There was a post on Gamasutra by one of the Civ IV devs talking about this very problem. It turns out that most players don't really want an enemy that makes perfect moves most of the time. The problem with AI is not making it hard enough, but making it feel good to win against. That's a much more difficult problem than making a good AI in many games.

I would argue against this -- you can make very effective AI without machine learning. I think that perhaps what your are trying to say is that current AI feels too "hand-scripted" -- if X, then Y. Agree about emergent behavior totally, but emergent behavior can be produced without machine learning. Simple example:

Enemies set of motivations: kill the player

Knowledge base: 1) An organism can be killed with an excessive amount of directed energy (heat, force, etc). 2) The player is an organism 3) Some general rules about the physical world (how gravity works, how fire works, what switches and levers activate which objects, blah blah blah).

Now, the enemy might take some pre-programmed path to kill the player (like fire a gun at the player). Or, if circumstances dictate that it is best, they might produce a more "creative," emergent approach. Say, for example, the enemy pulls a lever. This was never added in by the programmer. The lever activates a trap door, above the players head, and a bunch of boulders crush the player. Switch action -> directed energy -> kill organism -> player death.

In shorter words, it really comes down to the programmer determining an effective knowledge base (abstraction), and letting the AI run wild with reasoning. :) This is not to say machine learning wouldn't be the icing on the cake, but you could just as well let enemies (or NPCs) have the knowledge before the game is launched without having to learn it.