They are in the game. If you want to increase your chances of finding some, maximize the goods when you customize your map settings. Then it's just a matter of exploring the land faster than that cheating AI.
Also, please note that there are only huts(ruins/relics) at higher difficulty levels in CTPII.I think they you start getting them when you play at "hard" or above...but that is from my memory only. Anyway, the principle is correct.