I often wished that I had a cyborg-mode: gaming with a very programmable interface. (With basically something like Emacs and a REPL.) I could teach the computer new things as I explored, and eventually start to play in a very high-level way.
A friend worked on a gaming company where you train an algorithm to play a fighter in a mortal combat style game. The way you train it is by playing against it. Then you release it into the wild to fight other AIs using your style. When it came back, it was better than you, but not for long.
Product didn't go anywhere, but the architecture could easily be copied. It would be ridiculously cool to build this into Star Craft. There would be so many more people exposed to the AIs if all the knowledge needed to "program" them was in the game play itself.
Thinking out loud, for a fighting game you have two obvious measurable criteria (your health bar and the health of your opponent) which constitute a 2D coordinate system. Any action you take which is expected to reduce your opponent's health more than your own is going to be a beneficial one (unless it will push you to death, in which case you need to go for attacks that have minimal cost to your own health).
The game state would be the positions of both players on the x-axis and the health bars for both players. If you had jumping and kneeling, you might want to record positions & momentums for both players in x & y.
Now a very simple kind of AI could look for periodic subsequences that could return it to the same position while causing more damage to the opponent than to itself. That is, do some sequence of moves (strike, jump, block, etc.) and then return to the original game state except that both health bars have changed.
Then do this again, as you've "reduced it to a previously solved problem".
This of course would be too simple a thing to do because the opponent's responses would (a) be nonrandom and (b) he would not return to the exact same position. So you would need to build up a statistical database of expected countermoves to each moves (and update that for each new opponent). You would also probably want a similarity function for game states.
I guess overall this shouldn't be too difficult to do if you recorded the game states of many real games between two players, because the game rules don't change over time. Once you've got a few difficult-to-counter loops that cost them more health than they cost you, you can run them over and over again.
I agree with some of it... you'd need to keep track of the the location of each player on the x-axis and y-axis, momentums, etc... Additionally you'd want to keep track of the "visible" actions. For example, if the human hits the soft punch button, you can see the fist cocking before the punch. Similarly for other actions.
This gives you various points in the state space. The way I see doing this is:
1) Make the continuous variables discrete. You need enough granularity to have good responses of course...
2) Use genetic programming to pick reactions in each state. However, the reaction in each state is not a single action but a probability distributions over various actions (move left, move right, jump, punch, kick, etc...).
The randomness is key. I spent some time talking to a guy who plays in tournaments and he said that the absolute worst thing you can do is get into a cycle or become predictable.
