Starcraft AI blog

Some bots are so single-minded that they never make air defense of any kind, no hydralisks or spore colonies but only zerglings, no cannons or dragoons but only zealots. Black Crow is a zerg example, and protoss Carsten Nielsen has the same mindset. Theoretically a terran might make only vultures and tanks, though I can’t think of one that doesn’t also make marines or turrets.

Strong bots can cope, of course. But for a lower ranked bot, such an aggressive enemy strategy can be tough to survive. It calls for solid skills that take time to develop. If you prefer a different route, then instead of countering with skill, it’s possible to counter with strategy. Here is a trick counter-strategy for terran:

1. Make a wraith. Well, make as many as you can afford, but 1 should be enough to win. The enemy cannot shoot up, so your wraith is immortal.

2. Lift off any building. Your floating building is immortal, so you cannot lose by having all your buildings destroyed. If you like, you can wait until the building comes under attack.

3. It is still possible to lose on points if you do not finish off the enemy in time, so there is one more step: Use your wraith effectively. Kill overlords and workers to prevent the opponent from constructing buildings faster than you can destroy them. Then slowly take out buildings one at a time. Don’t waste a moment shooting at zerglings or zealots. You don’t need to defend yourself, because you are immortal.

The plan does not automatically work against fast rushes, because you may not get far enough to make a wraith. Possible advanced skill: If you finish the starport but can’t finish a wraith in time, you may be able to lift off the starport and float it to a location that the enemy can’t reach or won’t easily find. And of course you have to decide which opponents to try it against; that might be the hardest part for a low-level bot (and it’s not hard).

Protoss or zerg can play a similar plan on many maps, though it is slower and requires more skills, including analysis of the map. For protoss, make a stargate and a scout as your immortal air unit. To avoid losing, get a robotics facility and shuttle, carry a probe to some place which is buildable and inaccessible by ground—an island or plateau—and make a pylon there. For zerg, you can slow drop a drone on an island base if one is available, and make an extractor, or save up money if the map has an inaccessible space big enough for a hatchery.

One of my ambitions is for Steamhammer to eventually invent this strategy on its own. Steamhammer doesn’t need to be able to reason out that the plan cannot lose; it is enough to recognize the enemy’s habits and come up with logical counters. Step 2 is, “uh oh, the command center is under attack by zerglings, I have to lift it.” Step 1 is not much harder, “here are the units this opponent has made in the past, and based on this history, I could go air.” It doesn’t have to notice that the enemy never gets anti-air, only that going air is a good choice. Step 3 seems to be the hard part.

I’m thinking about unit tracking, and the many many issues it is connected with.

Steamhammer keeps a UnitData data structure to remember enemy units when they are out of sight. It’s only modestly modified from the one inherited from UAlbertaBot. The information manager keeps the information updated for both enemy and friendly units. But should it keep data on friendly units? On the one hand, it might be convenient to have a fixed format for all uses. And Steamhammer does use UnitData for friendly units in certain cases. On the other, it’s duplicating information that is already available directly through BWAPI. What’s the right design?

Many bots place a wrapper around BWAPI::Unit to keep their extra information. It seems like a good design, but I’ve been reluctant to switch to it, partly because there was no need for the extra work, and partly because I don’t understand all the ramifications. Now I’m thinking of doing the work anyway, and when do I ever understand all the ramifications? Well, I don’t need to decide yet.

Then there is the issue of inferred information. If I see a vulture, I know there is a factory, even if I’ve never seen the factory. It’s a known enemy building with almost no other information available; its location might be anywhere that I haven’t seen in the time it takes to build a factory and a vulture. If I see a tank, I know there is a factory with addon. If I see a dark templar, or if I see fast zealots, I know there is a citadel of Adun. I want Steamhammer to be able to draw all these inferences. Even with the current plan recognizer, it would make the recognition rules simpler. In the future, with a more powerful enemy strategy predictor, it will be valuable. I haven’t decided how to store the information. It could be fitted into a unit wrapper.

More inferences: If I see a spider mine, I know there’s a vulture and a machine shop. If I see a broodling, or a parasited neutral unit, I know there’s a queen. If I see something of the enemy’s on an island, or notice that the blocking minerals on an island have been mined out, I know there is transport. There may be an exception for units which were accidentally pushed through unwalkable ground, but that should be exceedingly rare. Also, some cases have an exception for mind control. If I dropped a worker on an island on Python, and it wandered near the edge, it could be mind controlled from a neighboring base, and the enemy could mine out the minerals and take the base without transport.

