Starcraft AI blog

Today’s game is Steamhammer vs. WOPR by Soeren Klett on Andromeda. The game is not only epically long, it is epically clumsy on both sides.

WOPR plays a mech strategy that is slow with air defense. When Steamhammer opens with mutalisks, it flicks WOPR aside. This game, Steamhammer randomly chose to open with a low-economy lurker rush, and momentum went the opposite direction. WOPR had just enough scans to stop the initial lurker attack (a cleverer or more persistent attack might have succeeded). Then zerg strangely decided that its next tech choice should be hydralisks. Steamhammer had seen enough tanks that it should have known it was making a bad decision, so I think the error was not in analyzing the unit mix, but in choosing the tech target based on the analysis. Yesterday I rewrote StrategyBossZerg::chooseTechTarget() in a way that fixes 2 subtle bugs and improves the intended behavior, and I hope that will solve the problem. Anyway, WOPR eventually went on campaign and wiped out the zerg natural and main and the in-base mineral only, while cementing its huge lead by expanding across half the map. All that was left was to clean up a few underpopulated zerg expansions.

In the picture, the zerg economy remains weak and the army is hopelessly outmatched because it has suffered continual losses due to poor unit mix and poor tactics. In a human game, zerg could give up. 2 new terran expansions are visible on the minimap. Also notice that there are 3 evo chambers even though Steamhammer only knows how to upgrade with 2—it’s another bug that I fixed recently.

Like many old-school bots, WOPR believes it is finished when it has destroyed the enemy main. It does not seek out remaining bases, but sends its army toward (0,0) in the upper left. But WOPR does move its army to react to enemy units that it sees, and it continues to take bases and defend itself. Terran was maxed and zerg was extremely weak, with 8 surviving drones and the only tech a spire built at the last minute before the hive was destroyed. In the minimap, red is everywhere and blue survives in a corner. (Light blue on the minimap represents neutral buildings.)

Steamhammer knows how to recover. It slowly rebuilt its economy and tech and made mostly air units, especially scourge since it had seen battlecruisers. When the few zerg units showed themselves, an overwhelmingly strong column of terran units appeared and chased them away. Even constrained to ignore the zerg bases, terran had a big advantage. If zerg built up fully and also maxed its army, terran still had more bases and had been banking resources for a long time. WOPR only had to hold firm until the time limit was reached, and it would be awarded victory on points.

After the above picture, the battle started to get interesting. The scourge scored more victories than losses against the battlecruisers and cloaked wraiths. The first ultralisks were annihilated by tanks with +3 attack, but zerg was starting to do some damage. Of course WOPR had a huge reserve of minerals and gas, and it instantly replaced lost units. But then zerglings and one ultralisk found their way into the terran 9 o’clock base and destroyed it before it had quite mined out. Terran forces had been distracted by air activity at the center base, and most of the terran army remained guarding the unimportant upper left. It looked as though zerg had a chance after all; WOPR’s tactical reactions were not accurate enough. Notice the zerg supply continuing to increase. WOPR replaced many of its lost workers with combat units, which was correct play because terran had a big bank and didn’t need the income.

Steamhammer attacked the upper left natural and didn’t quite finish it off. Then the ray of hope started to dim. Steamhammer made too many guardians and was in danger of losing them all to the battlecruisers. Then hope brightened: WOPR played poorly and Steamhammer had the sense to follow up with hydralisks and scourge, and the battlecruisers exploded. WOPR targeted hydralisks though battlecruisers can one-shot the more dangerous scourge. Zerg destroyed the upper left natural. Then hope dimmed again: Steamhammer decided that the next target had to be, not an undefended base, but the upper left main where the giant terran army was hanging out. In the picture, the zerg army could not even get close before it was forced back by terran reinforcements appearing to its rear. Still, notice that zerg has retaken its main and mineral only and is now taking the formerly terran upper left natural. WOPR retook 9 o’clock and finished mining it out, but was otherwise not as economically active as it should have been. The zerg economy was in high gear and zerg was ahead in minerals but hurting for gas.

