Starcraft AI blog

It’s taking a long time to write up the uses of burrow, because there are so many, so here is a note on queue reordering.

Steamhammer retains UAlbertaBot’s production system, with a queue of items to produce. The queue lays out the exact order of units to make, research to do, and so on. In the beginning of the game, the queue is filled by an opening build from the configuration file. Later, the build order planner BOSS (for terran and protoss) fills the queue with long sequences, or the zerg strategy boss fills it with shorter sequences.

Most of the opening builds, though not all, are tightly written. Executing the build in order is normally efficient. But game events can intervene. For example, if the enemy scout harasses gas workers and slows down gas mining, maybe it will be more efficient to rearrange the order slightly. Maybe the 100 gas for the lair is delayed, and it makes sense to pull forward the drone that was going to be built afterward. The zerg strategy boss will often blindly misorder items the same way: It will ask for a lair that there is not enough gas to make yet, then (say) a second extractor that could be made immediately. And BOSS creates long and poorly-designed sequences with many items out of order.

I started experimenting with queue reordering in version 1.4 to mitigate these problems. The first version of queue reordering is extremely conservative: It recognizes only one case of misordering, the gas case where we are waiting for gas to start the first item in the queue, and we can pull forward a later item (up to 3 items later in the queue) that requires no gas and has no dependencies other than a worker to build it (a resource depot, a supply unit, a refinery building, or a zerg creep colony—the supply unit might be an overlord, which requires a larva instead). Also it doesn’t try to predict mineral income; there have to be enough minerals to build both items before it will reorder the queue. Because of this conservatism, queue reordering happens rarely, about once per game on average, and has virtually no effect on the bot’s strength. But it doesn’t seem to introduce any bugs despite its trickiness, so it proved the concept.

I got e-mail from a Steamhammer user who suggested that I should make the queue production “multithreaded”. To me that meant reordering the queue more freely. Maybe a better analogy is a compiler’s peephole optimizer.

I extended the lookahead in the queue from 3 items to 4, allowing reordering in a slightly wider window. I removed the requirement that the item moved forward have no dependencies; now it checks that the dependencies are met. Most importantly, I added a second case: If the next item can’t be produced because no producer is available for it (you asked for a tank, but every factory with a machine shop is already busy producing something else), or because tech dependencies are not met (you asked for a goliath but the armory is not finished yet), then a later item whose dependencies are met can be pulled forward and produced next. I kept the conservative requirement that there must be enough resources for both, to reduce the risk that the reordering will delay production overall. To relax the requirement, Steamhammer would have to predict future income, and it doesn’t do that yet. There is still some risk that reordering will delay production, if an unimportant item is moved ahead of an important item that is produced from the same source—you desperately needed scourge to survive the air harass? Too bad, the larva was used up making another drone that could be started a little earlier.

So far, my tests have not turned up any bugs, although reordering the queue is delicate and seems easy to mess up. I also haven’t noticed any cases of important items being delayed in favor of unimportant ones, though I’m sure it must happen occasionally. In practice, it looks like all win.

The zerg queue is still not often reordered. The strategy boss is fairly accurate in its production, and also it usually puts out short sequences that don’t have many items to reorder. Protoss, and especially terran, see frequent queue reordering, and it helps noticeably. BOSS likes to do silly things like order 4 SCVs in a row when there are 2 command centers, delaying everything else. Now Steamhammer is able to start 2 SCVs, then look into the future and say “OK, the next SCV has to wait, but these marines can go ahead.” Protoss and terran macro is still not strong, but it is visibly less bad than before. Also some production jams are mitigated, since Steamhammer can move items ahead of the jammed item.

Of course I intend to drop BOSS when I get that far. But I don’t think the queue reordering work is wasted. It helps occasionally in the opening, and it allows even the more careful zerg strategy boss to be a little sloppy about its sequences. I think there is a fair chance that I’ll keep the queue reordering even after I replace BOSS.