Starcraft AI blog

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.

I have finally finished adjusting the terran openings, and I’m working on protoss. Initial signs are that protoss will be easier, but we’ll see. After that I need to make some changes to building placement.

It’s boring to work on openings all the time, so I diverted myself with a few other refinements. The biggest is another round of improvements to the tank siege/unsiege logic. The last round was a tiny tweak that made a difference only in rare cases. Tanks continued to fall into ludicrous siege-unsiege loops, often without firing a shot. This round I was more thorough. The decision to siege analyzes the situation to avoid common mistakes. The decision to unsiege is more strict; part of that I achieved as a side effect of improving tank targeting. The results are easy to see, and tank play is more consequent. Tank micro is still far from good, but the siege/unsiege logic is no longer the weakest link. Now the bigger problems are attack/retreat decisions, positioning, and the issue that Steamhammer has no understanding whatever of visibility.

In between the fixed openings—some are now stronger than they ever were before—and the fixed tank play, Steamhammer’s terran is looking up. I don’t think it’s hugely improved, because too many other problems drag it down, but to me the difference is unmissable.

I was intending the upcoming version 2.2.1 to be nearly the same as 2.2, with only the minimal updates to play on SSCAIT, but it is turning into something more.

I promised a post about how Steamhammer can eventually optimize its own openings. In fact, I intend for it to be able to invent its own openings from scratch, as well as adjust openings (whether hand written or automatically generated) based on calculations and experience. Here’s an outline of my ideas.

My next big project is strategy adaptation. A large part of it will be implementing abstract strategies and the ability to turn them into concrete lines of play. For example, “3 hatch muta” is an abstract strategy at a high level of abstraction, and Steamhammer’s opening lines ZvT_3HatchMuta and ZvP_3HatchMuta are concrete implementations of the strategy, optimized for different matchups. Once abstract strategies exist, Steamhammer will be able to experiment with different strategies by simply filling in its abstract strategy data structure—with random values if no other way—and playing out the game, turning the abstract strategy into a build order. I suppose I’ll do this at home rather than during tournaments! There are more focused ways to find new abstract strategies: Steal them from opponents, extract them from replays, systematically explore the lattice of strategies (since they are partially ordered) extending the promising avenues, note enemy timings and units and do a directed search for strategies that hit the timings and counter the units. The space of abstract strategies is exponentially easier to search than the space of build orders; that is the advantage of abstraction.

Another part of the strategy adaptation project is to collect data on opening lines—aka concrete build orders—with their resource use and timings and unit counts and stuff. If we play out a strategy and get a build order, we record the build order as an opening, and if we play the opening we measure its data in real games. With the measured data, we can compare openings to judge which one is better in a given situation: Does it hit the timings, does it counter the units, does it grow a strong enough economy, does it have adequate defenses?

One way to do the comparison, which both I and others have suggested, is to set up the armies of both sides and run the combat simulator. That compares army strengths; if you also know economy size and tech level, you can do a more comprehensive comparison.

Once you can compare 2 opening lines for goodness in a given scenario, you can optimize an opening line for the scenario without changing its abstract strategy. I think I’ll try goal-directed modifications to the opening line—the enemy attacked early here, we need units in time; or the enemy had too much stuff later, we need more drones to keep up. Modifications that pass the comparison check can be tried in games.

Many new skills are needed. My plans are more than my accomplishments, and my accomplishments turn out different from their original plans. Even so, I expect to get a system like this working eventually. If you try a new idea on Steamhammer and it has no counter, it will invent its own counter and polish it by experience and reasoning. Then I’ll have gotten somewhere.

It turns out that nearly all of Steamhammer’s terran openings are in need of adjustment. I’m working through them systematically, and I’ve made it to VultureWraith so far—4 more to go after this one. VultureWraith inexplicably makes a second factory shortly before it stops vulture production—well, I say it’s inexplicable, but I can explain it as leftover history from when I was exploring different followups. In any case, the final third of the opening line needs to be rewritten. When I’m done, the terran openings will be cleaner and stronger, though the bot will be as clumsy as ever after the opening ends. Though I have an idea for another easy improvement to siege-unsiege decisions....

I’m hoping that the protoss openings are in better shape. I guess I’ll find out soon. There are a bunch of unconfigured protoss openings. Should I go through and configure some of them?

I need to make some building placement changes too, to keep up with how bases work now. I’m considering plans.

All in all, there’s more work than I expected.

The next Steamhammer version will be 2.2.1 for SSCAIT.

• Update terran and protoss openings for new Steamhammer skills.
• Because of other changes, terran and protoss need some building placement corrections.
• Test for and fix any new terran and protoss bugs.
• Test and probably tweak some code details that I didn’t have time to polish.
• Probably add a minor feature or two along the way.

After that, I want to switch to BWAPI 4.2.0 and undo my workarounds for BWAPI 4.1.2 bugs, especially the irritating ones that affect zerg. Zerg drop strategies will become more viable.

