My post was just explaining that we could mathmatically predict how many calculations a truely 'smart' AI would require for Civ3. I didn't touch on current implementations of AI and whether or not they could be improved because it's rather obvious that they can.
View my post as a refutation of "It's impossible to prove something can't be done." as it pertains to game sentience, not a refutation of "Smarter AI's are possible".
The problem with 'smarter' AI's is that they will still be predictable as well. The tricks I eluded to teaching the AI can be viewed as a rather loosely defined gambit. For instance, the AI could be taught to use better combined arms stacks, and where to send them. Instead of sending a Archer/Spearman combo, they can send 3 Archers, 1 Spearman, and 2 Catapults. Eventually the player will learn to expect these stacks, and plan accordingly. The AI will not adapt.
Now you can add a random element, but then you have to be careful it doesn't have too much of a range. We wouldn't want completely inane stacks like 12 Catapults, 0 Spearmen, and 1 Archer basically giving the player 12 free Catapults. So we define ranges for each of the units. The player will learn to expect and plan for these ranges (knowing that there is a 'max' stack possible), but the AI won't adapt.
Even if we add all these tricks to a biological simulation on supercomputers, have it work out different combinations that work best, and implement that as our AI, it's still a combination of tricks we taught the AI in the first place, just ordered differently. The AI on the player's computer will still not adapt, and the player will be able to identify the patterns.
-------------------------
How to design a better AI
There are quite a few ways to do this, from distributed computing, to just hiring more programmers and spending more money.
A scripting language that is released to players can allow for a vast array of different AI's. Combine these in a AI library, which the game can choose from to implement, can reduce the player's ability to predict what the AI will do. The main problem with this is that few of the AI will be very efficient or difficult, and eventually the players will figure out how to identify the various AI's early on and play accordingly.
End user's computers can be hooked up in a network, allowing the AI to actually learn. Each computer uses idle time to help with the 'learning'. One computer might record something to the extent that "hey, I just captured a city under these circumstances by doing this..." for other computers to try out and rate in other circumstances. A central server would hold the ratings (type, effectiveness) for various tricks, which each individual computer can access. There are implementations of this in other feilds, SETI comes to mind. It would still be using tricks, but much more adaptable and less predictable. There could be a lot of really stupid AI's though until the project had been going on for a while.