Starcraft AI blog

Another interesting game was PurpleWave v Steamhammer.

PurpleWave opened with two gates on one base but noticed a lot of zerglings. It cautiously added cannons at its ramp before moving out to pressure. It was an overstep: The ramp with zealots was unassailable, but as it happened Steamhammer defeated the zealots in the field and then the cannons over the ramp in detail, before being chased out by new zealots. On the next moveout, zerglings again broke into the base, killed the new cannon, and did away with many probes. Zerg evened the worker count but could not quite pull a win. Stamhammer switched to droning up, and it was the start of a long fight. PurpleWave spent a lot of gas replacing observers.

A couple cannons are little defense if unsupported, and take away from the zealot count. The bigger issue is, how do you know when it’s safe to move out? The scouting probe was long dead, and sending a new probe does not necessarily reveal the zergling count. Speedlings could easily catch it before it gets far. For zerg, the eternal issue is the economy/army tradeoff. If Steamhammer had kept up zergling production, it would likely have won quickly because of the overconfident protoss play. But if PurpleWave held the ramp instead, zerg would have fallen behind and had no chance. Steamhammer is weak at managing the tradeoff in the middle game.

Starcraft. It’s a hard game.

A number of stronger terran bots make valkyries against Steamhammer. Not one of the terrans knows how to use them well. Steamhammer trades better against valkyries in nearly every game where they show up.

Valkyries are specialist units. Valkyries in small groups, when kept safe, can devastate mutalisks (or wraiths). A valkyrie wandering around on its own can’t devastate anything except one pair of scourge. Zerg will happily trade a pair of scourge costing 25/75 for a 250/125 valk. The valkyrie can run away from scourge, but only if it does not shoot. When the valk fires, it stops dead in the air!

In TvZ, defeating mutalisks is their only important role. In most situations they are not good for hunting overlords, because they are too vulnerable to scourge. To fight guardians, wraiths are better, because guardians have armor. Devourers have more armor, and goliaths and vessels are better.

Advice to terran bots: If you are facing mutalisks, consider keeping up to 3 valkyries in the air against a dozen mutas, maybe slightly more if the mutas mass up beyond that or pull ahead in armor upgrades. Valkyries are expensive; making too many is wasteful. Keep them together so they fire at nearly the same time. It makes them far more effective—seriously, mutas will melt away like light snow; zerg will be forced to spread them so that they cannot focus fire. Keep them near marines, goliaths, or turrets for protection from scourge. Make sure your anti-air units prioritize shooting down scourge; scourge are low in HP and expensive in gas, so they’re good targets whether you have air units nearby or not. Even with all that, valkyries may not pay for themselves unless you also implement valkyrie patrol micro as described in Liquipedia. It’s critical, and I’ve never seen a bot use it.

Valkyries can be worth it, but only for bots that know how to use them.

SCHNAIL players who try out Steamhammer often play a series of games one after another, and if they liked it they come back another day for more. I’ve watched enough of these series that I have a sense of the patterns they follow. Everybody’s different, of course, and Steamhammer’s play has random elements too. But often enough, a series with a terran or protoss opponent who is well-matched with Steamhammer more or less follows a prototypical sequence of four steps.

1. Get busted. Steamhammer is tuned against bots, where early aggression is successful, so it often starts out with a bust. Apparently many humans at this level are not quite prepared. Against terran it breaks in with zerglings or lurkers, against protoss with lings, hydras, or mutas. (Terrans are ready for mutalisks.)

2. Tighten up defenses. Players at this level figure out how to stop an incoming Steamhammer rush within a few games. That’s typically good for two or three wins before Steamhammer tries something else.

3. Get overrun by macro. Players at this level also tend to be too passive. Maybe macro and scouting and whatnot uses up their bandwidth, or maybe they’re used to being fine if they stay at home for a while. If the player goes active and begins attacks too late into the middle game, Steamhammer has already started to outmacro them and, even if it loses bases along the way, will finally win with hive tech.

4. Learn to attack actively. And players at this level don’t take long to understand how to react to zerg macro: Don’t let the zerg macro, but attack expansions aggressively. The new static defense code makes more sunkens at exposed outer bases against humans (not against bots), which helps them survive. But Steamhammer is not strong at defense, and players are fairly successful at taking the bases down anyway. After figuring this out, the human player will win games indefinitely, sometimes all games. If the two are closely matched, the games may be long and difficult.

