Starcraft AI blog

Predicting enemy unit movement is easy and fun, and it helps micro a lot. Now that I’ve implemented a version in Steamhammer, I recommend it for everyone.

Adding this feature dramatically improved Steamhammer’s micro in some situations. It affects almost every fight; with prediction, your units do less moving and more shooting. It’s most obvious in a chase. When chasing the enemy scouting worker, zerglings with prediction don’t pursue endlessly, but catch it. The most extreme case may be playing against Stone once zerglings come out. Stone’s SCVs flee like the wind, or they twist and turn trying to evade, but they can’t escape. Steamhammer wins with much less useless chasing.

making the prediction

Here’s my implementation in Steamhammer: Assume that the enemy unit will keep moving in a straight line at a constant speed, and predict a fixed number of frames ahead. It’s dead simple. ClipToMap() makes sure that we return a valid position—we may predict that the enemy falls off the edge of the world. ClipToMap() simply restricts x and y to valid values,. We predict a position closer to where the enemy will end up if it bumps into the edge of the map.

// Predict a visible unit's movement a given number of frames into the future,
// on the assumption that it keeps moving in a straight line.
// If it is predicted to go off the map, clip the prediction to a valid position on the map.
BWAPI::Position PredictMovement(BWAPI::Unit unit, int frames)
{
	UAB_ASSERT(unit && unit->getPosition().isValid(), "bad unit");

	BWAPI::Position pos(
		unit->getPosition().x + int(frames * unit->getVelocityX()),
		unit->getPosition().y + int(frames * unit->getVelocityY())
	);
	ClipToMap(pos);
	return pos;
}

There are fancier ways to predict. You can take terrain into account; an enemy ground unit will probably not pass through unwalkable terrain (though there are ways to do that). You may want to take the chasing unit into account—can it catch up? I believe Iron calculates the closest interception point where the chasing unit can catch the enemy, and heads straight there. That is a more elaborate calculation, but not too difficult, and there are several ways to do it.

using the prediction

How you use the prediction depends on your code, of course. In Steamhammer, it is as simple as making the prediction. Steamhammer normally calls Micro::AttackUnit() to issue an attack command. I added Micro::CatchAndAttackUnit() which attacks if we are able to, and otherwise issues a move command toward the predicted enemy position 8 frames in the future. Here is the working part (I took out irrelevant stuff like error checking and debug drawing).

	if (!target->isMoving() || !attacker->canMove() || attacker->isInWeaponRange(target))
	{
		AttackUnit(attacker, target);
	}
	else
	{
		BWAPI::Position destination(PredictMovement(target, 8));	// the number is how many frames to look ahead
		Move(attacker, destination);
	}

Then I substituted Micro::CatchAndAttackUnit() for Micro::AttackUnit() throughout the code wherever it made sense. The condition !attacker->canMove() means there is no problem if you call it for an inappropriate unit, like a burrowed lurker or a sieged tank, because then it behaves just like the original call. (But I didn’t call it for inappropriate units.)

I chose 8 frames fairly arbitrarily. I think a range of values will work. With 8 frames, we aim for a spot a little ahead of where the enemy is, and not so far ahead that they can throw us off by turning. Dan Gant points out in a comment that PurpleWave predicts a variable number of frames ahead depending on when the chasing unit will be able to attack; the goal is to come into range at the same moment that we are ready to attack.

It makes sense to predict further into the future if the enemy is far away. Calculating the interception point like Iron is the ultimate version of that. Maybe the ideal method is to find the interception point when far away, and switch to the Purple idea when approaching attack range.

There is a disadvantage to the change in Steamhammer. There seems to be a higher rate of units getting stuck, unable to move. I haven’t yet looked into why. It affects protoss the most. It’s possible that the change makes protoss play worse overall.

I’m still preparing for AIST, so expect Steamhammer to participate. The bot is going to struggle, though. There is not enough time to prepare it fully for the maps. Steamhammer will do well only if the other competitors are equally unprepared.

Sparkle is a genuinely difficult map. It requires specialized builds that are not right for any other map, which means that in the proper course of events I ought to delay work on it until Steamhammer can develop its own openings, which won’t be for a time yet. And the map has unique features that require special code. No matter how general I make the code, in practice it will apply to this map alone.

The high ground expansion on the island has zerg buildings that create creep. The creep is an issue for map analysis if you’re not zerg, because BWAPI doesn’t provide a way to find static creep on the map; you have to see it to know where it is, or figure out for yourself how it spreads. The high ground base also has a large crystal on top of the geyser. Any race can built a refinery of its type on the geyser, but the crystal blocks mining from anything other than a zerg extractor (well, you can mine if you glitch each worker through; a bot might be able to do it regularly, but it’s definitely not intended by the map design). Steamhammer is confused by the confusing features and isn’t able to take the base, even as zerg. The low ground expansion has a psi disruptor building on top of the geyser. To my surprise, on the AIST map version it’s also possible to build a refinery underneath the psi disruptor (I tested it by hand with the 3 races). I haven’t seen that in pro games, and assumed the building had to be torn down first. Steamhammer can build an extractor there. But no race can mine from the geyser until the psi disruptor is destroyed.

