Evolved artificial intelligence can play video games better than humans
randalolson.com
randalolson.com
On the theoretical side, I have a tiny bit of AI research under my belt, so I can make a few comments. The problem is simply that current AI techniques are geared towards solving isolated, "relatively simple" problems. These individual problems can be surprisingly complex, such as creating a very good algorithm for how to "micro" certain combinations Starcraft units. Even though there are ridiculous numbers of combinations, our current AI techniques are good enough to solve these.
The problem comes in when you try to combine multiple elements together. Combine your "micro"-algorithm with a general scouting and build order strategy, as well as having some kind of high-level decision making strategy which ties it all together... essentially this results in the complexity of each part being multiplied together. The number of combinations goes from "barely computable" to "won't happen, ever". What we actually need is something which is able to detect boundaries within the search space, decide where to start up new sub-algorithms, and how to combine them. To my knowledge, this field isn't very mature yet.
I believe we'll be getting interesting clues from how biological intelligences solve this problem within our lifetimes (not to say it will be completed solved by then). It will be very interesting, to say the least!
One "exception" to this rule is StarCraft [1]. But only because somebody hacked the core of starcraft to enable this. If you want to play a starcraft bot - be warned. They're not programmed to be fun, they're programmed to win.