In the longer term, the big project is strategy adaptation, as decided here. It will take a long time and has to be done step by step.

Earlier, I laid out a 3 phase plan for the work: Abstract strategies, then data collection and decision-making, then exploiting the new infrastructure for decisions throughout the game, not only early on. Probably, though, it’s better to think of aspects rather than phases. I think I’ll do parts of each and spiral around until it’s wrapped up. Data collection and decision making are not so much parts that can be done separately as parts that need each other to be useful.

The outline and goals are clear, but I keep changing my mind about the exact steps. One early part will be replacing the separate opponent model files for each opponent with a unified database, because I will need to collect more data and do more varied calculations with it. Another early part will be building out the production goal system, which will do much of the work of turning an abstract strategy into a concrete build order (and will improve play for all races, but especially terran and protoss, before abstract strategies exist). I may implement the tree of concrete opening lines as an intermediate step before layering abstract openings on top. A third early step is a build order analyzer that predicts how long different builds will take, what resources they will need when, infers the existence of some enemy buildings that have not been seen, and related stuff; it will provide input both to the new strategy boss and to the new opponent model.

I have a general idea of how I want to represent an abstract strategy and tie it both to concrete opening lines and to production goals, which are 2 ways to carry out the abstract strategy. I have a rough sketch for how to represent the opponent’s partially known build state and predict the range of possible or likely strategies. I need to figure out a ton of details, and decide on a general mechanism to tie the predicted enemy plans to strategy reactions.

The total is definitely more than I can finish before AIIDE. I have to aim for a useful subset of the ultimate skills.

Soon: The AIST S2 results.

Here are details of how zones and chokes are calculated.

Map partitions. This is old work, but I want to mention it for completeness. The partitions data structure is a grid of 8x8 walk tiles that divides the map into connected partitions—you can walk from any point in a partition to any other, while you can’t walk to another partition. The partitions are not used to calculate zones and chokes, but they are related map information.

Inset. The inset is the Manhattan distance of each walkable 8x8 walk tile from the nearest unwalkable walk tile. It’s calculated by a straightforward breadth-first search. The distance is measured in walk tiles. In code, you access inset values with the.inset.at(). The inset is directly useful for a variety of micro decisions, and indirectly useful because you can calculate other information from it.

The inset values take immobile static units into account, such as mineral patches and neutral buildings. There are advantages and disadvantages to the decision.

One idea I have considered: I could calculate negative inset values for distances away from walkable terrain. Then air units would be able to easily find places safe from ground units, such as overlord watch posts. Another idea: I could change the scale of the inset values (the values in the inset grid) from walk tiles (8 pixels across) to pixels. Walk tiles are the least often used scale, and I suppose it’s a cognitive burden to remember that insets are in an unusual scale.

vWalkRoom gives an estimate, for each walk tile, of the room around the tile: How big a thing could fit there, measured in walk tiles. It is calculated from the insets and used to calculate the tile room. The v stands for “vertical” because of the simplified algorithm: It scans down each column of the grid of insets (because of the data structure, it’s more cache-friendly that way), and fills in stretches of walk tiles with the maximum inset in that stretch. A stretch starts at the first walkable walk tile, or after the previous stretch ends. A stretch ends before the last walkable walk tile, or after the inset has been decreasing and starts to increase again. Note that scanning horizontally would often give different numbers! This is a fast and simple algorithm, not an exact one. To get the vWalkRoom, use the.vWalkRoom.at().

tileRoom is nothing more than the vWalkRoom scaled to tiles. Each 32x32 tile is filled in with the maximum vWalkRoom value of the 16 8x8 walk tiles that make it up. The purpose is to reduce the data volume so that zone calculations are fast; zones don’t need higher resolution than this. A disadvantage of scaling to tile size is that connectivity information is lost. Two adjacent tiles A and B might both have positive tile room, even though you can’t walk from one to the other (it does happen sometimes). To find connectivity, use partitions. The tile room is useful for tactical decisions, and for getting an idea of whether a unit or army will fit into a space. Get it with the.tileRoom.at().

Zones are calculated using the tile room. There is no separate data structure for chokes; a choke is simply a zone where isChoke() returns true. The data describing zones consists of a grid of tiles so you can look up the zone ID of any location, and a vector of Zone data structures indexed by the ID. (Keeping IDs in the grid instead of pointers means I can use inheritance of grid classes without needing a template class.)

Zones are calculated from the tile room values with an iterated flood-fill algorithm. The borders of a zone are the tiles at the edge of a walkable area, points where the ground height changes, and points that change from non-choke to choke or vice versa. A tile is (initially) in a choke if its tile room is less than a constant—I use 12 for now, which includes narrow bridges but not wide bridges. This creates a certain number of nonsense zones that then need to be cleaned up: Tiny isolated zones are deleted, tiny zones with only one neighboring zone are merged into the larger zone, and “choke” zones which have only one neighbor are not real chokes and are also merged into the neighbor. That’s about it; all done save minor details.