Alternately, a terran may make one big timing attack into the zerg natural, and break through. Steamhammer can usually deter this plan versus protoss.

It seems to me that if you start out struggling to beat Steamhammer, and without using any special anti-bot tricks learn to defeat it, then you must have improved your play. Tight defense and active play are good. The same skills you polished to beat the bot will help you against other opponents.

Of course, many series don’t go this way at all. A player of different strength may get all losses or all wins. Several days ago one player played a long series of cannon rushes on the 2-player map Destination, first trying to push cannons from the side of the zerg base, then in later games switching to cannon the natural. The rush, after adding proxy gateways, often eventually destroyed the zerg main, despite being slowed by defenses, and units from the proxy gates were then able to move out and destroy more bases. But protoss was never able to stop zerg from expanding, and ended up losing every game, usually after defensive cannons in the protoss base suddenly fell. Steamhammer made many missteps, but I was pleased with the defense against cannon pushes. This was likely a player trying out the strategy for fun.

In Steamhammer 3.5.1 (see the “zerg” section) I added a defense against cannon rushes which exploits the sunken range bug. The bug makes it possible, under specific conditions, for a sunken colony to target an enemy which is outside the sunken’s range. Exploiting the bug is allowed in human tournaments. In fact, it’s a standard defense against cannon rushes, one that players know and use. An example is ASL 11 Semifinal A, Mini vs Queen, game 1—see about 32 minutes into the vod for a complicated sequence where Mini eventually abandons the cannon rush knowing that it has been countered, and notice that casters Nyoken and Scan have little trouble understanding what happened and why.

At the time I wrote “Use of this bug seems to be universally legal,” but today I checked the AIIDE rules more closely. The rules include a list of allowed bugs to exploit, and add “All other bugs/exploits are forbidden.” The sunken range bug is not on the list.

I sent e-mail to Dave Churchill explaining the situation and its complexities. He’s busy and I don’t know if he’ll have time to look into it. Basically, I’m expecting to disable the behavior in Steamhammer for the tournament. I’m adding a configuration setting Config::Skills::UseSunkenRangeBug so I can turn it on and off.

Most likely no AIIDE 2021 protoss will cannon rush at all, so in a way the point is academic. But who knows?

what should the rules say?

It’s complicated!

The range bug is a game behavior, and it can happen unintentionally in real games, just because events happen to trigger its conditions. It’s fairly rare, but I expect all who play regularly have seen it (whether they recognized it or not). Bots should not be penalized for game behavior that they did not intend, and have no reason to even notice.

Steamhammer deliberately attempts to exploit the bug to beat cannon rushes. I have to interpret that as a violation of the AIIDE rules as they are written.

If you’re actively trying to enforce the rule, how would you do it? First, you’d have to examine the games, presumably with replay analysis software since there are too many to watch in person. Then you’d have to decide whether at least one instance of the bug was a deliberate exploit. That likely involves reading the code to be sure. Tournament organizers are not going to go to so much trouble, so probably the only practical enforcement would be for other authors or observers to point out possible infractions after the fact.

Then there’s the point that exploiting the bug is legal in human play, so presumably it should be legal in bot play. But that has a hidden assumption behind it: Humans can’t or don’t exploit the bug in any way that seems unfair, therefore bots won’t either. It might be true, but how sure are you? Bots with perfect timing and simultaneous view of all information might be able to exploit the bug in a way that feels unfair. Then the rules would be unfair.

Maybe it’s right to allow exploiting the range bug unless and until some bot implements an unfair exploitation.

Even if it may be a good idea to change the rules, it’s no good to change them close to the submission deadline. The rules for this year should stay put. Next year’s rules may be open to debate.

Update: I have mail from Dave Churchill. After some flip-flopping, the final ruling is “INTENTIONAL use of this bug via any specific code that invokes it is not allowed.” That follows the original rules.

Steamhammer has superhuman macro, or at least, its macro skills are far beyond those of human players around its level. I think pro-level zergs can probably macro better than Steamhammer in many situations, because of superior planning. But Steamhammer is utterly superhuman in some aspects. For example, humans can’t do mining optimization after the early game. And the bot can set every drone to work on the first frame that the drone becomes commandable.

