StarCraft II Build Order Optimization

A Terran base with the starting six workers. A seventh is being created in the Command Center.

The StarCraft franchise developed by Blizzard Entertainment is one of the most popular real-time strategy video games. StarCraft launched in 1998 and gave rise to celebrity-status professionals and prestigious tournaments, and is still updated with new content and expansions. Essentially a war simulation, the goal of the game is to eliminate your opponent by amassing an army and making your opponent forfeit, or destroying all of your opponent’s structures. A player has a choice of playing as three different races – Terran, Protoss, or Zerg – all with unique units, buildings, abilities, and mechanics. A player begins with nothing but a base and six worker units meant for collecting resources (minerals and gas) that are used to produce structures and more advanced combat and support units. The opening minutes and the timing of certain actions are crucial to the outcome of a game, as delaying unit production or failing to produce workers for a robust economy can cost a player a win. With this in mind, linear programming lends itself to finding the shortest time one can implement a rush-based build order, under 3 and a half minutes, with respect to a simplified model of unit, building, and resource economies.

Inspiration and Method

Inspiration comes from Churchill and Buro’s Build Order Optimization in StarCraft, an article focused on artificial intelligence advancement with respect to StarCraft. The authors successfully created a “planner” that when incorporated with a playing agent performed comparable to professionals. Methods included a depth-first branch and bound algorithm that takes a game state and performs a recursive search on possible build orders that satisfy a particular goal. The goal of this project was to apply linear programming to their notion of optimizing build orders and assess its efficacy. Regarding a linear programming method for approaching this problem, the critical path method was the original idea.

The Terran tech tree, showing building and unit prerequisites.

Each race has a particular tech tree that describes the prerequisites for constructing certain buildings and which units those buildings may produce. One can think of the the game as a task scheduling problem. For example constructing a Protoss Gateway, a first tier combat-producing building, is a critical activity for producing a Protoss Zealot, a first-tier combat unit. The critical path method however does not suffice due to the added complications of resource generation and management, continuous worker production, supply tracking, and race-specific mechanics. It is important to note that these models are consistent with game data from the particular StarCraft II expansion Wing of Liberty, as starting worker values and other parameters change in later expansions.

Model Overview

Definitions

Definition	Protoss	Terran	Zerg
First Tier Building	Gateway	Barracks	Spawning Pool
First Tier Combat Unit	Zealot	Marine	Zergling
Supply Building	Pylon	Supply Depot	Overlord

A close-up of a Terran Supply Depot

Supply is defined in-game as the sum of the number of workers and first tier combat units. Each race has a particular supply limit, and once that limit is reached, a player must build a supply building before they are allowed to produce any more units. The strategy is to construct such buildings well before the supply limit is reached, so that unit production does not come to a halt.

Basics

The models for the opening minutes of a StarCraft game are discrete in time, and variable are either declared integers or are integers by nature, other than minerals. For example, the following lines of code for the Protoss race’s model define the total minerals, workers, Zealots, Gateways (variable named Barracks for consolidation purposes), and supply at time t.

• var Minerals {t in 1..T} >= 0;
• var Workers {t in 1..T} integer >= 0;
• var Zealots {t in 1..T} integer >= 0;
• var Barracks {t in 1..T} >= 0;
• var Pylon {t in 1..T} >=0;

There following are additional integer variables that denote the start of construction of a building or unit:

• var build {t in 1..T} integer >= 0; Denotes the start of construction of a first tier building at time t
• var create {t in 1..T} integer >= 0; Denotes the start of construction of a first tier combat unit.
• var Create_Worker {t in 1..T} integer >= 0; Denotes the start of construction of a worker unit.

The variable "build" denotes the start of construction of a first tier building, "create" denotes the start of a first tier combat unit, and "Create_Worker" denotes the start of producing a worker. There is also a variable for each race that denotes the start of constructing a supply building. Construction of buildings and units takes time that varies from race to race which will be shown. The method for tracking unit economies lies in the constraints. The following constraints track minerals and Zealots respectively for each discrete time point.

A Protoss Zealot

A Terran Barracks

subject to Mineral_Count {t in 2..T}:

• Minerals[t] = Minerals[t-1] + Workers[t-1]*rate - 150*build[t-1] - 100*create[t-1] - 100*Pylon_Start[t-1] - Create_Worker[t-1]*50;

subject to Zealot_Count {t in 28..T}:

• Zealots[t] = Zealots[t-1] + create[t-27];

The coefficients in front of the latter four terms in the "Minerals" constraint correspond to their respective mineral costs of construction. Each worker collects a certain number of minerals per second. Additionally, notice that a Gateway will take 27 seconds to produce a Zealot, so the Zealot count is updated using the "create" variable at the time point 27 seconds in that past. The following lines of code implement that tech tree that dictates a player must have, for example, a Gateway before producing a Zealot.

