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.

A new version of Iron has been uploaded. It’s definitely different; the .dll file is about 25K larger, which makes it about 1.6% larger than the previous version. That’s a significant amount of code. But what is new? I played a few games and compared the binaries briefly, and so far I haven’t identified any specific differences. I searched them thar intertubes for discussion online, and came up empty. Does anybody know? I can’t tell whether it’s new code, or something like a difference in compiler settings that has no effect on play.

When I played Steamhammer versus Iron, the games went as I expected. Nothing was visibly different. I also played the 2 Iron versions against each other, though only for 2 games. They played exactly the same opening, with only the usual small timing differences caused by different starting positions and such. I could not identify anything new in the play. Each version won 1 game. To me, they looked the same.

Maybe somebody has heard from author Igor Dimitrijevic, or has more time than I do to compare for differences.

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!

As I write, SAIDA has fallen to #4 on SSCAIT; more and more opponents are finding the limits of SAIDA’s build adaptation. It seems that the secret to defeating SAIDA is to find a timing that SAIDA is not ready for. Apparently it matters less what units you make, and more whether SAIDA knows how to adapt its build to counter the timing you intend to hit—whether early or late.

Krasi0 in December was the first terran to find a reliable plan, a tank push timed before SAIDA was ready. Another idea to try would be the scary fast 8-8-10 vulture rush with a proxy factory, which I think ought to get a vulture into SAIDA’s base at around the same time that SAIDA’s own factory finishes. So far I haven’t seen any terran bot build a proxy factory.

Top protoss bots found holes in time to beat SAIDA in the SSCAIT annual tournament. Locutus denied scouting and sent dark templar from proxy gates, while PurpleWave alternated between arbiter rush and carrier rush, both successful. The variety of plans makes me wonder how many other plans would work!

Now zergs have started to catch up. Tscmoo zerg and Velicorandom zerg have beaten SAIDA with different early hydralisk rushes, and today Microwave beat SAIDA with 3 hatches before pool into hydralisks, a late timing. SAIDA did its vulture runby and killed a bunch of drones because Microwave had only drones to defend, but did not recognize its golden opportunity for a bunker rush—I guess it only does that against protoss nexus first. So Microwave overran it with too many hydras. Has anybody repurposed a ZvZ 1-base mutalisk build? I haven’t, but I suspect it might work too.

The SAIDA team’s stated goal is “to develop the first starcraft AI which can defeat a professional human starcraft player so as to improve our AI technology.” They haven’t succeeded yet, so I have to assume that they are still working. (Here is a game Best offracing as zerg versus SAIDA that shows they have far to go.) I am guessing that SAIDA’s next appearance will be in AIIDE 2019, and that they will have a deep learning plan recognizer or plan adapter whose holes will be smaller and much harder to exploit. I’m sure they will be collecting the opponents that beat them as test victims. Hmm, defeat SAIDA now or save up your secret weapons in hope that they will still work in AIIDE?

Tscmoo zerg was reuploaded today and plays at least 2 crazy new rushes. The one that caught my eye was a hydralisk rush that has defeated SAIDA 3-0 so far: Tscmoo opens spawning pool on 8 supply, then 7 gas, 6 hydra den, and sends 1 drone to scout (which may or may not ever return), leaving 4 to mine both minerals and gas. Then it sends out unupgraded hydras as fast as it can! It constantly juggles drones onto and off of gas, stopping gas as soon as the available vespine goes over 50. 4 mining drones are not quite enough to produce hydralisks without losing the occasional larva spawning opportunity, but Tscmoo comes as close as it can. (I have a source that claims you need 6 on minerals and 1 on gas to produce hydras non-stop from 1 hatchery. I haven’t done the measurement myself, but I’m pretty sure that 5 or 6 drones total are enough if you can juggle the gas like Tscmoo.)

Here are the 3 wins over SAIDA. Maybe SAIDA looks at Tscmoo’s base and concludes “I see a hydra den, therefore it is not a fast rush and I have nothing to worry about.” Or maybe SAIDA doesn’t worry about fast rushes at all, since its worker defense is so strong, and concludes “the drone count is low, I have nothing to worry about.” In any case, SAIDA continues with its usual greedy build and falls into a hole when the hydras appear and sweep away the first marine and first vulture. The worker defense skills against zerglings are no use, and SAIDA does not appear to adapt its build order at all. In the one game where SAIDA was not overrun altogether, its build got discombobulated and it let thousands of minerals stack up as it tried to counter the hydras with tanks—then lost to mutalisks. The 3 games show no sign that SAIDA was trying to adapt to the danger.

• 1. on Heartbreak Ridge - the first game, where SAIDA massed tanks
• 2. on La Mancha
• 3. on Jade - the latest and shortest game

The hydra rush is genuinely crazy. It can only work against a greedy build like the one SAIDA thinks it can get away with (and usually can), and then only if the opponent doesn’t understand what’s happening and adapt. Tscmoo also tried the rush against terran Tyr by Simon Prins, which played a slightly less greedy build and won. All that was needed was to keep making marines.

The hydra rush is unlike any strategy I have seen before. It is also not efficient as played. It didn’t take me long to code up a small family of related rushes to try out in Steamhammer. I got one version that starts the hydras at the same time as Tscmoo and produces them faster, and another that starts them earlier and still produces them faster (at the cost of needing to do more damage to be able to transition to a midgame build). Plus in some circumstances you can increase the punch by mixing in a few zerglings. I will likely end up keeping 2 or 3 variants permanently, for occasional use. It will be a fun challenge to get strategy adaptation to use them at appropriate times.

Still next: Longer-term plans for Steamhammer. It is taking me longer than I expected to gather my thoughts.

Update: I tested one of my variants, which I named 7-7HydraLingRush, against a few opponents. Though stronger than Tscmoo’s build, it scores less than 50% against the built-in terran AI—it is utterly weak against an opponent that makes units early. But—I love the contrast—it also breaks Iron bot like a toothpick. In a typical game, Iron smells it coming and walls in. Steamhammer hammers through the wall, killing the barracks and/or both supply depots and any SCVs that come to repair, then repeats the performance on the mineral line and command center while Iron’s few units shy out of range, unable to engage. Even in a test game where Steamhammer got confused and failed to attack, it held Iron in its base and won. I’ve configured it as a regular counter-factory opening; the development version of Steamhammer now has 6, up from 4 in the current release.

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.