And yet, and yet! Steamhammer’s macro is far from optimal. It feels strange that it can be at the same time so good and still have so much room for improvement. It’s not something I need to work on soon, because it’s a relative strong point even compared to other zerg bots, but in the long run there are steps to take.

For one, Steamhammer does not do all the mining optimizations that it could. Some bots ranked above it have put considerably more effort in.

For another, there is a limitation in the production system that it can only produce one queue item per frame (except commands; it can execute commands in the same frame as another queue item). The limitation reduces bookkeeping and simplifies the code. Usually, it makes little difference. When Steamhammer saves larvas to produce its first 3 pairs of zerglings, it hardly matters that the second and third pairs start a fraction late. But in the late game, occasionally there is a sudden need to produce many zerglings at a time when all the needed larvas are available (because production has been limited by gas). The last zerglings in the queue may be started over a game second later than they could have been, and that could affect the fight. It’s hardly a critical weakness, though. I’ll rework production eventually, but it is low on my priority list.

The big macro weakness is that Steamhammer does not plan ahead. It makes hatcheries and overlords at times decided by heuristics. The heuristics are not bad, but for hatcheries in particular it often ends up with too few or too many—commonly, too few and then it overcorrects and gets too many. It’s possible to do much better by predicting the needs of future production and adding hatcheries just in time. It could be tricky, because future production depends on how the game will go, which depends on the opponent’s play. Even if you knew exactly what combat unit mix you want (which you can’t be sure of), there’s a risk that you might lose drones and need to replace them, and drones are larva-intensive because they are cheap. But still, it’s definitely possible to do much better than Steamhammer’s current play. That change is sort of in the middle of my priority list.

Even the greatest strengths are not so great. It’s a hard game.

In TvZ, sometimes terran stops marine production and goes with factory units (maybe with starport units), whether early in the game to play a straight mech strategy or later to switch to it. Usually terran lifts the barracks to get it or them out of the way. If you see a lifted barracks, that’s a clue to the enemy strategy. Seeing vultures or goliaths appear may be your first clue, but unavailable barracks say that marine production is stopped (or at least slowed), so it’s a stronger clue. It rules out marine-tank unit mixes.

I think human players can usually read the clue correctly, when they need to. Bot opponents go marine-tank often, so it may be a useful clue for bots. But it seems a little tricky to read with assurance. You can’t just say, “overlord spotted a lifted barracks, cancel lurkers,” you need to look at more context. Maybe terran is only rearranging their base, or moving the barracks to a blocking position for the sim city. (Though if it’s in a blocking position, you may see whether it is making units.) Even a floating barracks far from the terran base may be intended to land as a proxy, maybe making a couple firebats to toast some drones.

Maybe bots should take a graded approach. Early in the game, terran should have only 1 or 2 barracks. Seeing a barracks in the air is a big deal, and the longer it floats or otherwise produces nothing, the more sure you can be that infantry is deemphasized. Later in the game you should have a rough idea how many barracks terran may have tucked out of sight, or at least how many barracks the terran’s bases can support. The more flying barracks you see, the more confidence you should have that fresh marines will be few.

At least that’s what I would start with if I were coding it by hand. My plan is to draw inferences like that largely by machine learning.

I learned a new trick from watching the ASL 11 games. The game was Sharp versus Best, the second game of group B in the round of 16. Watch with English commentary by Nyoken and Scan on Afreeca or on Youtube. On the Afreeca vod, the game starts a little after 55 minutes in. The Youtube vod was trimmed and it starts closer to 46 minutes.

Sharp scouted Best’s base with an SCV, which then left the base. Best blocked the entrance to his main with a zealot to prevent further scouting. But when the SCV returned for a second look, it mineral-walked through Best’s blocking zealot and got a look around anyway. I was surprised, and Nyoken (who knows more about Starcraft than I do) was also surprised: How did the SCV get vision of Best’s minerals to do the mineral walk? Sharp had no apparent way to see the minerals.

Scan explained it. The SCV was click-moved to a location far from the base (a location chosen so that the second-scout timing would come out right). As it was leaving, while it still had vision of the minerals, Sharp shift-clicked back to the minerals. That was the last time Sharp had the necessary vision. The SCV followed its orders to move far away, then followed the queued order to mineral walk back into the base. I had never seen it before.