Yesterday I started on the skill of clearing the neutral buildings that clog up the second and third bases on each starting island. As matters stand, Steamhammer can mine only 1 of the 3 geysers that it should have access to, which leaves it ridiculously weak. The map analysis creates for each base a list of “blockers” that ought to be destroyed, which it outlines on the map in red if map info is turned on. Almost all maps have none. Fortunately the coding and testing only took a couple hours.

Only then did I think through the rest of the steps to implement the skill. There is updating the list of blockers as they are destroyed, of course. Before that is sending a squad to do the work... but hmm, the usual tactical getAttackLocation() only returns a location, not a unit to attack. In fact, Steamhammer doesn’t have any way to order a squad to destroy a unit! I have to create a new kind of squad order, implement it in the squad, and add the tactical analysis to decide when to use the order. It’s likely a day’s work to write and test and finish, more if I hit a snag.

Well, that’s too much effort to support a single map. On the other hand, most of the code is reusable for destroying buildings that block paths, a more common skill though low on my list. I’m still thinking about it. In the meantime, I’ll work on other skills. There’s not exactly a shortage.

Steamhammer-Iron is the first game in which Steamhammer played its AntiFactory opening, which counters Iron’s vulture runby skill (as well as other stuff that opponents could try with a mech opening, and some opponents do try). If Steamhammer started with no history, it would counter Iron on the second game. In fact it started with all its past game records on SSCAIT since version 1.4, so it thought AntiFactory was just another opening to explore, more important than the average opening because it counters the predicted enemy plan, but still just another opening and not worth special attention. Since it lost, it probably won’t try the opening again for a while (though there is a lot of randomness in the decision).

If you’re familiar other Steamhammer-Iron games, like that one, you’ll notice that in this game the AntiFactory opening stops Iron’s early vulture pressure more or less neatly and gets mutalisks in time to break up the next attack, the followup that adds marines and 1 tank. Then Steamhammer starts to flounder. The mutalisks neither defend efficiently nor attack the enemy base efficiently, and zerg desperately wants a 3rd base and sends drone after drone to die. Still, it was a tough fight and Iron only gradually took the upper hand. With this opening, Steamhammer has a moderate chance to beat Iron.

Steamhammer needs more skills to beat Iron regularly.

• Place the initial sunken correctly. It makes a surprisingly big difference.
• Don’t send drones directly into enemy forces. If you can’t expand safely, make a macro hatchery in your base instead.
• Once another base is up, defend it. Steamhammer tends to lose all the drones there.
• Play more incisively with the mutalisks. Don’t hesitate in front of defenses, immediately switch to another target. Be more eager to pick off tanks and less willing to chase fleeing vultures and SCVs.

I think those 4 skills would be enough to win most games against Iron, and only 1 of them is a complex skill. Likely even 2 of them, any 2, would put the win rate over 50%. Tilt the game a tiny bit, and it rolls your way over time. More skills would help more. For example:

• Don’t lose overlords like an idiot from Idiot City, even if you are one. Steamhammer regularly flies into turrets.
• When it’s time to expand, coordinate actions: Clear any blocking spider mine, push attackers away, if necessary escort the drone to the expansion site.
• Use scourge properly.
• Clear spider mines systematically. Steamhammer has the infrastructure to track spider mines that it has seen once, but doesn’t use it; units ignore mines that are not detected at that moment.

Am I going to actually work on any of these skills soon? Maybe. Overlord safety is high on my list, because it is a critical weakness in all matchups. For the more complex skills, I am waiting for the revamp of squad structure, which won’t start for months yet. Priorities are hard.

Next: Priorities in light of the AIST competition.

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....”

Burrow is like The 500 Hats of Bartholomew Cubbins—it doesn’t have infinite uses, each more elaborate than the last, but it does have more than you expect. At the same time, burrow is like the hats in that is it not often practical. It’s fairly rare to research burrow in pro games, though there are situations where it is common.

The Liquipedia article on burrow is fairly thorough, though I know more than it does. I’d like to organize the information differently, by the tactical or micro purpose. Of course, it’s common for one use of burrow to have more than one purpose. As far as I can tell, my list of purposes is exhaustive. Did I miss anything?

First, an observation: Many bots don’t get detection unless and until they know that they need it. Also many bots don’t recognize or react to burrowing when they see it (though Steamhammer does). In bot play, I think burrow is highly abusable, in other words it has a strong chance to exploit the opponent’s weaknesses.

Also, coordination always helps. If the enemy is camping your burrowed units to keep them down, maybe you can pressure somewhere else to release them. If you’ve laid a burrow trap, maybe you can lure the enemy into it, or force detection somewhere else to distract. And so on.

To hide for safety. When a reaver comes in to drop, there is probably no observer around. Drones can keep mining until the reaver appears on the ground, then burrow before they are targeted. (It’s not good against storm drops, though.) If outnumbered units can’t get away (they are slow or are cornered), they may be able to burrow and hide; at worst, the enemy will have to make extra effort to detect them, and at best they may live. If you think the enemy doesn’t have detection, you can burrow almost any time that you don’t want to fight. It may complicate the enemy’s tactical reasoning. Of course the enemy could choose to stand around on top of your burrowed units until they can be dealt with, so it may also complicate your tactical reasoning.

