You have both tactical and strategic battles, unit customizing system that is much less forgiving to bad designs (compared to promoting some unit in Civ), plus Civ4 is made so that it's game concepts are AI friendly. And questing and creature economy are also concepts difficult to train AI for. Not to mention it's difficult to train AI to place buildings properly, without having cities block each other in growth. Or use spells on strategic level.
I can't see why some people insist this is so complicated. Elemental has tactical battles, but the model doesn't make it that complex. There are no formations, concept of flanking or defence by direction. The pattern for melee units to move forward can be decided mathematically. Granted the formula will be difficult to optimise, but it's less complicated than many of the strategic decisions the Civ AI makes.
Unit customisation - where is the decision making? You build the strongest unit of each class: melee, ranged and mounted you can afford. The AI will be preprogrammed with the ratios it prefers for combined arms based on the tactical algorithms it uses, but there is no reason not to use the strongest possible units at reasonable cost in each class (with some marginal utility applied so it doesn't spend 12 materials to turn a 30 defence unit into 31). There is no advantage to mixing your melee group with some 20 attack and some 26 attack units.
Creature economy - again nothing special. Hunting down creatures for gold is the same as hunting down barbarians to stop them pillaging your lands. It's even easier because the creatures don't enter your territory so you go after them when you want to, rather than having to be proactive. The decision is simple, the AI decides how much military it needs for expansion and how much for the home guard. Whatever resources is left over can be used to create hunting stacks. The composition of the stacks will be based on the strongest monsters that are currently roaming. How many stacks it builds depends on how much resources it has - it will always build a stack of a given minimum strength. These stacks then patrol a given region, or just randomly move around the unclaimed territory while staying close to friendly ground. They come back to heal and reinforce when damaged beyond a threshold.
Questing - this keeps being brought up as being complicated. It's not. You pop a quest location, it tells you to either go to another location, fight the monsters and bring back a goodie for reward, or to escort someone or something to another location for reward. Hunting stacks can be used to pop the quests. There's no time limit or anything special that needs doing, so if the target isn't too far away, it goes after it. The hunting stack that normally just patrols temporarily has a destination and it avoids monsters till it has done the quest.
Building - much less difficult than optimum city placement in Civ. Not even the avid players can agree on the best system for that, because terrain is so important. There is no special terrain in Elemental, only strategy resource which you should grab. You don't have to do city specialisation - it's not hard to realise you only need a market if you have a gold mine, or a school if you have a library. Otherwise, just expand the city in the direction with the most space. If you get a few conflicts, it's no big deal, not every city needs to grow beyond level 2 - in fact they shouldn't.
Strategic spells - much less complex than the strategic decisions for a Civ AI. Everything that AI has to do is strategic, because every decision has trade offs that are hard to quantify. Choosing civics based on current plans, setting the gold/science/culture/espionage ratios, deciding when to stop a city's growth to train a settler or worker... all these choices are hard enough for the player to make, they are even more difficult for the AI. Currently in Elemental, as a player your decisions are easy, because there is no penalty for making any decision. Essentially you can do everything, build everything, research everything - mostly because, due to the lack of penalties for expansion, your resource gathering grows exponentially. The AI can chose its order of research based on current priorities, just like a human. Currently, adding penalties for expansion would be a bad thing, because there is very little to do in the game as a builder and expanding is fast as you can is the only thing satisfying.
RPG - you didn't mention it but it keeps coming up. Heroes level up and you distribute some stats. Again, easy. The AI simply assigns a class to each hero. Spell Caster, Generic Melee, Generic Ranged, City Attacker, Hunter, Imbue Guy (this would be the Sovereign). The number of each the AI uses would depend on its falvour and play style. Each time one levels, the stats chosen are weighted towards improving the hero's effectiveness in its class, with a bit of randomness for variation. This is the same as how the Civ AI decides which promotions to give units (and in my opinion, deciding between extra jungle defence vs hills defence is more complicated than +2 strength vs +2 dexterity).
I'm not saying the AI is easy to make for any old programmer. It's still a very difficult job and needs a specialist. But based on how difficult it is as a player to "figure out" the ideal strategy for Elemental (1 game - maybe 2) vs Civ (years), I can safely assume that those strategic decisions that are hard for the player in Civ are even harder for the AI.