I sometimes see bots using queued commands to move units across the map through waypoints. (In BWAPI you do that by setting the optional shiftQueueCommand parameter of a command to true; it defaults to false.) It is usually a mistake. When you queue a move command, the moving unit completes the command by coming to a stop at the destination before the next command in the queue executes. It adds a delay—a very visible delay. If you’re following waypoints, it is normally better to issue a new move command in real time before the unit reaches the waypoint, so that it never slows down or stops, and reaches its final destination sooner. But in the case of mineral walk, you may not still have vision of the minerals later when it’s time to issue that command. If you want to issue a sequence of moves ending with a mineral walk, you may want to queue them all while you still have vision. It will execute later whether you have vision then or not.

I tried it myself, and it works. What a complicated game!

In its earliest days, Steamhammer had some trouble with cannon rushes due to bugs that you might imagine are unrelated. See Steamhammer’s funniest bug from January 2017, when it was only a month old. Back then it had no learning, and I manually configured it to play 9 pool versus cannon rushers and other cheese bots. Once the basics of scouting and so on were straightened out, it worked fine at the time, except against AIUR by Florian Richoux, which alongside other builds sometimes does sneaky cannon rushes (still among the best cannon rushes by any bot, in my opinion).

When I added learning, Steamhammer became able to recognize the cannon bots and react on its own. No more manual configuration. It still countered with 9 pool, which is simple and reliable. When Juno by Yuanheng Zhu came on the scene, it caused little new trouble. Only AIUR, with its unpredictable builds, occasionally won by cannon rush. The other cannon bots were predictable and easy to stop.

Today it is different. Krasi0P switches between cannon contain to lock you into your base, and defensive cannons. MadMix can execute an impressive variety of offensive cannon builds: In your base, in your natural, outside your natural; containing or directly attacking without trying to contain; with forge in base or forge up front. The 9 pool still stops them all, provided the cannons have been spotted, but since the enemy build is unpredictable, Steamhammer doesn’t know when to play it. Well, it could play 9 pool every game, except that it doesn’t have the skills to adapt its play when it sees that the enemy has done something else. If there were about 16 of me, I might be able to work on everything at once....

The current Steamhammer has many different reactions to help it cope with cannon rushes. And it can still lose.

• If the enemy is predicted to proxy cannons, choose 9 pool or a similar anti-cheese build. That takes care of bots with only 1 build, and bots that play the cannon rush too consistently after it wins.

• Scout the main base and areas near the natural with an overlord. How this happens depends on game events, but typically the second overlord starts the work; it may be replaced by a later overlord if the second is called away to join units. With Steamhammer’s current skills, scouting the cannons early is crucial to reacting well. This scouting may in practice be the most valuable skill on the list—although objectively it’s often better to send the overlord to scout the enemy.

• Recognize all nearby cannons, out to beyond the natural, as rushes. Early Steamhammer versions only noticed cannons in the zerg base, because that was all it faced back then.

• Recognize a forward forge as an incoming cannon rush. There is no other reason to build a forge near the enemy base. (Now we get to see if any bots make a pylon and start the forge when it is in vision, then cancel it, to spoof a cannon rush. Would Steamhammer overreact?)

• If a forge or unfinished cannons are near the mineral line, pull drones to attack. Steamhammer doesn’t pull drones far, though. I haven’t felt inspired to do the calculation of when workers reach the cannons versus when the cannons complete.

• If cannons are scouted before the spawning pool has been placed, start the pool ASAP, canceling stuff if necessary. This is often objectively an overreaction, but with Steamhammer’s skills it’s usually a good decision in practice.

• If a cannon appears near a zerg base, any base at any time during the game, place exactly one sunken to prevent the cannons from pushing closer. All bots that use cannons offensively also like to cannon push—except Steamhammer protoss, which prefers to add a gateway. MadMix can sometimes push cannons around the single sunken and reach a vulnerable point in the zerg base, so the defense is not airtight.

• Send a drone to a hidden base location if possible, and the next time we want to expand, expand to that base. If the scout drone is out scouting, it will be the one assigned. If we’re contained we’ll be able to produce units outside the containment, and if the main base is killed by cannons, we’ll have a distant base that protoss will have to find and deal with separately.

• Don’t assign units to the defense squad to kill cannons, assign units to an attack squad to go kill the enemy base. So far, I have seen no cannon bots defend the main with cannons—and, well, Steamhammer’s hidden base is hidden.