The idea of inferences with exceptions brings up the issue of estimates and uncertain inferences. As part of understanding the enemy strategy, you want to estimate the enemy’s economy—what count of resources mined so far, what rate of current mining? And the enemy’s production capacity—how many barracks, how many factories, how many starports? Sometimes, especially early in the game, you can get an accurate estimate by seeing the enemy’s army size and comparing it with what is possible. I saw when the first barracks was under construction, and by now it could have trained x marines, but I see x+n marines, so there are 2 barracks or more. More complex estimates are possible, based on income limits. On top of that, you can combine technical estimates made using the rules of the game with learned data (here’s what this enemy has done in the past). Fancy estimates like this do not fit into a simple unit tracking framework, but they interact with it; you have to take into account the intersection.

I’m not off the topic of unit tracking yet. When you get to the level of inferring the enemy’s plans based on all available information, there is one more input you want: A model of what the enemy knows about you. You can’t be sure what the enemy has seen, because the enemy may see you without being spotted in turn. There could be an overlord over that cliff watching, or the enemy units may have a longer sight range (for example, a probe has a longer sight range than an SCV or drone, thanks to protoss high tech). But when the early game enemy worker scout is cruising around your base, there is no problem (beyond technical details of visibility) keeping a unit tracking record of what stuff of yours it saw when. Top bots use their scouting data to get ready for what you are planning, and if you know what they know and can guess what they are getting ready for, you can lay better plans yourself (or try a trick like placing a hydra den in the main and a spire in a far corner of the natural).

These things will matter as I make progress on Steamhammer’s strategy adaptation, so I should start getting my ideas in order now.

In Martin Rooijacker’s post on the end of the rushbots: rushes and how to defeat them, the suggested plans to defeat a cannon rush are perfunctory, only enough to get started with. In my earlier post cannon like Nal_rA I suggested other ideas, but also did not go into full detail.

Cannon rushes have become more important in bot play. Jakub Trancik builds cannons in unpredictable places (usually easily visible places, though). Juno by Yuanheng Zhu tries to cannon contain and push in; it wants to contain as close as possible, but is willing to back off and contain the entrance to the natural if it judges that it can’t get closer (though it tends to judge optimistically). AIUR can place cannons in hidden positions to hit the mineral line. And now Krasi0P likes to set up a cannon contain outside the natural and then cannon push in as far as it can, plus it has a dangerous followup game plan. And those aren’t all the possibilities! So here are more ideas on how to react. I plan to implement all of these in Steamhammer, some soon and some eventually.

categorizing cannon rushes

Placement. Cannons can be placed to restrict your movement. The most restrictive placement is a containment, which might be a containment inside the main preventing you from reaching your exit, a containment outside your exit preventing you from passing your exit, or a containment outside the natural preventing you from reaching the center of the map. Or cannons can be placed to deny access to an area, such as your natural mineral line, without stopping you from leaving your base (consider cannons above the natural on Heartbreak Ridge). Or cannons can be placed to hit critical areas, such as the mineral line, the main resource depot, a key tech building like the spawning pool, or your first production building. The mineral line is a common target, since it does the most immediate harm.

Timing. In the fastest cannon rushes, the first pylon is hidden near the enemy and the forge is built next to it. Current bot rushes are played with the forge in the main and the cannons powered by the second pylon. But cannon attacks can be played at any point in the game. If you leave a base undefended, they can put cannons near it that may double as defense when they take the base for themselves (amateurs try this sometimes). On some maps, cannons on high ground can hit a mineral line on low ground (Heartbreak Ridge is only one example; see the mineral only bases on Python for another).

Followup. Most bots will keep making cannons, trying to push in as far as they can. Objectively, once there are enough cannons to give the enemy pause (maybe 4, depending on what you’re aiming for), it’s often better to make gateways and zealots instead; the zealots and cannons defend each other, and the zealots can exploit opportunities to attack. (Presumably bots don’t switch to offense until late because it’s complicated, but it’s only a matter of time before somebody implements it well). If the cannon rush holds the other side in check, then the rusher can expand and/or tech freely and get ahead in any way it chooses.

Goal. Most bots play all-in cannon rushes to win outright (because they know bot opponents will often fall over). Most humans play pressure cannon rushes to set the enemy back so they can get ahead (because they expect that opponents will know how to react). Also possible are low-cost harassment cannon rushes to cause distraction and delay (think 1 pylon and 1 cannon in a hard-to-hit location; the cannon can even be canceled before it finishes depending on what happens).

defeating a cannon rush

