How to solve this Civ5 inspired optimization problem

Factual Questions
1

I’ve been playing and watching Civilization 5, and I thought of a cute optimization problem that I’d like some ideas on. For those of you have played Civ 5, the idea is optimizing your production time on a wonder in certain ideal conditions. The “ideal conditions” being assuming a city with no border pops, unchanging tile improvements, no special buildings like an aqueduct, no hammer/food trade ships, infinite happiness, and so on. Basically a city that is JUST working tiles.

I tried to define the problem as formally as possible:

We start with a city with population p, current surplus food f, and food income i. A city grows when its current surplus food, f (as above), is greater than or equal to some value given by the function foodCost(p) where p is the same value as before. The exact value of foodCost is known, but irrelevant (in that the problem can be solved in terms of the function, not that it doesn’t matter).

Each turn, f is increased/decreased by i-2p (the income minus 2 times the population), whenever the population grows (the surplus is greater than the food cost), f is reset to f-foodCost(p) and p is increased by one. That is, the population grows by 1 and the current supply of food is equal to the amount of surplus exceeding the requirements for growth. If f dips below 0, f is set to 0, and p decreases by 1.

This city is trying to build a wonder, which requires a resource called hammers. We start with some value of hammers called h, and each turn we get b hammers. Meaning: each turn h is updated to h+b. If the number of hammers exceeds some value requiredHammers, the wonder is built and the problem is satisfied (this is our “end condition” or “goal state”).

Now comes the tricky interaction: The city has some set of tiles t ∈ T. On any given turn we are working min(p,|T|) tiles – we work as many tiles as we have people, unless we exceed the number of tiles in which case we just work all of them. The values of i and b are directly determined by the tiles we’re working. Specifically, each tile has two values we’ll call t.i and t.b that are greater than or equal to zero. Each turn the values i and b are equal to the sum of the t.i and t.b values (respectively) of the min(p,|T|) tiles we’re working.

The problem is then: optimize the selection of tiles to minimize the production time of the wonder (number of turns to complete it). The tricky part is that increasing p and getting another tile to work may or may not decrease production time, so it may be advantageous to not take a tile with extra hammers in the early turns to increase the hammers in later turns.

We can assume that there always exists at least one tile selection such that b is positive.

I used my optimization crutch, a graph search, to solve it. And it works. Given some initial state I can generate successor states upon request and run BFS to determine exactly which tiles I should have selected each turn. But I feel like there should be a better way to do this. Any ideas?

2

It sounds to me like this works the same way as in Civ 3, which is what I’m familiar with. In that case, a general heuristic is to maximize food production until you have enough population to work all available tiles, and then in a single turn switch completely over to maximum hammers (subject to the constraint that you’re not starving) for the rest of the duration. In the limit of high wonder cost, this method approaches optimality. Real wonders do not of course have infinite cost, but they’re usually close enough to be a good approximation.

That said, though, in the real game you’re likely to be able to shave off a turn or two due to various edge effects, of which you’ve got many. There’s a discontinuity every time the population changes, and another one at the end when it doesn’t matter how many excess hammers you have. Discontinuities are really hard to deal with using nice analytic functions, so you’re probably going to be stuck with either the brute force method you’re using now, or various approximate heuristics.

3

For people who read pseudocode, this may be a more succinct problem statement. Here would be roughly one “update cycle”



func NextTurn on integers p,f, h and set of tiles t ∈ T
    let i = 0
    let b = 0
    let U be a subset of T of cardinality min(p,|T|)
    foreach t in U 
        i += t.i
        b += t.b
    
    h += b
    if h >= requiredHammers
        Success()

    f += i - 2*p
    if f >= foodCost(p) 
         f -= foodCost(p)
         p += 1
     else if f < 0
         f = 0
         p = max(p-1, 1)

    NextTurn(p,f,h,T)

The goal is to smartly pick U each iteration so as to minimize the number of times NextTurn is done.

4

Yeah, it was mostly an interesting problem to think about. I’m generally okay at actually playing the game. You’re right that discontinuities are what make it really difficult. If assigning tiles give a more constant acceleration this would be more easily solvable with some integrals I think.