• If the enemy has no known mobile anti-air units, send overlords to watch over vacant bases on the map. This is also an anti-cannon skill! Steamhammer has lost games after killing the enemy main by not noticing that protoss had another base—zerg units gather to kill the cannons, the last known enemy buildings, which may take a long time and let the enemy recover.

• When there are cannons on the map, prefer hydralisks over zerglings. They’re more efficient versus mass cannons. Steamhammer is slow to switch, though, and often overproduces zerglings regardless.

That is a lot of skills! And they work fairly well and win most cannon rush games. How does Steamhammer still lose games? Mainly by blundering into cannons. Drones leaving the base to build don’t notice the cannons and die. Drones trying to transfer to the outside base do notice the cannons and mostly stay out of range, but clog up movement for other units. Safe movement is not perfect and loses some. Attacking is sloppy and loses more. Defense has a horrible bug which sends warriors through the cannons without fighting. I’ve concluded that threat-aware pathfinding is necessary, and that it has to be hooked into production so that Steamhammer doesn’t do things like make more drones in the main than it can support—it has to know whether it can transfer them out before it decides to produce them.

In other words, the losses are due to bugs that you might imagine are unrelated. If only there were 16 of me!

Most terran bots that lay spider mines don’t pay much attention to where the mines are relative to where their own units are, or to where their own units will be, only to where opponents are expected. Spider mines do massive splash damage to all units nearby, enemy or friendly, so it’s safest to keep your own units away from them. These pictures show what can happen when you leave a spider mine in your own mineral line.

In this case, the mineral line was thinly populated, so only 5 SCVs died along with the 1 zergling that triggered the mine. “Only” 5.

Laying a spider mine in an enemy mineral line can be good. Maybe you can lure a zealot to trigger it. In a neutral base, it will tell you if the enemy takes the base and may not give away that you know. If you take that neutral base yourself, your mine is a danger to yourself. You should kill it.

Most terran bots (even Krasi0) will happily set up a tank line in the midst of their own minefield. When a pro feels the need to do that, they kill their own mines if there is time. In bot world, most opponents don’t particularly notice the opportunity of triggering the enemy mines on purpose, so they score mine hits on enemy units by chance if at all. Some do it deliberately, though. Skynet by Andrew Smith has code which purports to drag mines into the enemy. I also see mine dragging code in PurpleWave, and I expect other top bots have the skill. It’s high on my list for adding to Steamhammer, because it is devastating when it works.

Starcraft has 3 suicide units: spider mines, scourge, and infested terrans. They need to be handled much differently than other units. All of them do high damage but are easy to destroy, so they are units with a lot of leverage (meaning that using them well brings a lot of benefit). Spider mines are difficult because they don’t move after they’re placed; you have to foresee the future to place them well. Scourge is difficult because it does move. Infested terrans are difficult because they are rarely any use unless they coordinate with other units.

Steamhammer is one of the best bots at scourge usage, but objectively it is distressingly weak. It often hits a target with more scourge than are needed to destroy it, is overcautious about attacking targets defended by ground units, suicides scourge against mass air units that can defend themselves, retreats scourge that have no immediate target too far from the fight, and other blunders. But it’s daunting to think of all the work needed to play well with just this one unit type.

How many scourge per target? Well, each hits for 110 damage, so divide. If a mutalisk target (120 HP max) is hurt more than slightly, you can kill it with 1 scourge, and you don’t want to waste any. But if there’s a long chase to catch it, it might heal during the chase and you’ll need 1 extra. Theoretically you could account for that beforehand. Or a target might recharge at a shield battery, or suddenly be mass-repaired, or d-matrixed. That’s hard to predict, and if it happens you might want to turn the scourge away—unless extras are already handy.

Scourge can be shot down on the way to the target. A battlecruiser has 500 HP, so it dies to 5 scourge. It can fire one shot before the scourge strike, and the shot can kill one scourge, so you need to send 6. Well, actually whether it kills the scourge depends on upgrades. 2 scourge kill a corsair. 4 scourge kill 2 corsairs. But 12 scourge do not kill 6 corsairs; the corsair damage splashes and protoss may defeat most or all of the scourge. In general, any enemies nearby may cooperate to kill your scourge. I don’t have a better idea than to simulate the attack and see how many scourge may be shot down, to decide how many are needed and whether it is worth it.

