Starcraft AI blog

Melee unit A is chasing enemy unit B. If they move at the same speed, when can A catch B? In principle, the answer is: When B reaches an edge and has to turn aside, allowing A to gain ground by taking a shorter path. An SCV B running loops around your base can be caught by a slow zergling A moving at the same speed if the zergling follows an inside track. If B is running across the map to safety among its friends, then as long as B takes the shortest path, A cannot catch up before B reaches its friends.

In practice, Stone’s SCV A can often catch a fleeing SCV B before B turns aside at an edge. And Steamhammer’s zerglings A can often catch Stone’s fleeing SCV B. And the same for many other bots, substituting other units A and B. The chasing unit A is using unit movement prediction to smooth its path, and is following a shorter path than the fleeing unit B. Starcraft’s native paths are not shortest paths (partly because units are often delayed near choke points or when passing an obstacle).

Does any bot implement good quality shortest paths for moving units B? It seems like a valuable skill. I don’t know of one, but I haven’t read most of the huge masses of code....

The good news is that I have definitely made enough changes to Steamhammer that the next release deserves to be called Steamhammer 2.0. In some situations it plays much more strongly. The bad news is that I still haven’t fixed all the bugs introduced in making such extensive changes. Changing the squad structure, which has little direct effect on unit control, had surprising indirect effects on the micro of different units—and I also made changes to micro itself. There are situations where it plays much worse, and some are difficult to debug. I may have bitten off more than I can chew.

The effect is big: Some formerly difficult opponents are easy, some formerly beatable opponents are difficult. With all the new names in the AIIDE entrant list, it’s impossible to guess whether Steamhammer will face opponents it finds easy or difficult.

Steamhammer also has new skills like defiler use, a new layer of micro infrastructure, more smarts in the opponent model (time-consuming to test), improvements to the strategy boss, and a bunch of new, fixed, or retuned openings. And stuff. Special preparations against Steamhammer might backfire.

Well, regardless of how well Steamhammer performs in AIIDE, I feel that I’ve made progress that I can believe in. The new squad structure is more complex so it allows more ways to go wrong, but it fixes fundamental weakesses that are inherent to the legacy design and it does not create new fundamental weaknesses. What I mean is that, in principle and if polished enough, it could be superior in many situations and worse in none. It’s not that polished yet....

Anyway, there is still over a week left. I have other things to do too, but I should be able to make fixes. Outlook: Moderately good.

Simplicity has been getting updates, and an update yesterday was apparently when it gained overlord drop skills. (There’s another update today.) It is the first zerg bot that I have seen use drops (well, in public at least). The drops look a bit stereotyped, with about 8 overlords loaded up in the main and sent (usually along the edge of the map) toward an enemy mineral line—it looks as though the drop happens when the overlords find targets to drop on. That makes Simplicity the first bot I have seen do mass drops, a unique skill.

I found 3 drop games on SSCAIT. Curiously, all 3 games are on Moon Glaive, although Simplicity does research drop on other maps. The less impressive games are Simplicity-Juno aka Yuanheng Zhu and Simplicity-NiteKat terran. Drops definitely did not change the outcome of those games. The best drop game is Simplicity-WillBot, in which WillBot randomed to terran.

The first drop started to load up at the zerg main just before 16:00 into the game—while a terran attack on the natural was underway, not the most auspicious time. Apparently Simplicity does not put much analysis into the drop decision. In the picture, the two players are roughly even (objectively, with no defilers in sight, the big terran army should win, but neither bot has the skills). The selected overlords are exactly those that are loading units. In the minimap, notice the long tail of terran units moving toward the zerg natural; the terran attack was kind of piecemeal.

Loading proceeded slowly, I guess since the ground units were distracted by the terran activity, and the overlords set out at about 16:40. The overlords proceeded counterclockwise around the edge of the map toward the terran main. Meanwhile, terran diverted to annihilate the zerg base at 9 o’clock before returning its attention to the zerg natural, and zerg units that were still on the ground bypassed the marines and tanks and headed for the terran natural to counter. Simplicity’s decision was good. Attacking the terran bases from both sides put WillBot into a difficult situation where it was tough to make the right choices.

