Combos weren't part of the original Street Fighter games until humans figured them out.
And the fact that they were inherent to the system rather than being a preprogrammed set of arbitrary values in a "it's a combo because we say so" list (like every other crappy fighting game, tekken/virtuafighter/etc had done) was what made Capcom's games so strong. You could find new ones by analyzing the system. Some of them worked on some characters but not others because they were bigger or smaller than the "average" sized character, and thus might "fall out" of the combo when their smaller sprite failed to collide with hit detection.
Then they were added to later versions so that the computer could take advantage of them.
No, the AI was simply reprogrammed to know the ones that the developers/playtesters had figured out.
Rocket Jumps? I'm sure the developers coded for it from day 1.
Actually, no. They were a reaction to code written for explosions to move "movable" objects (boxes, powerups, dead bodies, and included in the list, players). The fact that they were coded to "add acceleration", and stacked directly with jump acceleration, was not explicitly coded for.
And different humans have different creative problem solving methods. This is why real AI is hard.
Oddly enough, that was what made Deus Ex so brilliant, and the sequel so piss-poor. In the first, the designers really worked hard to give the players options - different paths for the run-and-gunners, methods for the stealthers/snipers to get around to spots to take guards out, and so on. The sequel, meanwhile, was just linear level after linear level.
You can't code for all contingencies.....and a truly adaptable AI would need to have learning skills to handle those scenarios that were not inherently programmed in.
A truly adaptable AI might (for example of a fighting game) in a writable section of the hard drive, store a list of the combos that the player had successfully used or that the player used most often. Given another 10 years (for processors to get even more powerful), it might analyze that for a weakness.
I'd love to see it. But I'm not going to hold my breath waiting for it, either. I'll take the decision tree + random variance that we get now, throw in a little "Easy = 3, Medium = 5, Hard = 10" Enemy scaling and I'll still play video games. When I want an opponent that is challenging, I'll go online and play against real people.
The one problem with that is that in addition to the fact that real people learn (or at least, some portion of the human population learns from their mistakes, setting aside anyone who's ever shopped at Wal-Mart), real people have Genuine People Personalities, meaning a large percentage of them are Real Assholes.