To start my post, I remind people that every problem-solving "machine" (whether the human brain or a computer) works based on algorithm, which is a set of mathematical instructions that must be followed in a fixed order, and that, especially if given to a computer, will calculate an answer to a mathematical problem.
But human mind differs from computers in the sense that, once an algorithm does not provide a satisfying answer, the mind creates a new fresh algorithm to work on, while the computer will stick to the resulting calculation of the algorithm it was provided to him by human input.
So, for instance, if a computer needs to pick the most optmal choice after a roll of algorithm calculations, it will pick it based on a limited number of algorithms that tell it which choice is best, either by random number rolls or by picking the result that best fits pre-set scenarios.
However, it won't create a new algorithm to better weigh the variables involved and get to the best result possible, which is a thing that man alone can do. Man, and man alone, can see "Well, this surely isn't the best result possible" and go there and create a new roll of algorithms, whether or not he'll eventually get a better result.
If you give a machine an algorithm which will always return bad results, it will pick those results nevertheless. Man, faced with that same algorithm, will discard it and build a new one.
So, when someone creates a game focusing on singleplayer, the AI must be the top one priority. It has nothing to do with the number of variables involved, and how they relate to each other, but to how many algorithms were coded to provide the AI with a wide range of viable choices. This is especially true for games with several variables to consider: if you don't have many complex algorithms that take into consideration all variables involved, the AI won't be able to handle itself in any viable way.
And it seems that people in Firaxis just forgot that when they were programming Civilization 5, because, based on the feedbacks I've read, the AI is really crippled, even though the game isn't less complex than Civ4 for the AI, as the loss of some game features was compensated with 1upt and pathfinding problems.