Starcraft AI blog

Today, a post about things I wanted to do and didn’t get to, or started to do and rolled back or didn’t finish. I accomplished a lot, but the to-do list is functionally infinite.

• UAlbertaBot executes unit orders as they are issued during the frame, retaining no state beyond what BWAPI remembers. Steamhammer inherited the system. I am in the process of changing it to record the orders and save status info, then issue any needed orders at the end of the frame. Adding the Micro object in the last version was one step. The Micro object now records the order and status of each of our units, and has all the infrastructure it needs to issue orders, including its own update() method with TimerManager calls to track how long it takes. But it doesn’t actually issue orders; there is no effective change to the micro system.

When this is done, it will be easier or possible to unstick units, to make sure units don’t get stuck in the first place, and in general to control units precisely.

• I worked a bit on analyzing Steamhammer’s use of the combat simulator. Improvements are there for the taking, but my first try was not successful and I left it for later.

• McRave suggested that micro to avoid big damage attacks was key. Equally important is to pull off big damage attacks yourself. Besides plague, the zerg big damage attack is scourge suicide, and Steamhammer sucks with scourge. Scourge control is on my list, but never came to the top.

• I implemented mine dodging to reduce the danger of spider mines, but the way I did it was not useful for zerg. Reacting to mines is tricky: If a mine pops up, sometimes you should drag it to the enemy, sometimes drag it away from your other units, sometimes shoot it down. I lost the “just shoot it” case, and it was a net disadvantage. The feature is in the code but is disabled.

• Steamhammer’s lurker skills were adequate for when they were implemented, but have fallen behind the times. It needs to stop doing things like burrowing one lurker at a time in cannon range.

• I haven’t done anything to improve overlord safety, dark templar reactions, or any of that stuff. Many weaknesses there.

• I planned and promised a skill to put pressure on the enemy in the early or middle game, but did not finish one. I had several ideas, and all of them hinged on what I call raiding: Harassing where possible, moving around but staying near the enemy, not retreating to rejoin the main army. Harassing mutalisks can be considered raiders in that sense, and so can Krasi0’s vultures and Bereaver’s reaver drops. Runby units and dropped units should act as raiders, and Steamhammer doesn’t have the skill—with a Hold order, they go idle if they clear their area to hold, and with an Attack order they may try to retreat to the main base. Picking up dropped units is also a good raiding skill.

• I implemented a Watch squad, but did not polish it up enough that it became useful. It is turned off. It had several purposes. It could keep watch on expansions and chokes, sometimes making it possible to disband the Recon squad. It could prevent enemy expansions in some cases, and clear mines and verify the safety of expansions that we wanted to take.

• I thought of adding pre-learned opponent model data for the fixed opponents carried over from last year, plus opponent model hint configuration (like “try this first and see how it works”) for opponents that I think I know something about. PurpleWave, we’re told, did an elaborate job of that for CIG this year. The idea of hints is that the opponent model can save exploration time if the hints are right, winning more games, and correct itself with little loss if the hints are wrong. I decided that, since AIIDE is a long tournament with plenty of time for learning to converge, other work would probably help more.

upcoming

Done with the testing, today I am resting. I’ll upload zerg-only Steamhammer 2.0 to SSCAIT tomorrow. On the blog side, I think I’ll start with an overall evaluation post, what I’ve done and how successful it seems, and follow up with posts about specifics like defiler skills and squad restructuring, and then the big detailed change list. At some point soon Steamhammer 2.1 will slip in. 2.1 will likely have a few minor fixes and deserve its own little change list.

Shortly, CIG should release its detailed results. They promised source and replays. If they also provide a game result log, I’ll analyze it and post my usual colorful summary tables. Not sure how that will fit in with the other posts, the blog may have a busy time.

Steamhammer 2.0 is submitted for AIIDE 2018. All I have left is the waiting.

