Let's discuss Mathematics
- Thread starter ParadigmShifter
- Start date
This is from a discussion I had with a friend.
I've often read that development of a civilization in Civ4, say, is roughly exponential. If this is taken literally can you prove it to be true or disprove it.
Some simplifications:
A city can be build in any element of (3Z)^2 (the cartesian product of (..,-3,0,3,..) with itself). You start with a single settler in (0,0). Cities can either grow (but no more than once per turn) or build a settler (but no more than one per turn). Cities can grow indefinitely. Settler movement follows normal Civ4 rules. We ignore city and unit upkeep however. As a measure of empire size we shall consider overall population. Does population grow exponentially? If not, derive it's asymptotic behaviour.
Bonus questions:
Does including workers in the problem make a difference?
Does your answer also hold for Sid Meiers Alpha Centauri?
I've often read that development of a civilization in Civ4, say, is roughly exponential. If this is taken literally can you prove it to be true or disprove it.
Some simplifications:
A city can be build in any element of (3Z)^2 (the cartesian product of (..,-3,0,3,..) with itself). You start with a single settler in (0,0). Cities can either grow (but no more than once per turn) or build a settler (but no more than one per turn). Cities can grow indefinitely. Settler movement follows normal Civ4 rules. We ignore city and unit upkeep however. As a measure of empire size we shall consider overall population. Does population grow exponentially? If not, derive it's asymptotic behaviour.
Bonus questions:
Does including workers in the problem make a difference?
Does your answer also hold for Sid Meiers Alpha Centauri?
Well, development is not smooth (all population levels are discrete), so any growth curve is just an approximation.
Besides, there are issues with the inhomogeneity of the surrounding terrain (but those can be approximated) and, more fundamentally, the finite size of the map, and continents, which but a maximum on the growth. This will lead to a logistic like model.
Another thing, a city can build a new settler in n turns. Optimally, you send these settlers in several (k) directions (probably NW, NE, SW, SE, or into a hexagon, I don't know what's optimal). However, after the city has built these 6 settlers, new settlers will have to walk a longer distance. This reduces the growth.
Besides, there are issues with the inhomogeneity of the surrounding terrain (but those can be approximated) and, more fundamentally, the finite size of the map, and continents, which but a maximum on the growth. This will lead to a logistic like model.
Another thing, a city can build a new settler in n turns. Optimally, you send these settlers in several (k) directions (probably NW, NE, SW, SE, or into a hexagon, I don't know what's optimal). However, after the city has built these 6 settlers, new settlers will have to walk a longer distance. This reduces the growth.
Please don't take the problem so literally. It's a mathematical problem. The Civ stuff is just illustration.
Assume that the map is infinitely large. (I did mention that in my previous post.) Homogenity does not matter as long as you can settle everywhere (no water, no peaks).
Assume that the map is infinitely large. (I did mention that in my previous post.) Homogenity does not matter as long as you can settle everywhere (no water, no peaks).
warpus
Sommerswerd asked me to change this
Exponential in terms of population or surface area? It'd probably be exponential in the first case but not the latter.
Are we assuming that there are no enemy civs?
Are we assuming that there are no enemy civs?
Off the top of my head, you should get something resembling a fibonacci sequence. You'll expand in a circle from your initial city, in a series of rings (more or less). There is a finite amount of food for each city, meaning that at some point a city's growth is capped. Settlers move slowly, so at some point settlers from the central cities won't be able to reach the edge of your empire in time to find an empty space. So eventually, the innermost cities won't contribute to growth at all, only the outermost x rings will. That's still exponential growth, assuming an infinitely large map.
City growth is capped in civ, but you said assume it's indefinite in your post. Doesn't change much if we do it that way. Initial city produces enough settlers for the first ring, then just grows. Won't matter if it grows at 1 point per turn, or if its growth gets slower thanks to food-buckets getting bigger (you didn't mention how to treat those). Each ring 1 city produces 1 or 2 settlers, whatever's required to make ring 2, then switches to linear growth. And so on for rings 3, 4, etc. Each city grows at a linear rate, but the number of cities grows at an exponential rate, so the overall population will grow exponentially. Even if the food-buckets increase in size, the slowing rate of growth for established cities will be outpaced by the growth rate of number of cities, so the overall population still grows exponentially, just a bit slower. Again, that will only work with an infinite map.
City growth is capped in civ, but you said assume it's indefinite in your post. Doesn't change much if we do it that way. Initial city produces enough settlers for the first ring, then just grows. Won't matter if it grows at 1 point per turn, or if its growth gets slower thanks to food-buckets getting bigger (you didn't mention how to treat those). Each ring 1 city produces 1 or 2 settlers, whatever's required to make ring 2, then switches to linear growth. And so on for rings 3, 4, etc. Each city grows at a linear rate, but the number of cities grows at an exponential rate, so the overall population will grow exponentially. Even if the food-buckets increase in size, the slowing rate of growth for established cities will be outpaced by the growth rate of number of cities, so the overall population still grows exponentially, just a bit slower. Again, that will only work with an infinite map.
Ah, you are right. I forgot about the increasing demand on food when growing. You can assume that growth costs a flat number of food for sake of simplicity.
I'm not satisfied with the answers. If you think growth is exponential give an argument that proves this.
I'm not satisfied with the answers.
If you think growth is exponential give an argument that proves this.
I'm not satisfied with the answers.
me said:
I'm satisfied with that answer.
Mise
isle of lucy
You still need a linear function somewhere to describe the case where the original city never produces a settler. I mean, the upper limit on city growth is exponential growth, where each turn a settler is produced in every existing city, has infinite movement, and settles a new city during that turn (meaning there's no linear component), but the lower limit is where the city never produces a settler (I'll ignore the case where a settler is produced but not used, or takes an infinitely long time to find a place to settle), and so there is only a linear component and no exponential component.
So I see the total population as having a linear component dependent on (a) the number of cities and (b) how long it takes to produce a settler, and an exponential component dependent on the same things, but inversely so for (b). I.e. the faster the city pops settlers, the slower the city grows, so the linear component gets reduced. The exponential thing also needs to account for the length of time taken for a new settler to find a free space to build a city, which will also be dependent on the number of cities.
So I see the total population as having a linear component dependent on (a) the number of cities and (b) how long it takes to produce a settler, and an exponential component dependent on the same things, but inversely so for (b). I.e. the faster the city pops settlers, the slower the city grows, so the linear component gets reduced. The exponential thing also needs to account for the length of time taken for a new settler to find a free space to build a city, which will also be dependent on the number of cities.
I'd just assume that for each 'turn', a city will grow by 1, or pop a settler that has time to move at least a few tiles and found a new city. If you only pop settlers from the edge of the civ, they'll always be able to found a new city inside of 1 'turn'. So every turn, interior cities grow by 1, exterior cities make a new city. The overall population on turn n+1 will be the population on turn n + the number of cities on turn n. The number of cities on turn n+1 will be the number of cities on turn n + the number of exterior cities on turn n.
Work out how you want your ICS to look, and it's easy to generate overall population numbers for however many turns.
Work out how you want your ICS to look, and it's easy to generate overall population numbers for however many turns.
I'm surprised everybody assumed or predicted exponential growth when it is so clearly wrong.
You have only shown that there is an exponential upper bound, you havn't really show that exponential growth can be achieved.
You are very easily satisfied
In fact, while trying to explain my objection, I figured out a simple proof why it cannot : imagine you had infinite settlers at your starting point at the start. The space they can cover is only quadratic with time, so that's an upper bound on the growth of the number of cities, since this scenario is strictly more optimistic than any actual model.
Assuming a linear upper bound on the growth of individual cities, this gives a cubic upper bound on global population growth.
You have only shown that there is an exponential upper bound, you havn't really show that exponential growth can be achieved.
You are very easily satisfied
In fact, while trying to explain my objection, I figured out a simple proof why it cannot : imagine you had infinite settlers at your starting point at the start. The space they can cover is only quadratic with time, so that's an upper bound on the growth of the number of cities, since this scenario is strictly more optimistic than any actual model.
Assuming a linear upper bound on the growth of individual cities, this gives a cubic upper bound on global population growth.
Now that we have an upper bound, let us try to achieve it.
Assuming movement as in civ and that cities build settlers in at most constant time, we can demonstrate quadratic growth in the number of cities, as follows.
1. Each city produces 2 settlers. (at most constant time)
2. For each city, one of the settlers moves 3 steps north, the other 3 steps east. (constant time)
3. All the settlers found cities where they are. Extra settlers are disbanded.
and repeat.
Each repetition takes constant time and, starting with 1 city, we get 3,6,10,15... or n(n+1)/2 at the nth step, achieving quadratic growth in the number of cities.
Of course, this is extremely wasteful, I just wanted to show that the quadratic upper bound is actually achievable.
Now, suppose we assume linear population growth in each city when not building settlers, the upper bound for total growth is cubic (as I said earlier). To achieve it, we need to modify the algorithm above so that cities stop producing settlers.
Simply have only the cities founded at the last step produce settlers (they will be those on the NE boundary), and the others focus on growth. Assuming linear city growth, this yields cubic growth (the population growth between each step is proportional to the number of cities growing, which grows quadratically).
Assuming movement as in civ and that cities build settlers in at most constant time, we can demonstrate quadratic growth in the number of cities, as follows.
1. Each city produces 2 settlers. (at most constant time)
2. For each city, one of the settlers moves 3 steps north, the other 3 steps east. (constant time)
3. All the settlers found cities where they are. Extra settlers are disbanded.
and repeat.
Each repetition takes constant time and, starting with 1 city, we get 3,6,10,15... or n(n+1)/2 at the nth step, achieving quadratic growth in the number of cities.
Of course, this is extremely wasteful, I just wanted to show that the quadratic upper bound is actually achievable.
Now, suppose we assume linear population growth in each city when not building settlers, the upper bound for total growth is cubic (as I said earlier). To achieve it, we need to modify the algorithm above so that cities stop producing settlers.
Simply have only the cities founded at the last step produce settlers (they will be those on the NE boundary), and the others focus on growth. Assuming linear city growth, this yields cubic growth (the population growth between each step is proportional to the number of cities growing, which grows quadratically).
This was the problem with your argument.
Exponential growth means that the growth is proportional with the value.
As the empire gets bigger, the ratio that is in the outermost x rings goes to 0, hence if only that contributes, it certainly can't be exponential growth of number of cities (unless there were other unrelated speedup factors).
I salute you. Your answer is absolutely correct.
Regarding the bonus questions: In Civ4 it's not possible to go beyond quadratic growth in city numbers no matter what. However, it is possible to achieve true exponential growth in Alpha Centauri and Civ2. Do you see how this can be done? In Smac they are actually two different ways.
Your answer is absolutely correct.Regarding the bonus questions: In Civ4 it's not possible to go beyond quadratic growth in city numbers no matter what. However, it is possible to achieve true exponential growth in Alpha Centauri and Civ2. Do you see how this can be done? In Smac they are actually two different ways.
Can you prove the ratio of exterior cities to total cities goes to 0?
I compared it to the fibonacci sequence, if you look at those, the ratio of T(n):S(n) doesn't go to 0, it actually goes to 1/Phi^2, where Phi is the golden ratio aka (sqrt (5)+1)/2. That sequence does grow exponentially.
Any reason you can't place your cities in a growing spiral like that, with every city in the outer 2 spirals producing a settler/founding a new city each iteration, and the other cities simply growing once per iteration?
I salute you.
Regarding the bonus questions: In Civ4 it's not possible to go beyond quadratic growth in city numbers no matter what. However, it is possible to achieve true exponential growth in Alpha Centauri and Civ2. Do you see how this can be done? In Smac they are actually two different ways.
It's been a while since I've played either of these games...
For Civ 2, I think the growth of the number of cities would be limited for the same reasons (movement speed).
If you can do exponential population growth, it would seem it would have to be through very fast city growth. I seemed to recall that you could add settlers to city even if the food balance was negative, so if you can achieve exponential settler production, that would be enough. I'm not sure how that would be possible though, since I think you can produce at most one unit (or anything) per turn per city.
I might be missing something, as it's been a while, but I don't see how to do it in Civ 2 (I remember caravans being somewhat tricky, is it something to do with those?). SMAC I remember even less, but it has way more tricks and I would be less surprised if it could be achieved there.
EDIT: I've just reread your post, it's not clear, but you seem to be implying that you can have exponential growth in the number of cities (not just population) in Civ 2. I am really puzzled and really can't see how to get around the movement problem.
I will be very interested to hear your answer.
You seem to be mixing up very different things. The fact that the ratio of consecutive Fibonnaci number converges is well-known (and yes, this implies that the sequence grows exponentially). What this has to do with our problem at hand, I don't know. I think too many of you were focused on the production of settlers (comparing to the rabbit problem), while the problem is essentially one of movement speed.
You can place your cities in a spiral if you want, that doesn't change the fact that, after n turns from the start, everything you own will be contained in a 2n+1x2n+1 square centered at your starting point, simply because of movement speed (again, just think of starting with an infinite number of settlers). In particular, the number of cities is bounded by a quadratic function.
I think an experiment might convince you:
Try to really achieve your Fibonnaci sequence for the number of cities.
That is, forget about city growth, just try to get an exponential number of cities.
I'll even allow you to build cities right next to each other, for simplicity.
And cities build settlers in 1 turn. In fact, I'll be even nicer, cities can create as many settlers as you want in a single turn (but the turn after the city is founded)!
BUT settlers can only move one square per turn (let's say they can move+found in one turn).
Now, try to match the Fibonnaci sequence with the number of your cities. That is, try to have F_n cities after n turns.
Even with all my generosity, you will still run into problems at some point.
Well, the gritty details depend on how exactly you set up the cities, but there are handwavy arguments that should be convincing.
Most "natural" shapes your empire could or would take have an area that is proportional to the square of the "boundary" and hence also proportional to the square of the area that is within a fixed distance of the boundary. This implies that the ratio between this latter area and the whole thing goes to 0. If the city densities are more or less bounded in both regions, that will lead to the city ratio to also go to 0.
To take an explicit example : suppose we start with an infinite supply of settlers at the origin, and try to build them so they are at least 3 squares apart (2 squares in between them) as fast as possible. After n turns, we will have very close to 4n^2/9 cities (4 for the 4 quadrants, 1/9 for the density). For n much larger than x, the number of those which will be within x of a border city will be something like 8nx/9 (the empire is basically a big square with side 2n, so perimeter 8n, you could make more precise but this is the highest order term).
For fixed x, 8nx/9 over 4n^2/9 goes to 0.
Similar threads
- Locked
- Locked
