Starcraft AI blog

“Cheese” is a put-down, and the proper definition of “cheese” has a flavor of “stupid trick that you shouldn’t have beaten me with.” But who cares? I can pretend to be objective, and define a cheese strategy as: A surprise strategy which is all-in and fails if the opponent scouts or expects it. If the opponent pays a cost to stay safe against cheese, then game theory says that you may want to take the risk to cheese a certain percentage of the time to force your opponent to pay. The cost can be the need to stick to rush-safe strategies, or only the cost of scouting for proxies. It depends on your risk of losing with risky cheese versus the opponent’s cost to stay safe, of course.

Another definition of “cheese” is: An all-in opening that sacrifices economy to an extreme degree. It doesn’t say how extreme, but it’s closer to how people use the word in practice.

Against a human you can’t play cheese often, because it fails if expected. By definition! But bots are not good at expecting things. Most bots are vulnerable to cheesy openings and only a few have strategy learning that may be able to learn to defend, so—why don’t other bots cheese more?

I’ll talk not only about cheese by my definition, but also other risks or tricks that seem cheeselike. I was only pretending to be objective.

cheese that current bots try

• 4-pool, 5-pool, 6-pool
• cannon rush, cannon contain
• dark templar rush (not cheesy, but risky if it’s very fast)
• hard zealot rush (not cheesy, but all-in when protoss commits to it)
• SCV rush (in some LetaBot versions, and formerly by Stone)
• BBS (two barracks before depot, played by Tyr)
• marine rush (10 barracks into infinite marines, UAlbertaBot)

other cheese

• offensive sunken in ZvZ (ASPbot did this in 2011)
• proxy hatchery
• proxy 5 rax (LetaBot used to do this with bunkers; variations are possible)
• proxy factory (make super-early vultures to kill workers)
• barracks float, factory float (into the enemy base)
• proxy gateways (which can mix with cannons)

The offensive sunken in ZvZ can work when combined with another attack. By itself it just fails if the opponent reacts. The natural other attack is, of course, a 4 pool or 5 pool after you scouted with a drone.

You can make anything at a proxy hatchery. In the early game you make zerglings or sunkens. If you get burrow, a drone may be able to hide in the enemy base for a long time before proxying. If you somehow remain unscouted in the middle game, you might build lurkers. In the late game, drop a drone in for creep to support a nydus. All these are risky cheese plays; if scouted, they lose resources for nothing.

I think it’s strange that we see zergling rushes and marine rushes with BBS, but no zealot rushes with early forward gateways. On a 2-player map, building gates near the enemy base at 5 and 6 supply kills most bots effortlessly. Many other forward and center gate variations are possible, at least up to 9-9 center gates.

In another point, if you’re making an all-in rush, there’s no disadvantage to bringing some workers along for the fight, no matter your race. Terran of course can make bunkers. Protoss can make a proxy shield battery (typically in the enemy natural) to support the rush—the pylon is “free” since you need it anyway.

It’s also strange that we see no in-base proxies other than cannon rushes. Many bots will pop like a balloon when you hide a gateway or two in their base. Against a terran bot that doesn’t scout its base, you can hide a probe and make a late in-base proxy gate for dark templar. Or try this BBS variation as terran: Scout early, and build your first barracks in a distant part of the enemy base, near a cliff. Build the second barracks beneath the cliff and float it up beside the first.

Some slower tech rushes are so risky that you could call them cheese. 1-base lurker is one example. AIUR’s fast 4-zealot drop is another.

cheeselike tactics

You can block stuff with a worker/pylon/etc. It’s not cheese, but it’s tricky and cheeselike.

• gas steal
• mineral steal
• manner pylon
• pylon block of terran add-on (especially the first machine shop)
• block natural hatchery/nexus (common against 12-hatch)
• block opponent from walling
• block opponent’s exit (on maps with a small exit like Heartbreak Ridge)
• pylon prison, a crazy blocking trick

Bots still know how to steal gas, but I think they've given up on doing it because they stopped seeing advantage. I think that once bots can read and react to the opponent's strategy well enough, they should go back to stealing gas, but only at times when it will channel the opponent's strategy in a direction that the bot can exploit. Opponent modeling helps. If you know that your opponent’s tech causes you trouble, then steal gas to delay their tech.

You can order your scouting worker to mine an enemy mineral patch, and then the enemy can't mine it at the same time. You can steal 8 minerals or stop mining early and start again. It's mild harassment that slows down enemy mining slightly. If you also steal gas, you can steal 8 minerals, steal 8 gas, steal 8 minerals... which is not useful but is funny.

Manner pylon is advantageous if done at the right time and place. It can cause the opponent to lose more minerals in mining time than the pylon cost. The reason we only occasionally see manner pylons in pro games is that pros prevent it when they care, briefly idling a worker to stop it if necessary. Manner pylon can be worth it in the early game, and it can be worth it later in the game at expansions. I think it's safe to guess that very few bots will react correctly to manner pylon; they will not know how to prevent it, and they will lose more mining time than necessary when it happens. Bots with fixed build orders will mess up their timings. It can be a little tricky to pull off a manner pylon, though, because you can only build it when the spot is free of enemy workers. Good players can predict when the spot will be free and slide through the mineral line with the right timing to build the pylon in passing.