To hide in ambush. This is something I tried as a beginner: Burrow zerglings on the map where marines will pass by, and when they unsuspectingly walk over, unburrow for a surprise attack. It’s hard to do successfully, and the few times I’ve seen it tried in pro games it usually fails, though in the best case it can be devastating. It’s easier to burrow outside the enemy base for a backstab after the enemy army leaves. Or burrow in position for a sandwich; for example, burrow outside your base and unburrow when the enemy approaches your sunkens.

Against corsair-reaver play, it is common to burrow hydralisks in places where shuttles may appear. Ideally, you can snipe shuttles before any reavers land.

You can burrow near a base location that the enemy should take, and wait for the base to start construction, or to finish construction, or even for workers to arrive, before springing the ambush.

An infested terran does tremendous damage, and an infested terran can burrow. (That’s some extreme infestation.) Infested terran burrow traps are tempting. If terran is making mass tanks, maybe there’s not much gas left over for vessels and you can burrow in position to wipe out clustered tanks. 3 infested terrans kill a command center. You can try to burrow them where a base will be. If the queen is still around and you want another infested command center, you only need 2 infested terrans. But in most situations, probably drop is more practical than burrow for deploying infested terrans.

Hiding has many tactical uses. If you are short of overlords near the enemy base (perhaps on purpose so they’re not spotted), you can elevator a force piece by piece into an unseen corner and keep them burrowed there until the attack force is complete. It’s not a skill worth implementing in a bot, but I want to show that creative uses are out there.

To gain vision. Also common in corsair-reaver is to burrow zerglings around the map to reveal where the enemy is flying. It’s especially useful in corsair-reaver, because observers do not come along so the enemy rarely finds the burrowed lings. It’s potentially useful whenever the enemy moves around without detection. You can burrow zerglings at chokes, or in between bases to catch when workers transfer.

You can burrow in the enemy base to watch. A scout that survives until burrow is researched but then is in danger of being caught—burrow. A zergling force sneaks in to pick at probes, but 1 burrows by the gateways to see what comes out, or near the ramp to see what passes by. If you see the robo, maybe you can find a spot away from the path that observers will take.

To block building construction. Some terran bots place spider mines at every base location. A zergling works just as well for gaining vision and for blocking construction, and it has the option of unburrowing to chase off the enemy worker, or to look around the area, or to flee if in danger. Because it can unburrow, it has a chance to spot the start of the enemy base, rather than just the presence of the enemy.

It’s theoretically possible to use burrow to spoil a wall, or to prevent a terran addon from being made. I find it hard to imagine when that would be useful. But consider: Many bots are unable to adapt when they fail to place a building, and simply try to place it in the same location again. A burrowed unit anywhere that one of these bots tries to build may mess it up severely.

To take advantage of stacking. Burrowed units stack, somewhat like air units. In other words, units under the ground never collide with each other. You can burrow arbitrarily many units in the same patch of ground, one group after another. You can make a large force look like a small force, even to a detector, by burrowing units on top of each other. If you stack lurkers on top of each other, the lurkers will probably fire at the same time at the same target and their damage will also stack. Strong players do this all the time, to make it unclear how many lurkers there are, to make it hard to irradiate all the lurkers, and to get the effect of the stacked damage.

Units above the ground of course do collide when their collision boxes overlap. When you unburrow units which overlap with other units you are unburrowing, or with units already on the surface, then the units don’t all fit in the space they occupy. They get stuck on each other and start to glitch and spread out. Sometimes that’s bad; it causes awkwardness all the time for Steamhammer when unburrowing lurkers. There are also ways to exploit the collisions.

The Hoejja build is a way to exploit the collisions. It uses burrow and unburrow to glitch early zerglings through the blocking mineral patch on some maps—not all the lings get through, but it can be enough. It relies on the opponent to play a build with no early mobile defense, namely protoss forge expand. On the one hand, the only SSCAIT map suitable for this trick is Destination. On the other hand, a bot should be able to do the burrow-unburrow trick much faster and more precisely than a human, and a machine opponent is unlikely to understand how to react.

You could try the same burrow-unburrow trick to pass units through a wall. Does it work against Iron?

Another way to exploit the collisions is to spring a burrow trap which causes the enemy units to glitch. If other forces attack at the same time, it won’t matter at all that some of your unburrowing units are glitching too.

To prevent spell effects. Burrowed units avoid some spells with area effects.

These spells leave burrowed units unaffected: Maelstrom, stasis, recall, ensnare, plague. Of course recall only works on your own units (which you must have gained by mind control if they can burrow), so inability to recall a burrowed unit is a limitation. (I imagine that the limitation is because burrowed units stack; the designers don’t want you to be able to recall an arbitrarily large zerg force.) For the other spells, you may be able to avoid the effect by burrowing early enough.

These spells affect burrowed units as usual: EMP, defensive matrix, yamato cannon, hallucination, psionic storm, disruption web, broodling, parasite. The visual effect of defensive matrix is not visible on a burrowed unit. Disruption web is mostly useful for disrupting burrowed units which are lurkers, because others can’t attack while burrowed. If you dweb burrowed zerglings, they can unburrow and leave the area of effect to attack.

You can broodling a burrowed unit. The 2 broodlings appear above ground and cannot burrow. (Liquipedia says that all ground units other than ultralisks can burrow. They forgot about broodlings.) You can hallucinate a burrowed unit. The hallucinations appear above ground and cannot burrow.