Here is the public interface of a Zone. Every method and every returned reference is const; once the zone is initialized, nobody is allowed to change it.

	int id() const;
	bool isValid() const;
	bool isChoke() const;
	int groundHeight() const;
	const std::vector<BWAPI::TilePosition> & tiles() const;
	const std::set<Zone *> & neighbors() const;

The id() is a small integer. isValid() is false for zones which were deleted or merged into another zone; the data structure itself is empty but is not deleted, because the zones are indexed by ID (this could be cleaned up if it ever starts to matter). groundHeight() is -1 if the zone has more than one ground height, which can happen after zones are merged, or is the zone’s constant ground height otherwise (actually the low bit is cleared, so that the “doodad” heights are lost). There is a vector of tiles so you can know what’s in the zone without scanning the grid (also used to delete and merge zones), and a set of neighbors so you can work with the map topology.

Overall, Steamhammer’s map analysis is not as polished or complete as BWEM. There are points I want to clean up, and a lot of features are on my list to add—and as I mentioned a couple days ago, I may yet restructure it entirely. As one example of an awkward point, some choke zones are not shaped as you might expect. On Benzene, to illustrate, the down ramp from each main base is next to the geyser and mineral line in the natural, tiles which are also low in tile room. So the choke zone extends down the ramp and then along the resources in the natural. Steamhammer as it stands has no trouble coping with the oddly shaped choke or the oddly truncated natural zone, but I will have to take it into account in new code; it constitutes technical debt.

Here, according to the ancient and honored tradition, is the big change list for Steamhammer 2.2. The most important items are in bold.

map analysis

I’ll write up map analysis in a separate post with the details. Here are a couple of related bits.

• MicroManager::unitNearChokepoint() formerly iterated through BWTA’s list of chokes to figure out whether a given position was close to any of them. Now it simply looks up the tile room, an O(1) operation, to see how much space there is around the position.

• The previous version had a bug where certain mineral only bases would be taken, but were never mined. A drone made there would transfer to another base to mine. It was a side effect of using BWTA for some decisions, and Bases for others. Using Steamhammer’s native map analysis for all decisions fixes the bug; those mineral bases are both taken and mined.

opponent model

• The plan recognizer detects an enemy proxy using both the zone and the distance. Results are more accurate, especially against a cautious proxy like Krasi0P’s.

macro and construction

• I fixed a bug in mineral locking that could assign more than 2 workers to a mineral patch. See WorkerData::getMineralToMine(). That prevented drones from being transferred to bases where they could mine more efficiently.

• In a related change, WorkerData::depotIsFull() ensures that 2 workers per patch are always enough. It’s not optimal in all cases, but on competition maps it is close enough, and it keeps the mineral mining model dead simple.

• If a worker is carrying resources, do not assign it to build. A drone carrying resources will lose them when it morphs, and an SCV or probe will leave the resources unavailable for that time.

• Do not assign a worker from a distant base to build unless the local base has no workers on minerals. If necessary, wait for a local worker to be free. Steamhammer would sometimes send a worker cross-country to construct something, merely because local workers were temporarily busy. It wasted mining time and caused buildings to be built late.

• Less wasted movement in constructing buildings. Version 2.1.4 fixed some cases; this version fixes more. Assignment of workers to buildings is revamped. Formerly, the production manager was responsible for deciding when to move a worker in preparation for construction, and the worker manager for moving the worker to the requested position. It meant that Move workers did not have a goal beyond moving; there was no persistent intention. Now the production manager takes control over the worker as soon as it decides to prepare for construction, and manages all the steps and contingencies until it is time to hand off the worker to the building manager. The worker manager’s Move task no longer exists; workers taken over by the production manager have the task Build as far as the worker manager is concerned. It not only works better, it is a net simplification of the code. Unfortunately, there are still cases where workers waste movement in construction.

tactics

• The early game worker scouting path actively explores the enemy base, instead of simply circling it.

• If scout harassment is turned on (Config::Strategy::ScoutHarassEnemy), do it only while the scout has over 20 HP. Try to, y’know, stay alive and stuff. Steamhammer has kept this turned off for nearly its entire life, but I would like to improve it and enable it someday.

• Don’t transfer workers away from a base merely because an enemy scout worker is there. This is a bug that crept into the last version as a side effect of defense improvements.

• The “back to the wall” final retreat position is slightly cleverer in some cases.

combat simulation

• Mutalisks get a small compensation when facing turrets and cannons, in addition to the substantial compensation when facing spore colonies. It reduces cases where too few mutas attack too much static defense.

micro

• Command jam bug is fixed. No more massive excess commands. This fixes a wide variety of misbehaviors that the command jam bug caused. For example, drop openings work reliably again.

• Unfreeze stuck units. The micro system monitors the movement of units which have been told to move, notices when they fail to make progress, and takes steps to fix the problem. The steps are not always successful, but it usually works.

• Add Hold Position as a supported micro command. Ranged units are coded to hold position after retreating, rather than to attack-move their own position. I think this doesn’t work exactly as intended; it looks as though melee units hold position too, which could be a mistake.

