Some of the ignorance in this thread is astonishing.
Like another poster said a bit ago, actual programming of AI is not nearly as time consuming as some have tried to claim, at least once you have the basic AI system set up. And I can say this, because its my job. I am an AI programmer for a games company. I've done fighting game AI before.
I'm not saying writing good AI is easy. Its not. However, the AI in SSBM could DEFINITELY be improved and it would not require anywhere near as much effort as some here have said. Code isn't done that way. Its modular. Code is built on top of other code. Well written code would require putting a small bit of code in one particular place and it would affect all situations.
As someone else pointed out, for example, you wouldn't need to change actual code to account for different stages. Instead, each stage has DATA that is read in and accessible to the AI. The AI reacts to this data. We call this table-driven or data-driven code, and it is the ideal way to code whenever it is feasible to do so.
If you wanted to have, say, a reaction to being near a ledge, all the code needs to know is where the ledge is in the world in comparison to the character. The ledge positions would be stored in memory easily accessible to the AI, and a function likely made called something like "GetNearestLedge" with other functions like "GetDistanceToNearestLedge" and so on. Lots and lots of functions like these are made and then used.
The data returned from these functions could then be used to determine actions. These actions would work on ANY stage because each stage's data would affect the results of those functions which would then determine the actions performed.
If there was any AI code written for a specific stage in Smash Bros. code I would be shocked. Its horrible coding practice commonly known as a "hack". Good AI code is set up to work no matter the environment, using data from that enviroment to make decisions. In a system set up correctly, adding new AI actions and reactions should be quick and simple - its just a matter of knowing which actions make sense to perform and that they are performed at times that make sense.
SSBM's AI is actually pretty decent at some stuff - pathing finding, for instance, is no easy task in a platforming-style game (you'll notice most platformers have AI that just stays in one area, it doesn't chase you around from platform to platform). Getting the character to chase another character down to attack them with multiple platforms from the stage data and not look like a complete idiot or get stuck in a loop running back and forth is not easy. There is plenty of info out there on pathfinding through a maze and such (like pathfinding in an RTS game) but I challenge you to find any comprehensive info on doing pathfinding in a platforming enviroment where gravity and jumping is involved instead of being able to move in any direction around a map. This is likely where most the AI work went into the game, even though most people in this thread probably don't realize it.
After pathfinding and a couple of impressive works of some characters attempting spikes or other advanced manuevers here and there, and some characters being pretty good at recovery, the AI is pretty sparse. Its clear they just didn't have time to make it better or decided it was not worth the effort when multiplayer was the focus of the game.
Oh, and as for the AI's "Level" - most AI of differing difficulty level is the same AI for all levels. The levels just are reference to a table of values that change the effectiveness of the AI. In the case of fightning games, the level generally just affects how often the AI does nothing useful versus attempting to attack the other player, and how often the AI properly reacts with the "correct" action. For example, you throw a projectile at an AI. At level 1, it has a low chance of avoiding the projectile. At level 9, it has a high chance of avoiding it by blocking, jumping, dodging, whatever. The code is the same either way, the difference is that in the data table for level 1 AI it has something like "AvoidChance = 10" and for level 9 AI it has "AvoidChance = 90". Again, data-driven code is the best way to code if it is feasible.
You can see this is what was done in Smash Bros. as well - notice how a level 1 AI, every once in a while, will do something you'd only expect a level 9 to do like pull off a spike. Its just that they do it FAR less often. The difference between 1 and 9 is just changing the chance of performing the actions (sometimes the chance is 0 to disable it as an option at all at certain levels) or changing the intensity of the correct action (i.e. how MUCH the AI uses DI as opposed to whether or not it does at all). The code, however, is the same regardless. Its all data-driven!