Not on either list above is irradiate. You can irradiate a burrowed unit as usual. But the splash damage of irradiate is absorbed by the ground: It does not splash from or to any burrowed unit. If one hydralisk in a group is irradiated, you can burrow it to save the others. Or you can burrow drones when terran tries the eraser trick, flying an irradiated science vessel overhead. Both ways prevent irradiate from causing splash damage.

To prevent splash damage. Burrowed units avoid some splash damage. Liquipedia explains it as a splash damage effect of dark swarm, but dark swarm is another topic. As far as I know, the only important splash avoided is tank splash. I didn’t test it to find out, but it’s possible that they also avoid the outer ranges of nuke damage.

If you set up an array of zerglings and have a tank fire once at the central ling, then tank splash works like this: The central ling and some around it are killed, while others a little farther away are damaged. If you burrow the zerglings and then have the tank fire once, then the central ling and some around it are killed, while those a little farther away are unharmed. The splash damage was eliminated outside an area of central effect.

Under dark swarm, the tank shot is offset from its aim point. It still kills zerglings in its area of central effect, so the terran may be able to analyze the pattern of units under dark swarm and aim at one that puts the actual impact point where desired. Or zerg can arrange the units so that important units cannot be hit by aiming at another unit. When I tested it, I found some unexpected tank splash outside the impact point, so it may be that dark swarm has more complicated effects. At least, there’s probably something I don’t understand.

To prevent slow effects. I haven’t tested this, but it seems likely to work. Some attacks, like the reaver scarab and the ensnare spell, are slow and you can see them coming because they have a “bullet” that has to travel to the target. Burrowing takes time too, but it is fast. I think you can probably avoid slow effects in some cases by burrowing immediately.

I thought of another tricky idea to stop reaver shots using burrow. It’s not practical, but it’s cute: Burrow a tight line of units in front of or around a target (likely across a choke). When the reaver scarab comes, you should be able to unburrow in time to block the shot. I expect the scarab would be unable to find a path to the target and would dud out. Then you can burrow again before the next shot. If you want it to look impressive, predict the scarab’s path and unburrow just the units needed to block it at each moment, like playing Pong with a scarab. (Seriously. Somebody should try to code scarab Pong, just for fun.)

The hold lurker trick. This isn’t about burrow specifically, but it is common in human play and it is related. It’s worth a mention. See the Liquipedia article for details.

If a skill is effective in games and not too hard to implement, and yet isn’t implemented in many bots, then surely it is an underused skill. For example, I think that evacuating workers from a base under attack is underused. It is easy to tell whether to evacuate workers: If you have a combat simulator or an army strength estimator or any method to tell whether you’ll win or lose a fight, then run it when the enemy reaches a base of yours, at least if you have another base that can keep mining. It is not as easy to tell where to evacuate workers to, since they might flee toward the enemy army. But you know the current place is bad, and running anywhere else is probably no worse.

Steamhammer doesn’t evacuate workers, and suffers for it. It’s high on my list. The 7 bots above it on the bot ladder do, except I think for XIMP by Tomas Vajda; Steamhammer may be the strongest bot missing the skill. Killerbot by Marian Devecka is particularly good at it, if as ask me. Most other bots don’t; it’s a fairly rare skill, which is why I say it is underused.

There is a special case that is even easier to implement: Terran can evacuate SCVs by simply lifting the command center. If terran has another command center landed anywhere else (reachable by land), then the SCVs will return their cargo there. If not, the SCVs will stay near the minerals or gas, not the best place to hide but better than nothing. As a side benefit, if the attacking force includes units that can’t shoot up, the command center will often take longer to destroy—even if it only floats there and doesn’t move away.

PenaBot by Henri Kumpulainen used to lift its command centers, if I remember from so long ago. Iron does it sometimes when losing, though I don’t think the purpose is to evacuate SCVs. LetaBot by Martin Rooijackers will float a command center, but only to move it into position. I can’t think of any current bot that lifts its command center to protect itself.

I nominate lifting the command center for safety as the #1 most underused skill. What do you think are underused skills?

I decided I was tired of seeing Steamhammer lose helplessly to Iron’s vulture runby and Tscmoo’s factory openings. Terran can start with vultures and force zerg to defend: Zerglings quickly become useless, drones are at risk, and terran can run by defenses into the main as Iron does. Steamhammer’s strategy boss understands that a sunken is needed at the front, and has a vague idea that hydralisks may be useful if the book line happens to end, but in the end it doesn’t defend adequately. Then terran can follow up with more factory units or with wraiths, and zerg has to be ready for a range of possibilities. Against Steamhammer, Tscmoo likes to follow up with goliaths, which is effective against Steamhammer’s mutalisk openings. Too many crushing losses.

Zerg has a standard way to defend: Place a sunken at the front as a vulture obstacle and keep a modest number of unupgraded hydralisks in a defensive position. The hydras are general purpose and can fight off vulture runbys, wraith harassment, small drops—all the natural followups. Zerg then continues to mutalisks as usual. The mutas are delayed, but terran is playing a slow strategy so it’s OK.

Today I set about developing an “AntiFactory” opening that implements the standard defense. I decided on development tests against Iron to see whether the runby defense works. In the very first test, when the opening timings were still all screwy, Steamhammer put up a persistent defense and didn’t lose until well into the middlegame. An improvement already, good. I made a few fixes and tried again. Steamhammer held the early aggression cleanly and fought a long level game until Iron finally mined out and collapsed.