zerg

• React to excess drones in the opening. To explain: For a long time, Steamhammer has had a reaction where, if the opponent did something greedy and unexpected, or if Steamhammer felt safe from the enemy because it had adequate static defense itself, the bot would turn planned zerglings into extra drones during the book opening. But Steamhammer did not make any other adjustments; the extra drones caused minerals to pile up during the opening, and it might reach the middle game with a huge mineral excess and struggle to make the right number of hatcheries to spend down its cash. (It usually added too few hatcheries at first, then too many later on, a bad combination.) Now Steamhammer has rules to use the extra minerals to take more gas geysers and add more hatcheries during the opening. The difference in play is giant. Steamhammer runs through the opening line faster with the extra resources and extra larvas, and reaches the midgame in a much stronger position.

• Steamhammer can get any evolution chamber upgrades in any order. The strategy boss originally supported only a fixed order of upgrades, first carapace and then melee attacks. The missile attack upgrade was not supported at all. The simplified system made it easier to check for problems and prevent production freezes (“oops, we lost the lair and now we can’t start +2”). The strategy boss does not make use of its new capability yet. I did update a few openings to take advantage, though (see the openings section below).

• Rare cases of production freezes are fixed. I believe there are very few of these left.

• I adjusted some strategy boss unit mixes: Favor guardians more versus terran. Favor mutas more versus protoss. Favor devourers slightly less versus protoss.

• Emergency sunkens adjusted modestly.

• If we made an emergency sunken, only replace the drone immediately if we are in the early game and don’t have that many drones yet. If we have enough drones, it’s better to add emergency sunkens at full speed, rather than interleaved with replacement drones.

• The earliest queen’s nest timing was shifted later. It’s still quite early. Sometimes you want a fast hive, but Steamhammer is not so good at judging when.

• The strategy rules for taking gas are slightly tweaked. Well, they’re mostly refactored for clarity, but the workings are slightly different too.

openings

I added 18 new zerg openings, raising Steamhammer’s total well over 100. I don’t think I’ve ever added so many at once before. Not all are valuable, but a few take Steamhammer’s play in new directions and put different pressure on the opponent. Besides new openings, I made the usual tweaks to the mix of openings in different cases.

• 6Hatch and 7HatchSpeed are mass zergling rushes that make an early second hatchery and no more drones than are necessary for the 2 hatcheries to produce constant zerglings. 6 hatch can be seen as a more polished variant of the old Newbie Zergrush opening of 8 hatchery 7 pool; it uses the time while the spawning pool finishes to reach its drone quota without delaying zerglings, so the rush is faster. The 7 hatchery version delays the rush a little to get zergling speed. These are deadly against opponents which don’t expect so many lings so early.

• 7-7HydraLingRush, 7-7HydraRush, and 8-8HydraRush are the hydralisk rushes inspired by Tscmoo zerg. The first 7 or 8 is the drone count when the spawning pool is made. The second is the steady drone count while the hydras are being produced. I made a number of variants and kept these 3. 7-7HydraLingRush is the one configured against factory first openings; it throws in an occasional pair of zerglings to make the rush a little less gas-rich and stronger against marines. It’s so successful that I set it to be tried 25% of the time when exploring counter-factory openings, reducing the rate of exploring the other 6 options. These openings are strong against greedy terrans that do not react to the outlandish build (why would you recognize something so strange?), and are hopelessly weak otherwise.

• 10HatchHydra is a slower hydralisk rush inspired by a Velocirandom build. My version is a little different. This opening is also fairly effective against factory first, but less so in my tests, and it is not configured to be used.

• 2HatchLingAllInSpire is based on an Effort opening used against Flash in the ASL6 finals. It is also intended for use against factory first builds. After barely enough drones, it masses lings for a timing attack against the factory while simultaneously working toward a spire as followup. It’s truly all-in; either the zerglings or the mutalisks have to do major damage. It’s quite different from anything else in Steamhammer’s repertoire, and configured to be explored against an expected factory opening 15% of the time.

• AntiFact_Overpool9Gas is my attempt to repurpose a ZvZ one base fast mutalisk opening against factory first. It seemed like a good idea, but it turned out less successful in practice. (Imagine, a pro like Effort came up with a better build than I did! How can that happen?) It is configured to be explored against an expected factory opening 5% of the time.

• 9PoolSpireSlowlings, Over10PoolLing, and Over10PoolMuta are zerg-versus-zerg openings of no special note. They fill gaps in the repertoire, but not wide gaps.

• 4HatchBeforeLair is adapted from Liquipedia. It is configured as another counter forge expand opening—Steamhammer now has 10 of these.

• ZvP_3HatchMuta fills a gap in the versus protoss repertoire. For a long time, Steamhammer’s mutalisks were too weak to make the opening work, but now they are somewhat improved.

• 11HatchTurtleMuta fills out a series of 11 hatchery openings that defend early and then strike back. It’s the weak mutalisk thing again.