In defending a cannon rush, you have a series of goals. 1. It’s best if you can prevent cannons from finishing, or at least hit them while they are few and can be defeated efficiently. 2. If the cannons finish, you need to put a brake on it so the situation doesn’t grow worse. Mitigate the threat. 3. Ultimately, you want to restore your freedom of movement or your access to a denied area.

1. Stop the cannons from finishing. If you see a cannon warping in or near your base, you need to react. If you only see a pylon, you should at least check it out in case you need to react, but it is also easy to overreact. On the one hand, if it is a manner pylon or blocking pylon to delay your natural, you react differently than to a cannon rush. On the other hand, nothing stops the enemy from building cannons next to a blocking pylon. (Or a gateway. Or a shield battery for zealots which are about to arrive.)

You can pull workers to stop cannons. To be worth it, the pull needs to be not too far away, to stop at least some cannons, and to not risk too many losses. In principle, a combat simulator can tell you whether cannons can be stopped before they finish. Are any current combat simulators accurate for cannon rushes? I doubt it. This seems easy to do crudely, difficult to do with fine judgment. Another try is to chase the cannon-building probe and make its job risky, but it’ll be hard to catch.

You also want combat units as early as possible. Start a barracks, gateway, or spawning pool. Cancel stuff if you have to. Pulling workers cuts your income and can delay combat units. Again, rules of thumb will help, excellent decisions are hard.

2. Mitigate the threat. First of all, if the cannons are in containment position, do your level best to get a worker outside before the containment is complete. If you have a scout worker already outside, it should first locate the enemy, which should be safe because there will be no gateway in the enemy main. Then keep the worker alive and hide it. If the containment is complete, you can still try to get a worker out with a diversionary attack: Send a few workers past and at the same time try to kill cannons; one or the other may succeed. If you’re zerg, the escaped drone wants to someday turn into a hatchery. If you’re terran or protoss, it might build anything. You may want a base to replace one that was denied by cannons, or production to go attack the enemy main that will be underdefended because of all the spending on cannons elsewhere. Escaping a worker is less important if you’re terran, first because terran can clear the cannons with a tank, second because terran can lift buildings to the outside.

If the cannons threaten to push closer, you may have to stop them. Zerg can commonly stop encroachment by building 1 sunken as close to the cannons as possible while out of range. Only make more than 1 if absolutely necessary. Protoss may want to add 1 cannon for the same reason, but the forge is an extra expense so it’s not as appealing. Terran needs a tank. An unsieged tank can prevent new cannons from warping in ever closer (it does need micro), and of course once siege finishes the cannons become fodder.

If the cannons deny something vital, you have to replace it. If you can’t mine enough because your main mineral line is under attack, expand. If a critical building is under attack, you may want to start a replacement before it dies. Terran should lift buildings that need to be saved or that can’t be used where they are (e.g. marines spawn in cannon range).

Those are the overall reactions. You have to get micro reactions right too. Don’t try to mine a mineral patch that is in cannon range; do mine any patches that are out of range. Don’t try to build a building, or land a floating building, in cannon range.

3. Restore your freedom. Don’t throw units away against the cannons; build up until you can take them out. This is the most basic thing, and yet most bots do it wrong, including Steamhammer. Terran only needs a tank and siege mode. Protoss wants dragoons, and if the number of cannons is huge, a reaver. Zerg prefers hydralisks. Ideally, attack containing cannons from both sides at once, including forces you’ve built up outside the containment. (Though as mentioned, the outside forces might want to hit the enemy main first.)

If you’re surviving well enough but you can’t afford to break the cannons (there are too many or the enemy reinforced them with an army), bypass them. Protoss should make a robo and shuttle. Zerg can go air or drop, depending on the situation—drop may be needed if you never got a drone out.

Steamhammer already has reactions to pull drones and to get an early pool (canceling stuff if necessary). It needs defensive fixes to prevent throwing away zerglings when the cannons are too strong. On my list for soon-ish are the encroachment-stopping sunken when needed, escaping a drone to make a hidden base, and mining and building only where safe. With those changes, Steamhammer should be resilient in the face of unexpected cannon rushes, at least until the next and stronger wave of cannon rush bots.

Long post, but I’m sure I know more than I remembered to write. What critical points did I forget or not know about?

Update: I reformatted the post and added a couple small bits.

A thought while I work on more bug fixes, like the 4 bugs responsible for this absurdly bad game. (1. The enemy refinery was considered inaccessible by ground and not attacked. 2. The squad tried to take a path down the ramp which is blocked by minerals. 3. A zergling was stuck in a key position at the top of the ramp. 4. Production froze due to an undiagnosed bug which I have never seen before.)