Cheese is healthy for bots because opponent bots need specific knowledge to respond well, and there are many kinds of cheese so much knowledge is needed. But cheese can also be difficult to play well. Current bot cheese is plain cheddar next to pro artisanal cheese. Tomorrow: Cannon like Nal_rA.

LetaBot suggested I should write about the decline of the rushbots. He pointed out that ZZZKBot by Chris Coxe (the best of them) is no longer a top bot on SSCAIT, but has fallen to the middle of the pack, and that UAlbertaBot has lost ground too. I’ll add that cannon rushes were never reliable, but remain moderately successful.

It would be interesting to examine the decline in historical data, but I don’t have the historical data. I once thought of setting up a job to scrape the SSCAIT page once a day, to save the game results for analysis, but I decided there were better uses for my time.

The rushbots are failing because rushbots have not changed and their opposition has improved in defense. The defense improvements include safer openings, better worker micro, and more cautious play with early military units (such as Tscmoo stationing early units defensively in its mineral line). Also the SCV rushbot Stone has been replaced with the non-rushing Iron—if Stone were still playing on SSCAIT, maybe its results would still be good. Or maybe not, we don’t know; its disappearance reduced pressure to improve rush defense. The fact that SSCAIT admins are tired of zerg rushbots (as we all are) and have disabled many of them also reduces pressure to improve rush defense.

This is going on a bit of a tangent, but I’ll tell a story. Once upon a time I was playing (on Lost Temple, it was that long ago) as zerg versus a protoss who was clearly better than me (which wasn’t saying much). I saw the protoss army move out toward my mineral-only. I had prepared a backstab: I ran a dozen speedlings past the protoss natural into the undefended main mineral line. Then I had to turn my full attention to defense, narrowly holding the attack, and I didn’t see what happened with the backstab. After I lost the game I watched the replay. I was astonished to find that the protoss had not lost a single probe to my backstab, but had microed probes to glitch out my lings and kill them safely. I hadn’t known it was possible. It was a memorable lesson: Micro can make the difference between losing everything and losing nothing.

Worker micro is a key skill, and it’s basic to good play. Even today’s best bots have visible flaws in their worker micro. As long as that remains true, the zerg rushbots have a chance to win even against some safe strategies, and they have a role to play as teachers. But if they want to keep that role they’ll have to improve their zergling micro. They need to know how to avoid defenders while attacking vulnerable workers, when to step back and change targets, and when to gather up a force before striking. At least they need to go around the bunker instead of running straight into it and dying.

For the rest of the post, I’ll concentrate on zergling rushes.

4 pool and 5 pool are objectively sound, and can be played at pro level. Like any playable opening, they counter some enemy strategies and are countered by others. If a pro plays a safe opening, then a 4 pool or 5 pool will lose. But pros are always looking for an edge, and they will correctly play unsafe greedy openings to get one—if you never play an unsafe opening, you are leaving money on the table. And if your opponent plays unsafe openings often enough, then it is correct to make them pay the cost for the risk they are taking. Also some openings are in-between, safe-ish but vulnerable to better micro or better luck.

4 pool comes in two variations. The build order for the more aggressive variant is: 4 pool, 6 lings. The other variant is: 4 pool, 1 drone, 6 lings; with the extra drone you have more economy but you can get 2 fewer lings before the first overlord. There is not much difference between the variants; they are both do or die. 5 pool is a little slower, but your stronger economy means that you need to do less damage to the enemy to break even. You can accumulate minerals while attacking, which gives options to transition into another strategy. 5 pool can be played against any race, but experts don’t 4 pool against protoss because protoss will normally survive and you need that touch of extra economy to make it to the middle game.

This old Team Liquid post lists pro games and statistics for 4 and 5 pool games between 2004 and 2009. There are not many; play them often and you’ll lose often; play them occasionally to punish greed and you’ll do well. 5 pool was played as recently as 17 July in Effort vs. Shuttle on the first day of the ASL (Afreeca Starcraft League). (It’s the first game of the cast, starting at 9:37 into the video. The English commentators didn’t count the drones and never realized it was a 5 pool.) Watch the game if you want to see the economic risk of a zergling rush. Effort got lucky and scouted the right way with his overlord, but Shuttle also got lucky and saw the lings in time to make a shield battery and pull the minimum number of probes to hold. Effort struggled for the rest of the game to catch up, but despite strong aggressive play in the middle game never drew even.

6 pool, 7 pool and 8 pool are considered inferior. They are seen as giving up economy without enough payback: The zergling attack at the later timing is too weak to be threatening.

9 pool is no longer a rush but a mainstream build. With 9 pool and zergling speed, the lings have greater potential to run by defenses, they can catch and kill fleeing workers, they can switch between targets with agility, and they’re generally more dangerous. And even this non-rush build is economically risky except in ZvZ. Overpool (overlord at 9 drones, then spawning pool at 9 while the overlord is in the egg) is the fastest build that is common outside ZvZ.