Usually you want to send enough scourge to kill the target. Don’t sent 2 at a time against that lone battlecruiser (as many bots do, including Steamhammer and PurpleSwarm), because only 1 will hit and you’ll need twice as many. Usually, but not always. A mutalisk has 120 HP, so a scourge hit leaves it with 10. A muta with 10 HP is nearly useless in an air fight, so if you follow up the scourge with your own mutas then the enemy muta will flee or die, or both. Neutralizing an enemy mutalisk with 1 scourge hit is a crazy-efficient use of gas.

What tactics? Scourge see corsair and chase; corsair sees scourge and flees toward safety (like a cannon or a group of dragoons). The corsair can try dodging micro moves to throw the scourge off; I doubt that works well against a bot. Pro players like to predict the path of the fleeing corsair and intercept it with another pair of scourge sent from another direction. I don’t know any bot that tries that.

Later, there may be many scourge and many corsairs. To minimize the splash damage to the scourge, try converging in a wide arc. That may make it worth while.

With lurkers versus protoss, you want to snipe observers. Undetected lurkers can delay protoss a long time, so it may easily be worth it to spend several scourge to kill a single observer that tries to stay safe among dragoons. But don’t fly in headlong, try to analyze the dragoon locations and choose the best angle.

In general, good scourge planning and pathing is complicated and depends on the tactical situation. And how are you supposed to do the planning, which has to happen before you can do an accurate combat simulation, without combat simulations first to figure out what works? I guess expensive methods may be needed.

Where to go when there are no immediate targets? Scourge are fast, so if the enemy has little anti-air, which is common versus protoss early in the game, a good idea may be to swoop around the map looking at stuff. But scourge have short sight range, so that’s dangerous once the enemy is good at shooting up. Scourge want to stay near where enemy air units may appear: Over or near the front-line army (which will protect them), above cliffs or unwalkable areas near the fight, along paths where dropships or corsairs may fly, or in your own base to defend against air raids. Making the best choices means predicting the enemy, not a simple skill.

The bottom line: Scourge use is awesomely complex. I don’t want to code all the details, I think I have to aim for more general methods of search and machine learning.

I have given Steamhammer a primitive ability to lift terran buildings. A terran opening can include a command like "go lift engineering bay" and every ebay that can lift, will. If it’s busy researching, it can’t lift. The StrategyManager code that manages terran production will lift every barracks and ebay if the plan calls for all factory production, so the command doesn’t have much practical use for those writing openings. Still, the lifted buildings will leave more space available in the main base, so fewer factories should end up in the middle of the map.

I thought the work would be trivial, but I had to make more changes to the parser than I expected. Now a MacroAct is able to parse and remember a command with a UnitType argument, in case I ever add any more commands like that.

Floating buildings are controlled by the new Scout Boss, which will find something useful for them to do. That’s why I added lifting now. I am also looking ahead: Lifting an infested command center is a zerg skill, and I’d like to be able to do that when appropriate. Steamhammer infests command centers on a regular basis, much more often than I’ve seen any other player do, bot or human.

You’ll need to write code if you want to lift off a specific building: Just this ebay that I built forward for scouting, not the one at home. A simple command has no way to specify. Still, I would like the production system to be able to tie production to specific units: Morph these hydras to lurkers, not the others; make this creep colony into a spore and that one into a sunken. I’ve seen only one game where it tried to make a spore (in main) and sunken (at natural) at the same time and got them switched, but it seems like something I had better get right.

Landing is not as easy as lifting off, because you have to decide where to land, and it depends on what you’re aiming for. Someday I’ll implement lifting off an endangered building and landing it again when the area is safe. It may involve ordering your own units out of the landing zone. That will likely be the first use case for landing. I think other cases will wait until there is an operations planner: Opening and closing “gates” in a wall, relocating a command center, floating in a proxy factory, reacting to enemy tricks like blocking the machine shop with a pylon....

This Steamhammer version is showing clear superiority over the previous one. I expected a small improvement that was hard to be sure of, but got an improvement that’s easy to see. Nevertheless, there is one new misbehavior: It takes bases in a poor order on some maps. On Heartbreak Ridge it takes the center base far too early, among other expansion order mistakes. Using the resource tracking info threw the base scoring out of whack, and my attempts to whack it back into whack were not enough. I have to hit it harder.

