Optimising Civ 5 cities using genetic algorithms

I recently came across a paper from 2005 about using genetic algorithms to optimise cities in FreeCiv, a free game similar to Sid Meier's Civilization. Genetic algorithms are an interesting approach to complex problems. Their brute force, trial and error approach means that they are often less effective than other algorithms but for some scenarios they can be surprisingly effective.

The paper spurred me to publish this post as over the course of 2015 I sporadically worked on a similar side project which used genetic algorithms to assign citizens in Civilization 5. The 2005 paper does not include any actual algorithms and there does not appear to be any follow up, so in this post I will discuss the algorithm I arrived at and its results.

Contents

As this is quite a long post I have broken it down into sections so you can skip the preamble. If you just want to peruse the code then it's all here on GitHub.

Civilization 5 city management

A core part of Civilization 5 is managing your cities. A city has a population of citizens that can be assigned to assets within the city. These assets are either tiles representing the terrain within the city's borders (e.g. farmed grassland, mines or desert trading posts) or buildings within the city itself. A tile can be assigned a maximum of one citizen. Buildings can be assigned one or more citizens, depending on the type of building.

At its greatest extent a city will have access to 3 rings of hexagonal tiles surrounding its base tile. The first ring contains 6 tiles, the second 12 and the third 18. The screenshot below shows the city management screen with assignable tiles being highlighted in green (currently assigned) and blue (not assigned) and assignable buildings appearing on the right under the heading of "Specialist Buildings".

The Civilization 5 city screen

When a citizen is assigned to a tile or building they generate resources that contribute towards the success of the city and your empire. There are a number of resource types but the most important ones are food, production, gold and science. Citizens can also be left unassigned in which case they might also produce some resources (usually not much) depending on game factors which are not relevant here.

In order to squeeze the most out of your cities it is often necessary to micromanage citizen assignments. In a newly founded city you might want to prioritise food in order to stimulate growth, in a city with access to luxuries (e.g. gems, spices or truffles) you might want to maximise gold and so on.

The game has built-in shortcuts for citizen assignment which can be used to assign citizens automatically to maximise a given resource type. This is fine if you simply want to focus on one particular resource type (apart from the minimal amount of food necessary to feed your citizens). However if you want to take a more nuanced approach - e.g. focusing primarily on production but also favouring science over gold - then it becomes more complicated.

This is the kind of complex scenario to which genetic algorithms can be applied to good effect.

Back to top

A (very) short introduction to genetic algorithms

Genetic algorithms are a topic that crops up every now and then on programming sites like /r/programming so there is a good chance you are already familiar with them. If not, this post by Lee Jacobson is an excellent basic introduction using Java.

A genetic algorithm aims to solve a problem by mimicking the process of evolution via natural selection. For a given problem a genetic algorithm requires 4 things:

The process is then fairly simple. A basic genetic algorithm might take the initial population and evaluate the fitness of each solution - if an acceptable solution exists then return that solution as the result. If no acceptable solution exists then use the combination and mutation functions to create a new population based on the fittest members of the current population and re-evaluate. The process can be repeated until an acceptable solution is found or some other exit criteria is reached. Note that genetic algorithms are essentially informed trial and error and so are not guaranteed to find the optimal solution for any given scenario.

The algorithm will generally have a limit on the number of times the process can be repeated before exiting. If the combination, mutation and fitness functions are suitably written then in general the fitness of the population as a whole should rise with successive generations.

That last sentence is really important. The complexity of the combination, mutation and fitness functions can increase enormously as the complexity of the scenario increases. Before turning my attention to Civilization 5 I originally looked at using genetic algorithms to try and create effective armies in Total War: Rome II. The sheer number of factors to consider (e.g. the multitude of unit stats and abilities, the definition of an effective army etc.) meant that the algorithm could just about produce viable armies but very little else.

So, before using a genetic algorithm for anything ensure that you are confident that you can effectively define combination, mutation and fitness functions.

Back to top

Implementation

The algorithm I arrived at works on a basic model of the Civilization 5 city screen that provides useful functions like the ability to assign/unassign citizens, calculate resource yields etc. I will not describe this model in detail here, but if you are interested then see Model.fs. Similarly there are a number of utility functions for working with random numbers, lists, optional values etc. that can be seen in Shared.fs

There are two parts to the algorithm - a set of foundational functions that describe how populations are evolved and a set of functions specific to Civilization 5 citizen assignments that can be passed to those foundational functions.

Back to top

Foundations

The first thing we need to do is give proper definitions to our combination, mutation and fitness functions given a solution type 'T.

type CombineFunction<'T> = 'T -> 'T -> 'T
type MutateFunction<'T> = 'T -> 'T
type EvaluateFunction<'T> = 'T -> Decimal