If you always play the same strategy, then you set yourself up for a counter. Bots with strategy learning will learn to counter you. If you always play the same cheese strategy like 4 pool or 5 pool, with standard hard counters, then you set yourself up to lose every game. Zergling rushes are sound, but not as your only opening.

If your bot has strategy learning, then I think it deserves at least one cheese opening to punish weak or greedy opponents. Zergling rushes are only one possibility—they are vanilla cheese, if the metaphor doesn’t make you gag. Tomorrow: More cheesy goodness. Cheese is great, cheese is good, and we thank it as our food.

Funny picture: Until just before this screenshot of a game between Igor Lacik's bot and Overkill, both sides were mining from this base. As you can see, terran ended up winning it... with a displaced command center.

Zia was reuploaded today. Its new description says “It has memory, and is trying to play like people do.” It sounds like it can now choose among its strategies as I hoped. It will take a lot of games to see how well it works....

What do y’all think I should write about?

I don’t have any shortage of material. I have 3 posts in my reserve, already written and pretty much ready to go, plus a to-do list of ideas, including a couple that I’m eager to get to.

But I think it’s time to pause and see what everybody else wants. I’ve been running down my own road, and maybe you think there are other cool avenues.

Is there a burning topic I’ve ignored? An idea I’ve mentioned that I should go into more detail about? Is there something in AI that you don’t know how to get started with? I may not know how either, but I can find out. Maybe a deep dig into this, or a wide survey over that? What do you say?

Post a comment or drop me e-mail. I’ll give feedback a few days to accumulate before I go once more into the breech.

Here’s what I learned in analyzing Skynet.

Skynet’s skills come across to me as first drafts of what you’d really want to implement. In looking at each one, it’s easy to see points that could be improved and shortcuts that were taken to get it working more easily. On the other hand, Skynet has a lot of different skills; the shortcuts paid off in time saved.

In other words, Andrew Smith put priority on breadth of skills rather than depth of skills. And it’s hard to argue with his choice, because Skynet is a great success, still a strong and interesting bot though its last update was in 2013.

I think it’s a key point. In a lot of posts I point out, “a better way to do X would be....” But you should only care if X is a weak point in your bot. It is better to play adequately in all respects than to play well in some and poorly in others. You want to minimize your worst weaknesses.

If you’re perfect at choosing the right unit mix to counter your opponent but your micro sucks, you lose. If you’re perfect at micro but you choose a stupid unit mix, you lose. Better to be fair-to-middling at both. Breadth of skills first.

You may be able to lift code from Skynet for your own bot, if you don’t mind being infected by its GPL license. You’ll probably have to do a bit of adapting to fit it into your own framework, but the code has clear interfaces and the important working parts seem mostly independent of the rest of the program. Once you’ve seen an idea it shouldn’t be too hard to reimplement it, either.

Skynet tries to avoid some area-of-effect spells and splash damage from some attacks. This is the fanciest skill that I’m writing up.

You can only avoid stuff that you can see coming. Skynet tracks threats in class AOEThreatTracker (where AOE stands for Area Of Effect), which creates and stores AOEThreat objects. Here is the key code from AOEThreatTracker::update(), which is called once per frame from the main onFrame() in Skynet.cpp:

	for each(Unit unit in UnitTracker::Instance().selectAllEnemy())
	{
		const BWAPI::UnitType &type = unit->getType();
		if((type == BWAPI::UnitTypes::Protoss_Scarab || type == BWAPI::UnitTypes::Terran_Vulture_Spider_Mine) && mUnitThreats.count(unit) == 0)
		{
			AOEThreat newThreat = AOEThreat(new AOEThreatClass(unit));
			mAllThreats.insert(newThreat);
			mUnitThreats[unit] = newThreat;
		}
	}

	for each(BWAPI::Bullet* bullet in BWAPI::Broodwar->getBullets())
	{
		const BWAPI::BulletType &type = bullet->getType();
		if((type == BWAPI::BulletTypes::Psionic_Storm || type == BWAPI::BulletTypes::EMP_Missile) && mBulletThreats.count(bullet) == 0)
		{
			AOEThreat newThreat = AOEThreat(new AOEThreatClass(bullet));
			mAllThreats.insert(newThreat);
			mBulletThreats[bullet] = newThreat;
		}
	}

Skynet recognizes enemy reaver scarabs and spider mines as splash damage threats. (A bot that might lay mines of its own should also recognize its own spider mines as threats. Skynet does not use mind control.) It also recognizes psionic storm and EMP as area effect spells to try to dodge.

What does it do with the information it’s tracking? Here’s the public interface from AOEThreatTracker.h:

	void update();

	AOEThreat getClosestGroundThreat(const Position &pos) const;
	AOEThreat getClosestAirThreat(const Position &pos) const;
	AOEThreat getClosestEnergyThreat(const Position &pos) const;
	AOEThreat getClosestThreat(Unit unit) const;

	bool isTargetOfThreat(Unit unit) const;