I did not expect that! Steamhammer lost drones by the barrel and miscontrolled scourge and chased 1 SCV with 3 ultralisks, all its usual mistakes, but Iron struggled too and could neither stop zerg from expanding nor keep a fourth base up. I guess Iron depends heavily on the success of the early vulture runby.

Well, one win does not make a champion. We’ll see how it goes as I polish the opening. It’s just that the test game was so long that by the time I finished watching it, I had forgotten what needed fixing in the opening....

When the opening is ready, will the opponent model be able to select it when it should? I think the answer is no. I think I will have to extend the plan recognizer to recognize early vulture plans. Then Steamhammer should be able to counter the vultures in the second game, and ideally cope with the followup. It would be nice if Steamhammer could get back into the learning war against Tscmoo terran, and come out on top this time.

AntiFactory branches fairly late from related openings. When the opening tree is available, Steamhammer should be able to recognize the vulture plan during the game and choose the right build on the fly, more like a human player. It might need some scouting improvements first, though.

Next: The new bots GuiBot and WillyT.

Steamhammer has 2 favorite lurker dysfunctions. One of them is kind of interesting.

Its #1 favorite blunder happens versus protoss. Lurkers act somewhat independently of the squad they belong to, because their burrowing ability lets them be more aggressive. But they’re not clever about it; they don’t understand detection. When a lurker sees a photon cannon, it understands it as a high priority target, walks up to it, and burrows in range. Then the cannon kills it. Not very interesting. I haven’t thought of a way to fix it without adding or rewriting too much code, so I put it off. I’ll fix it when I work on micro, likely in the 1.5.x series while I’m doing mutalisk stuff.

The second favorite blunder is less common but more interesting. It usually comes up versus terran. Lurkers approach a ramp with a bunker on top. They can’t see uphill, but when they get in range the bunker starts firing, so the lurkers can see the bunker and they burrow and start shooting back. Then the bunker can no longer see the lurkers, so it stops firing. The lurkers no longer see their target, so they unburrow, becoming visible... and the cycle repeats. Terrans that know how to place a bunker on top of a ramp generally know how to repair it, so the bunker usually wins. If the overlord catches up to provide vision, the overlord flies into bunker range and holds position... and doesn’t provide vision for long. This game versus Ecgberht shows it happening twice, before another lurker attack finally breaks the ramp because there were enough zerglings.

To fix the overlord behavior, overlords have to worry about threats. That’s on my menu for soon-ish. I may fix the lurker misbehavior with a rule like “if you’re on low ground and the target is on high ground and you want to burrow, move to burrow on high ground if possible,” that is, on the ramp. Ideally, the combat simulator would be able to tell whether the lurker can burrow successfully. Eventually I want to teach Steamhammer how to reason about visibility, instead of following rules.

I made an improvement to overlord production in Steamhammer, and it reminded me: Making overlords is a difficult skill. Supply is tricky for terran and protoss too, but zerg overlords are trickier because overlords have more uses and are more vulnerable.

When to make overlords. If you know ahead of time what units you will produce when, you can plan overlords at exactly the right times. Of course, you usually have only a general idea. If you scout that the enemy is getting mutalisks much earlier than you, then you have to make spores and that is that; an overlord in the egg will turn out to be unnecessary.

The tactical situation matters: Are corsairs out? Are you planning a doom drop? If you’re at risk of losing overlords, you may want extras to avoid being supply blocked. Ideally, bots should weigh the risk of supply blockage (which depends on events in the game) against the cost of extra overlords. I don’t know whether any bots do that; Steamhammer certainly doesn’t. When CherryPi loses overlords and gets supply blocked, it likes to hugely overproduce overlords and try to stay ahead by sheer volume. I don’t think that’s good play, but it seems at least as successful as Steamhammer’s method of producing the minimum number of overlords.

Conversely, if you find yourself ahead in supply, you may be able to take bigger risks with your overlords, at least for a while. Sacrifice one to scout and you won’t miss it.

The strategic situation also weighs in on overlord production. If you get supply blocked, instead of producing overlords, you could start a fight to reduce your army size. You want to compare the cost of the fight versus the cost of the overlords. Even if you’re not supply blocked, the cost of buying supply to feed your growing army can provide some impetus to attack. If you suddenly lose a lot of army in battle, you may even want to cancel overlords in the egg.

The result of all the complications is that bots have to rely on heuristics or approximations. Most bots do well enough with overlord production despite living by simple rules of thumb. But the stronger the bot, the more the fine details matter.

Where to make overlords. Since overlords have uses, it also matters where you produce them, especially before overlord speed is researched. In the early game, strong players plan ahead where to place and how to maneuver overlords to see as much as possible of key areas. Where each overlord is produced figures into the plan. Later, bases and armies may need overlord coverage to spot dark templar or to gain vision of high ground. New overlords should be made near where they will be needed—unless other units are higher priority. If corsairs are marauding, most overlords may have to be produced near air defenses (lacking this skill hurts Steamhammer).

Overlords are a tiny aspect of the game. It’s dizzying how complicated it all is.

A heuristic: If the enemy has one medic and some marines, target the medic first. Nobody will heal the medic, and the marines will be softer targets. If the enemy has more than one medic, target the marines. Medics have armor and more hit points, they are happy to heal each other and they do no damage. The heuristic is not always right, but it seems good most of the time.