The drop started to land at about 17:40. WillBot defended the ground maneuvers poorly; it left tanks forward to pressure the zerg, and lost them to zerglings, and sent marines back to defend, where they ran full tilt into burrowed lurkers. In the picture, notice that both sides have lost workers and WillBot has already fallen behind before the drop happened. The white dots in the terran natural are lurkers which are in range of the command center.

WillBot did finally clear the attack, but was far behind. Simplicity made 2 follow-up drops to finish off the terran main.

All in all, the mass drop skill could use improvement—but you could say that about almost any skill of any player. In Steamhammer, I have held off on zerg drop because I think it requires tactical analysis that the bot can’t do yet. In this game we see that mass drop can be a scary ability even with little tactical calculation behind it.

Zerg overlords are both an advantage and a weakness. That makes them complicated. In each situation, where do you send your overlords, and by what path?

Take early game scouting, when you are trying to find the enemy and see what they are up to. One of the most important things to see is whether they have started the natural already. On many competition maps, there is a single most efficient overlord scouting path from each base: The path where the enemy natural is between you and the enemy main, so you can see the natural first and continue to the main without loss of time. Most human zerg players, most of the time, scout like that.

But if there is only one path, it is predictable and can be exploited. The enemy can check whether you are at a specific base by sending a worker to intercept the overlord’s path—the overlord will spot the worker in turn, but that gives away no information. A pro will most often intercept at the midpoint between bases, to spot an overlord going either direction.

In ZvT, the overlord also wants to stay safe against marines. Overlord paths that may meet marines have to be evaluated for safety. “Unless the terran went 8 rax, I should be able to poke in this far to look and still make it back to the cliff alive.”

So sometimes zerg scouts differently. The overlord might go diagonally, which is good for noticing a center proxy but reaches the target base later. It might take a jog to avoid being caught in particular places, or to spend more time over cliffs. Occasionally the first 2 overlords follow complicated paths to seek out specific points of interest and give away as little as possible—this happens more often when zerg is following a tricky strategy and has to look out for different risks than usual.

Current bots commonly send the scouting overlord in a straight line, which means that intercepting the overlord could be an efficient scouting strategy in some cases. (Others don’t scout with an overlord at all, or only look around their own base.) I believe that current bots are also unable to recognize what information the enemy is exploiting, so having their overlords intercepted won’t tell them that they might benefit from being trickier... which is OK so far, because they don’t know how to be trickier. It seems like a difficult skill.

As the game goes on, overlord use gets harder. In ZvT, zerg usually wants to start placing overlords where they are safe from marines but can glimpse movements. They are usually set floating over cliffs or unwalkable terrain and near choke points the enemy may pass, especially the natural chokes of the 2 players. Typically, after a new overlord spawns, you direct it toward a nearby overwatch point, and any overlord already at the point gets orders to move on to a more distant point. By the time terran might have dropships, there should be enough overlords to start watching drop paths too.

Finding good overwatch points by map analysis is not too hard. Finding good paths to reach them is an adversary planning problem under uncertainty, and can probably be solved well enough by a search using estimated risks. Deciding which overlord should go where (“this one replaces that one, which moves to replace the other one, which moves to that dead space”) is another planning problem. That’s 3 problems to solve just to move scouting overlords in the early midgame in one matchup!

Then you also have to arrange overlords for detection and drops. For example, if you want to bust protoss cannons, protoss may try to defend with dark templar, even sacrificing corsairs to clear zerg detection. To do it right, you have to pre-position overlords close enough. How you move overlords depends on your game plan.

Overlord use is awesomely complex, and it’s only a small part of the whole game. It might be possible to implement by hand all the skills needed to play Starcraft well—but if so, you will need a large team. I’m agreeing more and more with Arrak’s comment yesterday, “put in some brains!”—whether the brains are machine learning, or search, or only nice problem descriptions and a constraint solver.

