Starcraft AI blog

It’s possible to reason about Starcraft games straight from the details, without explicit abstractions. One of the promises of deep learning is that it allows you to get away with that, to feed concrete facts into a black box and get back concrete actions (so that all the abstraction is hidden inside the black box), and deep learning is not the only way. I believe that for a complex game, it’s probably better to introduce abstractions and do much of your reasoning at an abstract level. For Steamhammer, I selected four levels of abstraction, which I call strategy, operations, tactics, and micro (the breakdown is not perfectly cleanly implemented right now, but I keep moving in that direction). This post is about strategy and how to represent it as a data structure.

The three classic elements of a Starcraft strategic situation are economy, technology, and army. I would like to add a fourth element (less emphasized in abstract theory but never overlooked in practical discussions), production facilities. These four elements are the things that you can spend resources to buy, and that you have to trade off as you make each spending decision. (Do I spend this on another dragoon, or a second gateway so I can later make dragoons faster, or do I get dragoon range?) I’ll call them the elements of strategy—that simplifies the meaning of the word “strategy,” but let’s go with it. If you can fully represent the four elements, then you can fully represent the strategic situation of a game.

You have only partial information about what the opponent is doing, but you know all about your own state. You may not want to store both using the same datatype, though you could. It’s elegant if both have the same underlying model, at least. You might store exact values for your own strategic situation and probability distributions over the same values for the enemy’s situation, for example. It’s ideal to use all available information to estimate the enemy values: Scouting info, feasibility calculations (“at this frame it’s not possible to have more than n workers”), past behavior saved in learning files, hand-coded constraints from reading the enemy bot’s code....

If you know how the strategy elements varied throughout a game, then you know a lot about what happened in the game. You don’t know the maneuvers, but you know who won and you know the ebb and flow of the battles.

economy

I think there are 3 things you’d like to know about a player’s Starcraft economy. 1. Total minerals and gas mined so far. 2. Current rate of mining minerals and gas. 3. Predictions of the future rate of mining minerals and gas, perhaps under varying assumptions so you can choose a course of action. For example, if the map is running low on minerals after a long game, it’s likely wasteful to make more workers.

For 1 and 2, it’s easy to keep track of your own current state. For the enemy, there are occasions when you can get exact values for 1 and 2, but usually you’ll have to estimate. And 3 is always an estimation problem. Data useful for making the estimates includes number of workers, number of mineral patches, and so on. For the enemy, you have to estimate those too. (If you don’t have an estimate of the number of enemy workers then you won’t be able to decide on the priority of killing a worker versus another unit, a question that falls under 3.)

technology

A command center is a tech building, because it allows you to build SCVs. (It’s also a production building.) A tech state is simply a set of tech buildings and research and upgrades: These things are the tech that I have, I can make (say) SCVs and marines and turrets because I have a command center and a barracks and an ebay. I’ll call it the tech set which represents a given tech state.

The set of tech states is partially ordered by the relation of teching: If you can tech from A (I can make marines) to B (I can make marines and medics and firebats because I added an academy), then you can say B > A. The partial order gives you a bit of mathematical leverage to reason about tech states (I see a medic, the enemy must have an academy—Steamhammer does this reasoning). The enemy can destroy buildings, though. Destroy the barracks and you’re in a state C with academy but no barracks, which cannot be reached by teching from the start state. C is neither greater than nor less than A, but B > C because you can tech from C back to B by rebuilding the barracks.

production

The production buildings are those that make units. The terran production buildings are command center, barracks, factory, starport. The more copies you have of a production building, the faster you can make units—provided you have the tech and the economy for them. There are complications for every race. Terran can spend resources to repair. Protoss reavers and carriers rely on scarabs and interceptors, which cost minerals. The only zerg production building is the hatchery (and lair and hive), but hydras may be able to morph into lurkers and mutas may be able to morph into guardians or devourers. These are all spending decisions, so they count under my definition of strategy.

You can represent your terran production state as a count of each of CCs, barracks, factories, starports. For protoss, you might want to include reavers and carriers are production facilities, or you might ignore them as irrelevant for the strategic reasoning you care about. For zerg, you may want to count hydras as production facilities if you have lurker tech and mutas if you have a greater spire, and if you’re reasoning about details you should count larvas too.

army

Your army state is simply your count of units of each type. If you care, you might also keep health information. The hard thing about armies is not knowing what they are, it is comparing their strengths and knowing what they can do.

The four strategy elements are all interrelated. Production facilities you see can help you predict the enemy’s unit mix, and enemy units you see can help you predict their production state. Economy and production tell you how fast an army can grow. You get the idea.