Another heuristic: If you are tearing down a base and may be interrupted, then a building that the enemy has only 1 of is more important than otherwise. If you find 2 x gateway and 1 x nexus, it may be better to target the nexus. If you find 2 x nexus and 1 x gateway, maybe the gateway is a better target. It’s not as firm as the first heuristic, but it seems to point in the right direction.

A similar idea is taking out one pylon that powers more than one enemy building. These can all be seen as special cases of key point analysis, where you recognize key points that are especially valuable to take out—or, if they are yours, to protect. The general idea is to understand what depends on what. You want to destroy the enemy dependencies that are the most important and take the least effort: The one medic, the one gateway, the one pylon.

Well, I happened to think of the first 2 heuristics and realized that they were related. It’s probably not time to implement this kind of reasoning in bots; I think for now it is enough to implement a few special cases as heuristics. But someday bots will be strong and will get into late game situations where precise reasoning makes a big difference: When to use your last minerals to make a cannon and surround it with dark templar, when to hide a pylon on a cliff, when to shepherd your probes with an arbiter for long-distance mining—that way of protecting your key points.

TeamLiquid has posted an excellent interview with Flash—the #1 human player, of course, not the protoss Starcraft bot. The post is by BigFan, the interview is by lemmata. A lot of the interview is about the thought process behind optimizing opening builds.

I want to draw special attention to this bit:

Q: You mix the 1-1-1 with +1 5-rax quite effectively. Does this force Zerg to mix between 3-hatch and 18-hatch builds?

A: That is a given. You always have to mix well.

Flash is talking about the importance of choosing openings randomly. Some points the opponent can scout out before making important decisions, and some points cannot be scouted, leaving decisions to be made blindly. At all levels of play, forcing adaptation from the opponent who has seen what you are doing puts some pressure on, because the opponent’s adapted build order is not likely to be as optimized as the mainline build the opponent had in mind. Flash creates optimized alternatives to make it difficult for the opponent to respond as accurately. At pro level in particular, where both sides are aware of the known deviations and adaptations, making a random choice when the opponent cannot scout what happened until later can put heavy pressure on. In general, both players want mixed strategies, in the game theory sense.

A later line is related: “By increasing the number of possibilities the opponent has to worry about, I can cloud his judgment and induce decision paralysis.” It’s the same idea, with a psychological instead of a game theory rationale.

side story

The interview gives a handy zerg build order for a “2.5 hatch mutalisk” aka “18 hatch mutalisk” opening that Steamhammer does not have. I’ve grown tired of chasing too many bugs that are too hard to find, so I decided to code up the opening and try it out. That should be a nice break.

The build order calls for making units up to a supply limit of 18, then starting the third hatchery, then finally getting the necessary overlord as late as possible. It’s a cute optimization taking advantage of the supply freed up by the drone used to make the hatchery, and it’s necessary for the build to work as intended. When I tried it out, Steamhammer made the overlord early, and ended up with an extra overlord at a critical time. Not good enough.

“Hmm,” I thought, “the heuristic for adding in overlords is too crude, but I can do an exact simulation of supply in the queue to see if the next planned overlord is in time. It will be a useful improvement, and it’s not hard.” So I coded that up too, and fixed a couple problems in the first try. And... it still doesn’t work. There is another bug, and it is hard to find! Argh!

Update: The rest of the story continues to be funny. There were several bugs in the supply simulation, mostly edge cases. The decisive one was that unfinished hatchery supply was not counted as pending supply—deliberately, since hatcheries take a long time to finish and only provide 1 supply. I decided to count hatchery supply if the hatchery was within 300 frames of finishing; I think that should make it good in all cases. After fixing every bug, an overlord was still started too early! The cause turned out to be a mistiming in the opening itself. The extractor was built one step too late, so that there was not quite enough gas to start the lair immediately when it came up. The clever, clever production manager said “I can improve on this, just move the overlord forward and nothing else will be delayed.” It was a real improvement on the build order as written, but it was not the best possible improvement....

Back when I played online regularly, one of the tricks I pulled sometimes was to build an expansion hatchery out of position, where it might escape being scouted. Main bases on many maps have space behind the gas geyser, and if the geyser is on the opposite side from the base entrance, I might put a hatchery there and mine gas and the edge minerals. Some maps, like Python, have space behind the minerals where a hatchery can go. If the base was defensible, I could add another hatchery in the usual position later.

Another reason to build out of position is that the position is blocked, for example by a pylon or a spider mine. Terran can build an offset command center and float it into place after the block is removed. Even zerg will sometimes build a hatchery in an offset position, especially if the expansion is desperately needed. (I don’t think I’ve seen a deliberately offset nexus in pro play. That’s a bigger investment.)

These tricks came to mind because Steamhammer doesn’t support them. I’ve been working on the base placement code, which assumes without question that there is One Correct Placement. It’s much easier to to code that way, and the results are good—special tricks are for special circumstances, not for most games.

Still, the thought reminded me again that bots need to be more flexible in their thinking. Placing a base should be like tactical analysis in that it considers different actions (at least in unusual situations) and compares them to choose the best.

What upgrades should you get? In what order? I often see bots get upgrades in an order that doesn’t make sense to me. I’ll mention 2 big examples.

