Spying

I think a good spy should yield more than just information. Depending on the quality and level of the spy, spies should be able to truly influence an opponent. Think of highly influential whisperers in George R R Martin's F&I saga: A spy might plant some seed of doubt, of hatred, of vanity, of fear, of heresy in some commander's ear, so that for a turn, the commander moves off in some random direction (much like the "insane" flag currently works in Dominions3). A spy might be able to cancel a certain amount of resource gathering for a turn (because he convinced some official to siphon it off and give it to someone as a bribe). A spy should be able to halt a caravan's movement for a turn. All of this depending on the quality, training, and experience level of the spy. If a player play's his (spies) cards right, he might truly screw up the decisions of a city in dozens of ways -- at least for a turn. A player -- and the AI as well -- will obviously notice when many things go wrong in one turn and suspect a spy, and have some degree of chance of succeeding in revealing that spy -- but not on the strength of patrolling alone.