Starcraft AI blog

I wrote a couple posts ago about dissatisfaction with Steamhammer’s primitive way of inferring the enemy’s opening plan from scouting information. What is the right way to draw inferences from scouting? One kind is the hard inference or deduction from what you have seen, like “I saw the lair start, so the earliest mutalisks can be out is lair completion time + spire morphing time + mutalisk morphing time.” You can also draw soft inferences or likely guesses about what the opponent is planning, based on your knowledge of good play. “The opponent is blocking its ramp with a probe, I bet something cheesy is coming.” Maybe the opponent is incompetent and left a probe there by mistake, or maybe it is trying to fool you into scouting for a proxy gate, but cheese is likely.

Well, drawing soft inferences based on good play is beyond the state of the art for bots, because bots have little knowledge of good play. But there is a theoretically sound way to make every possible deduction from scouting information. It could even be useful, if you have a theoretical computer with infinite speed and memory.

It’s simple: Brute force it. There are only a finite number of build orders, and you can enumerate them. Cross out the build orders which are inconsistent with your scouting information, the ones where the enemy has fewer workers than you saw or doesn’t have an academy yet or whatever. Counting up the minerals mined places a particularly strong constraint. You’re left with a much smaller set of build orders that the enemy might be following. If you have a question like “what’s the earliest mutalisks could be out?” or “how many dragoons do I have to be ready for at time t?” then you look through the consistent build orders and find the one with the earliest mutalisks or the most dragoons.

The idea goes back to precomputing a catalog of build orders, which I wrote about in April 2016.

Can this theory be made practical? I think it can, by cutting it down and dropping the theoretical promise of finding guaranteed correct answers for all possible questions. Instead of all builds, keep a catalog of a small number good openings for each race, maybe between 10 and 50. Instead of exact build orders, you could store ranges of variation, like “second gateway between frames x and y,” or store preferred values and check goodness of fit—or some other simple abstraction. When you have enough scouting information, it will rule out most openings from your catalog, and goodness of fit may narrow it down further. Also, you know what questions you want to ask, so you can store the answers with each build, so that when you know what builds match what you see, there’s not much computing to do. Well, it’s a vague idea, but I hope you can make it out.

LetaBot uses, or formerly used, a related idea with a catalog of build orders. See LetaBot’s build order inference (also April 2016). A weakness of LetaBot’s approach at the time is that, when it saw something that the build order expected, it increased the score of that build order—but when it saw something outside the build order, it did not decrease the score. It might see 3 hatcheries and conclude that the opponent was following a one-hatchery build, because the extra hatcheries did not cause a mismatch. If LetaBot still uses this method, then I imagine it has been improved since then.

Next: Early experience with opening plan recognition.