• 3HatchLateHydras and 3HatchLateHydras+1 are inspired by a Microwave build. They are hydra busts with a later timing and greater mass than Steamhammer’s existing 3HatchHydraBust build. The +1 variant spends a little extra to get missile attack +1, and is configured as one of the 10 options against forge expand.

• HiveRush rushes to hive. This version is intended for use against protoss forge expand. The early adrenal glands upgrade is valuable and I found that it can cause trouble for opponents, though not enough to justify configuring the opening for use. This could be stronger if Steamhammer understood how to follow up properly.

• FastScout sends one of the initial 4 drones to scout immediately. It makes 4 more drones, for a total of 8, and then the opening ends! It leaves everything in the hands of the strategy boss, even whether to next make a drone or an overlord. I originally coded this as a test of scouting, so I could evaluate changes to the scouting path more quickly; I was expecting to delete it when I was done. But I noticed that sometimes the strategy boss, given such early scouting info, makes better decisions than the default mix of openings. It’s not configured to be used (though Steamhammer will play unconfigured openings if it explores enough), but I left it in to inform the development of strategy adaptation. I want Steamhammer to decide for itself when to scout, and right away will be a useful timing to learn from.

• Now that the zerg strategy boss supports ground upgrades in any order, I updated a couple of existing openings to make better upgrade choices. Overpool+1 gets melee attack +1, and 4HatchBeforeGas gets missile attack +1. These are clear improvements. Formerly, they got carapace +1 because it was the only supported possibility.

• I tweaked the protoss DTDrop to avoid a bad queue reorder. I need to recheck all the terran and protoss openings, and update them to keep up with changes in Steamhammer’s skills, especially mineral locking and queue reordering.

configuration

• New debug option Config::Debug::DrawMicroState annotates friendly units with their micro goals in the form of BWAPI::Order and sometimes a little more info. The micro goal is stored as an order, but it is not necessarily the same as the unit’s current order. A unit told to move will have to goal Move, but if it is stuck it might have a different order at the moment while it tries to unstick itself. The micro state gives the unit’s micro goal (“move to there”) and describes the unit’s state in its attempts to achieve the goal. This is a step on my path to a goal monitoring architecture.

• I fixed a copy-paste error in executing the manual command /set drawhiddenenemies true during play. It mistakenly turned on Config::Debug::DrawEnemyInfo instead.

code

• Clear all squads in onEnd() before the program exits. This should fix the shutdown hang that was diagnosed by Bruce @ Locutus.

• Fixed a potential division by zero in the “is my army big enough?” tests. This never happened in practice, and now it never will.

• UAB_ASSERT no longer prints the text of a failed assertion. It’s redundant—it already gives the line number, which is strictly more information.

• Renamed MicroInfo to MicroState on the theory that it’s clearer.

• Added a new utility function GameMessage(const char * message) to send a public message visible to all players.

• Now uses GameMessage() to send the gg message. I was astonished when I realized that Steamhammer’s “gg” was visible to me watching but not to the opponent!

• After the bot has surrendered with gg, stop the module timers. This has no real effect, because of how the timers work, but it is cleaner if the timer implementation ever changes.

• StrategyBossZerg::checkGroundDefenses() is slightly simplified. It’s still too complicated.

• Added UnitUtil::TypeCanAttack(UnitType): Can the unit type attack at least one of air and ground?

• Renamed the building manager’s validateWorkersAndBuildings() to validateBuildings(), since that’s all it does.

• Removed the utility function ClipToMap(position) in favor of BWAPI’s position.makeValid(). I hadn’t noticed it before.

• Removed the unused WorkerManager::setBuildingWorker().

• Removed the unfinished BuildingManager::addPendingBuildingTask(). It is superseded by the worker assignment changes.

• A comment in ProductionManager::executeCommand() notes a rare bug in "go gas until".

I have sent in Steamhammer 2.2 to do battle in AIST S2. I think I’ll take several days to test with terran and protoss, and to fix up the terran and protoss openings and any new bugs I find, before I release 2.2.1 for SSCAIT.

The new map analysis does not change Steamhammer’s strength, or at least if it does, I can’t tell yet. Experience has to teach me. Also, in between working slowly, adding too many new openings, and fixing too many old bugs, I didn’t finish the useful tactical skill that I wanted to add (I did start on it). Nevertheless, a couple of the bugs I fixed were doozies, and one of the openings I added shreds certain difficult opponents. I’m expecting version 2.2 to be modestly stronger than the current 2.1.4.

The scouting path. One of the last changes I made—I finished it up today—was to fix the scouting worker’s path around the enemy base. The inherited code from UAlbertaBot did not work well with the new map analysis. I ripped out the amazingly complex code that calculated waypoints around the edge of the enemy base, producing a looping path, and replaced it with a simple exploration algorithm. The change reduced the DLL size by about 5K, which shows how complicated the old waypoint code was.