Although an academy has zero gas cost, terran has no reason to build an academy without taking gas first, or at latest around the same time the academy is built. All uses of the academy require gas. (A refinery has half the build time of an academy, but you also have to gather some gas. The rule relies on the fact that you never want to spend that much to get 1 medic or 1 firebat.) Protoss has no reason to build a cybernetics core without taking gas first, for the same reason. These are the only 2 buildings with that property. All other buildings either require gas to be built at all, or if they have zero gas cost, they enable production that also has zero gas cost. For example, an engineering bay, forge, or evolution chamber might be used to get static defense, which costs only minerals. Zerg has no building with this property. (Imbalance!)

If you generate your own build orders automatically, you can use this as a constraint on which build orders are acceptable.

I’ve been watching CherryPi’s AIIDE games. No conclusions yet, but I noticed that CherryPi likes to research burrow (not the first bot to do so) and burrow scouting lings at expansions to watch for the enemy (I think it’s the first to do that). SAIDA appeared unready for the trick. When an SCV showed up, CherryPi did not unburrow the ling, but sent another to prevent the expansion.

SAIDA is holding its position as #1 on SSCAIT, but it is under constant attack from other bots and loses some games. On the one hand, SAIDA has weaknesses against early harassment and timing attacks, especially if the opponent denies scouting. On the other hand, SAIDA appears to have a learning mechanism that recognizes rush timing and figures out a defense. The SAIDA page describes it as “He also catches perfect rush timing by using information he collected.” That’s a vague description, but the behavior does appear to involve learning from experience. MicroDK noted that SAIDA writes data only after it loses; this must be why. For example, BananaBrain tried a dark templar rush and won a series of games, but finally the learning kicked in and SAIDA figured out how to get turrets in time to stop it (SAIDA’s code was not updated). Since then, BananaBrain has mostly lost games, defeating SAIDA only once, in this game where the turret was seconds late.

Other examples include PurpleSpirit winning one game with BBS then being unable to win with it again, and Krasi0 winning with its fast barracks marine cheese with similar results.

In the latest attacks, Locutus won with center gates, making only 2 zealots before switching into dragoons, and Krasi0 added a bunker to its marine cheese to overcome SAIDA’s vulture counter to the marines (SAIDA crashed this game). Will SAIDA learn to defeat these tricks too? I don’t know, let’s find out!

How powerful is this learning mechanism? Surely there must be attacks that it cannot figure out how to forestall—or can’t figure out in reasonable time. If you find 2 winning tricks and switch between them, can it learn to defend against both? If you DT rush once so that it learns to get early turrets, does it get early turrets for the rest of time after you switch back to regular play? The unnecessary turrets give you a small advantage, and at a high level of play, small advantages are big.

Here are some of the weaknesses I see in SAIDA’s play.

• Poor defense against unscouted early attacks, mitigated by the learning mechanism. SAIDA loses more SCVs than it should.
• SAIDA recovers poorly from economic setbacks. It does not replenish lost SCVs as well as it should, and stops expanding after a while. If you gain an early lead, you can win by holding on and waiting for SAIDA to mine out.
• SAIDA is vulnerable to mine drags. It sees no danger in having its spider mines and its forces next to each other. It will even place mines in its mineral line, begging you to blow up its SCVs.
• SAIDA does not know how to build in safe locations. On some maps, like Moon Glaive, parts of the main base are easily sieged from outside. Krasi0 has won games by blasting down factories that are in range, and SAIDA keeps trying to rebuild in places that are also in range.
• SAIDA is consistent and predictable. It varies to counter the opponent, but at heart always plays the same strategy and the same tactics. The dropships always fly along the edge.

SAIDA also has great strengths. The greatest may be the big red animated arrow that points out the main attack position. As long as SAIDA has a monopoly on big animated arrows, I think it will remain #1.

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

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.

It always strikes me as strange when I see a bot pass by unexpected creep and fail to realize what it means. It’s somewhat common: You’re scouting around for enemy zerg bases, perhaps near the end of the game, and units spot creep at the edge of their vision. And... nothing. I’ve even seen large armies bypass a vulnerable base to strike at the defended natural, simply because no actual zerg buildings came into view, only a slice of creep that implied they were there.

Of course, if some bots do recognize creep, it might be hard to notice. I would see a game in which nothing odd happened, instead of a game in which a base was overlooked. Maybe a lot of bots have this skill.

I’ve held off putting creep recognition into Steamhammer because it seemed tricky. What conclusions can you draw when you see creep? Maybe it’s a destroyed base, and the creep is not finished disappearing. Maybe a long string of creep colonies extended creep this far; you have to find the source of the creep to know. Maybe it is neutral creep from a neutral building—that happens on a few maps.

