Starcraft AI blog

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.

The new zerg Simplicity has been getting a lot of games. Taking a peek at the binary, I see that it is a Java bot, and it lives up to its name: The compiled code is quite small, and most of the space used is in libraries.

Simplicity’s play is reminiscent of Proxy; it plays a similar mass hydralisk build with a similar late game addition of ultralisks. It’s a good general-purpose choice for a new bot, so no complaints there. At the same time, it puts on a direct and predictable kind of pressure. Proxy switched away from that build for both terran and zerg opponents, with good reason. (Well, Proxy still goes hydra against terran mech.)

Simplicity is weaker than Proxy, though (including the early Proxy before it was improved). Simplicity has been scoring around 50%, but many of its games are against low-level opposition. I forecast that its initial elo will come in below 1900. Simplicity does not have strong macro, and its tactics are clumsy. Also it appears to build a fixed amount of static defense, not adapting to the situation.

Simplicity does midgame scouting with reconnaissance in force, the same idea as Steamhammer—not common among bots, and unheard of among new bots made from scratch. It looked effective in games. I thought that that was Simplicity’s most impressive feature.

All in all, nothing dazzling, but good for a brand new bot, especially such a small one. After only one day, the bot got an update that I thought improved it, so development is proceeding rapidly. Any bot that improves rapidly has a chance to climb high.

Next: Analysis of potential paths.

Yesterday I changed Steamhammer’s Micro namespace into a class. Instead of Micro::Move(unit, position) or whatever, I write the.micro.Move(unit, position) (because I didn’t update the capitalization, at least not yet). The technical difference is that the class can remember state.

It is part of the process of rewiring Steamhammer with goals and goal monitoring throughout. Micro::Move(unit, position) is a command for the unit to move to a position. the.micro.Move(unit, position) will be, once I’ve finished the implementation, giving the unit a goal to move to a position. My immediate purpose is to make Micro unstick stuck units—this way hides the details from the rest of the code. Eventually, with its knowledge of what each unit is trying to do, Micro might take on many other jobs: Find paths, follow specified paths, evade enemies on the way, coordinate kiting units, and in general notice and work around all kinds of unit level goal failures, or notify the rest of the program if the failure cannot be worked around (“you can’t get there, a pylon wall is in the way”).

I’m not sure what jobs I’ll end up actually assigning to Micro. At a minimum, it will have the lowest-level unit control stuff. Path following seems likely; because implementing it this way looks clean and simple.

One step at a time!

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.

I am still working on squad tactics, as I mentioned some days ago. I wouldn’t say the tactical play is adept (I’m not far enough along to test for strength), but as I fix problems it is slowly starting to resemble decent play. There is more to straighten out, but the strange Steamhammer misbehaviors of darting sideways for no reason, trying to retreat through the enemy, hanging back from the front, or losing groups of rear units in bad fights—those problems are all gone. The potential for tactical skill is much higher, and the question is how much of the potential I can realize. More polishing to do!

As I make progress with the play, the code is growing messier. There were already too many special cases (see Steamhammer’s squad structure 1: awkward points), and I had plans to rewrite squads entirely (see the followup post Steamhammer’s squad structure 2: design ideas). Now the special cases need to be carefully stacked in the right order to stand up at all, and the structure is growing dangerously shaky. The rewrite is needed more than ever, and I have a firmer idea of what is needed.

This has me thinking of plans and priorities for after the AIIDE deadline on 1 October. I feel a need to return to basic infrastructure work. Steamhammer 2.0 for AIIDE will be zerg only, because I am deliberately ignoring terran and protoss skills. So the first order of business will be version 2.1 that can play all races again—it will take some work, I’d guess a few days. After that, probably the top infrastructure priority is to finish the map analysis work and drop BWTA. There’s only one big feature to go, chokes and regions, and I think I can finish it in one more step in version 2.2. After that, the major infrastructure needs are the squad rewrite and getting rid of BOSS, both of which will take longer and should probably be done in stages.

I hope that the AIIDE Steamhammer will be the strongest ever by a good margin. But after that I have to get into plumbing repairs. The version for the SSCAIT tournament in December should have cleaner code and be easier to work with, but it is not likely to be much stronger than the AIIDE version.

2 recent events with a connection to Krasi0.

Krasi0 updated

Krasi0 has been updated with terran wall skills. Locutus doesn’t understand the wall, and Krasi0 is winning against Locutus again. Bruce predicted it would happen before AIIDE, and here it is. With a wall, Locutus cannot run by into the terran main, and Locutus does not have the skills to pressure the wall.

I think Krasi0’s wall build versus Locutus leaves protoss with an advantage, because the terran natural is delayed. But Locutus, showing its Steamhammer heritage, is impatient and presses too hard early, falling behind. Krasi0 has been winning most games easily.

I’m sure that in time we’ll see a Locutus version addressing the weaknesses. For now, the elo ratings of the 2 bots are converging. Will Krasi0 be able to pass Locutus in elo? Even with wins head-to-head, that might be hard.