I had to choose something simple, because I didn’t have time. The exploration algorithm works pretty much the same as the algorithm for exploring the map to find the last enemy buildings. Instead of looking through the whole map for places that have not been seen recently, it looks around the enemy base, checking each 320x320 map grid square. If it is to scout “once around” the enemy base, then it leaves once every grid square has been seen.

The new behavior has advantages and disadvantages. On the one hand, since it actively explores it is less likely to miss important buildings. It is often able to leave the base sooner because it can see everything quickly, and it doesn’t have to look at anything that the scouting overlord has seen. On the other hand, leaving sooner means that it misses what happens next. Also the irregular path around the base is not as good for evading enemies; it’s harder to catch a scout that is moving in wide loops. The drone sometimes gets stuck on buildings or mineral patches. And it doesn’t peer into the corners, because the 320x320 cells are big (that’s 10x10 tiles). I’m curious to see how good the scouting is in serious games.

In coming days I’ll be writing up the map analysis with details and posting a change list—the usual new version posts. I guess longer-term plans will be after that. And I’m watching the spam attack so I can turn on comments as soon as it ebbs.

I’m not entirely satisfied with Steamhammer’s zones and chokes. The bot plays reasonably enough, but I’ve started to think that the data structure is not an ideal fit.

Steamhammer uses zones for recognizing proxies and figuring out areas that are in need of defense. This is essentially a heuristic, “these locations are in some way close to each other for practical play purposes.” But nothing in the definition of a zone (or, as best I understand, BWTA’s definition of a region, or BWEM’s definition of an area) says that its parts are “close together”—they’re only connected without any intervening choke. It seems to me that to reason about things like “where do I need to defend?” it is better to analyze paths and distances rather than use zones as a rough shortcut. And in fact Steamhammer does check distances as part of its calculations; the zone is not enough information by itself.

Properly, zones and chokes are for reasoning about the topology of the map. “I can go this way,” meaning through this sequence of chokes, “or go around the long way.” Or on Andromeda “I can block this ramp and protect both the main and mineral only.” Steamhammer has the familiar graph data structure so you can do that reasoning, but it feels a little lacking to me, a little awkward and low-level.

I’m thinking that different or additional data structures might be better than what I chose. It’s easy to think of practical situations where it might be convenient to have more or different information pre-computed. What are zones, as such, the right abstraction for? If you’re following a high-level path, the zones are just places you happen to pass through, and you only care about them if something interesting is there. But you don’t care whether the “interesting thing” (like an enemy army) is in the zone, you care whether it affects your concrete path through the zone; maybe it’s too far away to matter; maybe it’s on the other side of your army, and you are sending reinforcements to join up. If you’re defending a choke, you commonly want to set up units to hit enemies as they exit the choke on your side, so you want to know distances from the choke exit. Similarly if you are deciding how far to retreat before making a stand. You want to know the defensibility of a choke, and it may vary depending on which side you’re defending (up the ramp is better) and other factors. And you want be able to do it fast if you’re making a complex calculation, like finding the best set of chokes to defend (in graph theory terms, determining an optimal cut set).

Well, when I get that far I’ll see it more clearly. I won’t rush into decisions that don’t matter yet. Just note that, though I put a lot of work into Steamhammer’s map analysis, if I find a better plan I will happily throw stuff away and do it over. I’ll probably throw away strategy boss work first, though!

I’m accomplishing things slowly for now, but that doesn’t stop me from laying plans—or rethinking my past plans. Rather than working hard, I’ve been adding new openings, including a couple that are quite different in idea from anything else in Steamhammer’s repertoire. New openings don’t help in the short run (they mainly make it harder to find the right opening), but I am looking ahead.

Anyway, given my slow progress and the decision to participate in AIST S2, here’s my changed plan for the near future (it should be stable at least until tomorrow). Rather than get Steamhammer 2.2 out at the end of SSCAIT, which I missed by a mile, I’ll release it after AIST S2 submission at the end of this month. Or possibly I’ll skip 2.2 and release 2.2.1 slightly later, because I’m again concentrating on zerg for the tournament and there may be fixes needed for terran and protoss. With people worried about shallow forks, I’m thinking about releasing source less often anyway.

As far as visible play changes goes, the tournament version has bug fixes, including a fix for the debilitating command jam bug that makes macro games ugly. And it has the usual fleet of minor improvements, and a couple which are not as minor. For a tournament I have to bring something more, so I’m aiming to add at least one strong and unexpected tactical feature. I have a shortlist.

In AIST S1 I lost a lot of time coping with the map Sparkle, and other maps caused trouble too. I’m not expecting difficulties in this edition. So far, I haven’t run into problems with any of the AIST S2 maps (well, not beyond the usual). I will run a lot more tests, but so far so good. Not that my expectations are particularly accurate, but I expect to be ready in good time.

Next: Longer range plans.