Today I smacked myself in the head, which I knew was made of wood because there’s a solution that makes it easy to draw conclusions: Remember the creep you’ve already seen! Doh! So easy! When you spot new creep on ground that you know used to be bare, it can only have gotten there due to an enemy hatchery or creep colony. Look through the buildings that you know about, and check whether there is one to explain the creep. If not, you have a new scouting goal.

It can’t be neutral creep, because neutral creep spreads before the game starts. It could still be due to a destroyed enemy building, but that will happen mainly when you have just destroyed the enemy building and kept on going, seeing new areas of creep. But even if you make a mistake, the only consequence is that you posted a new scouting goal. You will scout the area, see the disappearing creep, and no further alarms will ring.

BWAPI provides hasCreep() for visible tiles and isExplored() (whether you have ever seen the tile) for all tiles. BWAPI does not provide a way to find out what tiles are covered with neutral creep at the start of the game. Steamhammer has a map of the last frame that each tile was seen, used when exploring for enemy presence, and probably most bots have something similar. Initialize the map of creep to whatever creep you can see from your starting position (likely your own if you are zerg), and fill in the rest of the map with “no creep here”. The rest is obvious.

An alternative is to remember destroyed enemy buildings and use them as potential explanations of any creep you see. That allows mistakes too; you might be late to realize that zerg is rebuilding, because you explained the creep you saw as disappearing creep from a destroyed building.

Of course, you can do better if you have an exact model of how creep spreads and disappears. I’m sure the model could be extracted from OpenBW. It will be more complicated. In principle, you could use detailed knowledge to put tighter constraints on the location and timing of the building generating the creep. It seems like a lot of work for little gain.

I’ve looked into creep recognition before, for early game scouting. See how far zerg creep spreads. I expect that creep colonies spread creep in a way similar to hatcheries. When you see a bit of creep, you can figure out the area that the building generating the creep must be in—and you can probably rule out some of the area immediately, because you can see it is empty.

Watching games today, I’m struck by how little bots still predict and how much they rely solely on what they see right now. See react to the future for my earliest post on the topic, over 2 years ago: It says that you want to react to what you expect, not to what you see. Today, it seems to me that top bots mostly predict at the lowest and highest levels: They predict individual unit movements for micro, and they may choose their own initial strategy by predicting the enemy strategy. Other than that, it seems to me that play is reactive: What have I seen, what do I see right now?

When Steamhammer is chasing an enemy unit and the enemy goes up a ramp—oops, I don’t see it any more, choose another target. That’s not so bad, since Steamhammer chases too much anyway. But when Iron has done its vulture runby and slow hydras are trying to fend them off, it’s a problem. Each time the vultures swoop out of sight around the edge of the base, the hydras think “Whew, mission accomplished, no need to defend the base any more.” Or when Bereaver’s shuttle with the deadly reaver slides away for another approach, “Ha! We win! Let’s head for the front lines.”

When you’ve seen a unit recently, you can predict that it is probably near the same location (theoretically it could have been recalled or gone through a nydus canal). I’m sure some bots do this (Steamhammer development version does it for purposes of clustering). When you’ve seen a ground unit in a region and you have watch over the exits, you can predict that the unit is still in the region (there’s a small chance that it may have been lifted away by a transport, and maybe a minuscule chance that it somehow died out of sight, or even that it was escorted out under cloak by an arbiter). Do any bots do that? In the general case, you can reason about how far the unit can have moved by what time, and what places you had vision over at each time. I doubt it’s worth it, though.

Predicting the enemy army size and composition is valuable. Many protoss bots get observers only after they discover an urgent need to fight lurkers or dark templar. Pros don’t play that way. A pro can tell when the enemy is teching in the early game from the army size: Press to force the enemy to defend, and if there are not enough units, then the income is going somewhere else. It amounts to partly predicting the enemy army composition (“enemy is probably getting dark templar or reavers”) from its size. It’s a complex skill; you have to factor in early scouting information and bases taken. But it doesn’t take a data-hungry deep learning algorithm to solve it; it’s within reach. (In practice, I would treat this as a tech prediction problem: What enemy tech will we see? For each tech, estimate the probability of seeing it at a given future time. Since we’re predicting when we will see it (not when the opponent first gets it), the game itself provides the necessary training data and it it isn’t necessary to go through replays.)