Since yesterday I fixed one bug, a newly introduced bug in the worker manager that could cause a small number of drones to temporarily go idle early in the game, when it matters a lot. I made an attempt to fix a lingering weakness related to cooperating with static defense, but had to roll it back. The fix was a 2-line change, but somehow it caused a hard-to-understand bug, and I can’t accept a risk like that so close to submission time. Also, since an entire day is too long to go without working on the openings, I added a new opening that helps Steamhammer sidestep weaknesses in ZvZ, allowing it to beat more opponents. And I ran all the tests I had time for, looking for new bugs, checking my fixes, and verifying that the new opening functions as intended and earns wins.

It’s hard to understand why, but now I feel tired....

New bot DaQin on SSCAIT matches an AIIDE entrant. It may be the AIIDE entry, or it may be a test version shortly before the entry is made. It looks like a Locutus fork. The .dll is larger than the Locutus .dll by about 24K out of 2.5M—a fair amount of code but no drastic rewrite. The play I’ve seen so far looks similar, lots of dragoons with strong Locutus micro, so without digging deeper I’m not sure what the changes are.

As one of my tests today, I ran a short match Steamhammer 2.0 - DaQin. Steamhammer took several games to find a way to win (not long at all), and after that it won every game, though I didn’t play many and one of the games was excitingly close. I didn’t try the old version Steamhammer 1.4.7, but with Locutus skills I expect that DaQin would have won every game. I don’t think Steamhammer 1.4.x has a way to beat DaQin. It was satisfying to see Steamhammer 2.0 score convincingly, and it helped my confidence.

We’ll see how much Locutus has improved since August!

Steamhammer is almost ready for AIIDE. I have fixed all the major bugs and weaknesses that I have time for—the last was a newly-introduced bug in mutalisks caused by tightening up the micro, it was a bad one. The rest will be simple low-risk fixes and testing to make sure I don’t have another disaster like in CIG (it’s a risk, I wrote a bunch of new code and my change log records over 80 items).

Steamhammer is still weaker against some opponents, though not by as wide a margin as in my last update. It still crushes some opponents that it used to lose to. I can’t foresee which way the balance will fall, definitely not in this tournament with so many new names. My ambition remains to finish in the top 3rd, about the same as last year, which will mean that I am keeping up with the blazing fast progress in the scene.

There are changes at all levels. I have the highest hopes for improvements to the opponent model (key for a long tournament), the squad structure (sounder in principle than the old one), and certain of the micro optimizations (not fully exploited yet, but a firmer foundation).

Regardless how well Steamhammer performs in AIIDE, looking back over the past year I feel I’ve gotten a good amount done. Steamhammer is still short on basic skills, but compared to a year ago it is smarter in most ways. There is a mountain left to move, but I am that much closer to having moved it.

Steamhammer 2.0 for AIIDE will be specialized for zerg only. There won’t be stuff for the other races in the config file, and I haven’t tested that terran and protoss work at all. I’ll upload it to SSCAIT shortly after the AIIDE deadline, only turning on a few of the screen drawing options. Since it plays so differently, I’ll erase the learned opponent data again. A few days after that, depending on how wiped out I feel and whether any surprises turn up, expect Steamhammer 2.1 and its identical twin Randomhammer that plays all races. Along with, of course, a series of posts about the details of my work, the unexpected problems that cropped up, and the known problems that I would have solved if only there were more time.

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.

One of the goals of BWAPI is information fairness: Don’t provide information to a bot that a human player in the same situation would not have. It makes a serious attempt. BWAPI won’t tell you about an enemy unit that you do not have sight of. But it also leaks information through many channels. BWAPI is an unofficial add-on, and the game was not designed to include a programmatic interface. I think it’s difficult to design an interface that provides everything necessary and nothing extra.

Here are some of the leaks that stand out to me.

• Screen visibility. A human player sees what is in the minimap plus what is visible on the screen, which shows only a small part of the whole map. A bot does not look through a peephole, but sees everything visible at once. It makes bots easier to code, so it is a correct tradeoff for early days.