In Steamhammer, I made a change to construction that was supposed to fix 2 bugs, the delay in starting construction for some buildings, and the abandonment of drones whose buildings cannot be started (they sit idle sometimes for a long time before being sent back to work). I figured out a plan so simple that I thought it should work on the first try—but no, in reality it brought enough bugs for Noah’s ark. It was such a setback that my motivation faltered and I have been debugging desultorily. Everything is delayed further.

Meanwhile, AIST S2 tournament registration is opening. No announcement made it my way; I had to seek it out myself. I decided only a couple days ago that Steamhammer should participate again, though I haven’t tested it at all on the map Eddy. Even if I move slowly, the submission deadline is the end of February and I should be ready. It’s possible that tournament prep may cause more delays (last year it caused long delays; this year won’t be as extreme). I may or may not release the tournament version, depending on how it turns out.

I hope Steamhammer 2.2 will be worth the wait. The new map analysis should not affect strength much, though it will affect play to a certain extent. Some critical bugs are fixed, others are pending; if I get them all done, play should be visibly cleaner.

In between ASL 7, the SSCAIT round of 8, about 4 hours of video on DeepMind’s AlphaStar, and keeping up with Steamhammer’s games, I was watching Starcraft today nearly from dawn to dusk. Coding progress: Zero. Time to do something else for a while and write about it!

In SSCAIT, the hard-to-predict matches were PurpleWave-BananaBrain and Iron-Steamhammer. PurpleWave 3-2 BananaBrain was the expected close match. In the next round we can expect PurpleWave > SAIDA and Locutus > Iron, so PurpleWave and Locutus will fight it out in the semifinal. I think Locutus has an edge, but PurpleWave retains chances.

I was not surprised by Iron > Steamhammer, but I was surprised by Iron 3-0 Steamhammer. It was unlucky that it was so one-sided. When Steamhammer has ample learning data, it has a small advantage over Iron. On a 2 player map, the 2 hatch muta variant usually wins, but here Steamhammer played it on a 4 player map where it usually loses due to poor execution—Steamhammer didn’t have enough data to connect its past wins with 2 hatch muta to the map size. On other maps, the AntiFactory build wins 50% or a little more, and in this match Steamhammer was still casting about for ways to win and didn’t try AntiFactory. It’s because I knew that Steamhammer didn’t have enough data that I gave the edge to Iron. Steamhammer is likely to win in the next round and, as others have also predicted, drop out in loser’s round 4 to SAIDA.

Interestingly, commenters who predicted Proxy > Hao Pan were wrong. All the information I can find seems to indicate that Proxy has the upper hand over Hao Pan. Did somebody hit a learning transient?

AlphaStar in Starcraft 2 gives us a foretaste of what to expect from advanced neural network learning. On the one hand, they spent huge computing resources—weeks at a time of “many thousands” of simultaneous games with 16 of Google’s TPUs per player—to learn to play protoss versus protoss on a single map. On the other hand, AlphaStar came out of that work with exceptional micro and strong judgment, areas in which all Brood War bots are currently weak. Machine learning is the way to get strong judgment. But it’s not easy.

They say that AlphaStar plays with average APM around 280 and latency around 350 ms, both somewhat slower than human. That makes its strength more impressive. They didn’t say so clearly, but I got the idea that the 350 ms latency is for free: It takes that long to evaluate their deep and complex network, so they can’t react faster! They did not talk as much about how AlphaStar’s real advantage is not in speed, but in precision: It does not misclick (at least not harmfully). Humans have a tradeoff of speed versus precision; if you do something faster, you do it with more slop. AlphaStar is a little slower, but far more precise than a human, so in fact it stands higher on the speed-precision tradeoff. It should play better, given equal knowledge. Still, it certainly takes fewer liberties than a BWAPI bot.

I’ve thought through the SSCAIT knockout bracket. The upcoming match between PurpleWave and BananaBrain could go either way, but I think PurpleWave has an edge. If PurpleWave wins, then it is likely to defeat SAIDA in the next round, then an easier opponent in the following round. In the semifinal, PurpleWave would likely face Locutus and have chances but stand at a disadvantage. SAIDA is likely to cruise through the loser’s bracket. If SAIDA faces Locutus, it is a probable win. If it faces PurpleWave, then maybe it will have played enough games for SAIDA’s learning to find a solution, but if not, then PurpleWave will win again. In the other case, PurpleWave loses to BananaBrain in round 2. In this case it will likely struggle on to face Locutus in the loser’s final, and again stand at a disadvantage. SAIDA will cruise through the top, and the final will be between SAIDA and Locutus or PurpleWave. So I think SAIDA and PurpleWave are the most likely winners, with SAIDA as the best single pick because it has fewer likely ways to lose twice.

Steamhammer defeated Krasi0P as predicted, and faces Iron next. The match could go either way, but Iron has better chances. I think if Iron wins, then Steamhammer will likely make it to loser’s round 3 or 4 before dropping out. If Steamhammer wins, in the best case it might get as far as the loser’s round 5. Last year, Steamhammer lost in loser’s round 4, so the relative level of play seems similar.

