[MikeLemmer]

I think randomization would go against the nature of the campaign. The AIs, when you redo a map, pretty much follow the same strategy as-is. It's not about winning/losing based on randomness; it's about finally winning by solving the map.

I think a replayable campaign could be made with one addition: let the other civilizations attack you.

1. Choose an age; this determines the size of the map.
2. Place 3-4 civilizations on the map. Each civilization starts with 4-5 regions.
3. Each civilization invades 1 region on their turn.
4. The 4 sides on the battle map are determined by the owners of the adjacent regions. Whoever wins that battle, wins that region.
5. The game ends after X turns; the winner is whoever controls the most regions.

Point 4 needs some analysis: not involving the adjacent regions would lead to nothing but 1v1 battles, but giving the region's owners their own start would need 5 start points on each map instead of just 4. I feel having each start's owner determined by an adjacent region is a reasonable compromise.

"What if my region is surrounded by enemies?"

Then it doesn't get any start location; it is picked apart as its neighbors fight over who controls the remains. A tad brutal? Yes. But it keeps things simple.