Clash of Clans: Barracks Optimization

Hopefully this’ll be the first of a many part series to examine CoC in a more mathematical manner, and actually use some of the skills and technologies I have acquired over the years.

The first thing that raiders in CoC know is that time spent not raiding is wasted time. In order to minimize that wasted time, a critical thing to minimize is time spent building troops, spells and resting heroes. Spells and heroes has no build order to minimize, while troops has countless possibilities of building a set army.

The problem is fairly easy to define: given a certain army composition, use the given set of barracks and create that army in the shortest possible time.

Sounds easy right? Meh.

Scheduling Theory

My first impression is to use scheduling theory, and turn it into a simple library call to an approximation algorithm there. Unfortunately, there are several complications.

First of all, since there are multiple barracks, this is a multiple processor problem. Multiple processor problem are actually NP-hard, equivalent to the partitioning problem. Many heuristics exist for a standard problem of many processor, and many jobs for minimizing time. The standard is longest processing time first (LPT).

If one simply implements LPT on this problem, we have a weird problem. The heuristic was designed for processors of equal power, and barracks of different levels have different capacity. The second (more minor problem) is that we need to impose the constraint that a barrack can produce that particular troop (i.e. level 1 creating a P.E.K.K.A).

So in essence, this problem became much tougher using this approach. I guess I can read up on heterogenous processor research, but that’s for another day.

Integer programming

The next approach was to convert it to an integer programming problem.

Let us define our problem then. Let be the number of barracks, and be the number of different types of troops (defined to be 10 by the current patch, but let’s keep it flexible). Let be a column matrix of time to produce a single barbarian, archer etc., and be a column matrix of the corresponding capacity needed to train a troop. This means that both such that

Δ