Starcraft AI blog

Yesterday LetaBot found the center tile of the location it wanted to wall. Here is the outline of the rest:

1. Precalculate some stuff.
2. Initialize useHighGround to true.
3. Call RecursiveWall() to calculate a wall or fail.
4. If it failed, set useHighGround to false and call RecursiveWall() again.
5. Do a final check: Is the wall in time?

The precalculation is surprisingly complicated. It looks like the main results are Closest and Furthest tiles in a bounding box that the wall must fit into. Closest is the tile in the bounding box closest to the original command center by ground and Furthest is the farthest reachable tile in the box. Both are required to be walkable and buildable.

If LetaBot can, it builds the wall on high ground. On many competitive maps, the main is on high ground with a ramp down, and the wall definitely belongs on high ground. On some the main is on level ground and the wall can be placed freely. On a few, like Jade, the main is on low ground with a ramp up. In that case, LetaBot will look to build its wall outside the main if it can. I’m not sure whether that’s good or bad; my Brood War knowledge is lacking. Conventional wisdom is that an up ramp means you should expand early so you don’t have to fight up your own ramp, so maybe any wall is a mistake. And I have seen LetaBot lose on Jade when its wall proved easy to attack and hard to defend. Can some terran expert tell us more?

The final check looks to see whether LetaBot has already started to build without waiting for the wall calculation to finish. Wall planning is done in a separate thread because it may take a long time. LetaBot is prepared for the case that wall planning takes too long and the bot has pre-empted the wall by starting to build elsewhere.

	  //also check if the producmanager isn't already building
	  //because if this is the case then don't go for a wall
	  bool StopWall = false;
	  //check if supply depot already build
	  BOOST_FOREACH( BWAPI::Unit* building , Broodwar->self()->getUnits() ){
		  if( building->getType().isBuilding() &&
			  building->getType() != BWAPI::UnitTypes::Terran_Command_Center ){
              StopWall = true;
		  }			  
	  }

	  if( ProdMan != NULL ){
	    if( ProdMan->TotalTypeInQueue( BWAPI::UnitTypes::Terran_Supply_Depot ) > 0
		    || ProdMan->TotalTypeInQueue( BWAPI::UnitTypes::Terran_Barracks ) > 0){
              StopWall = true;
	    }
	  }

	  if( StopWall == true ){
	     WallSound == false;
	     WallCalculated = false;
	  }

The first check looks for any existing building other than a command center, and the second check looks into the production manager’s queue for either a depot or a barracks. If either check finds that it is too late, the bot tells itself that no wall is possible after all.

Next: Starting on the details of RecursiveWall().

LetaBot’s wall code is hard to follow, so I’ll take it in bite-size pieces. Today, deciding where the wall should go. It’s likely to be a good location for other defenses, too.

LetaBot can calculate how to wall off its main base with a barracks and 2 depots. It’s the classic terran wall. Unfortunately it doesn’t seem to recognize cases where fewer buildings are enough. The call to calculate the building locations for the wall is BuildingManager::WallOff(). If successful, it stores the calculated locations in the object for later use. From the BuildingManager class declaration in BuildingManager.h:

	bool WallCalculated;//True when the map calculation is done
	bool WallSound;
	BWAPI::TilePosition BarracksWall;
	BWAPI::TilePosition SupplyWall1;
	BWAPI::TilePosition SupplyWall2;

Below, I left out some confusing redundant code plus code with unrelated purposes.