Both sides showed messy tactics and micro. Steamhammer made a few devourers for help against the battlecruisers and wraiths, but used them poorly. Zerg lost workers after taking the indefensible center base (which it had earlier kicked out of terran hands). Steamhammer also made many indecisive movements and often chose the wrong targets. WOPR played worse, though. It kept the goliaths in the corner surrounded by siege tanks, so the massive air defense was out of range of attacking guardians. Guardians slowly ate through the rows of tanks and finally killed the command center. Hydralisks, despite some confused behavior, kept terran reinforcements at bay though they couldn’t approach the mass of tanks.

Having killed the upper left command center, Steamhammer felt no need to engage the remaining terran army but set about the task of clearing the other terran bases. At least that part worked well. WOPR was less efficient and burned through its entire bank of minerals. Steamhammer won without ever maxing its army.

It was 46 minutes and full of events, many of which I didn’t mention. As one example, you can see on the minimap in the last couple pictures that Steamhammer built 2 macro hatcheries in a strange position outside its original base, where WOPR had taken the natural. I’m not sure what caused that.

By the way, this is the kind of game where either player would have benefited from being able to take island bases. If Steamhammer knew how to take islands, it could have made 2 more bases and would have recovered faster. If WOPR took islands and turreted them up, they could have been defended indefinitely by air units. To destroy a strongly defended island base you need a coordinated large-scale attack which no bot has the skills to pull off.

In AIIDE this year, Steamhammer scored much lower in the first 5 round robins (55%) than over the entire tournament (64% over 110 rounds). The difference amounts to finishing #10 instead of #13. It could be due to other bots getting confused by Steamhammer’s random openings and mislearning, but I think it is more likely to be statistical noise. Steamhammer happened to be unlucky early on, and the bad luck washed away over the long tournament. Data is cleansing.

SSCAIT has only 2 round robins. The 5 rounds of Steamhammer’s bad luck comprised 135 games compared to the 154 games each bot plays in the 2 rounds of SSCAIT, similar numbers. Some bots will be lucky and place a little higher than they would have in a very long tournament, and some bots will be unlucky. SSCAIT has a different purpose than AIIDE, so I think that’s OK. But it is a point to remember.