• Cloaked units. A bot cannot overlook the presence of a cloaked unit in its vision. By design, humans can easily miss seeing the blur, either by not putting the screen over it or by missing the subtle visual cue—even pros sometimes lose all their workers at a base before realizing that a dark templar has sneaked in. I don’t know how to implement this in a way that is 100% equal between humans and bots, because bots do not have the complicated perceptual apparatus. But something could be rigged up to make it approximately fair.

The same goes for other events that are easy to miss: Nuke targets marked by a tiny red dot, scans marked by an conspicuous but fleeting swirl of sparkles.

• Unit IDs. BWAPI labels enemy units so you can tell them apart. A human player sees a mass of zerglings, a bot sees a mass of zerglings each of which has a name. A human may be able to distinguish units in certain cases, by hit points or because the unit shows a visible effect like ensnare, but in general, one unit of a given type looks like any other. A non-leaking design would give fixed IDs to your own units, and for the enemy provide a bag of units distinguishable only by their properties, with temporary IDs and/or unit pointers that remain usable only while the unit remains in view. The change would add complexity.

In practice, bots use the extra information to draw inferences that a human player cannot draw. “I saw these units standing guard over that entrance—now I see them here. They are no longer guarding the entrance.” A human player might guess that, the bot knows for sure.

• Unit orders and targets. Mutalisks sweep in and notice an SCV scurrying across the terran base. Where is the SCV going? Will it construct or repair, or is it only moving? A human player has to see the SCV start to build or start to repair to be sure; a bot knows the SCV’s orders immediately. Steamhammer (like many others, no doubt) exploits the information to target SCVs that have important tasks.

When a unit wanders past in the middle of the map, a human will guess (or at least wonder) where it may be going. A bot knows where it has been ordered to go—though that may not be its ultimate destination. In a fight, a human can judge which enemy unit is targeting which friendly unit when the enemy fires, or sometimes as the enemy prepares to fire. A bot knows as soon as the order is given, or as soon as the enemy comes into sight range.

Lesson for bot authors: Tell your units to move to their destinations before handing down their orders about what to do there. You give away less information to enemy bots. Also, make long distance moves with intermediate waypoints, so that the enemy doesn’t know your ultimate destination (though mineral walking has to be an exception). Alternately, you can actively deceive the enemy by ordering a destination where the initial path is the same as the path you want, then changing the destination after that.

Information fairness is of course only one form of fairness. A computer with a programmatic connection to a computer game enjoys direct perception that humans can never match; it is intrinsically unfair in other ways too. You can get perfect fairness of a certain kind if the computer has to use a camera and robot hands, interacting with the game as intended by the game designers. But that’s no scene for students and hobbyists. I think that BWAPI is a good compromise for now between being fair and making bot coding easy. As bots become stronger, the fairness issues will loom larger—and bots are getting stronger fast. We ought to be thinking about it.

Do you have a favorite information leak that I didn’t mention?

Suppose you want to place static defense, or immobile defense like sieged tanks or burrowed lurkers, to guard your natural. Or maybe you want to place spider mines, or other scout units, in a picket line to spot movement. Where should you put your stuff? Well, it depends on the terrain and on what you are guarding against. To protect against ground attacks on the natural base, you normally want defenses which cover the choke. Many bots do it directly: Here is the base, there is the choke, set defenses in between.

In the general case, you want to analyze the paths your opponent must take, or is likely to take. If you can place defenses to cover every approach (out to beyond the enemy’s range of fire), then an attack must engage the defenses before it can reach the defended place—stand and fight, or siege them down from range, or run by while taking damage, no matter what there will be shooting.

This is true even against air units. If a pro terran suspects a drop early in the game, they may build 2 turrets widely spaced across the main (leaving most of the army in the natural for all contingencies). The turrets don’t close down every path, and the drop can still happen, but they make life difficult for the shuttle. The drop might come in at any angle and protoss may try to be tricky, but protoss has to find the turrets and either try to thread through (risky) or stop to take one out (slow). Bots are not sharp enough at defense to get by with so few turrets, but can still obey the principle that follows from path analysis: To defend against a drop with a small number of transports, widely spaced turrets do the most to limit the enemy freedom of action.