Psionic storm is both an air threat and a ground threat. Scarabs and mines are ground threats. EMP is the only energy threat. But of the 5 informational methods, only getClosestThreat() and isTargetOfThreat() are used in the rest of the code; the other 3 get methods serve no purpose. getClosestThreat() takes a unit and considers whether it is an air or ground unit to find the closest threat. It counts EMP as a threat to spellcasters only, even though all protoss units will lose their shields to it. It’s a little inconsistent; corsairs count as spellcasters, but Skynet never researches disruption web.

The results of all this tracking work are used in only one place, in BasicUnitAction::update(), which is a micro action like the others we’ve seen in the last days. The BasicUnitAction of course has very low priority among micro actions, so if the unit under consideration is already doing something else (like dragging the mine that is the threat), then none of this happens.

	const bool isTargetOfThreat = AOEThreatTracker::Instance().isTargetOfThreat(mUnit);
	if(!isTargetOfThreat)
	{
		const AOEThreat &closestThreat = AOEThreatTracker::Instance().getClosestThreat(mUnit);
		if(closestThreat)
		{
			const int distanceToThreat = mUnit->getDistance(closestThreat->getPosition());
			if(distanceToThreat < closestThreat->getRadius()+32)
			{
				stayAtRange(mUnit, closestThreat->getPosition(), closestThreat->getRadius() + 64, distanceToThreat);
				return true;
			}
		}
	}

First it remembers whether the current unit mUnit is the target of the threat, for later use. The explicit target does not dodge the threat (sometimes it can’t). If the current unit is not the target, but it is within range of at least one threat, then it finds the closest threat and tries to get out of its range. stayAtRange() calculates a direction and moves that way. There’s no attempt to avoid multiple threats, which are likely for spider mines; Skynet is happy to flee one and run into another. Also, I notice that AOEThreatTracker keeps careful track of each threat radius, but this code ignores it and flees to a fixed radius. I assume that’s good enough? Anyway, this limitation may explain why Skynet does not try to dodge lurker spines, which affect a long narrow area.

If the current unit is the target, the unit stays put so that the other units around it know what to do to avoid the threat. currentTargetUnit is whatever the current unit is already shooting at. This is not best if under attack by a reaver scarab, but it does help nearby units know which way to flee.

	// If the target of a threat, dont do anything to cause it to move
	if(isTargetOfThreat)
	{
		if(currentTargetUnit)
			mUnit->attack(currentTargetUnit);
		else
			mUnit->stop();
		return true;
	}

Skynet has other interesting skills. See BlockedPathManager and MineBlockingMineralTask, for example. But that’s enough for now.

Tomorrow: Wrapup and lessons learned.

Arbiters are tough to use well. You want to maneuver your arbiter to cloak as many of your units as possible while staying safe. You want to stasis or recall at critical times and places. Occasionally you want to do damage with the pea-shooter. The goals pull in different directions, and you have to decide what’s best.

Here’s how Skynet decides. Skynet has two arbiter skills: It knows how to cloak units efficiently and how to stasis. Skynet does not use recall, and it (understandably) doesn’t put any emphasis on targeting enemies with the puny gun.

Arbiter control is in ArbiterAction::update(), which is like the other micro actions, set up by Behaviour::createDefaultActions(). First it considers stasis:

	if(mUnit->getEnergy() >= 100 && BWAPI::Broodwar->self()->hasResearched(BWAPI::TechTypes::Stasis_Field))
	{
		const int stasisSize = 48;

		bool stasisUrgently = false;
		if(UnitInformation::Instance().getUnitsTargetting(mUnit).size() >= 6 || (UnitInformation::Instance().getUnitsTargetting(mUnit).size() >= 1 && mUnit->totalHitPointFraction() < 0.3))
			stasisUrgently = true;

First, if stasis is possible and the arbiter is in danger of being lost, Skynet sets stasisUrgently to true.

		UnitGroup stasisChoices;
		for each(Unit enemy in UnitTracker::Instance().selectAllEnemy())
		{
			if(!UnitHelper::isArmyUnit(enemy->getType()))
				continue;

			if(enemy->isUnderStorm() || enemy->isStasised())
				continue;

			const int distance = mUnit->getDistance(enemy);
			if(distance > 250 || distance < stasisSize)
				continue;

			stasisChoices.insert(enemy);
		}

Then it comes up with a list of candidate enemies to stasis. Enemies under psionic storm are not candidates—let them suffer!

		if(stasisChoices.size() > 4 || (!stasisChoices.empty() && stasisUrgently))
		{
			UnitGroup stasisTargets = stasisChoices.getBestFittingToCircle(stasisSize);

			if(stasisTargets.size() > 4 || (!stasisTargets.empty() && stasisUrgently))
			{
				const Position &stasisLocation = stasisTargets.getCenter();
				if(mUnit->getDistance(stasisLocation) <= BWAPI::TechTypes::Stasis_Field.getWeapon().maxRange())
				{
					mUnit->useTech(BWAPI::TechTypes::Stasis_Field, stasisLocation);
					LatencyTracker::Instance().placingStasis(mUnit, stasisLocation);
					return true;
				}
				else
				{
					mUnit->move(stasisLocation);
					return true;
				}
			}
		}
	}