subject to Available_Buildings {t in 47..T}:

• Available[t] = Available[t-1] + build[t-46] - create[t-1] + create[t-28];

subject to Building_Existance {t in 1..T}:

• create[t] <= Available[t];

First tier building construction takes 46 seconds to complete and the buildings are ready to produce units upon completion. Supply constraints are implemented by simply summing the number of workers and first tier combat units and ensuring it is less than the initial race's supply cap plus the number of supply buildings multiplied by 8, which is the number of supply each supply building provides. Details are discussed in the following section.

Race Specific Differences

Each race contains slight nuances that present their own challenges with respect to model economies.

Worker Dynamics

The most apparent differences are the worker dynamics with respect to building construction. While Protoss workers simply drop an orb that constructs itself over a certain period of time (46 seconds for a Gateway and 30 seconds for a Pylon), Terran workers remain occupied for the duration of construction. A Zerg worker is in fact lost when instructed to construct a building. The following code shows an additional term at the end that reflects Zerg worker loss.
Zerg Worker Economy
subject to Worker_Count {t in 13..T}:

• Workers[t] = Workers[t-1] + Create_Worker[t-12] - build[t-1];

Most complicated of course are the Terran worker economies, as 3 additional constraints must be added to account for occupied workers.

A close up of a Terran worker

Additional Terran Constraints
subject to Worker_Count {t in 13..30}:

• Avail_Workers[t] = Workers[t-1] - Supply_Start[t-1] - build[t-1];

subject to Worker_Count2 {t in 31..46}:

• Avail_Workers[t] = Workers[t-1] - build[t-1] - Supply_Start[t-1] + Supply_Start[t-30];

subject to Worker_Count3 { t in 47..T}:

• Avail_Workers[t] = Workers[t-1] - build[t-1] + build[t-46] - Supply_Start[t-1] + Supply_Start[t-30];

Supply

All races begin with 6 workers. Both the Protoss and Zerg start with an initial maximum supply of 10. The Zerg begin with an Overlord that provides 8 supply, and their base provides an additional 2. The Protoss' base provides 10 supply. The Terran base provides 11 supply. Each race's supply building provides 8 supply, and the following code shows the slight differences between how the models track supply.
Terran:
subject to Unit_Count {t in 1..T}:

• Workers[t] + Marine[t] <= 11 + 8 * Supply[t];

Protoss:
subject to Unit_Count {t in 1..T}:

• Workers[t] + Zealots[t] <= 10 + 8 * Pylon[t];

Zerg:
subject to Unit_Count {t in 1..T}:

• Workers[t] + Zergling[t] <= 2 + 8 * Overlord[t];

Additional Differences

An early-game Zerg base with a Spawning Pool as well as an Extractor for collecting gas.

The Zerg race uses larvae produced at their base to produce Zerglings provided a Spawning Pool exists. Only one Spawning Pool is required as opposed to other races who can take advantage of producing Marines or Zealots from multiple Barracks or Gateways simultaneously. Additionally, Spawning Pools cost 200 minerals while Barracks and Gateways cost 150. A pair of Zerglings costs 50 minerals, a Marine costs 50, and a Zealot costs 100. Zealots and Zerglings take 27 to complete, and Marines take 18 seconds.

Data

The following data chart is used across all races. Note that T corresponds to in-game seconds.

Parameter	Value
T (run time)	200
rate (minerals/worker/sec)	0.625
minerals0 (initial minerals)	0
workers0 (initial workers)	0
marines0 (initial tier1 units)	0
barracks0 (initial tier1 buildings)	0

Objective Functions

The objective functions for each race are essentially identical. The goal is to maximize the following value:

• sum {t in 47..T} build[t-46]*150/t + sum {t in 1..T} create[t]*100/t;

Notice that this value is maximal when the nonzero values of "build" and "create" occur at the smallest possible t. The variables are multiplied by their respective associated mineral costs. The above example is for the Protoss - a Gateway costs 150 minerals and a Zealot costs 100. It was noticed that the variable weights can chosen somewhat arbitrarily. Ideally, the weights would change so that after producing a Gateway, their is not as much priority on the second one. This was noticed most prominently in Terran's case where Barracks are prioritized over Marines.

Results

Protoss Build - 2 Gate Zealot Rush

The desired existing build order for Protoss

Action	Start	Completed
Worker	14	26
Worker	27	29
Pylon	49	79
Gateway	78	124
Gateway	108	154
Zealot	128	155
Zealot	154	181
Zealot	168	195
Probe	181	193
Probe	188	200
Zealotx2	200	227

The only difference between build orders is that the linear programming model prioritizes Zealots over workers. Building two workers before beginning Zealot production would delay the time of completing the first Zealot.

Terran Build - 3 Barracks Marine Rush

The desired existing build order for Terran

