Starcraft AI blog

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.

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

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.

The blog is under massive spam attack. I’ve temporarily turned off commenting. :-(

I’ll turn it back on as soon as possible. Spam waves usually don’t last long..

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’ve been trying out Steamhammer’s new map analysis for a while. It’s time to talk about it a little.

When I removed BWTA, the DLL file dropped to less than half its size. BWTA and its dependencies are big. It feels like a burden lifted. When I can get rid of BOSS too, the size will shrink again.

I settled on Zone as the name. The most straightforward replacement of BWTA::Region * is with const Zone *; I kept the pointer representation so I wouldn’t have to redesign any other data structures. Some uses only care about zone IDs and can be slightly simpler (and microscopically faster). Zones don’t have as many features as regions. A zone data structure has only a few fields; I don’t need anything fancy.

Unlike BWTA, there is no separate data structure to represent chokes. If you want to know how choke-like a place is, call the.tileRoom.at(const TilePosition & tile), which looks up the approximate distance between the walls around a given tile (as measured in 8x8 walk tiles, at least in the current version). At a main base entrance, a typical tileRoom is 9; at a natural base entrance, a typical tileRoom is 21; in an open area, tileRoom is much larger. The tile room is calculated at game start from the inset of each walk tile, accessible via the.inset.at(), which is the distance from the walk tile to the nearest unwalkable walk tile (BWEM calls this the “altitude”). The tile room algorithm uses a simple approximation to estimate the room from the inset in one pass.

After dropping BWTA, the first thing I did was run test games on random, mostly large and irregular, Blizzard maps. It was delightful to start up quickly without cached data.

There are still bugs on some maps, affecting the plan recognizer and the scouting worker’s looping path. The scout path needs to be rewritten anyway, it was never very good, but it will take time. I’m not entirely surprised, but still I didn’t realize how closely Steamhammer’s behavior is tuned to the exact regions returned by BWTA.

Still still next: Longer-term Steamhammer plans. Apparently “next” means at some point this year.

I spent a little time poking at CUBOT. I guess the name is a reference to the Sonic the Hedgehog character Cubot rather than the Android phone brand Cubot. It could also be an acronym for China University of Boring Ore Technology... or something like that. The author is given in the configuration file as Tommy Tang, and the name Zhentao Tang appears in the binary; they are likely the same person (choosing a Western name in a Western context is a Chinese custom, just as foreigners in China are expected to choose a Chinese name). I think this is the author:Zhentao Tang of the familiar Chinese Academy of Sciences, the institution that brought us CasiaBot among others. Yuanheng Zhu, author of the cannon bot Juno, is listed as a co-author on a few academic papers. I do not know what connection may exist between CAS and the China University of Mining and Technology that the author claims to be a student of at SSCAIT, but I get the impression that CAS is an umbrella organization so I’m not surprised if there is one (or he could have moved to CAS later). It’s hilarious that ResearchGate labels Zhentao Tang a Doctor of Theology, despite all his skills being in AI—it reminds me of the old joke where people create a series of ever more powerful computers and ask each the question “is there a god?” The last computer answers “Now there is.”

CUBOT is a Steamhammer fork, though there seem to be widespread changes. Or possibly it is a UAlbertaBot fork with extensive borrowings from Steamhammer. I can see from the configuration file and from text messages in the binary that a lot of Steamhammer 2.something code is included. Since the DLL is 3.5MB instead of Steamhammer’s 2MB, I looked inside. I see SparCraft (dropped from Steamhammer long before 2.0, one of the hints that it might actually be a UAlbertaBot fork), both BWTA and BWEM, Boost, and indications of machine learning code. Items that look like machine learning feature names suggest that the strategy boss has been swapped out for a learned version, something we’ve seen before in CAS Starcraft projects.

At the moment, CUBOT is ranked #42 with elo 1999, well below Steamhammer and UAlbertaBot by Dave Churchill. CUBOT’s play is... not very rich, strategically. If my interpretation of the binary is right, then the learned strategy boss does not learn diverse strategies. CUBOT does know 9 openings defined in the configuration file. It claims to choose among them by UCB like UAlbertaBot rather than with Steamhammer’s complex opponent model, and when I ran test games (and looked at the learned data), the claim looked correct (another hint). I think that is what the description means by “Adaptive weights toward different opponents.”

CUBOT is strangely sloppy in some ways. Some of the debug options, still included in the configuration file, do not work (including the basic game info inherited from UAlbertaBot). The openings like to collect 400 gas, no matter whether the opening needs 200 gas or 900. There are bugs both subtle and obvious. A subtle bug is that CUBOT will send a drone that is carrying minerals to mine gas, losing its 8 minerals; UAlbertaBot does that (a third hint), but Steamhammer carefully avoids it. An obvious bug is that it sometimes has trouble finding the last building on the map, even when it has already seen the building; neither Steamhammer nor UAlbertaBot has that bug.

I think I detect a family resemblance among the Chinese Starcraft projects that we have seen. They tend to have some machine learning feature, perhaps because of the national AI push. I get the idea that each project has a specific narrow goal, and aspects unrelated to the goal can be given short shrift. I see it in the way that the projects tend to display impressive amounts of hard work and ingenuity in some parts, and generous corner-cutting in others. It also seems that carrying on the project over time is not a goal. But this is all, of course, just my impression.

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?

Something is different this year.

Around February 2017 a rush of new bots swept in, inspired by the tournament that had just finished. Toward the end of the year, another rush arrived in time for the next tournament to start. But this SSCAIT edition doesn’t seem to come with many brand new bots, either before or after.

Why is that? Has something else become more popular? Has the level of competition risen so high that it makes beginners feel unable to compete? Or what?