Predicting the enemy army size is also valuable. This post was partly inspired by watching Proxy build sunkens to match the number of enemy zealots seen. (Steamhammer does the same thing.) Top protoss bots are careful to deny scouting and take advantage of the fact that opponents react only to units seen. In a forge expand, early in the game part of the protoss army tends to be out of sight behind the cannons. Later in the game, the protoss army size grows rapidly, and zerg doesn’t adjust its drone-to-army ratio until the new units are seen, which may be too late. It is a major strength of Locutus.

Plan recognition at the tactical level means predicting the enemy’s tactical movements. When an enemy army moves out, what is it doing? Is it coming out to fight your army, to attack a base of yours, to defend its own bases, maybe just to clear some mines or to see what’s up? It might be maneuvering to set up a drop, but bots aren’t strong enough to worry about that yet! Humans continually evaluate the enemy plan and react to what they expect. Bots do too, in a way, at a more primitive level. I’m thinking of Arrakhammer morphing its creep colonies into sunkens because the enemy is out on the map.

Some bots try to do proper tactical analysis, starting with MaasCraft. As I’ve mentioned before, I have an idea for tactical analysis that I hope will produce good results with less work than MaasCraft’s expensive search. There’s a chance I could get it done in time for AIIDE.

I thought that Proxy versus Tyr by Simon Prins was a good game to draw lessons from. It’s strategically simple and has a clear turning point.

Tyr played a Giant Terran Death Ball Will Crush You strategy, macroing up a juggernaut of tanks and marines before moving out. That gave Proxy time to do its thing and develop a roaring economy, in the meantime frittering away a few units in light harassment. Proxy went with a lurker-ling mix. When Tyr moved out, Proxy attacked repeatedly to little avail, looking almost helpless in the face of terran might. Zerg slowed the terran force but could not harm it much, fighting inefficiently and losing units at a high rate. Then suddenly the terran ball unraveled and the game was all Proxy. What happened?

Lesson 1. When Tyr’s force reached the bridges to the enemy natural, it became disorganized trying to move through the narrow choke. That’s the main reason the game was lost. At the same time, Proxy’s forces, trying to approach from all angles, concentrated their attack more effectively. I suppose that’s partly due to the map configuration and mostly due to Proxy realizing that it could attack the disorganized terrans with advantage.

The lesson is that movement is a big deal. Moving units around the map is important and difficult in itself. Bots struggle with moving around in good formation, and in difficult terrain they have no idea how to adapt. For the first micro skill that I implement with machine learning, I am seriously considering the skill of moving squads from place to place.

Lesson 2. Don’t waste units–well, it’s empty advice, everybody knows that. But look how many units Proxy lost needlessly before the decisive engagement. It could afford the losses because of its strong economy and strong macro, and fighting when it did was not wrong, because it slowed the terran down. But if Proxy had fought efficiently, the terran ball would have been broken in the middle of the map, not perilously near the zerg natural. Steamhammer desperately needs to learn this lesson.

More a suggestion than a lesson. I think terran did not take full advantage of the situation, and I don’t mean only neglecting to get stim. Leaving aside the need for terran to take a third itself, when zerg spreads to a large number of bases, terran should be thinking “how can zerg defend all that?” In this game, Proxy went all ground with no air defense. If I were the terran, I would have made a couple dropships: Drop marines and medics off to one side, stim, run in and eradicate drones, then focus on the hatchery. When defenders appear, fight them if you like, or else pick up and drop another base. If zerg invests in defending the many bases, the cost will be far more than you spent to harass them. The terran ball will be a little weaker, or will move out later, but zerg will be substantially weaker.

Here’s a recent pro game Snow (P) - Sharp (T), in which Sharp expanded behind a bunker somewhat like Krasi0, while Snow repeatedly ran by the bunker with dragoons much like Locutus. The game was played in KSL season 1 in group B on 3 August.

A point to note is that Snow tried to keep 3 dragoons inside the terran base. When the count fell below 3, it was time for another runby. 3 dragoons can kill an SCV in 2 volleys, or a tank in 3 volleys, so 3 dragoons are much more powerful than 2. (Versus a tank you’d prefer 4 dragoons which kill in 2 volleys, but with only 2 dragoons it takes 4 volleys—3 dragoons was the right number for this specific situation.) Also, Snow camped the single factory with the dragoons and felt no need to seek out other targets. Everything dangerous was going to come out of the factory, and if you can stop production, you win. Terran was forced to defend there.

Games like this remind me how far we have to go. It was so similar to a bot game in some ways, and so different in others. Compared to Locutus and Krasi0, the human players knew better what they needed to do, and were much better at coordinating their units to do it.

Bots are strangely ignorant of strategy. The strategies they follow are mostly hand-coded plans and rules. Other skills that look strategic are largely, it seems to me, not due to strategy knowledge but to the working of lower-level skills.