If you’re terran and you’ll be making marines for a long time, you want the academy upgrades. Standard is to get stim first and then range. Stim helps in almost every situation, and it helps a lot, while range has a smaller effect and gives the greatest boost to large groups of marines. Stim also takes less time to research. When I added stim to Steamhammer, I found it clear that stim made the marines much more dangerous, despite the fact that (like most bots) Steamhammer tends to overstim and run down the energy of its medics. Probably the most important change needed to stim is not reducing overstim, but making sure that stim is always researched as early as possible. BOSS doesn’t understand priorities, and just throws research in whenever.

And yet I think most bots that get both stim and range, get range first. Even sophisticated Tscmoo gets range first. Why is that? Maybe there’s a good reason—every bot is different, and you want to tune for its skills. Or maybe it’s a mistake.

The other example is zerglings versus zealots in ZvP. Unless you’re going all air like XIMP by Tomas Vajda, protoss should get +1 ground attack as the first forge upgrade. Bots generally do that right. (The second forge upgrade should be +2 attack, and the third should be +3 attack. Get armor, and maybe then shields, only if you’re upgrading at multiple forges, or after +3 attack finishes.)

If you opened forge first, you may be able to start the upgrade very early. It’s worth it. A zergling has 35 health. A zealot does 16 base damage, so it takes 3 hits to kill a zergling. A zealot with +1 does 18 damage, and 18 * 2 = 36 so it kills a zergling in 2 hits (the zergling will regenerate 1 hp, so the 36 is exactly what’s needed). 2 hits versus 3 is a giant difference. Zerglings suddenly turn into tofu.

A zealot has damage factor 2, meaning it hits twice in each shot: It doesn’t do 16, it does 8 + 8. So a zergling with +1 carapace avoids 2 points of damage. If zerg can get as many carapace upgrades as protoss has attack upgrades, then zerglings remain zerglings and do not become bean curd.

CherryPi gets +1 zergling attack instead of +1 carapace. It is effective against a protoss that does not upgrade at all. Against a protoss that gets +1 attack, it is a mistake. I’ll do the arithmetic. A zergling does 5 damage; a +1 attack zergling does 6. A zealot has 60 shields: That’s 12 hits versus 10 to remove the shields. A zealot has 1 armor and 100 hp: That’s 25 hits (100 hp divided by 5-1=4 damage per hit) versus 20 to finish the zealot off. I’m ignoring shield regeneration, because it gets complicated. That makes 37 hits versus 30, a nice improvement. 30/37 is .81; it takes about 4/5 as many hits after the upgrade. But 2/3 is .67—the zealot’s attack upgrade outweighs the zergling’s attack upgrade.

There are other examples. These are the ones that jump out at me.

I took a preliminary look at how far creep spreads from a hatchery. Here’s a picture from my first experiment.

The numbers on each tile are the distance from the hatchery, determined by hatchery->getDistance() and scaled to tiles instead of pixels. Tiles for which BWAPI::Broodwar->hasCreep() is true get orange numbers. Boxed tiles are unwalkable according to Steamhammer’s walkability map: A 32x32 tile is walkable if all its constituent 8x8 walk tiles are walkable, taking into account terrain and fixed neutral units only.

Creep spreads in an oval pattern, similarly to power from a protoss pylon. Of course creep spreads bit by bit, unlike the instantaneous power from a pylon, but at the start of the game the initial hatchery has its full spread of creep, so in that case we can ignore the spreading process.

After trying this on a variety of maps, including some irregular Blizzard maps, I found that the initial hatchery’s creep, though its outline seems a little odd, takes on a tile-for-tile identical outline on all maps. I’ll test further, but it looks as though I can predict the creep for the initial hatchery without much trouble: Hardcode one pattern of creep spread, match it to the hatchery location, clip it at the edges of the map, and trim away the minerals, geyser, and any terrain features that don’t allow creep. So far I haven’t tried a map where this method would give a wrong answer.

If it continues to look good, then an upcoming 1.4.x version of Steamhammer will be a little faster to find the bases of zerg opponents. Early game scouting units will definitively identify the occupied base when they see creep, and definitively identify an empty base when they don’t see creep that should be there.

Later versions will also have the ability to infer the existence of a zerg base by seeing creep later in the game. It’s strange to see bots pass in sight of creep and not realize what it means—“must keep looking, where is that last enemy base?” That feature will be a little more complicated. We don’t want to infer the existence of a base which was just destroyed, or get confused because outlying creep colonies of one base extend the creep as far as another base.

Next: Other near-term plans for Steamhammer.

Mutalisk bounce attacks are complicated.

In lore, the mutalisk attacks with a glaive wurm. A glaive is a sword. BWAPI spells it “glave”, which is a less common alternate spelling. Anyway, the attack does 9 normal damage directly. If an enemy unit is close enough, it bounces and hits the enemy, doing 1/3 as much damage, 3. If a second enemy is close enough, it bounces a second time and does 1/3 as much damage again, 1.

upgrades

If you upgrade mutalisk attack +1, the bounces are upgraded too. The first attack is 9+1=10; the second attack is 10/3 = 3.33 (rounding to 2 digits); the second attack is 10/9 = 1.11. The total gain is 1.44; for +2 upgrade, 2.88; for +3 upgrade, 4.33.