And finally Skynet decides whether and where to stasis. If it can stasis at least 5 enemy units, or at least 1 unit and stasisUrgently is set, then it does. UnitGroup::getBestFittingToCircle() finds a circle of the given size which covers as many units in the UnitGroup as possible, and returns the smaller UnitGroup which it covers.

It’s a simple heuristic. An arbiter will happily stasis 5 vultures uselessly when it reaches stasis energy after the army it was covering is destroyed by tanks and vultures. The “right” way to do this would be with a pay-me-now-or-pay-me-later tradeoff that compares the situation now with possible future situations, which would of course be far more complicated. And, since that’s not hard enough yet, it should also consider the effect on the battle: Stasis on a ramp to block reinforcements? Stasis the tanks that are doing the most damage, or the vessel that is detecting the cloaked army? And so on.

Next is maneuvering the arbiter to cloak units:

	UnitGroup unitsToCloak;
	for each(Unit unit in squadUnitGroup)
	{
		if(!UnitHelper::isArmyUnit(unit->getType()))
			continue;

		if(unit->getType() == BWAPI::UnitTypes::Protoss_Arbiter || unit->getType().isBuilding())
			continue;

		if(mUnit->getDistance(unit) > 250)
			continue;

		unitsToCloak.insert(unit);
	}

	if(!unitsToCloak.empty())
	{
		unitsToCloak = unitsToCloak.getBestFittingToCircle(136);
		if(!unitsToCloak.empty())
		{
			Position cloakLocation = unitsToCloak.getCenter();
			if(mUnit->getDistance(cloakLocation) > 110)
			{
				mUnit->move(cloakLocation);
				return true;
			}
		}
	}

Candidate units to cloak are basically military units in the squadUnitGroup which can be cloaked and are near enough. Skynet never tries to protect probes or observers with the cloaking field (UnitHelper::isArmyUnit() returns false for both), but it will try to cloak dark templar that are already cloaked (a simple omission from the above code and trivial to fix) and units that are already covered by another arbiter (only a little harder to fix). It does the getBestFittingToCircle() thing to find the largest circle of units that it can cloak, and moves toward the circle’s center if it’s not close enough. If it’s already close enough then the micro action does not occur, which I assume frees the arbiter to fire its gun when possible, flee danger within limits, and so on.

Tomorrow: Avoiding splash damage, finishing the series.

Spider mines do a ton of splash damage when they explode, and they don’t discriminate. Everything in splash range suffers, enemy or friendly. So it’s popular to intentionally trigger enemy mines while running up to enemy units, dragging the mine into the enemy to cause damage. Mines can sometimes follow a unit for quite a distance before going off. Protoss usually drags mines with zealots, though dark templar are also good. Zerg usually uses speedy zerglings in small groups, because they’re cheap and fast. Terran can sometimes trigger enemy mines with drops, but doesn’t have an appropriate unit to drag mines otherwise.

Skynet knows how to drag mines with a zealot. It uses the same system of micro actions that I touched on yesterday. In Behaviour::createDefaultActions() it records a possible mine drag micro action for every zealot:

	if(unitType == BWAPI::UnitTypes::Protoss_Zealot)
		mMicroActions.push_back(MicroAction(new MineDragAction(mUnit)));

By the way, the micro actions are evaluated in Behaviour::update(), which checks them in order. Each unit can only execute one micro action at a time, and the first action to return true is what happens. Skynet’s only prioritization is to record the most important micro actions first in createDefaultActions(). Mine dragging is recorded near the end, as a low-priority action. Yesterday’s archon-zealot undetected unit attack is higher priority.

Here is the entirety of MineDragAction::update():

bool MineDragAction::update(const Goal &squadGoal, const UnitGroup &squadUnitGroup)
{
	for each(Unit unit in UnitInformation::Instance().getUnitsTargetting(mUnit))
	{
		if(unit->getType() == BWAPI::UnitTypes::Terran_Vulture_Spider_Mine)
		{
			int distance = std::numeric_limits<int>::max();
			Unit closestUnit;

			for each(Unit enemyUnit in UnitTracker::Instance().selectAllEnemy())
			{
				if(enemyUnit->getType().isFlyer() || enemyUnit->isLifted() || enemyUnit->getType().isBuilding() || enemyUnit->getType() == BWAPI::UnitTypes::Terran_Vulture_Spider_Mine)
					continue;

				int thisDistance = mUnit->getDistance(enemyUnit);
				if(thisDistance < distance)
				{
					distance = distance;
					closestUnit = enemyUnit;
				}
			}
			
			if(closestUnit && distance < 32*5)
			{
				mUnit->attack(closestUnit);
				return true;
			}
		}
	}

	return false;
}

This seems to only notice spider mines which have already popped up and are targeting the current zealot. If one is found, then the code checks for suitable enemy units (not stuff in the air, for example) that are close enough. If any is found, then the zealot targets the nearest for attack, end of story.

That’s basic mine dragging. A stronger version would also consider detected or remembered mines: If a mine in the ground is detected or remembered to be near valuable enemies, then check whether it can be activated and dragged into the enemies. You can remember a mine location if you detected it in the past, or if you saw it being laid or moving and reburrowing. That’s more complicated, but human players do it as a matter of course. Humans will even try to drag mines that they expect or hope are there, without being sure.

