Starcraft AI blog

You see an enemy unit. Sometimes it tells you what else the enemy has; for example, if you see a marine, you know there is a barracks even if you haven’t seen it. Drawing the inferences makes it easier to figure out the opponent’s plan. I thought it would be trivial to calculate the inferences, since BWAPI provides UnitType::requiredUnits() that tells what you need to create a unit of a given type. But it took me some head scratching; inference does not equal creation in reverse. Here’s what I ended up with. I edited the code slightly for readability; the real version is a little more obscure.

The code should be close to correct, and it works in tests so far, but I won’t be surprised if I’ve missed cases. There are a lot of cases.

// Trace back the tech tree to see what tech buildings the enemy required in order to have
// produced a unit of type t. Record any requirements that we haven't yet seen.
// Don't record required units. An SCV is required for a barracks, but don't count the SCV.
// A hydralisk is required for a lurker, but it is used up in the making.
void PlayerSnapshot::inferUnseenRequirements(const PlayerSnapshot & ever, BWAPI::UnitType t)
{
    if (t == BWAPI::UnitTypes::Zerg_Larva)
    {
        // Required because BWAPI believes that a larva costs 1 gas.
        return;
    }
    std::map<BWAPI::UnitType, int> requirements = t.requiredUnits();
    if (t == BWAPI::UnitTypes::Terran_Vulture_Spider_Mine)
    {
        requirements[BWAPI::UnitTypes::Terran_Factory] = 1;
        requirements[BWAPI::UnitTypes::Terran_Machine_Shop] = 1;
    }
    if (t.gasPrice() > 0)
    {
        requirements[the.enemyRace.getRefinery()] = 1;
    }
    for (std::pair<BWAPI::UnitType, int> requirement : requirements)
    {
        BWAPI::UnitType requiredType = requirement.first;
        if (!ever.contains(requiredType))
        {
            if (requiredType.isBuilding() && !UnitUtil::BuildingIsMorphedFrom(requiredType, t))
            {
                unitExists[requiredType] = true;
            }
            inferUnseenRequirements(ever, requiredType);
        }
    }
}

The code recursively traces back all the requirements to the root of the tech tree, if necessary. If you see an arbiter, you may learn about the stargate, the arbiter tribunal, the templar archives, the citadel, the core, and the gateway. In practice, an early scout which is turned back by a dragoon and sees nothing else concludes that protoss has a gateway, assimilator, and cyber core. It should infer a reaver from a scarab and a carrier from an interceptor. An opponent plan recognition rule does not have to say “if they have a cyber core, or some unit that requires a cyber core...” it can say “if they have a seen or inferred cyber core....”

The parameter ever remembers what enemy unit types we have ever directly seen, at any time in the game, even if all the examples have been destroyed since. That is because, if you see a vulture, all you know is that at some point in the game a factory existed to make the vulture. You have to remember. ever is filled in at the beginning of the game (or at the latest when we see the first enemy, if they went random) with the units that exist at the beginning of the game: The resource depot and worker types, plus for zerg, the larva and overlord types. That prevents loops: According to UnitType::requiredUnits(), it takes a nexus to create a probe and it takes a probe to create a nexus. True, but you have to ground the recursion!

Notice the bit !UnitUtil::BuildingIsMorphedFrom(requiredType, t): A lair requires a hatchery, but that doesn’t mean that when you see a lair you can infer a hatchery somewhere on the map. You can only infer the spawning pool. I think this serves essentially the same purpose as UnitType::isSuccessorOf() in BWAPI 4.2.0, but I haven’t switched yet. Non-building units are tricky to infer without isSuccessorOf(), so I didn’t. I don’t try to infer the vulture from the spider mine. A sunken colony requires a creep colony, but the creep colony disappears. An archon requires 2 high templar, ditto.

I filled in a couple of special cases. Spider mines: As far as UnitType::requiredUnits() is concerned, even though spider mines are units, they do not require units to create but only tech. Gas: If we see anything that requires gas, infer a refinery building. It may help early in the game. I haven’t tried to draw inferences from tech. You should be able to infer a control tower from seeing a cloaked wraith, an academy from seeing a scan occur, a lair from seeing a lurker, and so on. But one step at a time!