void BuildingManager::WallOff(){

	BWAPI::TilePosition TileChoke;
		
	TileChoke = BWAPI::TilePosition( InfoMan->PosMainChoke );

It’s looking up a location recorded in the InformationManager. Here’s how InformationManager calculates it, at first naming the target choke BunkerChoke.

	BWTA::Region* natRegion = BWTA::getRegion( PosOurNat );
	BWTA::Region* mainRegion = BWTA::getRegion( PosOurBase );

	BWTA::Chokepoint* BunkerChoke = NULL;
	BOOST_FOREACH( BWTA::Chokepoint*  choke, BWTA::getChokepoints() ){
	   if( (choke->getRegions().first == natRegion && choke->getRegions().second == mainRegion) ||
		   (choke->getRegions().second == natRegion && choke->getRegions().first == mainRegion) ){
			BunkerChoke = choke;
	   }
   }

It walks through the choke points as reported by the Brood War Terrain Analysis library BWTA until it finds one which is between the main and the natural. In theory there could be more than one, but it doesn’t worry about that. The natural (at PosOurNat) is calculated earlier as the gas base which is closest to the main by ground distance. That should be fine for standard competitive maps, including maps with an internal mineral-only like Andromeda and Electric Circuit.

	if( BunkerChoke == NULL && mainRegion != NULL && natRegion != NULL ){
		int closestNat = 99999;
		BOOST_FOREACH( BWTA::Chokepoint*  choke, natRegion->getChokepoints() ){
		   if( BWTA::getGroundDistance(  BWAPI::TilePosition(choke->getCenter() ), OurBase ) < closestNat ){
			   BunkerChoke = choke;
			   closestNat = BWTA::getGroundDistance(  BWAPI::TilePosition(choke->getCenter() ), OurBase );
		   }
	   }
   }

If that doesn’t succeed because the map has no choke between the main and natural, it tries again. It could happen if the natural is internal to the main’s region or if the closest gas natural is farther and there are intervening regions (which is likely if the closest next base is mineral-only, as on Nostalgia or Korhal of Ceres). (It also fails on an island or semi-island map, but presumably LetaBot is not intended to play on those.) The code considers the chokes to the natural. It walks through these chokes and picks the one that is closest to the start location (OurBase) by ground distance. I’m not sure how well it works, but that’s what it says. It may mess up if there is an intervening region between the main and natural and the intervening region has another entrance. My first thought is to consider the chokes out of the main and do a path analysis: Go through the choke to the next region; from there, compute shortest ground paths to the possible enemy base locations; if none of the paths involves returning back through the main, then that choke is toward the enemy and may be worth walling.

   if( BunkerChoke != NULL){
     PosMainChoke = BunkerChoke->getCenter();
   }

If one of the two methods worked, then PosMainChoke is the center of BunkerChoke, all done.

Discussion. It looks like some maps will confuse the wall locating code, especially non-standard and old-school maps. If there is an internal natural, or an entrance to the main other than through the natural, LetaBot may do something unhelpful. For example, Alchemist (as played in CIG 2016) has two entrances to each base. It’s a 3-player map arranged as a big circle, so that the enemy is closer to one of your base entrances than to the other. This code will choose the natural base with its wall location sometimes toward the enemy and sometimes away—it probably should put the wall toward and the natural away (there are bases outside both doors). In another example, the old tournament map Bifrost has a front entrance to the main plus an internal mineral-only with a back entrance. Hypothetically, if we gave the internal base a geyser, then this code would build an unhelpful wall between the main and the internal natural, allowing enemy units that came through the back entrance access to the ledge above your mineral line. The right plan is to block the front and back entrances separately.

Even choosing a wall location can be tricky! LetaBot is optimized for the usual case, and nothing is wrong with that. It would be extra work for little gain to handle all cases well.

The name BunkerChoke is a hint: A wall is only one form of defense. The same choke may be good for other defenses, whether static defense or units standing guard. Even smart bots sometimes misplace their early defense. For example, watch Zia on Andromeda place early zerglings on guard well back from the ramp in the “choke to the main,” because it treats the high-ground mineral-only as a separate region. Or watch Skynet on Benzene misplace its early zealots, because there are two entrances to the main and Skynet does not realize that one of the entrances is blocked by map buildings. It may seem like an easy decision, but it’s hard.

I imagine that everyone who cares has seen the DeepMind and Blizzard to release StarCraft II as an AI research environment announcement. Apparently DeepMind’s Google power and AlphaGo prestige, plus the fact that it just plain makes sense for all parties, were enough to negotiate official support from Blizzard.

Of course details are vague for now. That’s how announcements go. The availability promises I see are that it will be open “to AI and Machine Learning researchers” and “be open and available to all researchers next year.” Does that include hobbyists, or only people with some kind of research credentials? I’m sure Blizzard will have concerns about cheating and will address them one way or another.

I originally wasn’t going to post about this, but one line caught my attention: “We recognise the efforts of the developers and researchers from the Brood War community in recent years.” To me it sounds like they realize that they may be undercutting Brood War and BWAPI, and hope to avoid hard feelings.

Anyway, this is good news for DeepMind, good news for Blizzard (though I think they should have thought of it on their own and done it themselves earlier!) and good news for AI. And except for stealing any good ideas they may publish, I plan to pretty much ignore it on the theory that it doesn’t touch BWAPI world.

Walls have a lot of uses in Starcraft. In defense, walls can keep units out of your base, narrow a choke so that it is easier to defend, or create a maze so that units have to take long paths. In offence, walls can trap enemy units to keep them out of the fight or protect your offensive placements. Liquipedia has pretty good articles on walls (see the links at the bottom of the Liquipedia article)—they have almost enough information to design wall-building code.

Here’s how LetaBot walls on Ride of Valkyries. This wall blocks zealots, but the probe can pass between the barracks and the depot. LetaBot can lift or land the barracks to open or close the wall whenever it wants (though in practice it only lifts the barracks once).

Here is a standard protoss wall on Fighting Spirit, from a game between ever)P(Say and linearity. The zealot and probe are stopping up small gaps in the wall so that zerglings cannot get through; if zerglings did get past, they would run by the cannon and into the main. A potential disadvantage of the wall is that zerg can try to bust with hydralisks, killing the wall from outside cannon range before protoss gets storm, which would harm the zerg economy but force protoss to make many cannons.

Another common protoss wall is the pylon wall to hold off vulture harassment, or sometimes to block dragoons or lurkers. Zealots, hydralisks and zerglings can pass through. This one is placed at the outside ramp of a side expansion on Fighting Spirit to stop vultures. Partial pylon walls outside the natural to narrow the choke are standard versus terran. In some locations, pylon walls between a nexus and a cliff partially protect the mineral line against vulture harassment.

Here is a zerg wall. Zealots or dark templar have to circle around the wall to reach the sunken, funneled through a narrow pass. Zerg has different wall designs, often using a hatchery plus an evo chamber or a hydralisk den. Protoss can try to bust with dragoons.

Next: LetaBot’s wall code.

Back in March, one of my early blog posts was about a game between Iron and Killerbot in which Iron successfully ran by Killerbot’s static defenses with vultures and SCVs and cleaned out the main. At the time Iron didn’t have the skills to seal the win, but it was a promising start.

Soon after, author Igor Dimitrijevic turned off the runby feature. I suppose his development strategy was to get the basics down before adding such a risky skill. But more recently the runby feature is back. I saw Iron do runbys in September already.

Here’s a game played today where Iron rolled Krasi0. Iron opened with two factories making vultures followed by a starport. Krasi0 made a barracks and then immediately expanded behind a bunker. With repair, the bunker can stop most early game harassment. It’s a good opening.

The moment that Iron gathered 3 vultures outside Krasio’s natural, it ran by the bunker and into the main, like so.

1 vulture was lost in the attempt. The other 2 stopped all mining in the main. Notice the kill count—that vulture got 8 SCVs and 1 newly-made Krasi0 vulture.

Meanwhile, wraiths from the starport flew over as they were made and also stopped mining in Krasio’s natural. Krasi0 specializes in defense, but could make only feeble attempts to ward off the attack.

Runbys still rule, especially if you have aggressive micro skills like Iron. Lessons for the defender!

1. If you see a runby coming at you, you may be able to pull workers to physically block the runby. Then your static defense will drive it off. It’s an advanced skill, though.
2. You can place buildings to restrict the path for the runby. Krasi0 could have landed its barracks and/or built a depot near the bunker. Stopping runbys is one of the ideas behind IceBot’s building placement. Killerbot also has anti-runby building placement, though it’s not enough in itself to stop a runby.
3. Krasi0 could have defended better after the runby. The SCVs were too fearful. Krasi0 needed to gather resources and produce defenders to defeat the few attacking units; it’s no use to retreat SCVs at the cost of resources needed to win. In recent years I notice that pros increasingly often leave workers at work when a base is under attack, instead of running them, and I assume that’s their reasoning.

Back when I was analyzing Skynet’s code, a class LatencyTracker came up. It sounds like it might have to do with latency in network games, doesn’t it? Latency is a confusing issue for bots, and Krasi0 asked me to look into it. It’s been on my to-do list ever since.

It turns out that LatencyTracker has nothing to do with network latency. It keeps track of the location and duration of storm and stasis. Oh well. :-(

It’s used in only a couple places in code like this. mUnit is of type BWAPI::Unit*. isStormInRange does what its name says: Is a storm calculated to be in range of the current unit? I’m not at all sure what the practical effect of this test is, since it looks redundant. Maybe it is working around a bug in some version of BWAPI, or maybe it is used with hypothetical units that BWAPI doesn’t know about. Or something.

bool UnitClass::isUnderStorm()
{
	if(exists())
		if(mUnit->isUnderStorm())
			return true;

	return LatencyTracker::Instance().isStormInRange(shared_from_this());
}