So the combine function takes two instances of 'T and combines them to create a third. The mutation function takes an instance of 'T and mutates it, usually in a fairly minor way. Finally, the fitness evaluation function takes an instance of 'T and returns a decimal score. Depending on the problem domain this might be a percentage or a points score of some kind.

Next, we can define a record type that contains settings for the algorithm.

type AlgorithmSettings<'T> = {
    IsElitist : Boolean; 
    TournamentSize : Int32;
    MutationRate : Decimal;
    Combine : CombineFunction<'T>;
    Mutate : MutateFunction<'T>;
    Evaluate : EvaluateFunction<'T>;
    Population : 'T list;
}

This record contains the current population, the three functions used to evolve the population and some settings that control how that evolution is affected.

The IsElitist flag is used to specify whether the fittest individual in a population should be carried forward to the next generation.

The MutationRate setting is used to control how often mutations occur during evolution - e.g. a setting of 0.25 would result in the mutation function being applied to approximately 1 in 4 of the offspring produced by the combination function.

Finally, the TournamentSize setting controls how large the tournament that is used to select individuals during combination is (see Lee Jacobson's post for information about tournaments).

Running a tournament given an instance of our settings record is straight forward - randomly select competitors from the population and return the fittest.

let run settings = 
    settings.Population
    |> List.selectMany settings.TournamentSize
    |> List.maxBy settings.Evaluate

Creating a new population based on the current one is similarly straight forward - run tournaments and use the combination function to create offspring until we have a new population of the desired size.

let combine settings = 

    let init _ = 

        let x = Tournament.run settings
        let y = Tournament.run settings

        settings.Combine x y

    let size = List.length settings.Population

    let offspring = Array.Parallel.init size init
    in Array.toList offspring

Note that this method allows what we shall delicately call "self combination" - the same individual could be selected from the population by both tournaments.

Now that we have a new population all that remains is to apply mutations.

let mutate settings individual = 
    if (RNG.rate settings.MutationRate) then
        settings.Mutate individual
    else
        individual

The implementation of the RNG module as well as the related List.selectOne and List.selectMany functions can be seen in Shared.fs.

We can put all of this together to create a function which evolves a population based on a settings record.

let evolve settings = 

    let offspring = 
        if settings.IsElitist then

            let fittest, remaining = 
                settings.Population
                |> List.sortBy settings.Evaluate
                |> List.rev
                |> List.detach

            let settings' = { settings with Population = remaining; }
            in fittest :: (combine settings')

        else
            combine settings

    offspring
    |> Array.ofList
    |> Array.Parallel.map (mutate settings)
    |> Array.toList

This function will use the population combination function defined above to create a new population, carrying forward the fittest member of the current population if the IsElitist flag is set, before applying mutations to the result. Note that when the IsElitist flag is set it is possible for the fittest member of the current population to be mutated.

Finally, we can now create a function which will evolve a population for a given number of generations, keeping a record of the fittest individual in each generation.

[<RequireQualifiedAccess>]
module Algorithm = 

    let run generations settings = 

        let rec runWithHistory generations (history, settings) = 
            if (generations = 0) then

                let history' = 
                    history
                    |> List.rev
                    |> List.index
                in (history', settings.Population)

            else
                let population = Population.evolve settings            
                let fittest = List.maxBy settings.Evaluate population

                let generations' = (generations - 1)
                let history' = fittest :: history
                let settings' = { settings with Population = population; }

                runWithHistory generations' (history', settings')

        runWithHistory generations ([], settings)

All of the code for the foundational functions can be seen in Genetics.fs.

Back to top

Civilization 5

Now that we have foundational set of functions that can be used to run generic genetic algorithms we need to implement the combine, mutate and fitness functions for our Civilization 5 citizen assignment scenario.

Our code algorithm can be thought of as an additional Civilization 5 advisor, so it will reside in the Advisor module. Firstly, we can define a record type which contains the advisor's settings. We can then use this record type to create our foundational AlgorithmSettings<'T> record where 'T will be the model type City.Instance.

type AdvisorSettings = {
    PopulationSize : Int32;
    TournamentSize : Int32;
    Generations : Int32;
    MutationRate : Decimal;
    Weightings : (YieldType * Decimal) list;
}
with
    static member Default =
        {
            PopulationSize = 40;
            TournamentSize = 8;
            Generations = 100;
            MutationRate = 0.3M;
            Weightings = 
                [
                    (YieldType.Food, 1M);
                    (YieldType.Production, 1M);
                    (YieldType.Gold, 1M);
                    (YieldType.Faith, 1M);
                    (YieldType.Culture, 1M);
                    (YieldType.Science, 1M);
                    (YieldType.GreatArtist, 1M);
                    (YieldType.GreatWriter, 1M);
                    (YieldType.GreatMusician, 1M);
                    (YieldType.GreatEngineer, 1M);
                    (YieldType.GreatScientist, 1M);
                    (YieldType.GreatMerchant, 1M);
                ];
        }

Most of the properties of this record are self explanatory. The Weightings property is used when calculating the fitness of a solution and allows us to specify the relative importance that each resource type should be given.

We can use the weightings to define a fitness evaluation function.

let evaluate weightings =

    let getWeightedValue yield' = 

        let type' = Yield.getType yield'
        let value = decimal (Yield.getValue yield')

        let factor = 
            weightings
            |> List.tryFind (fst >> ((=) type'))
            |> Option.map snd
            |> Option.unwrap defaultWeighting

        (value * factor)  

    fun city ->
        match city with
        | Starving -> 0M
        | _ -> 
            city
            |> City.getYields
            |>  List.sumBy getWeightedValue

Here we simply take the yields of the city, weight them accordingly and sum them. We use an active pattern to detect starving cities and arbitrarily give them a fitness of 0. Note that the defaultWeighting is 0 so if no weighting is supplied for a resource type then its yield will not contribute towards the city's fitness score.

Combining two cities is slightly more complex. The approach I have taken here is for each citizen to randomly choose between their assignment in the first city and their assignment in the second. If the chosen assignment cannot be used (e.g. the asset is a building and is at full capacity in the new city) then the citizen is left unassigned.

let combine =

    //Get a flattened list of assignments - e.g. [ (asset, 2); ] becomes [ asset; asset; ]
    let getAssignments =
        City.getCitizenAssignments
        >> List.collect (fun (asset, count) -> List.init count (fun _ -> asset))

    //Randomly chose between a city X and a city Y assignment
    let pickAssignment (assignmentX, assignmentY) = 
        if (RNG.flip ()) then
            assignmentX
        else
            assignmentY

    //Apply an assignment if possible. If not, the citizen is unemployed.
    let applyAssignment city asset = 

        let assetId = Asset.getId asset

        if (City.isAssignable assetId city) then
            City.assign assetId city
        else
            city

    fun cityX cityY -> 
        let assignmentsX = getAssignments cityX
        let assignmentsY = getAssignments cityY

        let unassignedCity = City.unassignAll cityX

        List.zip assignmentsX assignmentsY
        |> List.map pickAssignment
        |> List.choose id               
        |> List.fold applyAssignment unassignedCity

Similarly mutation is fairly complicated. The approach I have taken here is that if a city has unassigned citizens there is a 50/50 chance that one of them will be assigned to a randomly chosen asset. Otherwise a citizen will be unassigned and there is a 50/50 chance that they will be reassigned to a randomly chosen asset.

There is a bias here towards assigning rather than unassigning citizens - I took this approach because unassigned citizens rarely contribute towards a city as much as assigned citizens.

let mutate city = 

    let unassign, assign = 
        if ((RNG.flip ()) && (City.hasUnemployedCitizens city)) then
            //50% chance of assigning an unemployed citizen, if possible...
            false, true 
        else
            //Otherwise definitely unassign a citizen and 50% chance of assigning them elsewhere
            true, (RNG.flip ())

    let city' = 
        if unassign then
            let assetId = 
                city
                |> City.getAssignedAssets
                |> List.map (fst >> Asset.getId)
                |> List.selectOne 
            in City.unassign assetId city
        else
            city

    if assign then

        let assets = City.getAssignableAssets city'

        match assets with
        | [] -> city'
        | _ -> 
            let assetId = 
                assets
                |> List.map Asset.getId
                |> List.selectOne
            in City.assign assetId city'
    else
        city'

We can use these functions and the AdvisorSettings record to create an AlgorithmSettings<City.Instance> record that can be passed to our foundational Algorithm.run function. The initial population is created by taking a prototypical City.Instance that has no assignments and assigning citizens to the highest food producing assets until the city can feed itself, and then randomly assigning any remaining citizens.

For the purposes of this scenario we reformat the results of the Algorithm.run function. That reformatting and all of the various utility functions used above can be found in the Advisor module and can be seen in Civ.fs.

Back to top

Running the algorithm

The example program included in the GitHub repository loads details of the city from an embedded JSON file. This file contains the city's size (number of assignable citizens), base yields and details of tiles and buildings. The algorithm is run for the city and details of the final solution and fittest solution in each generation are printed to the console.

As you can see in the code above, the default settings for the algorithm are a population size of 40, a tournament size of 8, 100 generations and a mutation rate of 1/3. This is probably overkill for smaller cities.

You can run the program for yourself - simply configure the settings at the top of Program.fs and run the project. After a brief pause the results will be printed to the console.

In order to make the program's output as readable as possible I have assigned tiles a label in the format "ring/index". This diagram illustrates this system, where B is the base tile.

Results

We shall run our algorithm against two cities, one small and one large, and compare our results against the game's built-in shortcuts. These shortcuts allow you to quickly change citizen assignments within a city to focus on a particular resource type.

Firstly we shall compare the "default focus" shortcut which should be broadly equivalent to running our algorithm with every resource type given a weighting of 1.

Then we shall compare the built-in shortcuts for the four primary resource types (food, production, gold and science) to our algorithm. In this scenario the selected resource type will be given a weighting of 1 and all others will be given a weighting of 0.

Finally we shall run our algorithm with a variety of multi-focus weightings to see if the related resource type yields respond as we'd expect.

Some notes on the results:

Constantinople (11 citizens)

Our first set of tests will by run against the city of Constantinople (screenshot), a modest city with a few resource producing buildings.

The table below shows yields for the "default focus" scenario. Maximum possible yields for resource types are included in the headers.

Food (65) Production (41) Gold (35) Science (9)
Built-in shortcut 56 32 32 6
Genetic algorithm 54 30 33 9

As expected our algorithm, while significantly slower, produces similar yields to the built-in shortcut.

The next table shows yields for the four primary resource focus scenarios.

Resource Maximum Built-in shortcut Genetic algorithm
Food 65 65 65
Production 41 35 40
Gold 35 35 35
Science 9 9 9

For the most part our algorithm achieves similar yields as the built-in shortcuts. The notable exception is production, where our genetic algorithm sacrifices food for more production leaving the city stagnant with just enough food to feed itself (42). I did consider implementing a penalty for this condition but in the end I have only penalised starving cities.

Our algorithm is significantly slower than the built-in shortcuts, however the most useful property or our algorithm is that we can request more nuanced solutions than simply maximising a given resource.

The table below shows some example outputs for various focus scenarios. Weightings are shown as an abbreviation (food = F, production = P, gold = G, science = S) and their decimal value.

Weightings Food (65) Production (41) Gold (35) Science (9)
1.0F, 1.0P 61 34 25 3
1.0F, 0.75P 65 30 24 3
1.0F, 0.5P, 0.5G 64 31 33 3
1.0G, 0.5P 43 38 35 3
1.0S, 1.0G, 1.0P 45 36 35 9

Despite the trial and error approach the genetic algorithm seems to be arriving at good solutions. Production and food are produced by a large number of assets and so nearly always have high values. Gold and science, which are produced by fewer assets, vary more dramatically based on their weighting.

Mecca (28 citizens)

Below are tables of similar test runs using the much larger city of Mecca (city screen). As before we shall start by comparing the "default focus" yields.

Food (90) Production (99) Gold (51) Science (40)
Built-in shortcut 68 87 25 37
Genetic algorithm 58 76 33 40

With more citizens and more assets to assign the differences between our algorithm and the built-in shortcut become more noticeable. I believe this is because the built-in shortcut does not actually give exactly equal weighting whereas our algorithm does - e.g. it treats food exactly the same as Great Merchant points, whereas I suspect the built-in shortcut is slightly more nuanced.

The next table shows yields for the four primary resource focus scenarios.

Resource Maximum Built-in shortcut Genetic algorithm
Food 90 83 90
Production 99 96 99
Gold 51 51 51
Science 40 40 40

As expected, our algorithm is slightly better at squeezing resources out of a city but not by much.

Finally, the table below shows the yields for the same example focus scenarios used previously.

Weightings Food (90) Production (99) Gold (51) Science (40)
1.0F, 1.0P 87 92 25 16
1.0F, 0.75P 86 94 25 16
1.0F, 0.5P, 0.5G 86 86 37 16
1.0G, 0.5P 56 87 51 16
1.0S, 1.0G, 1.0P 57 85 40 40

It is notable here that, in the first two cases, the production yield is lower when weighted by 1.0 than by 0.75. This illustrates the imperfect nature of genetic algorithms - they will, with suitable combine, mutate and fitness functions, generally produce reasonable results but they are not guaranteed to find the "best" solution for any given problem, if such a thing even exists. All you can say is that it will generally arrive at a good solution.

Back to top

Conclusion

In this post I have shown how I approached the problem of optimising citizen assignments in Civilization 5 using genetic algorithms.

Genetic algorithms can be applied effectively to this kind of complex problem. The results show that, while significantly slower, for simple cases the algorithm produces similar solutions to the built-in shortcuts. However it is when the desired outcome is more complicated, and cannot be expressed simply as "maximise X", that genetic algorithms come into their own.

There are a number of optimisations which could be made to the algorithm that would improve performance. The population size and maximum number of generations could be set according to the population of the city - larger cities will likely require more work to optimise. There are a number of early exit strategies which could also be adopted - e.g. if a plateau in fitness scores is detected. I believe that with further optimisations the performance of my implementation could be improved significantly.

The full source code for the project is available on GitHub.

Back to top

Comments