Action	Start	Completed
Worker	14	26
Worker	27	39
Worker	38	50
Barracks	67	113
Worker	76	88
Worker	84	96
Barracks	108	154
Barracks	130	176
Supply Depot	144	174
Marine	156	174
Marine	159	177
Marine	176	194
Marine	184	202
Marine	187	205
Worker	188	206

Again, due to objective function prioritization, two Barracks finish before Marine production starts. Dynamic prioritization could possibly produce a similar build, but with earlier Marine production at the expense of slightly later Barracks timing.

Zerg Build - 8-Pool

The desired existing build order for Zerg

Action	Start	Completed
Worker	14	26
Worker	27	39
Spawning Pool	68	114
Worker	80	92
Worker	91	103
Zergling Pair	114	141
Zergling Pair	119	146
Overlord	128	158
Zergling Pair	137	164

Zergling production continues at the following time points: 146, 155, 164, 172, 181, 190, 199, and 200 seconds. This build order only differs from the original in Overlord timing. This is of course in an effort to produce Zerglings as soon as possible.

Afterthoughts

Hard Coding

Choosing the placement of the first Pylon with a visible potential power field.

Some hard coding was necessary to produce desired results in a timely fashion. Firstly, the Pylon timing was hard coded as a constraint.
subject to PylonReq:

• Pylon_Start[49] = 1;

The Protoss have a special condition. Pylons produce a circular power field, and building construction is limited to these power fields. A fix for this issue would be to implement a conditional variable that equals zero when there are no Pylons, and one otherwise. Multiplying this conditional variable by the "build" variable in the Protoss' Gateway constraint would ensure a Pylon exists to power buildings.
Another instance of hard coding was the timing of the Zerg Spawning Pool. This was in fact because only one Spawning Pool is required, and the timing choice is the user's. The particular pre-existing build called for a Spawning Pool at 8 supply, which led to evaluating the worker output, noting the instant the supply reached 8 and the mineral count 200, and hard coding the Spawning Pool timing accordingly.
subject to 8pooltime:

• build[68] = 1;

Additional hard coding included designating a particular number of worker for the build as well as the number of Barracks in the Terran build. These were choices made with respect to the desired build order, and aided in simplifying consistent worker generation and the objective function. Problems arise when worker terms are included in the objective function - the function becomes unbounded.

Output

The Mineral output for the Terran model

The Zerg Worker count for the 8-pool build order

During model manipulation and testing, the output became invaluable. Displaying worker count and mineral count provided great insight into how the economies changed given certain actions. The linear program not only successfully produces comparable rush-based build orders to existing ones, but provides the user with some useful data such as economic situations at later time points and how one more or less worker can impact the timing of building and unit creation.

Limitations and Missing Elements

There is a large part of the game that linear programming cannot model, such as various powers and abilities different units and buildings possess. For example, the Protoss base can accumulate energy, and expend a particular amount of energy to use the "Chrono Boost" ability which speeds up the production of a unit by a certain percentage. Terran are able to call down MULEs that mine minerals at an increased rate. Zerg units have a faster movement speed while standing on "creep" - a slimy substance that surrounds their base and spreads given the existence of certain units. Nonlinearities such as these and probabilistic actions that depend on game state are beyond the scope of what this basic linear program is suited for. The model's run time is another one of its disadvantages. This model, written and solved using AMPL and CPLEX, can take an astoundingly long time to run. Some runs had to be terminated after more than 7 hours. Hard coding became handy in this case, to reduce the amount of iterations required by the algorithm. The successful Protoss build took 49093070 simplex iterations, and other runs exceeded 220 million iterations. This is most likely due to the existence of large numbers of integer variables. Player versus player interactions and unit micro-management are other game aspects not assessed by such a linear programming model.

Future Work

The next steps for the model is to include gas as a resource. This will open up multiple new possible units and buildings, but presents large challenges. Gas is mined by workers similarly to minerals after a building is constructed on gas geysers. There are two gas geysers per base, and gas is mined at a maximal rate with 3 workers assigned to the geyser. This means workers must be re-assigned to collect gas from minerals. The following shows initial constraints to implement a simple gas economy.

subject to Gas_Total {t in 2..T}:

• Gas[t] = Gas[t-1] + Gas_Workers[t-1]*rate;

subject to Assigned_Task { t in 1..T}:

• Gas_Workers[t] + Mineral_Workers[t] <= Workers[t];

However, the addition of such an economy would further reduce efficiency with respect to model solve time. Solve time is another priority, and relaxing integer constraints might aid in that respect with the challenge of producing plausible results with respect to game strategy. The objective function also requires improvement to reflect the dynamic prioritization that occurs after first tier buildings complete and unit production is available.
This linear programming model proved to be a useful tool for finding precise timings down to the second for actions rather than supply guidelines for build orders. With improved run time and a more complete model including gas and a fuller tech tree, this model could be used to develop, alter, and optimize early-game build orders.