Actually I don't think Civ is as complicated as it seems. Sure there are loads of 'potential' things to do each move but not everything needs to be analysed and you could break down each move into just a few options,
for example build infrastructure, build military, wage war, group units, move units etc.
The computer could pretty easily select what squares are the most productive in a city radius, and what buildings, improvements need to be made to maximise efficieny. It's just number crunching really.
Waging war should be easy enough as well. Program some AI's to fight with constant waves of a few attackers, program others to stack massive forces before attacking.
To analyse by brute force would be impossible but using this approach its a lot more accessible for the computer to play well.