1. Firaxis celebrates the "Asian American and Pacific Islander Heritage Month", and offers a give-away of a Civ6 anthology copy (5 in total)! For all the details, please check the thread here. .
    Dismiss Notice
  2. We have selected the winners of the Old World random draw and competition. For the winning entries, please check this thread.
    Dismiss Notice

New algorithm for starting positions (upcoming in v0.98)

Discussion in 'Civ 4 - Advanced Civ' started by f1rpo, Jul 21, 2020.

  1. f1rpo

    f1rpo plastics

    Joined:
    May 22, 2014
    Messages:
    1,156
    Location:
    Germany
    I was going to post this as a reply to @crullerdonut's game report Isle of Isabella. Then this idea about having multiple threads sunk in a bit further and ... here we are.
    The balance of starting positions is the main thing I've been working on (mostly finished now) for the next version. As an experiment/ a demonstration, I've used the savemap function (Alt+Shift+M) to allow the new algorithm to assign starting locations for crullerdonut's map. One caveat: savemap doesn't remove the extra "normalization" resources and features that were placed near the original starting sites. I'm attaching three screenshots for a comparison; I'll mostly talk about the 3rd.
    1. Starting position in crullerdonut's game;
    2. A starting position produced by the new algorithm;
    3. Result of another run of the new algorithm, slightly different outcome because it's randomized, and without swapping starting sites around based on the difficulty level (human handicap) in the end. Omitting that last step makes it easier to read the algorithm's log file.

    The algorithm begins with the position computed by the BtS algorithm, i.e. what AdvCiv 0.97 uses too, and moves civs around iteratively. (I've named the algorithm "starting position iteration.") The log file after the final iteration (see below) shows that the position in the third screenshot is considered to be pretty well balanced: The "start values" range between 4186 (Isabella; with two others on the largest continent) and 6100 (Hannibal; alone on the smallest continent). If savemap wasn't involved, then extra resources could narrow that gap a bit further, and, if the log file wasn't enabled, human Isabella would swap her start with Pericles (I guess), the 3rd worst start among 8.
    Spoiler :
    Reduces avg. error to 97 permille (was 167 permille)
    Increases start position value to ca. 11426 (was ca. 8523)
    New worst outlier: 0 (was 2)

    Evaluating starting position ...

    Site #0(Isabella)
    From found-city value: 3142
    From exp. space: ca. 4546
    Rival distance factor: 82 percent
    Volatility: 15 percent
    War factor (2 pot. enemies): 72 percent
    Trade factor (2 pot. partners): 92 percent
    Start value: ca. 4186

    Site #1(Shaka)
    From found-city value: 2960
    From exp. space: ca. 5122
    Rival distance factor: 87 percent
    Volatility: 7 percent
    War factor (1 pot. enemies): 83 percent
    Trade factor (2 pot. partners): 94 percent
    Start value: ca. 5525

    Site #2(Joao II)
    From found-city value: ca. 3082
    From exp. space: ca. 4672
    Rival distance factor: 84 percent
    Volatility: 9 percent
    War factor (2 pot. enemies): 72 percent
    Trade factor (2 pot. partners): 92 percent
    Start value: ca. 4365

    Site #3(Justinian)
    From found-city value: 3196
    From exp. space: ca. 5968
    Rival distance factor: 89 percent
    Volatility: 5 percent
    War factor (1 pot. enemies): 83 percent
    Trade factor (1 pot. partners): 81 percent
    Start value: ca. 5567

    Site #4(Pacal)
    From found-city value: 3160
    From exp. space: ca. 5245
    Rival distance factor: 96 percent
    War factor (2 pot. enemies): 72 percent
    Trade factor (2 pot. partners): 92 percent
    Start value: ca. 5389

    Site #5(Gandhi)
    From found-city value: 3116
    From exp. space: ca. 5190
    Rival distance factor: 89 percent
    Volatility: 4 percent
    War factor (1 pot. enemies): 83 percent
    Trade factor (1 pot. partners): 81 percent
    Start value: ca. 5046

    Site #6(Pericles)
    From found-city value: ca. 2917
    From exp. space: ca. 5296
    Rival distance factor: 88 percent
    Volatility: 5 percent
    War factor (1 pot. enemies): 83 percent
    Trade factor (1 pot. partners): 81 percent
    Start value: ca. 4924

    Site #7(Hannibal)
    [The found-city value, i.e. the city radius around the starting site, is given less weight, and space for expansion is given more weight because Hannibal is alone on his continent. Getting off to a good start isn't so important for him.]
    From found-city value: ca. 693 (weight 23 percent)
    From exp. space: ca. 5904
    Volatility: 15 percent
    War factor (0 pot. enemies): 110 percent
    Trade factor (1 pot. partners): 84 percent
    Start value: ca. 6100
    The "volatility" values measure, let's say, how "weird" a start is. None are too bad here. The highest two: Isabella, who is fairly close to two other starting sites; and Hannibal, who is – not really isolated – but alone on his continent. Volatility values can also affect whether the human position gets swapped and with whom; but, in this example, volatility is too low to matter.

    Regarding the original positions (first screenshot), the BtS algorithm probably placed Hannibal, Justinian, Gandhi and Pericles in the best spot available (city radius mainly + nearby surroundings) on their respective continents, ultimately and without regard for the other civs still to be placed. This greedy strategy really doesn't work well for continents that have room for only two or three civs.
     

    Attached Files:

    kaltruhe, carp, Cruiser76 and 2 others like this.
  2. crullerdonut

    crullerdonut Warlord

    Joined:
    Jun 29, 2020
    Messages:
    103
    Imbalanced starting positions have certainly always been an issue in Civ4, especially for Continents and Fractal maps. Making an algorithm which produces consistently fairer results would be a pretty major back-of-the-box feature of AdvCiv.

    How does the new algorithm work with regards to Fresh Water? In the third screenshot, it seems like Pericles would have to walk quite some distance to get some Fresh Water.
    Also, in the new algorithm, does resource normalization happen after picking the starting locations? (Producing the big-fat-crosses of forests surrounding the start site, etc.)
     
  3. f1rpo

    f1rpo plastics

    Joined:
    May 22, 2014
    Messages:
    1,156
    Location:
    Germany
    Consistency is still a bit iffy. When I've tried that same map with 7 civs, one of the two civs on the northeastern continent got placed south of the equator again, giving the northern neighbor too much space. That problem is fixed now, but probably a few more will reveal themselves and probably some will remain that are just inherent to the algorithm. Anyway, screenshot for 7 civs attached. The logfile suggests that the two civs on the northwestern continent have too much space then, which is a tiny bit better than with 8 civs, when that continent has too little space for three.
    Spoiler Logfile for 4th screenshot :
    [...]
    Reduces avg. error to 95 permille (was 256 permille)
    Increases start position value to ca. 12466 (was ca. 6794)

    Evaluating starting position ...

    Site #0(Isabella)
    From found value: 3664
    From exp. space: ca. 8108
    Rival distance factor: 86 percent
    Volatility: 23 percent
    War factor (1 pot. enemies): 83 percent
    Trade factor (1 pot. partners): 81 percent
    Start value: ca. 6840

    Site #1(Shaka)
    From found value: ca. 3090
    From exp. space: ca. 4919
    Rival distance factor: 86 percent
    Volatility: 8 percent
    War factor (1 pot. enemies): 83 percent
    Trade factor (2 pot. partners): 94 percent
    Start value: ca. 5377

    Site #2(Joao II)
    From found value: ca. 3342
    From exp. space: ca. 4881
    Rival distance factor: 95 percent
    Volatility: 2 percent
    War factor (1 pot. enemies): 83 percent
    Trade factor (1 pot. partners): 81 percent
    Start value: ca. 5300

    Site #3(Justinian)
    From found value: ca. 1079 (weight 34 percent)
    From exp. space: ca. 5370
    Volatility: 23 percent
    War factor (0 pot. enemies): 110 percent
    Trade factor (1 pot. partners): 84 percent
    Start value: ca. 5964

    Site #4(Pacal)
    From found value: 3711
    From exp. space: ca. 7635
    Rival distance factor: 87 percent
    Volatility: 16 percent
    War factor (1 pot. enemies): 83 percent
    Trade factor (1 pot. partners): 81 percent
    Start value: ca. 6715

    Site #5(Gandhi)
    From found value: 3349
    From exp. space: ca. 5581
    Rival distance factor: 96 percent
    War factor (1 pot. enemies): 83 percent
    Trade factor (1 pot. partners): 81 percent
    Start value: ca. 5830

    Site #6(Pericles)
    From found value: 3522
    From exp. space: ca. 6221
    Rival distance factor: 87 percent
    Volatility: 7 percent
    War factor (1 pot. enemies): 83 percent
    Trade factor (1 pot. partners): 81 percent
    Start value: ca. 5766
    The algorithm often tries to compensate for an abundance of space by moving starting sites closer together or away from the continent's center. That wasn't my idea, it just turns out to be the result of the optimization goals I've set. I guess it's a good thing so long as it's done within reason.

    As before, normalization will happen only once, namely after the starting sites have been assigned. (Ideally, it should happen before swapping civs around based on handicap, but I don't think I'll change this; too laborious.) For the screenshots, I'd prefer if savemap could remove the normalization that was already applied in your savegame, but that's not currently possible. Arguably, savemap should apply another round of normalization after new starting sites have been assigned; would be easy enough to change – but isn't the case in the screenshots. (The starting position algorithm nevertheless anticipated normalization to an extent, i.e. didn't greatly prioritize "natural" fresh water.)

    I've been making some (further) changes to the normalization procedure too. Fresh water is still guaranteed at or adjacent to each starting site unless the land is so narrow that no river or lake (or oasis) can be placed. Those "big-fat-crosses of forests," however, won't be so conspicuous anymore. I hadn't realized how many forests get placed during normalization until I read the code. Now I find it really jarring how one can always tell by the forests when a site has been deemed too weak.
     

    Attached Files:

    crullerdonut and Leoreth like this.
  4. f1rpo

    f1rpo plastics

    Joined:
    May 22, 2014
    Messages:
    1,156
    Location:
    Germany
    Here are some links to older posts by me and others on this subjects. I was going to quote them, but there are too many for that: Starting on page 24 with a post by Cruiser76, going on through the rest of that page and most of page 25. Also most of page 26 and a few more on page 27. And a ping to @xyx because he was quite involved in that discussion and wrote (part of) the savemap script that I mentioned in my posts above.
     
    Last edited: Jul 28, 2020
  5. crullerdonut

    crullerdonut Warlord

    Joined:
    Jun 29, 2020
    Messages:
    103
    Your new algorithm certainly seems to produce consistently better results than the vanilla one. In the original vanilla 8-Civ one, the most glaring problems were with Pacal and his pitiful brown corner, and with Justinian and his massive unchallenged domain. But with the 0.98 algorithm, those issues seem to be consistently fixed.

    Have you tried the algorithm out with some Fractal maps? Seeing the before-and-after screenshots is very interesting. Similar to including screenshots of the Blue Marble "Light" comparisons, you could provide a series of screenshots to show how your new algorithm results in fairer placement.

    As for big-fat-crosses of forests: In terms of gameplay, that's always pretty much been a signal to go chop out some kind of rushing strategy. I would say that there probably should still be enough normalization forests so that this kind of chop-rush strategy is still something that happens. On the other hand, having a big-fat-cross of forest in the middle of a barren plain has already been a huge problem for immersion. (In vanilla BtS, there's the additional detail that you'll occasionally have a single empty plot among a huge BFC of forest. Oh, I wonder what that could be? Not some strategic resource? :rolleyes: But I know that AdvCiv has alleviated this issue.)
     
  6. f1rpo

    f1rpo plastics

    Joined:
    May 22, 2014
    Messages:
    1,156
    Location:
    Germany
    I've tried a bit of everything. Attaching some screenshots of a Fractal map. In this case, the tangle of civs on the large continent gets moved apart a bit and Ragnar is given a fighting chance (perhaps; still doesn't look ideal). The third attachment shows the steps taken by the algorithm; it moves one or two civs at a time (in this example always two), marked with "a" and "b" in the image.
    I'll be sure to link to this thread from the release notes and mention the changes somewhere in the manual. Actually, I've already added a sentence there and put the full documentation in the appendix (change id 027; link to current version of the manual; edit: that link is dead now; replacement: link). My impression is that unbalanced starting positions have been a greater issue with AdvCiv than in plain BtS, presumably because of AI changes, higher default player counts and the inclusion of the PerfectMongoose map script with its scraggly land shapes. I.e., to an extent, I'm fixing a problem that I've created, so I probably won't write it "on the back of the box."
    The last attached image shows the final starts, i.e. after normalization, on that Fractal map. Not quite the same as in the large screenshot (#2) because, for that screenshot, the civs had not been switched around based on handicap and then the (randomized) normalization process works out differently. The rivers near the human start (Ramesses; taking the spot originally assigned to Louis) also look strange; so perhaps it's not 100% the same map either ... [Edit: I think it's legit - one normalization step places a river in the north, the other in the south.] Eh, not the point really. I'll increase the overall target frequency of forests a little bit to compensate for the lower frequency at starting sites. You were right in the other thread about Fishes being placed too close together. They're supposed to be at least two tiles apart and that restriction had gotten lost. Already fixed in the screenshots.
    I didn't even connect those dots. :blush: Yep, good riddance to that.
     

    Attached Files:

    Last edited: Nov 15, 2020
    crullerdonut likes this.
  7. Leoreth

    Leoreth Vampire of the Blue Moon Moderator

    Joined:
    Aug 23, 2009
    Messages:
    35,714
    Gender:
    Male
    Location:
    Paris
    The only thing that gives me pause is whatever player shares the southwestern island with Arabia (can't make out the civ from the colour). Are they really in a better position here? Seems like they're boxed between the Arabs and the desert.
     
  8. f1rpo

    f1rpo plastics

    Joined:
    May 22, 2014
    Messages:
    1,156
    Location:
    Germany
    That's Alexander. You're right, those moves are at best questionable. Before the first move (#6) on that continent, Saladin's start is considered to be too powerful and even the worst outlier. He has a good shot at claiming the two Nilotic rivers, but that's really not much land. I guess the bigger factor is that he'll have intercontinental trade with the north (Ragnar, Bismarck). After move #6, Sal's overall start value decreases enough to make him no longer the worst outlier. Mainly due to starting a little bit closer to Alexander. Distance seems to have a bit too much impact here; I'll tweak that. The bigger problem is move #7, which reduces Alexander's space for expansion in exchange for making it easier for him to trade across the sea (coastal start at the northern coast).

    In his final position, Alexander should be able to place 3 cities along the eastern coast (in addition to his capital). Sal may also end up with only 4 cities on the mainland, but should be able to get at least one colony in addition. Screenshot attached. Well, that's what I might do; AI Auto Play shows the AI letting two seafood go to waste (another screenshot; note the 2 blue and 2 green circles marking planned cities).

    The algorithm assumes that the space values of Sal and Alexander are 4974 vs. 4255. That's not necessarily wrong – the value is supposed to account also for strategic resources and, to a small extent, for possible conquests; – but doesn't capture that Sal has enough space to compete peacefully at least until the midgame, while Alexander is forced to start an early war. I haven't built any absolute notion of sufficient space into the algorithm; may have to amend that.

    It seems that if there was a bit more space overall, there'd be a significantly greater margin for error when computing the starting position. One fewer civ would yield too much space on average for my taste, but increasing the grid size by 4 rows or columns is worth a try. That said, there can always be a continent far too large for one and barely large enough for two.
     

    Attached Files:

    crullerdonut and Leoreth like this.
  9. crullerdonut

    crullerdonut Warlord

    Joined:
    Jun 29, 2020
    Messages:
    103
    How does the new algorithm deal with this map? The player starts as Genghis Khan in brown on the bottom-right. Early expansion is shown with red arrows.
    start.png

    This is a game where I simply quit after ~100 turns because I didn't want to bang my head against the wall. It's probably winnable but... no thanks.
    The player (brown, bottom-right) starts stuck on the end of a peninsula with a gigantic desert and very limited ways to generate :commerce: besides perhaps the Great Lighthouse. By the time I started the GL, Justinian cut me off from anything past the desert. There is also very little way to increase the Happiness :) cap. Meanwhile, Ragnar is sandwiched in a little area; Suryavarman is in the middle of nowhere, and Zara Yaqob gets a beautiful start with Gold and ample Floodplains.
     

    Attached Files:

  10. Leoreth

    Leoreth Vampire of the Blue Moon Moderator

    Joined:
    Aug 23, 2009
    Messages:
    35,714
    Gender:
    Male
    Location:
    Paris
    Genghis Khan of the seas (or should I say. Genghis Kahn?). Sounds like an interesting premise.
     
  11. crullerdonut

    crullerdonut Warlord

    Joined:
    Jun 29, 2020
    Messages:
    103
    Feel free to try playing the map... if you dare. :evil:

    Also, here you go:
    Spoiler :

    Genghis Kahn.jpg
     
    Last edited: Aug 10, 2020
    DarkLunaPhantom and Leoreth like this.
  12. Leoreth

    Leoreth Vampire of the Blue Moon Moderator

    Joined:
    Aug 23, 2009
    Messages:
    35,714
    Gender:
    Male
    Location:
    Paris
    Oh, I know him from the Spongebob opening.
     
  13. f1rpo

    f1rpo plastics

    Joined:
    May 22, 2014
    Messages:
    1,156
    Location:
    Germany
    Pretty great start for a Keshik rush.

    Attaching two screenshots (with the usual caveat about normalization due to savemap).
     

    Attached Files:

    • t0.jpg
      t0.jpg
      File size:
      319 KB
      Views:
      67
    • t118.jpg
      t118.jpg
      File size:
      373.2 KB
      Views:
      65
  14. xyx

    xyx Chieftain

    Joined:
    Aug 7, 2013
    Messages:
    40
    So much better now. As you might recall, I generally think that (reasonable) uncontested expansion space is the main issue causing imbalances, so I very much welcome that this is now considered in the algorithm.
     
    f1rpo likes this.
  15. Lanstro

    Lanstro Prince

    Joined:
    Sep 20, 2004
    Messages:
    326
    Low sample size, but in ~15 games of 3v3v3v3v3v3v on bigs & smalls in 0.98, we (the humans) have almost always been put on the snakey islands part of the map instead of the fat continent bit. Feels like it's cut down a lot on the diversity. If it's not just our imagination, would be good to have a setup option to go back to the old way of generating maps.
     
  16. f1rpo

    f1rpo plastics

    Joined:
    May 22, 2014
    Messages:
    1,156
    Location:
    Germany
    In a quick test, I've also gotten island starts three times in a row with v0.98, whereas, with v0.97c, I got a continental start right away. The new algorithm is actually (always) disabled for team games (somehow the manual doesn't mention that). Must be some other, minor change that I can't easily identify; I don't think it's a bug really. Anyway, at one point the BtS function that swaps the initial starting locations around in order to decrease the distance between teammates goes through the civs beginning with slot 0 (i.e. in the order given on the Staging Room/ Custom Game screen). If I go through the civs in a random order instead, the bias for human continental starts seems to disappear. So, probably easy enough to fix in the next update. For the moment, it could help to put some of the human players into lower slots (i.e. higher player ids; team ids don't seem to matter) during game setup. In a test with v0.98 with one human at the top (id 0) and two at the bottom (ids 16, 17), I got two continental starts in a row iirc. Perhaps one will only get continental starts this way; in that case, maybe ids 8 and 9 can go either way(?).

    The BtS algorithm for swapping the starting sites generally doesn't look great. Apparently it only tries to minimize (path) distances between teammates. I haven't ever really played a team game, but my impression is that the most important criterion should be whether teams outnumber each other on a continent. For example, I expect that BtS would put a whole team of 3 on a continent with room for 4 civs, which is unfair to whichever team gets to take the 4th spot. I've thought about replacing the algorithm, but I'm not sure just how much fairness should be prioritized over vicinity.

    For example, if we have 3 teams of 3 and one continent with room for 6 civs and one with room for 3, the fairest solution (by virtue of being symmetrical) would be to let 2 civs of each team start on the large continent and 1 civ of each team on the small continent. (The "quality" of the starting sites should also matter, but that seems less important to me, more suitable as a tiebreaker – e.g. which 2 sites does which team get on the large continent.) The assignment that minimizes distances within teams isn't overtly unfair in this example either: Two whole teams would go on the large continent and one whole team on the small continent.

    Or how about one continent with room for 5 and another with room for 4. Should the larger continent host one entire team of 3? Or should it be 2+2+1 on the larger and 1+1+2 on the smaller continent? (And how to generalize this into an algorithm?)

    Edit: I actually don't see any harm in enabling the v0.98 algorithm for the initial starting position for team games, regardless of whether those positions get swapped around by the BtS algorithm afterwards or by some replacement yet to be implemented.
     
    Last edited: Nov 25, 2020
    crullerdonut and DarkLunaPhantom like this.
  17. Lanstro

    Lanstro Prince

    Joined:
    Sep 20, 2004
    Messages:
    326
    Nice, we'll try starting games where we're not the top 3 slots then.

    Yeah it's a tricky one. It's definitely important to keep the teams together, but it does as you identify lead to not infrequent situations where one poor little AI is stuck on an island with three of us, or the other way around.
     
  18. Lanstro

    Lanstro Prince

    Joined:
    Sep 20, 2004
    Messages:
    326
    Just reporting back - this seems to have worked - thanks!
     
    f1rpo likes this.

Share This Page