Tomorrow: Arbiter control.

Archons do splash damage that affects all enemy units, included undetected units. That means that you can use an archon to, for example, kill a burrowed lurker that you can’t detect, by attacking one of your own units. The usual way is to park a sacrificial zealot on top of the lurker and attack the zealot with the archon; the archon will do full damage to the zealot and splash damage to the lurker.

Archon splash affects both ground and air. An archon attacking a zealot will damage a cloaked wraith that is in splash range. An archon attacking a floating ebay should clear spider mines in a small area (I haven’t tested to make sure).

Here’s how Skynet does it. Behaviour::createDefaultActions() recognizes the unit types and records possible micro actions to test and execute later:

	if(unitType == BWAPI::UnitTypes::Protoss_Zealot || unitType == BWAPI::UnitTypes::Protoss_Archon)
	{
		firstTargets.insert(BWAPI::UnitTypes::Terran_Siege_Tank_Siege_Mode);
		mMicroActions.push_back(MicroAction(new ArconZealotKillUnDetected(mUnit)));
	}

When the micro action comes up for testing, it runs ArconZealotKillUnDetected::update(), which either fails the test and returns false or succeeds, executes the micro, and returns true. Given the original archon or zealot in mUnit, it looks for the closest enemy unit that meets the conditions:

	Unit lurker;
	int lurkerDistance = std::numeric_limits<int>::max();
	for each(Unit unit in UnitTracker::Instance().selectAllEnemy())
	{
		if(unit->exists() && !unit->isDetected() && (unit->isCloaked() || unit->getType().hasPermanentCloak() || (unit->getType() == BWAPI::UnitTypes::Zerg_Lurker && unit->isBurrowed())))
		{
			int thisDistance = mUnit->getDistance(unit);
			if(thisDistance < lurkerDistance)
			{
				lurkerDistance = thisDistance;
				lurker = unit;
			}
		}
	}

	if(!lurker || lurkerDistance > minDistance)
		return false;

The variable is called “lurker” but it looks for any unit that is undetected and is temporarily cloaked (like a wraith or a unit under an arbiter), permanently cloaked (like a dark templar), or is a burrowed lurker. I skipped over the next bit of code: It checks for the other unit (of type typeToFind) and if it’s close enough puts it in other; if it has a zealot it looks for an archon, or if an archon it looks for a zealot. If it finds the needed other unit, it executes the micro:

	if(typeToFind == BWAPI::UnitTypes::Protoss_Archon)
	{
		if(mUnit != UnitTracker::Instance().selectAllUnits(BWAPI::UnitTypes::Protoss_Zealot).getClosestUnit(lurker))
			return false;

		mUnit->move(lurker->getPosition());
		return true;
	}
	else
	{
		if(otherDistance <= 14)
		{
			mUnit->attack(other);
			return true;
		}
		else
		{
			mUnit->move(other->getPosition());
			return true;
		}
	}

If the unit is a zealot (because typeToFind is archon) and it’s not the closest zealot, it bails so that the target doesn’t get swarmed by zealots—one volunteer at a time, please! The zealot moves to the position of the target. If the unit is the archon, it moves toward the zealot (not toward the target; this corrects for miscoordination that could occur if there’s more than one target around) or, if the zealot is within splash range of the target, attacks the zealot.

The bottom line is that Skynet has the basic skill, but its implementation is not sophisticated. It knows all the possible targets, but can only use a zealot as the sacrifice—pros in a pinch will use anything that works as the sacrifice. It doesn’t know that it could use a reaver instead of an archon. It doesn’t consider whether the sacrifice is worth the damage to the target (you’ll hurt your zealot and the cloaked wraith will probably escape). It does no preparation (keep the archon and zealot near each other if they may need to work together) and minimal coordination (if there’s an observer just out of range and approaching, you shouldn’t have bothered; if you have high templar around maybe you should storm it). If the target evades, Skynet may keep microing both units, leaving them out of the fight. But of course most bots don’t have even the basic skill.

Reminder: Other units that do splash can also kill undetected enemies this way. Reavers, sieged tanks, and lurkers are the prime splash-dealing candidates. Corsairs, firebats, valkyries, and infested terrans also have occasional uses. (Mutalisk bounces are technically not splash and do not hit undetected enemies.) And, of course, spell effects like nuke, irradiate, psionic storm, ensnare, and plague affect units whether they are detected or not. Ensnare and plague are particularly useful because they make cloaked units visible.

Near the end of this 2008 game, Stork fires on his own carriers with corsairs to hold off cloaked wraiths.

Tomorrow: Mine dragging.

I meant to write another post or two about how particular bots keep their squads in formation, but after grepping source code for every keyword I could think of, I didn’t turn any up. We already know that OpprimoBot keeps its squads compact with a flocking algorithm, so my search was definitely not comprehensive... but I still gave up.

Instead I’ll write a short series about interesting skills coded into Skynet. Of bots whose source I have, the three candidates for Bot With the Most Hand-Coded Skills are ICEbot, Skynet, and Tscmoo, and Skynet is the easiest to read.

