or, you don’t really care about tiles except that are directly around the players, as long as there’s a reasonable path between them. the city between them can regenerate and it wouldn’t matter; it’s not like they’d compare notes (and if they did, it’d be an odd coincidence rather than broken)
or, you can always use a map seed so the PRNG that makes it non deterministic (assuming that’s the only thing that does) generates the same numbers so that it is deterministic. the age of empires (old yes, but still relevant!) team wrote a great little piece about their multiplayer, and how they kept all their PRNGs in sync so that the games remained the same across hosts