Actually AI is not easy to code, ever wondered why commercial games progress so slowly in this matter? Because it's hard..
Actually no...in the last few years all games has been released with weak AIs. Why? Hell knows..there were games in the past with excellent AIs.
Try out Knights of Legend, its a 15+ years old RPG, it came on a few floppy disks...check out the combat, the AI is able to kick your ass. It is making excellent decisions all the time. Well well, programmers knew how to code back in the old days it seems.
The problem with modern coders isn't that they are sloppy with the AI. It's that the environments they work with now are more complex than before. So coding the same advanced behavior takes much more time and resources (both CPU and memory) than it used to. In the end they must settle for passable AI instead. But even then, coding AI, as coding anything else game-logic-wise, is like building a house of cards. You just set any parameter wrong and the game goes to hell. See what happened with Oblivion and their much publicized Radiant-AI. It ended up being a mere shadow of what it was supposed to be. Most behaviors are scripted (when it was supposed to have almost no scripting in the AI) and still the characters tend to go nuts and do silly and stupid things (DF style) with their non-scripted behavior if you push them (figuratively) a little.
Old games were very simple and gamers didn't expect too much of them. You just added a minimax algorithm with alpha-beta pruning or A* to your AI and it would do wonders with it. And even then most game AIs didn't use (and still don't use) something as complex as minimax. I cannot even imagine how could you add minimax or A* to a realtime game like an RTS or FPS. The preferred way to make AIs more difficult is by adding more HPs and making their weapons more dangerous.
Actually, I would like to mention Civilization 4: BtS. Combine it with the FfH 2. mod, make a custom game with like 8 AI players at Emperor level at least, and you will see some decent AI. I am seriously surprised by the BtS AI. If an AI player declare war on you, it will attack with huge forces. I am not kidding, I constaly see 50+ units big AI army stacks, and not one but more. The AI is also attacking from more directions, it is summoning units/casting spells, promoting his units perfectly, so its really neat. If you will be at war vs. an AI..you will have a very hard time to survive.
In my current game theres a global war. 4 factions [3 AIs + me] vs. 4 factions [4 AIs]. Its just plain awesome to be honest, and I am lucky that my territories are far from the actual battlefronts...since the other team of 4 AIs is attacking with like 400+ units constantly, but me + my 3 AI "allies" managed to defend against them so far. [..and to be honest its not because of me, since I have the smallest military

]
I dont know that the AI is cheating or not [if true not in BtS], but the strategical army is just plain amazing. You should try it out.