As an appetizer, here is a comment from TaskManagerClass::getPriorityList, which sorts tasks related to build order, research and production into priority order:

	// If I am vulnerable to counter attack / have no map control, place defense higher
	// If I am not behind on army size but its not safe to attack, tech
	// If I am not behind on army size but its safe to attack, produce
	// If I'm behind on army supply, produce

The ideas in the comment are not implemented. Skynet is already one of the cleverest bots in adapting its build to the game situation. Imagine how much cleverer it could be if Andrew Smith had had enough time to implement these ideas.

Tomorrow: Killing undetected lurkers.

Nova is from 2011 and was a mediocre performer at the time, so I figure that a current bot ought to do at least as well. Nova’s page points to source code and to Alberto Uriarte Pérez’s thesis “Multi-Reactive Planning for Real-Time Strategy Games,” among other stuff.

The thesis gives this diagram but is vague in explaining what Nova actually does. At least we can see that the centroid of the squad is important.

The source code knows all, tells all, if we have but time to listen as it talks on and on. In SquadAgent::onFrame() I see this, freely leaving out irrelevant bits:

	switch (_state) {
		...
		case GetPosition:
			if (isSquadBio()) {
			 ...
				checkSpread(); // check to compact squad
			} ...
    }

_state == GetPosition means that the squad’s orders are to move to a position. isSquadBio() is true if the squad contains at least one marine or medic. So checkSpread() is doing the job (I deleted commented-out code below).

void SquadAgent::checkSpread()
{
	// if we are close to our base, don't checkSpread
	if (informationManager->home->getCenter().getApproxDistance(_center) < 30*TILE_SIZE) return;

	double maxSpread = MAX_SPREAD_BASE + _squadUnits.size() + _squadMaxSpread;
	double minSpread = MIN_SPREAD_BASE + _squadMaxSpread;

	if ( _movement == SquadAgent::Normal && _spread >  maxSpread) {
		// get nearest chokepoint
		BWTA::Chokepoint* bestChokepoint = BWTA::getNearestChokepoint(getClosestUnitTo(_positionTarget, UnitTypes::None, true)->_unit->getPosition());
		// get unit closest to chokepoint
		Position location;
		if (bestChokepoint != NULL) {
			location = getClosestUnitTo(bestChokepoint->getCenter(), UnitTypes::None, true)->_unit->getPosition();
		} else {
			location = getClosestUnitTo(_positionTarget, UnitTypes::None, true)->_unit->getPosition();
		}
		for(CombatUnitSet::const_iterator i=this->_squadUnits.begin();i!=this->_squadUnits.end();++i) {
			if ((*i)->_unit->getType() == UnitTypes::Terran_Dropship || (*i)->_unit->getType() == UnitTypes::Terran_Science_Vessel) continue; //ignore special micro
			(*i)->_unit->move(location);
		}
		_movement = SquadAgent::Cohesion;
	}
	if ( _movement == SquadAgent::Cohesion && _spread < minSpread ){
		for(CombatUnitSet::const_iterator i=this->_squadUnits.begin();i!=this->_squadUnits.end();++i) {
			if ((*i)->_unit->getType() == UnitTypes::Terran_Dropship || (*i)->_unit->getType() == UnitTypes::Terran_Science_Vessel) continue; //ignore special micro
			(*i)->_unit->attack(_positionTarget);
		}
		_movement = SquadAgent::Normal;
	}

	Unit* closest = getClosestUnitTo(_positionTarget, UnitTypes::None, true)->_unit;
	if ( (closest->getOrder() == Orders::AttackMove || closest->getOrder() == Orders::AttackTile || closest->getOrder() == Orders::AttackUnit) && _movement == SquadAgent::Cohesion ) {
		_movement = SquadAgent::Normal;
	}

	Broodwar->drawCircleMap(_center.x(), _center.y(), (int) maxSpread, Colors::Red, false);
	Broodwar->drawCircleMap(_center.x(), _center.y(), (int) minSpread, Colors::Green, false);
}

That’s clear enough, a little state machine. It calculates a maximum, minimum, and actual spread as drawn in the diagram from the thesis. If the squad’s movement is Normal and the actual spread is greater than the maximum, then figure out a location to gather the units and move them there, and set the movement state to Cohesion. The gather location is the location of the squad unit which is closest to the chokepoint which the most advanced unit is closest to. The cohesion state waits until the spread falls below the minimum, when it restores the regular orders and resets the state to Normal. There are exceptions for dropships and vessels, and an escape from cohesion mode, depending on the orders of the nearest unit to the destination, which I assume cancels cohesion mode when the squad comes under attack. Regular orders are to attack-move and cohesion orders are to move, so you have to cancel cohesion mode when under attack.

I assume that the gather location calculation is fancy for a good reason, but maybe a simpler gather location could be some squad unit which is farther ahead. Then the effect would be to make the leaders pause while stragglers caught up. This calculation looks like it will sometimes have the squad moving backward to gather up.

