[thejeff]

Note that almost all the current turn processing time is battle calculation. Very little is spent on generating the AI orders. Maybe 10%?

I suspect most of the AI improvements fall more into the category of lots of programming time, rather than calculation time.

A lot of simple things could improve the AI difficulty drastically. Better pretender design being high on the list. Better use of sacred troops. (Buys expensive sacred troops, even when the pretender has no bless. Takes a bless not suited to the units. Gets a good bless and then doesn't send a priest into battle to bless the troops.) Some ability to make basic SCs.
I doubt fixing any of that would require much calculation time, just better design.