A funny picture:

Krasio is taking its third base as it should, and mining out the blocking minerals at a good timing so that it can transfer SCVs along the back path. Steamhammer has 2 drones in view. The drone on the right also wants to take the base, and is just noticing the command center in its way; it will give up and return home. The drone on the left knows, “We’re about to take this base, so I’d better clear this path that’s near it.” The SCV and drone are cooperating to mine out the stacked minerals, entirely to Krasio’s benefit.

Steamhammer stands at an advantage in this position, but ended up losing, most importantly because it took bases in the wrong order. Terran pushed out, and by the time zerg gained the strength to break the attack—which it did—the center base had already fallen. Many bots expand unsafely to that center base.

Let’s suppose there are two safe spots where you want to station overlords to watch for enemy movement, a nearer one A (perhaps near the entrance to your natural) and a farther one B.

    *     A     B
    1

Overlord 1 hatches. Of course you send it toward A. It’s slow, so it takes a while to get there.

    *     A     B
      --> 1

Then overlord 2 hatches. You could send it toward the next spot B, but that’s silly.

    *     A     B
    2     1

It’s faster to send overlord 1 from A to B and replace it with overlord 2 at A.

    *     A     B
      --> 2 --> 1

Humans do this kind of overlord shuffling all the time. Here’s a TeamLiquid post showing the overlord repositioning patterns of a few pro games. I don’t know of any bots that do it. It seems like it might be tricky, no? But in fact the problem of assigning overlords, or scouting units in general, to locations is an example of the mathematical assignment problem, and there is no shortage of known algorithms to solve it either exactly or approximately. I’m still thinking about how I want to solve it in Steamhammer.

Scouting in the presence of an enemy is not as simple. To do it optimally you’d have to understand how scout timings interact with possible timings of the opponent’s build, and consider the risk to the overlord from early marines, and take into account that an enemy that sees your overlord learns something about you too—and they might actively look for the overlord, humans often do (“if you’re at that base and scouting the most efficient way to the closest natural, your overlord will be here at this time; if I see it I found you, and if not, I ruled out one base”). The optimal strategy is surely a mixed strategy, meaning that you don’t play the same every game, and there’s no way it’s possible to calculate it on the fly. You have to either pre-calculate a plan or figure it out heuristically.

Steamhammer’s existing gas steal skill works by UCB, like the opening selection of many bots. It has a bias toward not stealing gas, but the basic behavior is that it will steal gas if that wins more games than not stealing, or if it hasn’t tried a gas steal in a while and it’s time to give it another spin. It pays no attention to what the opponent is doing, so it will try silly things like stealing gas while under zergling attack from a 4 pool. The silly decisions hurt.

Steamhammer 3.0 will have a completely recoded gas steal skill using the skill kit, and it will be much fancier. In fact it got too complicated; today I finished rewriting it to simplify the rules. I’ll upload 3.0 as soon as it passes tests.

The skill records three values for each game: The frame a gas steal was decided on (0 if never), the frame when the refinery building was started, and the lifetime of the refinery (when did the opponent clear the gas steal?). Also newly recorded in the game record is the frame when the enemy was first observed to have spent gas on a unit or building.

All this information, plus a few other items like the recognized enemy strategy, goes into the gas steal decision. The outline is that various checks are made first to see whether stealing gas makes sense (“no, this enemy doesn’t take gas for a long time anyway”). If so, attempt a gas steal randomly with a certain probability until we’ve accumulated 5 games of experience with it. Once the data is in hand, adjust the probability up or down depending on the amount of evidence, with fudge factors to try to take certain strategic points into account (“versus 2 barracks? are you sure about this?”).

It’s still crude compared to the analysis I’d like to do. The ideal would be to figure out the effect of stealing gas on the enemy’s strategy and play, infer the best time to attempt it, and send a worker then to threaten it. But it should avoid many of the blunders that the current method makes.

Next: The Cadenzie-Locutus match.

Today I pretended to have enough time to play around, fired up my development vm for the first time in days, and took an hour out to solve a niggling issue: How do you correctly predict when an enemy building will finish? My first try gave inaccurate predictions.

If it’s your own building, call building->getRemainingBuildTime(), done. If it’s an enemy building, that doesn’t work. You can see the building’s hit points and predict its completion time from that, but it’s a little tricky. Today I learned the 2 tricks.

