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

[f1rpo]

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.

I think that part of the reason why my Isabella game ended up so difficult came down to having 8 civilizations instead of 7, on a Continents map. This map ended up with 4 main continents, somehow. One AI, Justinian, ended up alone on a huge area of the biggest continent; three AIs were shoved onto a medium-sized island, I and Gandhi ended up on a small food-barren island, and Pericles (!!!) ended up on his own private isle where he could just sit and tech in peace. [...]

[...] it seems to me that having 8 AIs makes Continents even more luck-dependent than it already is, as it can really lead to lop-sided spawns.

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.

 

[crullerdonut]

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.)

 

[f1rpo]

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.

 

[f1rpo]

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.

 

[crullerdonut]

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? But I know that AdvCiv has alleviated this issue.)

 

[f1rpo]

Have you tried the algorithm out with some Fractal maps? Seeing the before-and-after screenshots is very interesting.

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.

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.

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."

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.

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.

(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? )

I didn't even connect those dots. Yep, good riddance to that.

 

[Leoreth]

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.

 

[f1rpo]

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.

 

[crullerdonut]

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.

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 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.

 

[Leoreth]

Genghis Khan of the seas (or should I say. Genghis Kahn?). Sounds like an interesting premise.

 

[crullerdonut]

Genghis Khan of the seas (or should I say. Genghis Kahn?). Sounds like an interesting premise.

Feel free to try playing the map... if you dare.

Also, here you go:

Spoiler :

 

[Leoreth]

Oh, I know him from the Spongebob opening.

 

[f1rpo]

How does the new algorithm deal with this map? The player starts as Genghis Khan in brown on the bottom-right. [...]

Pretty great start for a Keshik rush.

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

 

[xyx]

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.

 

[Lanstro]

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.

 

[f1rpo]

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.

 

[Lanstro]

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.

 

[Lanstro]

Just reporting back - this seems to have worked - thanks!