archive by month
Skip to content

what inferences do bots draw from scouting?

Yesterday I wondered what bots concluded from their scouting info. Today I try to find out.

I grabbed the AIIDE 2015 sources of 10 bots from Starcraft AI Competition - Data Archive. What inferences could I catch them drawing from scouting data? There’s a ton of code and I didn’t read most of it, so I may have missed a lot. Here’s what I failed to miss.

Bots that I did not catch making any inferences: AIUR, GarmBot, LetaBot, Overkill, Skynet, tscmoo (though it’s hard to read), Xelnaga. I think all these bots are adaptive (except possibly Xelnaga), but they seem to adapt based on directly observed data tied to decision code, not based on separately drawn inferences. You could take adaptation choices as implicit inferences, if you like.

One inference I intentionally skipped over was inference of where the enemy base is, given that all but one starting spot has been scouted. I think it’s a common ability.

Bottom line: Adaptivity is common, but explicit inferences seem scarce, and those that I found are not deep or clever. Certain bots have special-purpose “You are XIMP, I will beat you like this” code or settings, but I want some bot to say, “You built that much static defense? Are you nuts or what? Please excuse me while I take the map... hmm, siege down the front or drop?” Maybe Killerbot does that?

IceBot

IceBot recognizes enemy strategies in MentalState.cpp (I love the name). Here it recognizes terran marine rushes based on the game time, the scv count, the marine count, and the buildings it sees. The bb == 0 check (no barracks has been seen) presumably recognizes that no useful scouting happened, or that it’s facing proxy barracks.

        bc = enemyInfo->CountEunitNum(UnitTypes::Terran_Command_Center);
        bb = enemyInfo->CountEunitNum(UnitTypes::Terran_Barracks);
        ba = enemyInfo->CountEunitNum(UnitTypes::Terran_Academy);
        vf = enemyInfo->CountEunitNum(UnitTypes::Terran_Factory);
        vs = enemyInfo->CountEunitNum(UnitTypes::Terran_Starport);
        scv = enemyInfo->CountEunitNum(UnitTypes::Terran_SCV);
        marine = enemyInfo->CountEunitNum(UnitTypes::Terran_Marine);
        tank = enemyInfo->CountEunitNum(UnitTypes::Terran_Siege_Tank_Tank_Mode);
        vulture = enemyInfo->CountEunitNum(UnitTypes::Terran_Vulture);

        if (Broodwar->getFrameCount() <= 24*60*2)
        {
            if (bb > 0) STflag = TrushMarine;
        }
        if (Broodwar->getFrameCount() <= 24*60*2 + 24*30)
        {
            if (marine > 0) STflag = TrushMarine;
        }
        if (Broodwar->getFrameCount() >= 24*60*3)
        {
            if (bb == 0
                ||
                (bb >= 2 && (vf == 0 || bc == 1))
                ||
                (scv > 0 && scv <= 11))
            {
                STflag = TrushMarine;
            }
        }

IceBot has similar code to recognize zergling rushes. The protoss code is the most elaborate, recognizing 6 different protoss strategies. In MentalState.h is the enumeration of all strategies it knows of, though it doesn’t seem to recognize or use all of them.

	enum eStrategyType
	{
		NotSure = 1,
		PrushZealot,
		PrushDragoon,
		PtechDK,
		PtechReaver,
		BeCareful,
		P2Base,
		PtechCarrier,
		ZrushZergling,
		Ztech,
		Zexpansion,
		TrushMarine,
		Ttech,
		Texpansion,
	};

Tyr

Tyr makes an attempt to infer something about its opponent’s strategy, though it doesn’t try hard. The possible strategy classes, from ScoutGroup.java:

	public static int unknown = 0;
	public static int zealotPush = 1;
	public static int cannons = 2;
	public static int tech = 3;
	public static int defensive = 4;
	public static int besiege = 5;

With several rules like this to detect protoss strategies:

				if(gatewayCount >= 2)
					opponentStrategy = zealotPush;

Curiously, an expanding opponent is under the “tech” strategy class.

				if(nexusCount >= 2)
					opponentStrategy = tech;

This version of Tyr can classify a terran strategy as “defensive” or “unknown”. It doesn’t have any rules for zerg strategy. The “besiege” strategy class is referred to once in the rest of the code but is never recognized.

UAlbertaBot

UAlbertaBot seems to draw few inferences, but it knows to suspect cloaked units as soon as it sees a Citadel of Adun—it doesn’t wait for the Templar Archives. I didn’t notice any sign that it suspects mines when it sees vultures or lurkers when it sees hydra den + lair. From InformationManager.cpp:

