Honestly I think that most people don't understand the difficulty associated with making a good AI, especially in a 4x game, and unfortunately improvements often go unnoticed simply because people don't notice or think about the problem that is no longer present, they think about the ones that still are because when they play those are the problems they see on the screen (and oddly enough, people are looking at the screen while playing, who knew? [e digicons]
[/e] *)
I also think that people are misdiagnosing the problem. Now problems are very rarely simple but if I might make some observations worth considering.
1) the faction power box actually isn't a very good representation of power as it represents pure military might. I remember my first game where I decided that magic was obviously the most important thing ever, who needs an army? Or even cities? So I just had one city, used arcane monolith to claim shards and research bonuses (and a bunch of other stuff too, but in hindsight I didn't need most of them) and rolled around with my insanely leveled soverign and some summons smashing the enemy either on the strategic map with tidal wave/starfall/etc (my sov was master of all schools of magic) or in battle with fireball/flame dart/etc and I destroyed everything, but the AI was still convinced that it was more powerful than me, and before I started my rampage I was convinced that the AI was more powerful than me.
Now obviously this was on one of the easier difficulties (either one or two below expert, I forget which) but that faction power bit is still utterly ignoring a very strong part of strategy in FE so when I easily beat the ai, I assumed that the ai was just bad (and I had uber leet skillz, obviously). Having played a bit more I now know that a) that was with the ai on a easy setting and b) it wasn't my weak kingdom stomping all others, it was my strong kingdom stomping all others, the game just didn't present it that way which lead me to assume that the AI was bad.**
2) The AI cheats, and the player knows it. Higher difficulties give it straight up advantages over the player so when the AI wins, it's because it cheated, when the AI looses, it's because it's bad (obviously)
3) The AI doesn't learn, because learning AIs are a new technology that require a lot of processing power and many many games, so when you get better the AI doesn't, and gets relegated to stupid in your perception.
4) You are smart, and the AI is stupid. I know this seems to contradict what I just said ("AI get's relegated to stupid, and that's wrong") but AI's and computers in general have a great many weaknesses compared to a human mind. A great many strengths too, mostly based around repetitive actions, speed and attention to detail, although their superior multitasking is greatly diminished as an advantage by the turn based nature of FE and most other 4x games. And of course, playing to the AIs advantages.... is the AI cheating whenever the player notices it.
BTW, just out of curiosity, how hard would it be to mod in a sort of Dungeon Master style AI that tracks the player and trys to keep them challenged and buffs the AI where it needs it vs the human. FE is currently, and from the looks of it FE:LH will be, scratching a gamer itch that I didn't even know I had and it might be a fun project to try to mod that kind of thing in.
*yes, I know I'm not funny, shaddup.
**it's actually possible that faction power does account for magic somehow and I just haven't figured out how, but I'm convinced that it's under-representing it at the very least)