Many bots know how to counter the enemy’s unit mix. In Steamhammer that’s called “strategy”, but it’s a generous term. Do any bots know about high-level plans and recognize which ones are effective? Possibly Krasi0, whose mechanisms are secret. Often there is a simple method like “I’m killing more than I’m losing, I should keep this up” versus “I’m losing too much, let’s try the next option.” Killerbot by Marian Devecka appears to be pretty good at that, it’s also generous to call it strategy.

When to keep the pressure on and when to step back and consolidate is a basic strategy decision. When one of Steamhammer’s pressure openings has broken through, Steamhammer has no idea that it can win quickly by keeping the pressure on. It has cut drones in its build, and it wants to shore up its economy, and that can give a stubborn opponent a chance to stay in the game—in a longer game, maybe Steamhammer will mess up and lose. To be sure, it can be a delicate judgment: It you have a decisive advantage, be decisive; if you have a modest advantage, getting ahead in economy is a way to keep your advantage.

Bots commonly have a virtually fixed level of aggression. When it comes to army movements, Steamhammer believes in keeping its units as forward as possible, and it has company. Many other bots build up and then move out for a timing attack; XIMP by Tomas Vajda and LetaBot by Martin Rooijackers are big examples, but it’s common to many other bots. I think the timing is usually fixed or decided by simple rules.

There’s nothing wrong with a timing attack at a good timing, but if it doesn’t win outright then you have to follow up. You need a strategy for the rest of the game. One of the basic tenets of strategy is that it is advantageous to defend a fixed position: You can siege tanks, build cannons, burrow lurkers, take high ground, form a concave, position units to hit a bridge, and so on. Conversely, it is advantageous to attack an enemy that is on the move or otherwise out of a strong defensive position. Many bots use this principle when they try to contain the enemy. I believe they have scope to use it more deeply.

Another basic is that more resources are better. Bots follow that principle too: They like to take bases for themselves and destroy enemy bases, they like to make workers and to kill enemy workers. So here are 2 simple principles that bots know—yet I don’t notice any bot that seems to understand how the principles interact. A constant level of aggression is not correct. If you are ahead in resources and army, what you want to do is prevent enemy action while you increase your lead. If you keep harassment losses down and prevent the enemy from expanding, while you can expand yourself, then you are on the road to winning. Containing the enemy is only one way. You can also scout and react to enemy attempts to expand or move out. Use both principles together: Let the enemy move out of their defensive position, and strike them while they are weaker. I haven’t seen a bot do that. Before you switch into frontal attack, wait until you are maxed, maybe even until the enemy is mined out. You are winning, there is no hurry!

If you’re behind, you might try to safely extend your defensive position to another base so you can expand (a natural plan for terran). Or you might try harass your way back to a good position. In any case, you have to fight more efficiently to have a chance.

I think this kind of strategic play should emerge naturally in a bot which does sufficiently faithful tactical analysis. No actual strategy reasoning should be needed. I also expect that there are quicker ways to start getting the capability. I’m seriously considering whether and how to get some high-level strategy decisions in for AIIDE. Steamhammer is far too willing to beat its head against a wall when it should step back and wait.

After defilers, I did smaller micro and tactics fixes, corrected a few openings, and made other quick improvements. Then I looked over my to-do list and marked the items that would benefit from having on hand the results of a tactical analysis—wow, that’s quite a few, tactics are next! So far I have implemented clustering as mentioned here. I think that within a few days I should be getting practical results like decisions on which direction to retreat in, and then I’ll start seeing where my tactics plan needs revisions.

spider mines

In the meantime, I am also thinking about spider mines. In spider mine placement I wrote about the complicated considerations behind laying mines. Coping with the enemy’s mines is also complicated. These 5 counters to spider mines are all common in pro games.

1. Sweep the mines. The most obvious counter is to bring a detector and ranged units to safely clear the mines.

2. Force the mines. With good micro and the right choice of units, you can try to get by without a detector: You can shoot down spider mines after they pop up. It’s the most common way for terrans to cross a minefield. Dragoons and hydralisks can do it too, with more care, and so can dark templar, or zealots with high enough attack upgrade (+2 for 20 damage, enough to kill a mine in one hit), or in fact any combination of units which are quick and coordinated enough to do the damage in time. One risk that too many mines will pop up at the same time, and you’ll have to dodge them to reduce the damage. Another risk is that the enemy may appear, possibly forcing you back since you won’t be able to cope with mines and enemy units at once.

