Starcraft AI blog

In Starcraft it seems that decisions have to be made at about 3 levels of abstraction, which go something like this:

• strategy - what tech to pursue, when to expand, etc.
• tactics - maneuvering the army, deciding when to fight
• unit control - moving, targeting, casting

Most people seem to like 3 levels. Maybe some prefer 2 or 4. For example, if you have opponent modeling or strategy learning then you might want to write it in at the highest level, a meta-strategy level at which decisions have effects over multiple games. And of course there’s no agreement on the names of the levels or on exactly which decisions each one includes (the decisions above are examples and don’t cover everything). But my list is similar to most.

One way to look at it is that plans made at a higher level last longer and have to be made less often: They are in effect for a longer period. At the strategy level, which tech path you take or how many workers you cut for a rush may be part of a plan that the bot follows for minutes. At the unit control level, which enemy you target in a fight may have long-term consequences (do you win or lose the battle?), but the decision itself may be over in a fraction of a second and then it’s time for the next one. The paper A Survey of Real-Time Strategy Game AI Research and Competition in StarCraft points this out, as well as other differences between levels of abstraction.

Bottom up. The way I think of it is this: It’s theoretically possible to make all decisions at the unit control level. Your initial nexus is a unit, each probe it makes is a unit, all you have to do is give the right commands at the right time. But it’s crazy hard to coordinate a strategy if you only think at the detail level. Abstraction is necessary if you want to have effective game plans; it is just plain infeasible to find a good strategy by trying different patterns of low-level actions until you hit on something that works, simulated annealing-style. If it’s possible at all, that kind of strategy search has to happen offline.

Top down. On the other hand, PerfectBot certainly doesn’t make strategy decisions without considering the tactical and combat situations. The levels of abstraction are not isolated. Remember mine laying from yesterday: Mines have long-term strategic, short-term tactical, and immediate combat uses. To decide how to best to place spider mines, PerfectBot has to consider every level of abstraction.

Someday actual bots will want to consider every level of abstraction too. Cue topic hierarchical search, which I’ll write about someday. Another idea for integrating levels of abstraction is mission command, a term from the real life military. In outline, the commander sets overall goals and the subordinates figure out how to achieve them. One implementation for Starcraft (quite different from how it’s done in real life) might go like this: The strategy boss, paying no attention to the tactical situation, figures out possible strategic goals and scores them. “We need resources most of all, 100 points for a new expansion. We need to counter lurkers, 50 points for vessels and enough tanks. The opponent is taking bases, 50 points for killing an enemy base. It would be nice to harass, 20 points for wraiths to hunt overlords or 20 points for small drops to get drones.” The tactics boss considers tactical plans and scores them in part by how well they achieve strategic goals. “We can’t expand (0 points) or kill bases (0 points), we’re lurker contained (curse KillerBot!). Tech to vessels and make tanks until we can break out (50 points); harassment is worth less.” You get the idea.