In unrelated news, I’ve re-uploaded Randomhammer. It’s the tournament version, Steamhammer 2.1.4. The last uploaded version of Randomhammer was 2.1, so there are improvements that were previously only visible in zerg play. But note that the drop openings are not working properly. Drops are working in the development version, but I still have a bunch to do before I release it.

On the BASIL ladder, Steamhammer in early days performed poorly. But today Steamhammer ranks #8, ahead of KrasioP. If we skip the BASIL participants which are not in the SSCAI tournament (Krasi0 terran and ChimeraBot), that corresponds to place #6 on SSCAIT, just behind BananaBrain, as compared to Steamhammer’s actual tournament finish at #11. The performance corresponds in general to Steamhammer’s performance curve in AIIDE 2018, starting low and rising strongly, but seems even more dramatic.

Many bots have different rankings on BASIL compared to SSCAIT. Random bots are handicapped on BASIL by comparison, since the opponent knows the race ahead of time. There are other differences in rules, plus the environment can cause different reliability and possibly different behavior. For most bots, I think these differences should not matter much—though anything could happen for a bot with reliability problems. Am I wrong? Am I missing something that can make a big difference?

If I’m right, then the important difference is that BASIL plays more games, so learning bots learn more. Other than environment-specific bugs, I don’t know another way to explain big differences in rank, such as Killerbot by Marian Devecka being #19 on BASIL while it came in #7 in SSCAIT 2018: Killerbot is not a learning bot. Another difference (just to give a second example) is that BASIL ranks Ecgberht one step below Arrakhammer, rather than far below (SSCAIT #16 versus #33): Ecgberht is a learning bot.

Steamhammer has a surprisingly high crash rate on BASIL, over 6%. It doesn’t crash remotely that often on SSCAIT. I’ll have to look into that.

Here’s my answer to what major feature should be next?

My analysis of SSCAIT games said that most losses were due to poor strategy decisions (in the Steamhammer sense of strategy, which is mainly “what should I spend on?”). Dan Gant did his own analysis of Steamhammer losses and drew the same conclusion. To be sure, some of the bad production decisions are deliberate choices to cover weaknesses in Steamhammer’s other skills. For example, Steamhammer makes an inefficient spore colony to defend against corsairs, rather than saving the expense and going with mobile units that have more uses, because its hydras are poor at air defense. Also, some losses are traceable to tactical mistakes. Even so, most losses are due either to bugs or to poor strategy decisions. Choice 1, strategy adaptation, is my pick for the next major feature. It does the most good.

I want to work on the ops boss too, but it’s too much; I can’t do everything at once. I will miss its interesting skills. The ops boss is a prerequisite for most of the sneaky tricks, flexible tactics, and multi-step plans that I have in mind. Going that way would make Steamhammer’s play more fun.

My goal is not to win the most games in this year’s tournaments, though I wouldn’t mind. I want to make the most progress toward my end goal, an imaginary Final Steamhammer that is strong in every aspect. It just so happens that making the most progress this year helps with making the most progress in the long run. Last year I found that working on macro improvements as I had been was no longer helping; Steamhammer’s tactical and micro weaknesses were dominant, so that improving an area that was already relatively strong made no visible difference. If I made a macro improvement that I thought was big, or one I thought was small, either way Steamhammer’s performance stayed about the same, because it was losing games for other reasons. That meant I could not measure my progress! I had to concentrate on immediate improvements to be sure that I was getting anywhere at all.

This year, tactics and micro are still not strong, but are improved enough that they are no longer the weak point. It’s time to take another loop around the spiral. Next year, if not earlier, I’ll reevaluate and likely bend my course again.

I laid out a 3 phase program for strategy adaptation. My plans change often, so you can be sure I won’t carry through exactly as advertised. Given my past rate of progress and the number of side features I throw in, I doubt that the year is enough time to finish all 3 phases. Still, I should get a lot done and make big improvements.

Speaking of side features, commenters who wanted specific fixes are not entirely out of luck. I can’t do deep reworking of tactics like last year, but I will patch some of the big weaknesses. Lurkers will grow bigger brains. Units will gain at least a limited ability to foresee threats and route around them. I’ll see what I can do about losing units piecemeal while retreating. Stuff like that. Plus I’ll add some skills purely for fun, maybe queen support. Can’t let things grow dull, it’s bad luck—er, I mean, bad for motivation.

Anyway, next up is Steamhammer 2.2 with a variety of fixes and improvements, and without BWTA—good riddance. It will be out when the worst bugs are squashed. After that might be 2.2.1 or 2.3 with incremental changes to fix any fresh bugs and to help with big weaknesses. Strategy adaptation is a big enough change that it will probably deserve the name Steamhammer 3.0, but it will be a while before 3.0 appears. Early versions of strategy adaptation are likely to play worse than current Steamhammer, because it will take time to whip it into shape.

I predict that Steamhammer will score 4 wins and 3 losses in its last 7 games in the SSCAIT round robin phase. Its remaining set of games has an excess of opponents that give it trouble. Let’s see how accurate I am!