bool InformationManager::enemyHasCloakedUnits()
{
    for (const auto & kv : getUnitData(_enemy).getUnits())
	{
		const UnitInfo & ui(kv.second);

        if (ui.type.isCloakable())
        {
            return true;
        }

        // assume they're going dts
        if (ui.type == BWAPI::UnitTypes::Protoss_Citadel_of_Adun)
        {
            return true;
        }

        if (ui.type == BWAPI::UnitTypes::Protoss_Observatory)
        {
            return true;
        }
    }

	return false;
}

strategy selection in Overkill

Zerg bot Overkill by Sijia Xu placed 3rd in the CIG2015 and 3rd in the AIIDE2015 tournaments. It’s not the very best, but it’s a top bot. Its games are entertaining to watch because it has more than one strategy.

Today I’m going to poke into Overkill’s C++ source code for strategy selection. There’s not much to it.

Overkill knows 3 strategies, 9-pool zergling, mutalisks, and hydras. For mutas it knows 2 different build orders, a faster one (10 hatch) and a slower one (12 hatch) with a stronger economy. It has an idea of when to switch between strategies within a game. It also learns from experience which strategies work against each opponent. If that sounds fancy, then the code is probably simpler than you imagine. It ain’t long and it ain’t tricky.

Overkill keeps a history file for each opponent so it can remember which strategies work. Code from the main program Overkill.cpp shows that if it doesn’t know the opponent yet, it goes 9-pool on the first game. (I stripped out a few irrelevant comments.)

	string enemyName = BWAPI::Broodwar->enemy()->getName();
	string filePath = "./bwapi-data/read/";
	filePath += enemyName;
	
	//for each enemy, create a file
	historyFile.open(filePath.c_str(), ios::in);
	
	//file do not exist, first match to the enemy
	if (!historyFile.is_open())
	{
		BWAPI::Broodwar->printf("first match to:   %s", enemyName.c_str());
		historyFile.close();

		//default opening strategy
		chooseOpeningStrategy = NinePoolling;
		StrategyManager::Instance().setOpeningStrategy(chooseOpeningStrategy);
	}
	else
	{

I’ll skip over reading the history file (it’s just reading this-strategy-got-that-game-result records and adding up) and go straight to the decision. Strategy selection is a multi-armed bandit problem, and Overkill solves it with a UCB algorithm that makes a tradeoff between exploration (“I’m not really sure how well this strategy works against this opponent, better try it again”) and exploitation (“this one usually wins, I’ll do it”). This is about the same method as other strategy-learning bots.

		double experimentCount = historyInfo.size();
		std::map<std::string, double> strategyUCB;
		for(auto opening : StrategyManager::Instance().getStrategyNameArray())
		{
			strategyUCB[opening] = 99999;
		}

		for (auto it : strategyResults)
		{
			double strategyExpectation = double(it.second.first) / (it.second.first + it.second.second);
			double uncertainty = 0.7 * std::sqrt(std::log(experimentCount) / (it.second.first + it.second.second));
			strategyUCB[it.first] = strategyExpectation + uncertainty;
		}
		
		std::string maxUCBStrategy;
		double maxUCB = 0;
		for (auto it : strategyUCB)
		{
			if (it.second > maxUCB)
			{
				maxUCBStrategy = it.first;
				maxUCB = it.second;
			}
			BWAPI::Broodwar->printf("%s , UCB: %.4f", it.first.c_str(), it.second);
		}

		BWAPI::Broodwar->printf("choose %s opening", maxUCBStrategy.c_str());
		int openingId = StrategyManager::Instance().getStrategyByName(maxUCBStrategy);
		if (openingId != -1)
		{
			chooseOpeningStrategy = openingStrategy(openingId);
		}
		StrategyManager::Instance().setOpeningStrategy(chooseOpeningStrategy);

		historyFile.close();
	}

If you haven’t seen something like this before it might be a little hard to understand what it’s doing, but you can’t say that the code is complicated. strategyExpectation is the strategy’s winning rate so far: You want to pick winners. uncertainty is high for strategies that have not yet been played and decreases as the strategy is tried more times: You want to experiment with strategies that you haven’t tried enough yet. Add them up and pick the one that’s best overall.

The initial strategy is one of 9-pool lings, 10-hatch mutas, or 12-hatch mutas. It never starts the game intending to go hydras. This is declared in StrategyManager.h:

enum openingStrategy { TwelveHatchMuta, NinePoolling, TenHatchMuta };

