Starcraft AI blog

I want Steamhammer to infer the existence of enemy buildings that it has not seen. Right now, the plan recognizer explicitly encodes its conditions: If I see an early factory, or a unit that came from a factory, or an armory, or a starport, then I can guess that the enemy is playing a factory opening. The zerg strategy boss uses related reasoning. Every bit of code that wants to know if the enemy has a factory has to also look for things that depend on the factory. It’s more general and powerful to decouple the inferences. The information manager should notice when it sees things that can’t be explained by known enemy structures, and infer what was necessary to produce them. If it sees a battlecruiser, it should infer the science facility with physics lab, the starport with control tower, and all the way down. Then the rest of Steamhammer can rely on the inferences, and not have to do any extra work on its own. In principle, it could draw conclusions like “Wait, I’ve seen the whole enemy base and there is no physics lab there. I should look harder at the rest of the map.”

Research counts too. If I see a wraith cloak, I know there is a control tower, even though a control tower is not necessary to make wraiths. It’s necessary to research cloaking. If I see a unit with an attack upgrade, I know what buildings were needed to research the upgrade.

It occurs to me that there are tricky cases. Suppose I break into the enemy base and find a factory—and destroy it. Later, I reach farther into the base and find an armory. I can’t infer that there is a second or new factory; the armory could have been started when the first factory still existed. To interpret the armory correctly, I have to remember that the enemy used to have a factory, and without more information I can’t be sure whether it has a factory now. This is building inference level 1; I have to know history to draw true conclusions.

But sometimes I can infer that there is another factory. If the armory is in a place that I know was empty when the first factory was destroyed, then I know that it is a new armory. There must have been another factory, or another factory was built after the first one was killed; in any case, I can infer a factory that I did not see. To do building inference perfectly, you have to not only remember the history of enemy buildings, you have to remember the history of places. This is building inference level 2; if I understand it, I can draw more conclusions.

Building inference level 3 (I’ll call it) is drawing conclusions about the number of enemy production buildings from the number of units that they are seen to have produced. “Hmm, my scout saw your barracks under construction, and by now it could theoretically have produced n marines. You have more than n marines, so you definitely have at least 2 barracks.” Resource counting can figure into this: If your scout counted the enemy minerals, or if you have a table “it’s possible to mine x amount by time t,” or if you simply know the maximum number of marines that can be produced by one barracks without being sure when it was started, you can draw inferences. In the most general case, you know all the good build orders and their production potential, and can rule out the ones which are not consistent with what you see. Later in the game it should at least be possible to make a rough estimate of the enemy’s income, correlate it to the types and/or number of units you see, and get a fair idea of how many production buildings are likely. At this point you’re making estimates instead of drawing definite inferences.

How many levels of building inference does PerfectBot have? “Oh, this army movement suggests that you are trying to draw my forces forward. Maybe you are trying to set up a drop in the rear? I’d say that means a 20% chance of a robo support bay....”