Steamhammer still has occasional devastating bugs in its reactions. Steamhammer-Sungguk Cha is an example. Sungguk Cha is an opponent Steamhammer usually has little trouble against. In this game, zerg played a not-very-appropriate lurker rush and handily held the initial marines. The zerg economy was weak, but the tech was there to cope with the next phase of vultures and wraiths, and zerg was in position to fight on. Instead Steamhammer fell into a loop, spawning zergling-overlord-zergling-overlord etc. With massive oversupply of overlords, a broken unit mix, and money piling up with no second hatchery in sight, only terran was in the game.

There are actually 2 bugs. The main bug is that an emergency reaction (“Oh no I have no army hurry hurry spawn stuff”) didn’t recognize that it had already occurred and fired repeatedly, dumping the long sequence of zergling-overlord into the queue. There are checks to prevent that sort of thing, and I haven’t spotted the mistake yet. If I don’t find it soon I’ll let it go until after the AIIDE deadline, because there are more urgent fixes to make.

As often happens, the primary bug triggered a secondary bug—bugs tend to cause unusual conditions, and unusual conditions tend to bring out more bugs. After a few extra overlords, any further overlords should have been recognized as excess and dropped—the idea is to drop planned overlords that are no longer needed after the army is destroyed in battle. That bug I have fixed. The issue is that Steamhammer was still technically in its opening book, though it was nearly at the end of the opening line. The opening book sometimes deliberately makes extra overlords (to save up larvas and produce mutalisks or lurkers in number all at once), so the check was turned off in that case. It was easy enough to add back a check that is loose enough that it doesn’t break openings.

As Willy Wonka said, so much time and so little to do. That must be why I haven’t posted in a week.

The development Steamhammer version still makes many facepalm-level mistakes—the guardians press forward into enemy corsairs while the devourers run away, that level. Even so, testing today shows that its tactical play has improved so much that it can win long difficult macro games against opponents that used to smash it every time in those games. The old blunders where Steamhammer might at any moment throw away its army by suddenly retreating through the enemy, or the like—those blunders are completely gone. In restructuring squads I introduced an all-new stockpile of different mistakes, and those mistakes I have cleaned up enough that they are minor by comparison. Defense squads especially needed a lot of attention.

Since late last year, Steamhammer has been able to play with strong macro. It has finally gained the ability to use the large number of units it can make without wasting too many. It can freely enter into situations that formerly I tuned its openings to avoid. The work took a tremendous amount of time, but the time was well spent.

I still have stuff to fix and features to add, and the time is wearing on. In AIIDE, I hope that Steamhammer can keep up with the field and finish about as high as it did last year. Progress has been blistering, and if I can keep up with it then I feel I’m doing great.

Today, trying to track down a mysterious regression, I noticed this condition in an if in CombatCommander::getAttackOrder():

enemy.type == enemy.type == BWAPI::UnitTypes::Protoss_High_Templar

Hmm, it looks a little different than I intended. == is left-associative, so this always evaluates to true. The effect is that Steamhammer might make a poor decision of which enemy base to attack. The decision is pretty rough anyway, though, so the buggy decision is not much worse.

Gotta love edit slip bugs, they are so creative. In this case, the original intention is also wrong, because high templar are excluded by an earlier check—the condition would have always been false.

If only I could find the bugs that matter, instead of the bugs that don’t hurt much....

One of the earliest improvements I made for the upcoming Steamhammer 2.0 for AIIDE was superior zergling micro. In an equal fight, zerglings on zerglings, Steamhammer tended to come out ahead of Killerbot more often than behind. Now, after many other changes, I have somehow broken it, and Steamhammer loses equal fights. I tried undoing all the changes that seem as though they could be related, but no go. I don’t know what I have done wrong. It’s amazing how fragile some skills are.

Weaknesses are stubborn. The first wipe doesn’t clear away the dirt, you have to scrub repeatedly. I made changes to improve kiting, and hydralisk play is noticeably sharper. But mutalisk micro is worse, because the changes caused seemingly unrelated code to misbehave. I think it will be easy to fix, but what weaknesses did I introduce without noticing?

