What the AI needs is what every chess AI ever made has: a book of opening moves. Once into the midgame, it becomes impossible to map out a coherent strategy ahead of time, but if the AI had a book of opening strategies, say "Pyramids->Caste System->GP Farm," "CS Slingshot," "Cottage spam" or "Early Rush" then it could play a dominant opening game that might make up for it's mid game weakness. Right now, the AIs each seem to have a personality and a strategy to match. Ideally, this would be their dominant strategy on lower levels, while on higher levels they would decide on a particular "book opening" based on circumstance and then play that. For the mid game, on higher levels of play, the AI should use higher level strategies. Various strategies can be devised and categorized according to how many turns they will take to play out. On lower levels, the AI will only consider short strategies, while on higher levels it will pick longer term strategies. For example, on lower levels, the AI might decide "build an army, attack closest weakest enemy." On an intermediate level it might pick "Scout for best opponent, build an army of conquest and several raiders, attack city X while pillaging the remaining land." and an advanced AI might pick "beeline to engineering, amass a herd of cats, escort with some swordsman, a longbowman and a pikeman, take city X, while pillaging cities A, B and C regroup and heal, take city Y then try for peace." Or for a really out-there idea, have the strategies governed by a genetic algorithm. The strategies that survive the longest, get the highest scores, or actually manage to beat players get to breed (over the Internet, with the AIs of every other player!) creating new, ever more unbeatable AIs. Of course, we all know what happens then. The game becomes conscious and decides that the only way to end human suffering brought on by our civilization is to end civilization. "Shall... we... play... a... game?"