After a few dozen games, I tended to get in a 'rut' in terms of tactics and strategy in AI War. Changing AI types only went so far.
What if there were human outposts that encouraged a new style of play and gave a reward. For example:
Take <X> system without using <ship type>.
Don't go below <n> <ship type> for <m> minutes.
Build and deploy <superweapon> <n> times in <m> minutes.
Players would be encouraged to try new tactics and strategies, or use a suboptimal strategy to get a bonus later.
This would be especially impactful if the reward were something which further altered the strategic landscape (temporary bonuses to certain ship types/weapons/armor)