So how does Overkill decide to switch between strategies? That’s in the StrategyManager::update() method.

	switch (currentStrategy)
	{
	case HydraPush:
	{
		ProductionManager::Instance().setExtractorBuildSpeed(0);
		ProductionManager::Instance().setDroneProductionSpeed(250);

		if (hydraUpgradeTrigger && BWAPI::Broodwar->self()->allUnitCount(BWAPI::UnitTypes::Zerg_Hydralisk) >= 12)
		{
			hydraUpgradeTrigger = false;
			ProductionManager::Instance().triggerUpgrade(BWAPI::UpgradeTypes::Zerg_Missile_Attacks);
			ProductionManager::Instance().triggerUpgrade(BWAPI::UpgradeTypes::Zerg_Carapace);
			ProductionManager::Instance().triggerUpgrade(BWAPI::UpgradeTypes::Zerg_Missile_Attacks);
			ProductionManager::Instance().triggerUpgrade(BWAPI::UpgradeTypes::Zerg_Carapace);
		}
	}
		break;

Well, this isn’t switching strategy at all, it’s implementing the strategy by sending orders to the ProductionManager. Once Overkill goes hydra, it sticks with hydras. What if it goes muta? Here I stripped out the instructions to ProductionManager and left the decision logic.

	case MutaPush:
	{
		std::map<BWAPI::UnitType, std::set<BWAPI::Unit>>& enemyBattle = InformationManager::Instance().getEnemyAllBattleUnit();
		int enemyAntiAirSupply = 0;
		for (std::map<BWAPI::UnitType, std::set<BWAPI::Unit>>::iterator it = enemyBattle.begin(); it != enemyBattle.end(); it++)
		{
			if (it->first.airWeapon() != BWAPI::WeaponTypes::None)
			{
				enemyAntiAirSupply += it->first.supplyRequired() * it->second.size();
			}
		}

		// if lost too many mutalisk , and enemy still have many anti-air army, change to hydrisk
		if (enemyAntiAirSupply >= 2 * 1.5 * 12 && BWAPI::Broodwar->self()->allUnitCount(BWAPI::UnitTypes::Zerg_Mutalisk) * 3 < enemyAntiAirSupply)
		{
			goalChange(HydraPush);
		}

	}
		break;

This is Overkill’s most complex strategy logic, and it’s not very complex. If the enemy has too many units that can shoot down mutalisks, according to a short formula, then stop making mutalisks and switch to hydras.

What if Overkill is still on zerglings? This time I left in the orders to the ProductionManager.

	case ZerglingPush:
	{
		int hatchCompleteCount = 0;
		BOOST_FOREACH(BWAPI::Unit u, BWAPI::Broodwar->self()->getUnits())
		{
			if (u->getType() == BWAPI::UnitTypes::Zerg_Hatchery && u->isCompleted())
			{
				hatchCompleteCount++;
			}
			else if (u->getType() == BWAPI::UnitTypes::Zerg_Lair)
			{
				hatchCompleteCount++;
			}
			else
				continue;
		}
		// slow the drone production speed when only one hatch
		if (hatchCompleteCount == 1)
		{
			ProductionManager::Instance().setDroneProductionSpeed(750);
		}
		else
		{
			ProductionManager::Instance().setDroneProductionSpeed(250);
		}

		ProductionManager::Instance().setExtractorBuildSpeed(15);

		if (BWAPI::Broodwar->self()->gas() >= 100)
		{
			goalChange(MutaPush);
		}
	}
		break;

It counts the hatcheries and, if there are 2 or more, makes drones faster (I think that’s what it means). In other words, make a bunch of lings early on to see what you can do, then focus on drones. This is again implementing the strategy, not switching it. The strategy switch is: As soon as we’ve collected 100 gas (enough to start a lair), switch to mutas. In other words, the strategy path is hardcoded zerglings to mutas to hydras, and Overkill can start with either zerglings or mutas (and for mutas, with either a 10- or a 12-hatchery build). Dead simple.

You might draw the lesson, “If this is all the smarts a top-3 bot has, no wonder humans play so much better!” You won’t be wrong. But that’s where we are today, and we have to make progress one step at a time. The stronger Tscmoo bot knows more strategies than Overkill, but its strategy selection and strategy switching are hardly any smarter.

A more fun lesson to draw is “Hey, this is easy! I can make a top bot without worrying much about strategy selection, even though it seems like such a hard problem.” That’s true too.

There are plenty of other lessons to draw. When Overkill doesn’t expand early enough to its natural, it often gets stuck on one base for the whole game and (since zerg have a lust to expand) gets smooshed. Also, Overkill’s zergling and mutalisk strategies work okay, but the hydralisk strategy can backfire, especially against terran. A terran ground army can roll up an equal-size hydra army like a rug. The first thing you should worry about is not picking a good strategy, but making the strategy you pick good. Any decent strategy can beat other bots if it’s carried out crisply.