3. Dodge the mines. Find out which unit of yours the mine is targeting (the mine’s getOrderTarget() will tell you, as Purple Dan pointed out). Simply move the target unit away from the mine—and ideally away from any other units of yours which might be in splash damage range. There is a delay between when the mine decides to stop and explode and when the explosion occurs, and if you are moving away during that delay then you can suffer only splash damage instead of the full effect. (The same idea works for scarabs.) It makes a big difference.

4. Sacrifice to clear the mines. If you want to attack through a minefield, or if you are otherwise in a big hurry to destroy the mines, you won’t be able to do any of the above counters. Send a few zealots or zerglings through the minefield on move command, to trigger as many mines as possible. Being on move command is important; a unit that fires on a mine will stop moving and won’t trigger as many mines. The mine clearing units will be lost, but attackers can follow behind. I’ve occasionally seen terrans sacrifice marines to clear mines, but it is not as common or as effective. This technique is probably worth using during an attack when there is any suspicion of a minefield.

5. Drag the mines. If you are sacrificing a unit on move command to clear mines, what is the best place for your unit to end up? Right next to the enemy, making the enemy’s weapon backfire. A great mine drag can blow up a mass of tanks in moments. Pros know to place spider mines away from where their units intend to go, and to destroy their own mines when their units go there anyway. Bots tend to be careless about mine placement, and are acutely vulnerable to mine drags. Zealots from a shuttle can drag mines too; I think that variation is most valuable when you already know where the mines are.

Less common counters to spider mines exist. You can clear mines without damage by dropping units from a transport and picking them up again with exact timing. Psionic storm will clear mines from an area, but is generally not worth it. Disruption web stops mines from triggering, a use that I have never seen.

One other idea comes to mind, not a common technique as far as I have seen: Play tricks with the mines. You can deliberately leave mines in place and use them to show the enemy what you want the enemy to see. For example, an observer can spot mines without being seen in turn. Notice some mines and leave them unmolested and seemingly undiscovered. Then, when you need a diversion, send an empty shuttle over the mines and it will look convincingly like a drop (a fun use for hallucinate). Someday bots will be smart enough to be fooled!

Knowing that there are spider mines on the map affects your tactical planning from the beginning. Even units like workers that don’t trigger mines will be seen by them, giving away information. Some mines you may spot ahead of time; some you will not. If you’re smart, maybe you can guess where mines are likely. No matter what, you know that moving around the map will rely on the 5 counters.

I would like to get all 5 into Steamhammer for AIIDE, but I’m not sure how much progress I’ll make. I guess mine dodging will be first, since it is so similar to scarab dodging that it can probably be done at the same time.

Tscmoo zerg uses defilers and casts dark swarm, one of few bots with the skill. And... it’s clumsy at it. The swarms usually end up in unhelpful places, or overlap wastefully. Well, Steamhammer can’t place swarms either. The skill is extremely difficult for bots, for 2 related reasons.

One reason is that dark swarm is a coordination skill, and bots suck at coordinating their armies. For an attack, the defiler has to be charged up and in position as the attackers move forward, and place its swarms not only in the right places, but also at the right times, to neutralize as much enemy fire as possible. To do it well, you have to plan or predict how the fight will go, and set up the pieces in good locations ahead of time. One way would be with an abstract combat simulator or planner that could accurately foresee the general movements without working out the details—quite different from today’s concrete combat simulators that inaccurately foresee the details of the fight. Another way would be a large learning system that would be time-consuming to train. I don’t think any current bot has either.

The other reason is that dark swarm is a tactical analysis skill. Suppose you spot a group of marines in the middle of the map. You can’t simply drop a swarm on them and mop them up; if the enemy is any good, the marines will step aside. As long as you have zerglings around, the marines had better stay out of the swarm, but you can only swarm a small portion of the map. Or suppose carriers find your hydras, and you don’t have enough hydras to win, so you lay a swarm over them. Good, the hydralisks are safe, but the carriers can fly away and attack somewhere else. Dark swarm doesn’t protect buildings.

To do it right, the bot has to analyze the tactical situation. If you’re defending a narrow space from marines, great: Swarm the choke, put some lurkers under the ground, and you’re cool until swarm wears off or everything gets irradiated. If there’s more room, then you need to analyze possible maneuvers. If I swarm here, the marines can back up or go around. If they back up, are they farther away from where they want to go, or closer? If they go around, can I trap them? Will the defiler be safe, or is there a risk that this will be my last swarm until I can get another defiler over here? Strong play is super complex.

It just so happens—I’m sure it’s a coincidence—that I am planning to write a tactics analyzer next. Maybe that will help.