In another example. I have been systematically working through Steamhammer’s openings to fix faults that have crept in because of other changes: Queue reordering, queue jam clearing rules, mineral locking, and so on. Most openings are OK, but a surprising number need minor adjustments. I also found a subtle one-frame-late timing bug in the interaction between the building manager and the strategy boss that broke a single rarely-played opening. Everything is connected.

Strong interdependence seems to characterize Starcraft skills. When you change one point, it doesn’t matter if it’s a big improvement, you have to also align other points to realize the improvement. As Dan Gant expressed it, a bot is usually at a local maximum in skill. When you nudge it in any direction, it is no longer at a maximum, and you have to hunt around for a new local peak, which you hope is higher.

It makes progress bumpy. On the one hand, that drives me to machine learning: I don’t want to get all these details right by hand! It’s too much! On the other hand, it poses tough problems for machine learning algorithms, too, whether learning holistically or piecemeal. Such a complex and difficult fitness landscape is hard to optimize over, whether by hand or by machine.

After zerg Pineapple Cactus and terran Toothpick Cactus, protoss Prism Cactus is the latest in the cactus family. (Pineapple Cactus is the odd one out, since its name doesn’t match its race. Maybe the author will reimplement it as, say, Zig-zag Cactus?) Looking into the binaries, I get the impression that the same binary can play all 3 races (although the binaries are in fact not identical between Toothpick and Cactus, and Pineapple is a DLL.) For one thing, I see all 3 bot names in the binary, with the names of build orders for each race, and for another I see the name Rainbow Cactus, which sounds like it might be a random player. It’s weak evidence, though, especially since the protoss build order names don’t seem to correspond to how Prism Cactus actually plays.

Prism Cactus is performing a bit above average, similarly to Toothpick Cactus. The older Pineapple is a bit below average.

Carrying on the cactus tradition, Prism Cactus has a lot of nice skills, though it is not as polished as a top bot. It can use shuttle and reaver, and it gets psionic storm early and deploys it fairly well. It likes dark templar and it understands the enemy’s static detection range, so it doesn’t waste its DTs fighting next to a turret (curiously, the skill doesn’t seem to extend to shuttles versus static defense). It can make corsairs versus zerg. In the late game it adds carriers.

I have seen Prism Cactus play various build orders (which don’t correspond to the 3 protoss build order names I see in the binary). Its favorite is a tech build which branches: It either makes dark templar, or it researches dragoon range, or it gets zealot leg speed. It also knows a 14 nexus build, and a forge-expand build that I assume is for use against zerg and random opponents (the cannon timing is not rush-safe, though). I saw it open with 2 gates before core once, but that may be a reaction because its mining was disrupted. When playing the same opponent repeatedly, it switches build order after a loss, and I have seen it keep the same build after a win (there aren’t many games to go on), suggesting that it may use a bandit algorithm like many bots. Once the opening has played out, the rest of the game seems to follow a predictable path; it gets a shuttle and reavers, it gets high templar with storm, it expands. Apparently it doesn’t have any great strategic variety in the middle game, and it doesn’t research or upgrade much. But it can defeat weaker opponents by gradually out-expanding them.

Prism Cactus also has grave macro weaknesses. It gets supply blocked often. As it transitions out of the opening, it stays on 2 gateways too long, and is unable to spend all its minerals. It commonly goes over 1500 minerals before it expands and adds more gateways. Later in the game, with 2 bases and 5 or 6 gateways and gas-heavy production in its tech build, the mineral excess builds up again. Fixing the macro weaknesses would give the bot more punch. It would benefit from some combination of faster expansions, defensive cannons when useful, more gateways, fewer gas-intensive units, and masses of zealots (especially after zealot legs are researched).

Overall, an interesting bot with complex play. There is always more to do!

New terran SummerHomework is a Steamhammer fork, so it’s easier for me to make sense of. The author is named in the configuration file as FuZhouL. It is still moving fast; the latest upload was 3 September, and this version has roughly twice as much new code over Steamhammer as the previous upload, going by the binary sizes.

