Does the option to build a palace randomly appear for rulers, like recruiting volunteers or moving the family home for Heroes? Does the option only appear in the capital? And will the option appear if a previous ruler already built a palace in that city?