Compare late game defense against arbiter recall. The arbiter cannot come in at just any angle—there’s a big terran army in position to catch it! And at this stage in the game terran has the minerals to afford fences of turrets across any vulnerable approaches to a mineral line—covering the direct paths. In addition, depending on the terrain, many terrans will build turrets right up against the edge of the map to guard against the arbiter sliding in along the edge where the army won’t see it. That is an example of covering the likely path.

Path analysis can also tell where it may make sense to place pylon walls. I would love to be able to automatically discover the possibility of pylon walls to protect the mineral line at the mineral only bases on Circuit Breaker. Pylons there between the nexus and cliff can keep vultures far enough away that the probes can evade some of their fire.

The advantage of path analysis over choke analysis is that it is more general. It automatically covers all cases. You don’t need special case code to figure out how to defend your natural on Moon Glaive, which has 2 entrances, or to defend a mineral only on Python, which is not behind a choke at all. You don’t have to calculate separately whether a photon cannon’s range is enough to cover a wide choke, or leaves a path open; the analysis tells you. If there is a backdoor entrance, you don’t have to go looking for it, a thorough path analysis will remind you. But how do you do the analysis?

shortest path method

Steamhammer inherited distance maps from UAlbertaBot (originally DistanceMap, more recently renamed GridDistances). UAlbertaBot may have borrowed the idea from Skynet—nothing new here, and I’m sure many bots use this idea. Anyway, the algorithm is trivial: Specify a tile as the start, and give it distance 0. Tiles adjacent to 0 get distance 1, tiles adjacent to 1 (and not already marked) get distance 2, and so on. If you only mark walkable tiles, then you get something reasonably close to a map saying how far away everything is by ground from the start tile.

You can use the distance map to effortlessly find shortest ground paths either to or from the start tile. It’s efficient if you find many paths to or from a specific place (such as a base you want to defend or attack). In fact, it’s more general: In principle, you can specify any subset of tiles as start tiles, even tiles that are far away from each other. Specify the set of tiles where your workers are, and you find shortest paths to any part of your mineral line, for example. You can also use tricks like adding fake extra distance to tiles which are under fire, to route around dangerous places as much as possible.

If you’re only worried about shortest paths, there’s an easy algorithm to find the set of all tiles that are on a shortest path to a given place, your origin (which might be a tile or an area). First, make a distance map starting from the origin. Then pick a point outside—say, the center of the map if it’s reachable—and look up its distance. Let’s pretend it’s 100. Mark all tiles that have distance 100, or perhaps all tiles with distance 100 which are not in a base you control (since the enemy won’t start out from there). Then walk inward along the distance map: Mark all adjacent tiles with distance 99, then 98, and so on. When you’re done, you know all the tiles that are on a shortest path from anywhere at distance 100 to your origin.

The analysis only includes shortest paths, but it is thorough. It counts shortest paths in every direction, including through back doors.

region and choke method

BWTA and BWEM both calculate chokes and regions, creating a graph of the overall map structure. BWEM does pathfinding on this graph, rather than directly on the map, and if you use BWTA it’s easy enough to implement something similar yourself. You can enumerate high-level paths through the graph, then work out low-level path details inside each region using the distance map method above (make distance maps from each choke).

random method

Instead of calculating all short paths, you might prefer to take a random sample from a larger set of paths. Start with a random point outside (not in a base you control), and create a path using a distance map toward your origin—but don’t always choose a direction that decreases the distance. If the distance decreases on average, the path will eventually lead to the origin. You can also generate random paths with the region and choke method.

To make sure the random paths are diverse enough, you could use a multi-scale method. Start with a coarse path whose steps are far apart. It can be done directly using a distance map; pick random angles and find the tile in that direction at a given Euclidean distance (of, say, a randomly chosen 10 plus or minus 5 tiles), and accept it if it has a ground distance that is not too great (this choice can be random too). Once you have a coarse path, you can fill in the detailed path between the coarse path tiles using the same distance map.