Starcraft AI blog

BWAPI 4.3.0 (release page) was released on March 1. Already it warns “This version is known to crash a lot.” Looking at the commits since then, which fix a couple of simple pointer bugs, confirmed for me the impression that quality control was not up to full speed for this release.

The change log lists mostly welcome but minor items: Documentation fixes and clarifications (always valuable), 2 fixes that prevent kinds of cheating that I wasn’t aware of, and 4 bug fixes to correct crashes or wrong behavior. There is one more substantial feature, which is that latency compensation has been “rewritten from scratch with turn size awareness.” Looking at the issue thread, I see that the new code is generalized to work in more cases, and some known misbehaviors are fixed. And it notes that latency compensation is hard and it’s still nothing like perfect, which is hardly surprising.

If you’re running 4.2.0, obviously you don’t want to upgrade to a version that crashes often. But if you want to try it out, theoretically you should be able to just drop in the new BWAPI library. You might want to test whether any of the fixes affect your bot. To me it seems entirely possible that rewriting something tricky like latency compensation could introduce new bugs, and anyone who reports those will help everybody.

Steamhammer is still running 4.1.2, and I plan to move it to 4.2.0 soon. That’s more effort, because I have to switch compilers. It seems that the version that fixes 4.3.0’s new bugs will be 4.4.0 (rather than 4.3.1 as I would expect), and it should also be a drop-in replacement for 4.2.0. For now, my expectation is that I’ll run 4.2.0 for a while, and wait to see if 4.4.0 proves stable and is supported by tournaments.

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 story of AIST S2 is Velocirandom, the winner that struck by surprise. Locutus defeated 5 other opponents and looked strong, but it lost two matches to Velocirandom. How did Velocirandom do it?

Velocirandom plays random on SSCAIT, but chose protoss for this tournament where random is not allowed. Velocirandom is a cheese loving bot with tailored builds for given opponents. Here are the names of the enemy-specific strategies it was configured for:

Ecgberht	Protoss_ZealDTGoonT
Hao Pan	Protoss_ZealGoonT
LetaBot	Protoss_Zerglings
BananaBrain	Protoss_ZealDTGoon
Locutus	Protoss_ZealotT
MadMix	Protoss_FourGoonA
PurpleWave	Protoss_ZealotT
Steamhammer	Protoss_ZealGoon
tscmoo	Protoss_ZealotT

Velocirandom was specifically prepared for everybody who was there, plus LetaBot which did not compete (and was set to face the strangely named Protoss_Zerglings build, nexus first into zealots and dark templar). The only opponents it actually faced were Steamhammer, Hao Pan, and Locutus. I have not checked whether Velocirandom’s preparation for the other opponents was as good as for these three. But I think it’s likely that each build is a timing attack or exploit to take advantage of a weakness of specific opponents. That’s certainly how I read the choice against Steamhammer.

The openings have short names, but they are long and detailed build orders. The ones with “zealot” in the name, for example, make a fixed number of zealots at fixed times, then a fixed number of dragoons, and so on. The lesson of the tournament is that even the strongest bots still have weaknesses that can be exploited by a well-chosen fixed build order.

The Velocirandom DLL is about 3.5KB bigger than the SSCAIT Velocirandom that was last updated on 18 February. That’s a reasonable chunk of code, but not huge. In the AIST vods, organizer Nathan Roth speculated that it may have some transplanted Locutus dragoon micro code. That seems plausible to me.

It was a near miss for Locutus, which had a hard road and made all opponents but one look weak. Hao Pan also performed well. I was impressed with McRave’s PvP play (and it still has those deadly scarabs).

The good news for Steamhammer is that it maintained its performance from last year even as the field grew stronger (always one of my goals): It lost 4 of its 5 games and was knocked out as early as possible. In a knockout tournament this strong, that’s within the expected range, so it’s only a little disappointing. Still, with different pairings Steamhammer could have won a few matches. Knockout tournaments are unpredictable.

The blog is 3 years old today: The first post marched forth on 4 March 2016. As I write, there are 766 posts (roughly 2 every 3 days) and 3401 comments (more than 4 for each post).

Onward!

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.

Attempted spam comments fell to a more normal level today, less than 200 (sad that I can call that normal). Commenting is restored.

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