I've already seen a related idea with flocking, and you could implement other related ideas with potential fields too. Nova’s contribution is explicit gathering of the squad when it scatters too much.

Here’s a perfect example of why path analysis and tactical analysis should go together.

This map has two paths through the center. Johan Kayser’s bot has thoroughly blocked one path. WuliBot knew better than to confront the bunker farm head on, but never seemed to conceive the idea of bypassing it by taking the other path through the center. WuliBot could have walked unopposed into the terran base.

Instead, terran eventually won.

Left to itself, a group of units sent across the map will tend to string out into a line, often with gaps. If that line runs headlong into waiting enemies, it will be eaten alive. The enemy “crossed your T,” as in battleship tactics. The whole enemy force can fire, while only the front units of the approaching line can engage, so you get defeated in detail.

Some bots keep their squads in compact formation as they move. They stay ready to engage any enemy that may suddenly appear. Other bots don’t care. They let their units string out and take the risk of being caught off guard.

AIUR is an example of a bot that doesn’t care about formation. It will happily attack in single-file and be ground up like sausage. In fact, I think that’s one of the main ways that it loses won games: Instead of gathering up its superior force and attacking with a coherent army, it fights with dribs and drabs as they arrive.

A number of terran bots that train marines and medics let the two get separated. The marines and medics form up into a squad and set out for a distant destination. Along the way, the marines find something to shoot at and stop to do that, while the medics continue on to the original destination. Separated, of course, they all die.

Exceptions. Letting units string out into a line is not always bad. If you’re in a hurry, then run run run at full speed. Staying compact would mean slowing down.

The line formation can be good.

Run your line of units parallel to the enemy formation, and when you’re in position, converge on them. In human play, this tactic is common with zerglings and zealots, whose melee attacks are most effective when they approach in shallow formation across the breadth of the enemy army. I haven’t seen any bot do this skillfully, even though it’s basic micro. For example, lining up zealots is key to breaking a terran tank push.

Tomorrow: The old terran bot Nova keeps its squads compact while moving. I’ll look into that.

I like Johan Hagelbäck’s writings (see this post), but one point bugged me. He kept repeating the idea that units should engage at their maximum shooting distance. Well, he talks about various kinds of unit micro that you can achieve with potential fields, and most of it is simplified from the ideal, but this one simplification bugged me.

Keeping near your maximum shooting distance is often a good idea. You’re close enough to harm the enemy, but being at the maximum range increases your options (you could run away or kite out of range during cooldown) and decreases the enemy’s (maybe they have to approach to hit you at all). If you have only one behavior, then staying near maximum shooting distance is a good one.

But look at the giant exceptions:

• If you have a group of ranged units, you want as many as possible to fire. If there are too many to fit into a single arc (you have a large number, or you’re fighting in a narrow space), then some of them must come closer. If you’re going to stand and fight, then bring the most possible firepower to bear. When your reinforcements join the battle, they have to be able to reach the front line—it’s a kind of coordination and hard to implement, but it’s critical to good micro. The front line can make gaps to allow reinforcements through (a skill also useful for reaver scarabs), or can move forward to let reinforcements into range.

• Sieged tanks can shoot farther than they can see, so you have to consider vision range too.

• Sieged tanks have a minimum range, so if you’re attacking them you may want to snuggle up. Also, if the enemy has sieged tanks on the field, any enemy unit you snuggle up to is at risk of taking splash damage from its own side. Few bots seem to know.

• If you’re blasting down static defense (cannons, say) with siege tanks, don’t siege just inside tank range like most bots, siege just outside cannon range. You’ll probably be able to destroy more cannons before you have to unsiege and move, so you’ll clear the cannons faster and be more likely to win overall (carriers may be coming, yes?). This advice will usually be right when the enemy front line is static defense, but might be wrong if the enemy has other units in wait. Humans commonly siege tanks at different ranges, partly to save micro but also because it’s more robust against surprises from different directions.

• If you have ranged units and there’s an obstacle between the armies, then your only reason to keep your distance is so that fewer enemies can shoot at you. Dragoons on a cliff can take potshots all day at zerglings down below, and the same for guardians uphill from marines.

• If you’re going to win the battle, then staying at maximum shooting distance gives the enemy better chances to escape. If you can’t surround, then keep close so you can pick off more escapees.

In full generality, the distance at which one unit should seek to engage another (given that you want to) depends on the range, damage, cooldown, speed, and acceleration of both units, plus the terrain, with consideration of special abilities (psionic storm, mine laying, medic healing...), and if you want to be utterly thorough, the full game situation too. For most unit pairs the basic calculation is easy enough. For example, if you have more speed and more range (speed vulture versus slow zealot, ranged dragoon versus unupgraded marine), who cares how close you get, as long as you don’t get hurt?

For army on army, the formation and distance you want depend on the sizes and unit mixes of both armies, plus the terrain, plus the game situation. The maximum shooting distance is a good base to start at, but you’ll need to expand beyond to win.

Today I noticed that the the blog’s RSS feed has become the most popular single file on my site, surpassing robots.txt. (I have on the order of 10K pages, so it’s a distinction.) Finally, more people want to know about robots than robots about people!