Brood War does track fractional damage behind the scenes, though you can’t see it in the user interface. There is also a hard floor; every attack, even one that is smaller than the target’s armor, does at least 0.5 hp of damage. At least that’s my understanding of how it works.

If you’re under attack by mutalisks, +1 armor applies to all 3 bounces, so it prevents up to 3 points of damage per shot.

For ZvZ air battles, zerg players disagree on whether it is better to get +1 armor or +1 attack for mutalisks. +1 armor is more popular; it costs more (150/150 instead of 100/100) but prevents more damage (3) than +1 attack causes (1.44), and it also protects scourge and overlords. Nevertheless, some strong players prefer to get +1 attack. The best choice can depend on the game situation—for one thing, upgrades don’t use up a larva; for another, scourge have 25 hit points and are vulnerable to bounces.

you don’t have to attack an enemy

It doesn’t matter what the mutalisk attacks, the glaive wurm will bounce to an enemy if one is close enough. You can attack a harmless enemy building, or a neutral building or neutral critter, or your own unit or building. Mutalisks have a short range of only 3 tiles. By bouncing from a safe object, they can do some damage to enemies while keeping at longer range. In the best case, the bounces can hit marines while the mutalisks are out of range of marine fire.

Human players do this when a good opportunity presents itself. I’ve never seen a bot do it.

which way does it bounce?

This TeamLiquid translation from Korean gives 2 rules for how glaive wurms bounce. You can have some foreknowledge of which enemy each bounce will hit.

Rule 1: It bounces to the left if possible; otherwise, it bounces down if possible. If it can’t bounce left or down, it will go another direction. This rule applies no matter what direction the mutalisk attacks from. It means that separated mutalisks which attack the same target at the same time will get the same bounce pattern, which is good for the attacker because it focuses fire. It also means that the defender can arrange units to try to minimize the bounce harm, for example by putting healthier units or units with higher armor on the left of the formation.

Rule 2: If you attack from directly to the left, it bounces the minimum possible distance, hitting the closest enemy. If you attack from directly to the right, it bounces as far as it can. It can make a difference when fighting marines, if the mutalisks are numerous enough that the bounce can kill a marine. In that case, other things being equal, it’s better to attack from the left and kill a close marine that is in range to shoot back, rather than from the right and kill a distant marine that may be idle. You’ll escape taking that much less fire.

These rules aren’t enough to tell exactly which unit the bounces will hit. It’s coded into OpenBW, so there should be people who know....

Some bots, like Willbot, take a passive line and build up a large force before taking any offensive action. Others, like Steamhammer, prefer to keep the pressure on and attack whenever possible, even at high risk.

Neither style of play shows real understanding of strategy. Here are 2 simple principles that should be uncontroversial:

1. The side with more stuff has an advantage. If you have more units, or better upgrades, or higher tech, that is an advantage. You get those things by spending minerals and gas, so ultimately the side with more resources has an advantage.

2. The side on the defensive has an advantage. If you have static defense built, tanks sieged, lurkers burrowed, or simply units deployed in good position to engage, that is an advantage. If you have a shorter route to your production buildings, then reinforcements arrive sooner and that is an advantage. If you can stop or delay or channel attacking forces with blocking buildings or chosen terrain, that is an advantage.

From these 2 axioms, we can act like Euclid and derive a theorem: If you control more resources, you don’t have to attack. You can attack if you spot a weakness, but you don’t need to. You can hang back, in a safe defensive position, until your theoretical resource advantage manifests as a practical battlefield advantage, and then attack. At least you can wait until you are maxed at 200 supply.

Containment is the common case we see in bot play. When Steamhammer has the opponent contained, it constantly tries to press forward to notice and immediately exploit any weakness. It’s usually a mistake. Typically you should contain at the best defensive location you can, take care with the forward units you risk for vision, and scout to make sure the opponent can’t sneak an expansion or bypass the containment with drops or air play. You control the resources on the rest of the map, and that is an advantage.

The general rule is: If you can take expansions and deny expansions to the opponent, you will win. You can win without ever entering a fair fight. If the opponent takes an undefended expansion, smash it. If the opponent moves their army to defend a new expansion, smash the enemy natural instead. At worst, you force the opponent to allocate forces accurately to defend all threats. Tscmoo is the bot which implements this rule the best, though it still seems a bit crude to me.

The extreme case is a map split, where each side ends up controlling about half the map—except one side controls an extra base or two. Humans sometimes play from the beginning of the game for a favorable map split. I don’t think any bot understands the idea.

How do we get from here, strategic ignorance, to there, understanding tactical force allocation risks and tradeoffs to meet the strategic goal? Well, I mis-stated it; bots don’t have to understand, they only have to take the right actions. Bots today that contain the enemy don’t (it seems to me) understand what they are doing. They are following rules that produce containments as an emergent behavior. It’s a valid approach. But I recommend more explicit knowledge representations, because I think it will lead to faster progress.

Sometime this year Steamhammer will get an evaluation function that tells it how good or bad a situation is. The first version may be a simple hand-written evaluator that is used for a few decisions. In time, I hope to create an accurate evaluator by machine learning, good for decisions throughout the game. Then the same underlying knowledge, encoded the evaluator, will let Steamhammer adapt its openings moment by moment, choose its unit mix, and maneuver its forces.