Civ, is more complex then chess by a huge order. The two big problems is the number of varibles:
I'm not so sure that chess really *is* that much simpler. Could it just be that the basic rules have had only minor amendments over centuries, when with Civ, they throw the old one out and start again with each version? If chess was invented today, the AI would be no less difficult than for Civ5. But for chess, we have centuries of books about strategy, opening moves etc. Imagine if that existed for Civ?
Personally, I think starting again each time is a flawed design strategy. In contrast, I'm very much enjoying Europa Universalis 3 with it's 3 full explansions, several years of AI improvements - and another huge expansion coming soon! And EU3 on release was a lot worse than Civ5 on release....
The underlying question is "What is a sequel for?". A total re-invention of a series or an organic improvement? Why did Civ5 need to be created anyway? I believe the answers are down to marketing and business, rather than technical. Hence any debate about the AI's technical capabilities - and there are many interesting comments here- is just irrelevant anyway. With organic improvement, the AI can improve too. However Civ5 is probably the biggest single rejection of previous conceprs in the series so far. A big risk, but perhaps with the right marketing and names behind it, it could never fail anyway?
If only 1% of the effort put into graphical baubles was put into AI. Compare the thousands of hours spent by huge teams of graphic and audio designers with that spent by a couple of devs on the AI.
I worked in games development many years ago, and was told the same thing as people are saying here, that "gamers don't want an invincible AI that crushes them". But they don't want one that rolls over and lets them tickle it's belly, either!!! And that is the current state of Civ5 AI. The aim is to make the gamer *think* that they are some kind of tactical genius to win, so the AI has to put up a fight, before bowing to the intellect of the Mighty Human. Sure, the AI 'brain' will never be as sophisticated as the humans, but this is easily balanced by the fact that the whole game is in *its* memory, not yours! It knows where you are and what you do at exactly the moment you do it. It especially applies to FPS, as it's actually easier to code enemies that instantly home in on the human every time, than those that behave more 'life like' and make mistakes. The former would result in nobody ever playing a game for more than 10 mins though, before quitting in frustation.
They need to get rid of the obvious AI flaws in Civ5 (but no more than that) and I'm sure they will do that as people keep saying, there are some very trivial things that would make huge improvements.