It’s difficult to judge by intuition whether a bot is getting lucky or unlucky. The majority of Steamhammer’s losses so far are “unlucky” losses against opponents that Steamhammer usually defeats. That is exactly what we should expect. The bots in the highest places (Steamhammer is currently #6 out of 78) don’t have many opportunities to lose to stronger opponents. Look at the crosstable and you’ll see that all the top bots have the majority of their losses on the right-hand side, against weaker opponents. No player is perfectly solid, we all lose occasionally due to our own mistakes; it’s a hard game.

That said, I have a clear idea of which games I see as unlucky results. For example, Steamhammer lost 0-2 to Flash this tournament, while in my test at home, Steamhammer beat Flash at a ratio of 4:1. In its losses, Steamhammer happens to randomly choose openings that don’t work against this opponent, or gets into less common situations where weaknesses pop up. Steamhammer’s first game against Flash is its worst game of the tournament so far; Steamhammer barely seems to be in the game at all, but simply falls down when poked. I should repeat that an unlucky result against one opponent doesn’t mean that Steamhammer’s overall result is unlucky. With 2 games against each opponent, lucky and unlucky results against given opponents are virtually inevitable. And it’s hard to judge by intuition whether the good and bad luck balance out.

Steamhammer does have one clear lucky win, Steamhammer > Microwave. Microwave learned that 5 pool on average beats Steamhammer’s ZvZ opening mix, and played it this game too. Steamhammer got lucky and randomly chose 9 pool speed, which counters 5 pool, and won after a long game. Steamhammer maintained its lead the whole game, but Microwave defended stubbornly and had to be ground down (it’s a good game if you like that kind of thing). How will the second Steamhammer-Microwave game go? I can’t predict! Microwave will have an edge if it keeps its opening, but after losing it may switch.

For the rest of the tournament, I predict 2 losses to Iron and 1 more loss to McRave. TyrProtoss is also likely to take its game, and if CherryPi adapts against Steamhammer in the same way it has adapted against other zergs that defeated it, then CherryPi will have an edge in its remaining game—and those are all the likely losses. If Steamhammer wins any of those 5 games, they will be lucky wins. I can’t predict the Microwave or Tscmoo games. Any other losses will be unlucky losses. It seems plain that the majority of Steamhammer’s losses for the rest of the tournament will be unlucky losses, losses against opponents that Steamhammer usually beats, and that is how it should be. Frequent unlikely chances outweigh scarce likely chances.

Next: An epic game.

A zerg creep colony has a base health of 400 hp. A zerg sunken colony has 300 hp. The way it works is, just when a creep colony finishes morphing into a sunken, it suddenly loses 100 hp. If it falls below 0 it doesn’t die, though; there is a floor of 1, and zerg healing has instant effect so the sunken colony completes with 2 hp (I think it takes 1 frame for the second hit point to be granted). When you start morphing a sunken, the UnitType immediately changes from creep colony to sunken, but the hit points are not removed until the morph completes.

Good players exploit this. I don’t know of any bot that takes advantage. Steamhammer certainly doesn’t. It could be hard to notice in a bot’s play, though. Does anybody know of one?

If you’re attacking morphing sunkens, then you should avoid doing unnecessary damage. If a morphing sunken will heal to no more than 100 hit points before it completes, and your units will still be in range then, and there is something else in the area worth attacking, then you should probably switch to attacking the something else. You will normally be able to kill the brand new sunken with one hit before it can get a shot off, saving the time it would have taken to inflict nearly 100 hp of damage. Depending on the situation, you may also be able to stop early if for some reason you’re pre-emptively hitting creep colonies before they morph. (I think most bots don’t waste their time on that, though.)

If you’re considering morphing a sunken, you may want to hold off if the creep colony has less than 100 hp left, or any low number that would leave the sunken helplessly weak. That may be best if an enemy attack is near; don’t waste 50 minerals on a defense building that will die instantly, get a pair of zerglings instead (if you have a larva and supply). On the other hand, if you don’t expect enemy action for a long time, you may want to morph the sunken immediately. By losing less than 100 hp in the morph, you are effectively speeding up zerg healing compared to the case of waiting to morph the sunken later.

It’s a strange behavior, and the considerations it induces are strangely complicated. You can only make the best choices if you have skill in seeing the unclear future. Taking all considerations into account is too hard, but I think the top bots have become strong enough that they could gain from taking into account the basic considerations.

Spore colonies have 400 hp and don’t show the same strange behavior.

Christian McCrave, author of McRave, is writing a building placement library named BWEB. BWEB is C++ and depends on the BWEM map analysis library by Igor Dimitrijevic, and within those constraints should be easy to add to a Brood War bot. It’s currently in beta at version 0.8, finished enough to try out but not yet thoroughly tested.

The idea behind BWEB is to place buildings not one at a time like most bots, but in compact predefined “blocks” of several buildings of different sizes. A protoss block will include at least 1 space for a pylon plus possibly large spaces for gateways and other large buildings and medium spaces for buildings the size of a Citadel of Adun. From McRave Blocks v1.2 (mentioned in the code):

You can think of a block as a sort of macro for buildings. There are 2 ideas behind it: First, building placement can be compact. Bots that place buildings one at a time often leave space around each building for units to pass through, wasting room and filling up the main base. (ICEbot is a notorious example; its buildings tend to spill out of the main.) BWEB only has to leave space around each block. Second, the library itself can be faster, because it has to choose the locations of a small number of larger blocks rather than a large number of smaller buildings.

Here is the key part of the API, how to get a location for a building:

	// Returns the closest build position possible for a building designed for anything except defenses, with optional parameters of what tiles are used already and where you want to build closest to
	TilePosition getBuildPosition(UnitType, const set* = nullptr, TilePosition = Broodwar->self()->getStartLocation());

	// Returns the closest build position possible for a building designed for defenses, with optional parameters of what tiles are used already and where you want to build closest to
	TilePosition getDefBuildPosition(UnitType, const set* = nullptr, TilePosition = Broodwar->self()->getStartLocation());

	// Returns the closest build position possible, with optional parameters of what tiles are used already and where you want to build closest to
	TilePosition getAnyBuildPosition(UnitType, const set* = nullptr, TilePosition = Broodwar->self()->getStartLocation());

It’s simple enough; ask for a building location, get one. BWEB also has a method to fetch a wall to place in the natural choke, and various utility and debugging methods.

A comment in the code may be a to-do list:

	// Currently missing features:	
	// - Counting of how many of each type of block
	// - Defensive blocks - cannons/turrets
	// - Blocks for areas other than main
	// - Variations based on build order (bio build or mech build)
	// - Smooth density
	// - Optimize starting blocks

thoughts

Gaoyuan Chen’s grid of protoss buildings is similar in idea to BWEB’s blocks of buildings. Unlike BWEB, Gaoyuan Chen places medium buildings in large spaces (and it doesn’t seem to be a problem). In the picture, buildings off the grid are enemy proxies:

BWEB seems suitable for protoss and terran building placement. Zerg building placement has different requirements and doesn’t seem like a natural fit with the block technique. Sure enough, in the BWEB code I see plenty of special cases for terran and protoss, and no mention of zerg. Of course, terran and protoss benefit from compact building placement. Zerg has less space to place buildings, since they have to go on creep, but also has fewer buildings to place.

How does BWEB ensure that the mix of small, medium, and large building spaces fits the mix of buildings you will create? I got the impression that if, say, you want to (or later in the game end up wanting to) create many gateways (large) and fewer than usual tech buildings (mostly medium), then BWEB will pre-allocate blocks with more medium spaces than you finally use. That doesn’t sound like much of a problem, though.

It’s new software, and many features you might want are not there, at least not yet. You may want tech buildings in remote parts of your base so they are safer and harder to scout, and production buildings near the ramp. You can do that with the “build closest to here” feature, but you may have to take extra care to place pylons ahead of time. The wall feature is very limited so far. The game gives us many uses for complete or partial pylon walls and for supply depots as obstacles. There’s no apparent support for proxies or gas steals; you’ll have to use your own code. The same for spotting pylons or blocking the opponent’s natural with an incomplete engineering bay. And of course there are inherent limitations to the idea of predefined blocks of buildings. A predefined block is never quite optimized for the exact terrain and matchup and build order and so on.

Still, it seems fast and easy, and it’s an improvement over what most bots do today. It should be well worth trying out for a protoss or terran bot, especially if you already use BWEM.

Thanks to the author Christian McCrave for letting me know about it!

Today I fixed the Steamhammer bug that sometimes had the building manager reserve minerals and gas and not release them. When I put in debugging code, the error turned out to be much more common than I suspected. In the first test game after fixing the bug, late game macro went from sometimes spotty to smooth and strong, and Steamhammer scored a win over McRave from a situation where it never had before. The bug deserved earlier attention than it got.

The error was that one caller of undoBuildings() skipped out on its responsibility to release resources when buildings were canceled or unable to be started. (undoBuildings() is a Steamhammer addition, so the bug does not affect UAlbertaBot or early Steamhammer forks, at least not in the same form.) I fixed it by moving the responsibility of releasing resources from the caller into undoBuildings() itself, adding these lines:

		// If the building is not yet under construction, release its resources.
		if (b.status == BuildingStatus::Unassigned || b.status == BuildingStatus::Assigned)
		{
			_reservedMinerals -= b.type.mineralPrice();
			_reservedGas -= b.type.gasPrice();
		}

Of course those callers that release resources have to be changed so they don’t. Not all of them are supposed to—sometimes the building is under construction and the resources are already released.

Don’t trust this bug fix too much. There could be more bugs. I left the debugging code in for now, so if there are more building resource issues, or mistakes in the fix, then I should find them before the 1.4 release.