SummerHomework adds terran skills over Steamhammer. To me, the most obvious new skills are spider mines, wraith cloak, and improved building placement. There are also changes in unit mix, tactics, and combat, though it’s harder to parse out what they are. I see mentions of Locutus in the configuration; SummerHomework has at least been tested with Locutus. Besides new skills, SummerHomework adds new bugs. I noticed bugs in the openings, building addons, building placement (the defensive bunker on Heartbreak Ridge can trap units in the base), and supply when the bot is near maxed. (Maybe some of the bugs were already in Steamhammer, and SummerHomework tickles them.) Perhaps the author is a less-experienced programmer who is struggling with the complexity—no shame in that, it is in fact highly complex. (CasiaBot from last year introduced worse bugs, and yet scored over 50% in CIG 2017.)

SummerHomework seems to play more cautiously than Steamhammer. It likes to make an early bunker and build up a substantial force before moving out in strength. In general terms, that is probably correct for a terran bot; Steamhammer plays all races with zerg aggression, and it is not always appropriate. SummerHomework, with wraith cloaking skills, also likes terran air units. It often builds many wraiths even against protoss, and later in the game adds battlecruisers.

Overall, SummerHomework is not playing strongly so far, but it looks like work is moving fast.

Next: New bot Prism Cactus.

In comments to the previous post, lIllIIlIlIlIIlIIl pointed out that unit IDs are assigned sequentially and the sequence is shared by both players, so that each player’s sequence of unit IDs conveys information about the other player’s production. In other words, bots can cheat by looking at their own unit IDs to learn without scouting what the opponent is doing. If a bot makes 2 units one after the other, it can tell how many units the opponent produced in between by simply subtracting the unit IDs.

I tried it myself, and it’s true. It is trivial for a cheater bot which is steadily producing workers at the beginning of the game to recognize that an enemy zerg is going 4 pool or 5 pool. More complicated builds are more difficult to recognize, and the information you get depends on your own build too (for example, if you’re saving up for a new base, you don’t get new information via this cheat until you start the base). But even there, I think it’s not too hard to usually tell the difference between 9 pool and 12 hatch and other early build orders. Later in the game, you could use the cheat to recognize when the opponent is supply blocked, or when the opponent is maxed, and judge whether the opponent is making many cheap units (marines, zerglings) or fewer expensive units (tanks, mutalisks). The cheat seems to have many uses.

Also, it seems possible to use this cheat with little risk of being caught. To avoid being caught by behavior, don’t accurately react to unscouted zergling rushes too often. I think most other behaviors that the cheat enables will be difficult for observers to detect. To avoid being caught by code inspection (in a tournament that publishes code), use some code obfuscation—stash IDs with other stuff in a data structure, so that it’s not obvious what information the computation is operating on. A machine learning algorithm would make an excellent code obfuscator: Simply feed it unit IDs along with everything else, and a good enough learning algorithm will learn on its own how to cheat without giving any clues away. Machine learning data can be extremely difficult to interpret.

It is a terrible exploit. I have opened an issue at the BWAPI repo.

How the hell are we going to catch people who abuse this? If it is fixed in a future BWAPI release, it will still take time before we can require that new bots use the new BWAPI—especially if there are other incompatible changes.

Maybe the answer is to make 4.1.3 and 4.2.1 releases which are compatible with the current 4.1.2 and 4.2.0 releases, with the only change being that IDs are randomized or otherwise mixed up. Then it might be possible to deprecate 4.1.2 and 4.2.0. If BWAPI allocated unit IDs in blocks (of 100, say) and randomized the order in which they were assigned within each block, then even a bot which used the IDs as an array index would continue to work.

Update: Besides randomizing unit IDs, there is another solution: Partition the space of IDs so that each player that creates units is assigned IDs from a different partition. For example, if there are 2 players (me and you, since the neutral player doesn’t create units after the game is underway), assign even IDs to my units and odd IDs to your units. That might still allow unit counting exploits (“you have a unit with this ID, so you made at least x many units”), but at least you have to see the enemy units first.

Next: New bots SummerHomework and Prism Cactus.