Steamhammer strange crash

Here’s a new one. In Krasi0-Steamhammer on Icarus, Steamhammer lost its main and natural and was left with only its third. It’s a situation Steamhammer has been in many times, and zerg normally recovers if given time. It can win the game if the opponent never finds the base, or is also crippled.

This time something went wrong that I’ve never seen: Steamhammer rebuilt drones up to 14, which is abnormal. It is coded to replace the spawning pool at 9 drones. Then, even stranger, with an idle drone because there were too many and its minerals piling up, it got into a loop where it made nothing but overlords. It seemed to be in Plato’s cave, watching a bad movie that had nothing to do with the game.

Then it crashed. Some data structure must have broken. :-(

CIG 2018 results are announced. See CIG 2018 maps and entrants for my preview of the tournament. Rankings and win rates are included; replays and source are being held back until the AIIDE 2018 submission deadline of 1 October. They did not say what the release policy is for detailed results (game by game results). So far, they have published a slide show and a 2-minute highlight video with short clips from games by the top 3 winners.

I expect they'll put the result table on the website before long. In the meantime, since the slideshow is inconvenient for looking up basic data, I'll reproduce the results here, copying only the minimum information.

#	bot	%
1	Locutus	92.06%
2	PurpleWave	91.14%
3	McRave	82.09%
4	tscmoo random	81.29%
5	ISAMind	80.31%
6	Iron	74.31%
7	ZZZKBot	69.08%
8	Microwave	64.83%
9	LetaBot	63.60%
10	MegaBot	61.17%
11	UAlbertaBot	60.58%
12	Tyr	57.23%
13	Ecgberht	52.80%
14	AIUR	51.54%
15	TitanIron	51.45%
16	Ziabot	51.08%
17	Steamhammer	34.83%
18	Overkill	34.68%
19	TerranUAB	34.40%
20	CUNYbot	29.51%
21	OpprimoBot	27.11%
22	Sling	26.52%
23	SRbotOne	24.37%
24	Bonjwa	23.57%
25	Stormbreaker	21.23%
26	Korean	7.69%
27	Salsa	1.54%

There are no surprises in the top 4. #1 Locutus nosed out #2 PurpleWave. The win percentage over time graph after the results in the slide show says that PurpleWave was ahead of Locutus for the first third of the tournament, but then fell slightly behind: Locutus's learning (based on Steamhammer's opponent model with some changes) was a little more effective. #3 McRave did well but could not keep up with the top 2. #4 Tscmoo is a perennial high finisher. #7 ZZZKBot in past years has generally found a way to push into the top ranks, but perhaps it has reached its cheesy limits this year (or maybe it had less work done).

Unfamiliar protoss #5 ISAMind finished impressively high. To outscore #6 Iron in your first tournament, even a year-old Iron that has not been updated, is a big achievement. I look forward to learning more about ISAMind.

#15 TitanIron appeared to have a large and talented team behind it and showed signs of being based on Iron, so its even score is a surprise. It finished behind #13 Ecgberht and #14 AIUR, both of which have good skills but are only middling overall.

Also noticeable is that no protoss scored under 50%. In this tournament, playing protoss got you a plus score, no further questions asked! It truly is an era of protoss ascendancy. It's up to us zerg and terran to see if we can break that in AIIDE.

#17 Steamhammer was not disqualified, but performed poorly as expected due to its fatal bug—notice the giant gap in win rate between Steamhammer and #16 Ziabot just above it.

I’ve been revising the internal structure of Steamhammer’s squads to make them more capable. It’s not nearly as big a rewrite as needed, but it adds new capability and in theory it should be a big win. After several days of work, yesterday I was able to try it out for the first time—it’s not completed, but it’s finished enough to work as designed in common situations, so I can test it in real games.

After fixing one severe bug, it worked as intended. And—it played horribly!

Adding features decreases strength, fixing bugs increases strength. I believe it more than ever. It’s not that new features bring new bugs, at least not necessarily. A new feature is not well tuned yet, not integrated with other features of the bot. If it’s a big feature, it tends to disrupt successful patterns of play that arise from the interaction of the existing features. When a new feature is a good idea, it takes time to tune it up and make it successful.

I’m convinced my new feature is a good idea, or I wouldn’t be working on it. It’s an open question whether it will be successful in time for AIIDE.

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.

There are 2 changes I want to make to Steamhammer’s opponent model. Both of them will take some reading up and thinking.

1. The exploration algorithm is not good enough in practice. Its purpose is to try different openings to counter the opponent. Steamhammer uses epsilon-greedy (that is, a fixed probability) to decide when to explore, and to decide what to explore it uses an ad hoc strategy of at first trying openings to counter the opponent’s recognized plan, then with more games casting a wider net.

The problem with deciding when to explore is that Steamhammer knows more openings than it has time to try. With more choices than games, we can model the situation as an infinite-arm bandit. I haven’t read up on it yet. Here are a couple papers I found in a quick look for infinite-arm bandit solutions, if you want to get ahead of me.

Algorithms for Infinitely Many-Armed Bandits (Wang, Audibert, and Munos, 2009)

Simple regret for infinitely many armed bandits (Carpentier and Valko, 2015)

The problem with deciding what to explore can be solved with opening data. Data telling which openings work across all opponents (versus different races, on different maps, with opponents following different plans) can be used in solving both problems. But it will take a long time to collect the data; expect it late this year at the earliest, likely later.

2. It doesn’t mix up its openings enough. Steamhammer’s classic randomized openings were effective. Now it often chooses an opening depending on what the opponent has done in recent games, and can get stuck on fixed responses after the opponent has switched. For example, Proxy was updated to follow a mutalisk plan instead of a zergling plan in ZvZ, but Steamhammer is still responding to the zergling plan, and losing every game because of it.

Steamhammer tries to tell whether the opponent follows a fixed plan, or varies. It doesn’t matter whether the variation is random, or reacts to past games, or reacts to events in the current game, or is due to the bot being updated; the opponent is playing a fixed plan, or not. For example, if Steamhammer tries a 5 pool and Bereaver reacts with its cannon defense, Steamhammer will conclude “Oh, Bereaver doesn’t do the same thing every game.”

Right now, the “my opponent is a constant” recognition is used in a tiny way. I have always wanted to use it to optimize opening choices, like so:

If the opponent plays a fixed plan, Steamhammer should seek a fixed counter. Most bots with opening learning, including Steamhammer so far, seek the best fixed counter; it’s easier and works faster. If the opponent varies its plan, Steamhammer should in general follow a mixed strategy, which is to say, it should choose randomly among some of the effective counters. This is not as easy to code and takes longer to converge on a good solution, but it makes life difficult for opponents which try to learn or adapt.

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.

Steamhammer crashed in the game Steamhammer-Middle School Strats. The game itself is not interesting. Middle School Strats is a rushbot, and Steamhammer had played it twice before, according to its game records. In the second game, Steamhammer misdiagnosed the opponent’s opening, so in this third game it played the wrong counter and got run over. Since Steamhammer crashed, it did not save a game record and will likely lose the fourth game in a similar way.

From the timing of the crash, it looks as though it was caused by the “impossible” bug that I recently fixed. The underlying crashing bug has been there since version 1.4.1 in April, and this is the first time it has manifested in public. I only discovered the crashing bug because I introduced another bug in my development version that brought about the infrequent conditions needed to trigger the crash!

Reliability is hard. Another bug is that Steamhammer’s reaction to having a mutalisk irradiated is broken—it has been broken since last year, and I still haven’t found the cause. An irradiated mutalisk is supposed to move away to save other zerg units. The code worked when written, and to my eye it looks as though it should still work, but somehow it has bitrotted—mutalisks don’t seem to react at all to being irradiated. How am I supposed to handle an interesting case like an irradiated ultralisk when I can’t handle an easy case?

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.

I habitually take a top-down view of things (I’m a lumper, not a splitter), and I want to use an example to draw a comparison. The example is: Steamhammer’s production queue data structure is inherited from UAlbertaBot. It looks like this (I left out the constructors).

struct BuildOrderItem
{
    MacroAct macroAct;  // the thing we want to produce
    bool isGasSteal; 
}

Steamhammer renames UAlbertaBot’s MetaType (which might mean anything) to MacroAct, and extends it with a MacroLocation to specify where things are to be built (and other changes).

I want to simplify this, and it should be easy to understand why. Stealing gas amounts to building a refinery at a given location—it should be specified as a MacroLocation, not as a separate flag outside the MacroAct. I can drop the wrapping BuildOrderItem data structure and keep a queue of straight MacroAct values. There will be one less level to the data structure, a distinct improvement.

On the one hand, it simplifies the code and it’s a straightforward, low-risk refactoring. There are many uses of BuildOrderItem and it will take time to handle them all, but the compiler will tell me if I forget to rewrite one of the uses. On the other hand, it doesn’t affect play in the least. The production queue will behave the same, and it is not a heavily used data structure that affects performance.

So from a project management perspective, what’s the best time to carry out the work? The sooner you do a code simplification, the longer you benefit from it. But it will take time, and I want to concentrate on play improvements for AIIDE. What’s the best timing?

Well, it’s not an important question. I might do it before AIIDE or after, and it won’t make a big difference either way. But I find it interesting to think about. Optimizing the development process is similar in concept to optimizing Starcraft play: It is about taking actions, sometimes tiny actions, that improve efficiency over time. It requires similar subtle judgment calls. Take actions with big enough cumulative effect, and you pull ahead; you have to decide which actions are worth your limited time. To me, taking the abstract view, the big difference is that in software development you get more time to think about it—coding is a slower-moving game.