One: A building just starting construction doesn’t start at 0 hp and work up, it starts at 10% of its final hp. Over the course of construction, it progresses smoothly from 10% to 100%. Liquipedia on buildings explained it to me. Two: After the hp reach 100%, there is extra latency before the building is actually complete. I didn’t read OpenBW, but a few quick experiments let me measure the latency fairly closely. I got 2 frames for a terran building, 72 or 73 frames for a protoss building for the warping-in animation, and 9 frames for a zerg building. Knowing that, with one glance you can predict the completion of an enemy building to within a few frames (usually to +/- 1 frame in my tests).

    // Predict the completion of a building under construction from its current HP.
    // isBeingConstructed() is false for a terran building with no SCV building it.
    // It's also false for non-buildings, so we don't need to check that separately.
    // A morphed zerg building cannot be predicted this way, so skip those.
    if (unit->isBeingConstructed() && !UnitUtil::IsMorphedBuildingType(type))
    {
        // Interpolate the HP to predict the completion time.
        // This only works for buildings. The prediction is usually accurate to within a few frames.
        // Known cases where the prediction is wrong:
        // * The building was damaged.
        // * The prediction is made during the extra latency period (see below).

        // A building begins with 10% of its final HP.
        double finalHP = double(type.maxHitPoints());
        double hpRatio = (unit->getHitPoints() - 0.1 * finalHP) / (0.9 * finalHP);

        // Buildings have extra latency for their completion animations.
        int extra;
        if (type.getRace() == BWAPI::Races::Terran)
        {
            extra = 2;
        }
        else if (type.getRace() == BWAPI::Races::Protoss)
        {
            extra = 72;
        }
        else // zerg
        {
            extra = 9;
        }

        return extra + BWAPI::Broodwar->getFrameCount() + int((1.0 - hpRatio) * type.buildTime());
    }

Here unit is the building and type is equal to unit->getType().

As the code comments point out, there are ways for it to go wrong. It doesn’t work on a terran building if the constructing SCV has wandered off to play pinochle. It doesn’t work on a zerg morphed building, like a sunken colony morphed from a creep colony or a lair morphed from a hatchery, only on a zerg building made from a drone. If you shoot at the building and hurt it, you’ll get a wrong answer. If the HP have already reached 100% and the building is in its extra latency period, then there’s not enough information to know. I think all those issues can be corrected for if you make the effort, but I didn’t today.

Did I miss anything else? My short time was not enough for many tests.

Using the building completion times for enemy static defense will help the combat simulator avoid mistakes. And the times of tech buildings will help decipher the enemy build order.

You’ve located an enemy refinery building and you want to know whether your ground units can walk there to attack it. Is it on ground that they can reach, or on an island? For other buildings, Steamhammer solves the reachability problem with a partition map: Areas reachable by ground from each other are in the same partition, and 2 simple lookups tell it whether one point is reachable from another.

Refineries are trickier. First of all, a geyser is not walkable ground, so properly speaking it doesn’t belong to any partition. The same for a refinery built on it; every other building is built on ground that can be walked over after the building is destroyed. This actually causes a rare bug in Steamhammer, where the ground squad understands that it cannot attack an island—except for any refinery that may be on the island, it may attempt to attack that! It knows that a refinery building is a special case, but it doesn’t understand the special case correctly.

Of course, the problem can be solved by filling in the partition map for the refinery with the partition that the geyser is in. “Of course”? No, actually it can’t: The geyser itself might be part of the unwalkable terrain between partitions. Imagine a wall on the left and a wall on the right, and a geyser plugging the gap between them. North of the geyser is one partition, south might be a different partition, and there is no way to walk from one to the other. The geyser, and any refinery you build on it, is adjacent to 2 partitions but doesn’t belong to either.

This actually happens in an even more complicated way on maps like Gold Rush and a number of others, where two assimilators form a gate. An assimilator is smaller than a geyser (protoss space warp tech, no doubt), so if you destroy the eggs between the assimilators, units can pass through. But if you destroy the assimilators the gap disappears and the bare geysers block passage. A bot needs sophisticated knowledge of the game to understand the effects.

I haven’t chosen a way to fix it yet. But it’s clear that geysers and refineries have to be treated with special care.