Starcraft AI blog

AIST S3 completed. Round up the usual suspects, you can see the results for yourself. There are replays for all the games, but no video so far. The replays are labeled “Round 1” through “Round 14”; you can read the round numbers (I would have called them match numbers) from the bracket diagram. I like seeing all the results at once, but if you prefer to follow the tournament without spoilers, you could download the replays at the top of the page, scroll down no farther than the picture of the initial bracket to match up replays with the tournament structure, and watch the replays by round number.

I was especially interested to see LetaBot by Martin Rooijackers. LetaBot, it seems to me, is strategically strong but suffers from many bugs. Its standard game plan is a classic terran strategy, defend while building up a large army, then bury the opponent in an avalanche of units. LetaBot knows a variety of specific defenses against different cheeses, and has reactions to enemy moves that threaten its game plan, so I think its potential is high. This version is updated to BWAPI 4.4.0, so possibly it has more updates besides. Martin Rooijackers long ago promised a stronger version with bug fixes.

Versus Dragon: I especially wanted to see this match because of the players’ opposite game plans. Dragon plays an early attack and harassment style. In game 1 of the best of 3, at about 2:35 into the game, Dragon sent its first 2 marines and 5 SCVs to breathe some fire. LetaBot luckily scouted in the right direction and timing to spot the force as it left Dragon’s base, and LetaBot had a bunker on its ramp in plenty of time. Fireproof. Dragon sent the SCVs home right away, but inexplicably continued to produce marines that it posted outside LetaBot’s natural. LetaBot appeared to read the situation and react; it made vultures and goliaths—a strong force when the enemy has fallen behind early—batted aside the marines, and continued straight on to Dragon’s base. Dragon had been preparing medics and tanks behind the scene for its next wave of aggression, leaving itself open to LetaBot’s timing, though LetaBot was well ahead even without that opening. Luck plus skill, 1-0.

In the second game, LetaBot crashed on startup. 1-1

In the third game, Dragon tried the same plan again. LetaBot did not get the lucky scout, but cross positions favored defense. Dragon seemed indecisive, sending SCVs forward and back before attacking with 7. LetaBot floated its barracks after 1 marine, Dragon’s SCVs defeated the marine and moved into LetaBot’s base, some blocking while one built a bunker for the following marines. LetaBot pulled SCVs to defend, and with more it easily won the worker fight, but the bunker completed. LetaBot pulled SCVs out as far as the center of the map to keep marines away from the bunker, but eventually retreated and let 2 marines enter. But the timing was OK, another SCV pull past the loaded bunker kept further marines away while a tank came out and kicked over the bunker; not perfect defense but more than good enough. Fire resistant. Dragon’s SCV attack left it far behind LetaBot’s cheaper SCV defense; LetaBot seemed to understand and quickly won with a tank-goliath attack. LetaBot advances 2-1 on its strong defensive and counter-attacking reactions.

Versus Locutus in the next round: LetaBot crashed 2 games in a row.

Versus BananaBrain in the loser’s bracket: LetaBot crashed 2 games in a row.

So... there might be bug fixes, but we didn’t get to see because there were bugs. :-(

I don’t want to write up any games that might be from the SSCAIT elimination phase, since it wouldn’t be polite to scoop the official announcement. But there are some good ones. In particular, CherryPi is starting to show its full opponent modeling skills, which are more sophisticated than we could see in the round robin phase with only 2 games against each opponent.

So here is a close game from the round robin, Steamhammer versus LetaBot by Martin Rooijackers. Steamhammer randomly chose a 1-hatchery lurker rush, a risky opening which often beats LetaBot quickly. This time, Steamhammer got distracted chasing the scouting SCV and put on no pressure with its early zerglings, allowing LetaBot to bunker safely at the front of its natural instead of in its main. Often LetaBot overreacts to the threat of the early zerglings, which is actually slight, and leaves itself weak to the lurkers. Here it defended nicely.

Well, not quite nicely. A bunch of marines stood in front of the defenses and were slaughtered by lurkers outside detection range of the turret. But Steamhammer is no smarter. As soon as the way to the bunkers was clear, zerg became overaggressive with the lurkers and lost them quickly. One lurker stayed outside bunker range and drained terran minerals into repair for a while, but as soon as marine range research finished in the academy, it died too. Steamhammer had rushed to lurkers with a weak economy (see the worker counts in the picture), so after an even-ish combat outcome, terran was ahead.

Followup lurkers behaved the same, killing infantry that placed itself needlessly in danger, then placing themselves needlessly in danger and dying. LetaBot expanded much later than it should have, letting zerg catch up in economy. But Steamhammer had been frittering its army away while LetaBot continued to build up despite losses, so terran was still ahead.

Finally the terran push came. The 4 sunkens and small zerg force can only delay the inevitable; the natural will definitely be lost. Zerg has 4 bases and an adequate economy, so it can attack the terran ball from all sides, but chances to save the game seen small.

The rear-placed sunkens were highly effective, because LetaBot assaulted them without regard to losses. Marines funneled between the buildings, suffering both sunken hits and splash damage from tank fire. Scattered zerglings ran in from every direction, but SCVs kept the tanks repaired. Steamhammer kept sending more drones to mine the natural gas, while LetaBot had expanded and added to its SCV count, so zerg was falling behind in economy again.

A small number of terran reinforcements were intercepted by zerglings taking a strange path across the map. The terran attack started to become disorganized, with some units running into the zerg main before the natural was reduced. In the picture, the spread-out tanks are under attack from both ends, and in the minimap is an engagement between zerglings and reinforcing marines, preventing the marines from joining up promptly.

The zerg army remained tiny, but it was LetaBot’s turn to rush in pell-mell without organizing its forces. Without marines supporting the tanks, and with adrenal gland research finished to increase the zergling attack rate, the small number of zerglings finished them off easily.

With the slow-to-replace tank mass destroyed, Steamhammer had enough forces to stop any followup attacks. The turnabout was sudden. Zerglings broke into the terran natural while the double bunkers were unoccupied, and simultaneously 1 lurker and a handful of zerglings erased the terran third. There was a little more drama with a last-ditch battlecruiser as Steamhammer was slow to deliver the finishing blow, but in the end an unnecessarily massive zerg force battered down the undefended terran buildings.

It was another narrow comeback. Those make fun games.

Next: Analysis of solid versus daring bots.

Steamhammer’s round of 16 game in the SSCAIT was entertaining. It was played on Moon Glaive against Martin Rooijackers, the latest LetaBot. Steamhammer has played a bunch of games against this version of LetaBot, so I can roughly estimate by eye (without counting the games to be sure) that Steamhammer wins maybe 1/4 of the time or so. LetaBot is clearly stronger, but there is a chance of an upset. The round of 16 is single elimination, so the winner moves on and the loser is out.

Steamhammer 0.2 opened with its 2 hatch muta rush and LetaBot went rax-expand. The video doesn’t show it, but Steamhammer’s first 4 zerglings got 3 SCV kills between them. They sniped the SCV building the natural command center and 2 more that came to replace it before marines chased them off. That set terran back, though not decisively. Here the zerglings are escaping from marines that you can see on the minimap, and LetaBot is about to resume construction.

LetaBot built 2 bunkers in front of its natural for safety. Unfortunately for Steamhammer, the map positions meant that the bunkers were on the straight line flying path between bases, so Steamhammer’s bunker OCD meant that zerg could not harass. The mutalisks stopped and stared at the bunkers in a standoff. Nepeta in the video politely called it “containing” the terran, but since zerg played a rush opening and terran played an economic opening, zerg was falling behind with every passing second. The rush must do damage to win.

LetaBot already had a winning game when terran moved out. If the terran ball had stayed compact, the terran forces would have punched through all opposition and won on the spot. But LetaBot let its forces string out, and the mutalisks were—just barely—able to defeat the army in detail. (Watch Carsten Nielsen play. The protoss bot may be the champion of maintaining good formation with its zealots while attacking. Few bots can do it at all.)

I selected a mutalisk so you can see the zerg resources and supply. Steamhammer 0.2’s poor macro is showing; it expands too late and does not know how to build macro hatcheries, and it did not have enough hatcheries to spend all its income. Terran was economically far ahead and zerg was failing to keep up production, so it hardly needs saying that the next attack brought victory to LetaBot. (Macro is much improved in the current development version, though still not good enough. The current version would have crushed the attack with forces to spare, and would have still been in the game.)

An entertaining game, though more one-sided than it may look!

One of the stories of SSCAIT 2016 is that LetaBot (playing under its author’s name, Martin Rooijackers) scored easy wins over certain tough opponents with SCV rushes. Classic LetaBot used to play bunker rushes and recent LetaBot versions still sometimes performed SCV-marine rushes, so the rush opening should not have been a total surprise. But it worked perfectly against Krasi0 and even against micro-virtuoso Iron. The losers tried hard to keep their own SCVs safe, lost too much mining time, and could not keep up.

I approve. That’s the way to do it. If you find a weakness, exploit it ruthlessly and don’t worry about whether people look down on you as a cheeser. In fact, that is ZZZKBot’s entire modus operandi, and ZZZKBot is doing well with it, departing from its traditional 4 pool often and effectively with opponent-specific builds. Ruthless wins are your opponent’s way of telling you what you need to fix, and that’s good for everybody.

LetaBot’s rush looked similar to the rush we used to see from Stone, before Stone evolved into Iron. LetaBot pulled back its damaged SCVs into loving mutual-repair couples before returning them to the fray. I rather wish Stone were still playing alongside Iron. Stone would constantly remind other bot authors of the importance of good worker micro—worker micro is difficult (and I sure haven’t gotten around to it in Steamhammer), but it’s key.

These 2 pictures are from a game between Bereaver and the AIIDE 2016 version of LetaBot. It was a great game—Bereaver lost its natural and narrowly held its main over and over against LetaBot’s powerful attacks, until finally LetaBot ran out of steam and lost. LetaBot didn’t scout Bereaver’s third base. But I want to pick out a funny detail:

I dub this reaver The Little Tailor.

Seven at one blow! One marine lived and kept shooting until the next scarab got it. It’s good reaver targeting.

I’m done looking at code, but I have a bunch of final observations.

limitations

As written, LetaBot’s wall code can only plan walls with a barracks and two supply depots. In theory it might create a wall with a barracks and one depot, or with only the barracks, but the map would have to have a strange layout of unbuildable spots so that the later buildings fail to be placed during the search. Normally it will squeeze all buildings in, all in contact with each other, even if some are unneeded, because it places all buildings before checking whether it has a wall.

It looks easy to reconfigure to use another fixed set of buildings. SpaceArray already includes data for the command center (wall until you lift it off) and the academy. Walls including a factory are more common, and it looks simple to add the data for that. If you have the time for the extra calls to WalledOffAStar, you could do a more extensive search that considered different possible buildings and stopped as soon as it found a wall, so that no unnecessary buildings are included. Of course the choice of buildings interacts with the build order. If your build order has the factory late but you need the wall early....

If you know the size and form of the choke, maybe there’s a way to figure out the right set of buildings to wall it off, so that you don’t have to try different sets until you find one that works. It’s an idea, anyway. For protoss, simple heuristics would do pretty well: To close a wide choke as tightly as possible, start with gateway + forge. To narrow a wide choke without closing it, use pylons. To wall a ramp, use pylons. Of course LetaBot doesn’t have code for protoss building restrictions.

reusing the wall code

The wall code is complicated. It’s also fairly messy, showing the scars of a lot of surgery. Some of the rework may be due to changing goals as the bot’s strategy shifted, but I suspect that most of it is from the sheer difficulty of getting the complex calculation to work properly in real play. If I wanted the code for a project of my own, I would first take time to clean and tighten it, comb for bugs, and make the efficiency improvements that belong in a second draft. It’s unpolished, but I judge the code quality overall as within the normal range for an academic project done under the usual heavy time constraints.

Legalities. I didn’t find any copyright license info in the CIG 2016 version of LetaBot. Of course it’s not required! But authors who actively want their code to be reused should think about conditions. For example, academic authors probably want credit and might choose a license that allows reuse on condition that the author is credited. Creative Commons offers choices. Copyright laws are different everywhere, and international copyright is even more confusing, so it’s helpful to make things as easy as possible for those who want to get by within the legal system.

more uses for WalledOffAStar

WalledOffAStar takes a start and end location and looks for a path between them for a unit of a given size, staying within a bounding box, taking into account known buildings. If there is no path, then the way is blocked by buildings or terrain (there may exist a path that goes outside the bounding box). It is coded to work only for the buildings that LetaBot uses in its wall, but it doesn’t seem difficult to generalize. You could use it to check for walls that you suspect or fear might exist.

If one of your units is trying to move somewhere, and it hasn’t made expected progress, and it is near your own buildings, then you might want to use code like this to check whether you have accidentally walled it in. If yes, you can also use it to pick a building to lift or destroy to break the wall.

If you see enemy buildings near a choke point that you want to attack through, you can use code like this to see which of your units fit through, or how much the choke is narrowed. The result can inform whether you should try to destroy buildings as the first stage in the attack.

spawning inside or outside

I don’t see any attempt to judge whether units will spawn inside or outside the wall. Terran and protoss units as well as zerg larvae spawn in predictable locations relative to the building that creates them, so I think it would be a comparatively easy extension. For a wall that includes a production building, it seems important to know. On the other hand, there’s usually not much you can do about it when units spawn outside.

how I expected the wall code to work

When I heard that LetaBot uses A* to plan its wall, I imagined a different algorithm than it actually uses. LetaBot uses brute force: It places buildings in different arrangements and figures out whether the buildings form a wall by looking for a path through them. Humans plan a wall by spacial reasoning, not brute force.

I imagined an algorithm that’s sort of closer to the human method. First, identify a flat area that you want to wall and find the two edges that the wall should run between. Let’s say the edges are the top and bottom. We’ll use A* to place buildings in a best-first way. When you use A* to find a path, the cost of a partial path is g(x) the length of the path so far plus h(x) a heuristic estimate of the remaining path length. The wall we want is basically a path of buildings from the top edge to the bottom edge! Our h(x) will be the distance from the bottommost point of the bottommost building in the wall to the bottom edge. g(x) is a measure of how long the path is so far: It will be the sum of the heights of the buildings placed.

As LetaBot does, decree a maximum gap size and don’t allow any larger gaps between buildings. Place the first building against the top edge, respecting the gap size. The A* formula of g(x) + h(x) tells you which placement to try first. Place the second building against the first one, and A* again tells you which placement to try first, etc. You’re done when the distance to the bottom respects the gap size.

This is a more expensive version of A* than WalledOffAStar, but you only run it once so apparently wall-finding would take less work overall. Though you shouldn’t trust human intuition when it comes to run times! It’s likely that g(x) and h(x) would have to be tweaked for best results—why should my first idea be the best idea? As always, it’s just an idea.

Continuing from yesterday, here is how RecursiveWall places buildings to try to create a wall. It is of course recursive. It wants a vector of building types and a current search depth.

void BuildingManager::RecursiveWall(std::vector Buildings, int depth){

The call is like this. (The three bits of code here are in different places in the source.) The numbers representing buildings are used as indexes into the SpaceArray mentioned yesterday, which has the information needed to compute the gaps between buildings. I’m not sure why the two depots get different indexes into SpaceArray (which has the same data for both). Is it so they can be told apart in maps, so that building adjacency can be found? Anyway, depth is initially 0.

	  WallSound = false;
	  
	  std::vector Buildings;
	  Buildings.push_back(2);//Barracks
	  Buildings.push_back(3);//Supply depot
	  Buildings.push_back(4);//Supply depot

	  RecursiveWall(Buildings,0);

The code is full of implementation details that don’t matter at this level of discussion (and includes some redundant code), so here is pseudocode. CanWall() is a utility function to figure out whether a building can be placed at a given location. mapWall() maintains a 2D map of building locations. I should also mention, though I didn’t realize it until today, that WalledOffAStar() returns false if a wall exists and true if you can walk through, despite its name and some comments. It’s confusing.

RecursiveWall (vector Buildings, int depth) :
  if (WallSound) {                    // we found a wall
    return;                           // so stop the search
  }
  if (depth == Buildings.size()) {    // all buildings are placed
    walkable = WalledOffAStar (...)   // can we walk through?
    if (not walkable) {               // no, try lifting the barracks
      gate = WalledOffAStar (..., ignoring barracks)
      if (gate) {                     // can we walk through now?
        WallSound = true;             // yes, we found a wall
        BarracksWall = ...;           // record the building placements
      }
    }  
    return;                           // either way, we're done
  } else {
    int BuildType = Buildings[depth]; // next building to place
    for (int x, y inside the bounding box) {
      if (CanWall (BuildType, x, y)) {
        mapWall (x, y, BuildType, BuildType); // update data structures
        BWAPI::TilePosition thisTile = BWAPI::TilePosition (x, y);
        BuildingPlace.push_back (thisTile);
        RecursiveWall (Buildings, depth+1);   // recursive call
        BuildingPlace.pop_back();             // roll back updates
        mapWall (x, y, BuildType, BUILDABLE);
      }
    }
  }

Wow, it’s a little hard to follow even boiled down this much. WallSound is initialized to false before the call. So WallSound ends up true only if both the wall is sound and lifting the barracks opens it (so that the barracks is a functional part of the wall and not an appendix to a wall of supply depots). Older versions of LetaBot sometimes got that wrong and walled themselves permanently into their bases.

RecursiveWall does not know which of the buildings in its vector are the same, so if one building fails to place at any location it simply continues on to the next. As far as it knows, a good wall might still be possible with the remaining buildings. An optimization might be to prune the search appropriately when building placements fail. Is it too rare to matter?

Here’s what CanWall does, again in pseudocode. It is given the building’s type and proposed location and returns whether the location is good to build on. Buildings are required to be adjacent to an already placed building. It knows that the barracks is first and lets it be “adjacent to itself.”

CanWall (buildingType, buildingX, buildingY) :
  nextToB = false;       // adjacent to an existing building?
  for (int x, y in the building's footprint from SpaceArray) {
    if (outside the map) return false;
    if (not buildable) return false;
    if (covers Closest or Furthest) return false;
    if (useHighGround and this is not high ground) return false;
    if (buildingType == barracks) nextToB = true;
    if (adjacent to an already placed building) nextToB = true;
  }
  return nextToB;

The code runs the “adjacent to an existing building” loop even for a barracks. For efficiency, it could skip adjacency checks (the inner loop and thus the most expensive part of the code) once nextToB turns true, since it never goes false again. The compiler may be smart enough to lift the “is this building a barracks?” test above the outer loop, since it doesn’t depend on x and y, but it would be tidier to code it that way from the start.

Next: Discussion of walling code.

Today, a few low-level parts that RecursiveWall() relies on. As mentioned yesterday, LetaBot plans its wall to fit inside a bounding box around the center of the choke to be walled off. It finds the Closest and Furthest tiles from the original command center that are in the box.

First, the SpaceArray that stores the sizes of buildings. The information can be found under List of Unit and Building Sizes in Liquipedia. The top, bottom, left, and right numbers are pixel gaps that the building leaves along each side. It’s the basic data you need to figure out how tight a wall is. With the gap sizes of two adjacent buildings, you can find the total gap between the buildings and see which units fit through the gap. Here is a sample of the initialization code:

ExtraSpace SpaceArray[10];

	ExtraSpace Barracks;
	Barracks.Top = 8;
	Barracks.Bottom = 15;
	Barracks.Left = 16;
	Barracks.Right = 7;
	Barracks.width = 4;
	Barracks.heigth = 3;

	SpaceArray[2] = Barracks;

MaxGap() is the function that uses the SpaceArray to find the gap. You pass in x and y and it looks to see what’s there. If the location is at the edge of a building, it looks for a neighboring building, figures out the relative locations of the buildings, and does a bogglingly complex calculation to find the horizontal and vertical gaps between the buildings, in pixels. I didn’t try to understand the details.

// a 2x2 part of the walkable array
//check for gaps between each of the tiles
int BuildingManager::MaxGap(int x, int y){

And WalledOffAstar() is the function that determines whether a wall has been created inside the bounding box. For some reason you pass in Startx and Starty, which are always at the Closest location. WalledOffAstar() uses the A* algorithm to look for a path between Closest and Furthest, a path which a unit with horizontal size unitH and vertical size unitV can follow. If no such path exists, then there’s a wall across the choke!

bool BuildingManager::WalledOffAstar(int Startx, int Starty, int Ignore, int unitH, int unitW){

When I heard that LetaBot used A* in its wall planning, I imagined that it used A* directly to search for building placements. But now we can see the real strategy. RecursiveWall() tries a building placement and then calls WalledOffAstar() to see whether that placement constitutes a wall. No? OK, try the next building placement.

Next: Finally, RecursiveWall() proper, finding the wall.

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.

Games of Iron against different versons of LetaBot have been entertaining me. Iron has learned the same trick as Tscmoo of killing tanks by laying mines next to them. LetaBot often suffers unnecessary mine hits when it sieges up just as a mine triggers. On the other hand, LetaBot also has micro skillz and likes to kill mines after they trigger—I’ve seen it kill a mine with two fast-reacting SCVs!

The games go back and forth, but Iron has the upper hand for now. Iron has become strong against other bots. LetaBot could improve by sieging more cautiously, which is part of the terran technique of inching units forward to force a minefield. Or it could scan for mines. Scanning intelligently for mines is not that easy because the bot has to keep track of where mines are likely or possible, which seems like a lot of coding work to support a single skill.

in other news

Rob Bogie has uploaded MaasCraft (originally written by Dennis Soemers) to SSCAIT, and it plays like the replays I watched last month. MaasCraft is scoring poorly—the opposition is a lot stronger than in 2014. He also re-uploaded it, which sounds like an update. Is MaasCraft going to see major updates under its new ownership? I haven’t yet noticed any changes to its play.

PS Making slow progress on the website improvements. I chose a hard road for myself.

LetaBot does an elaborate inference of its opponent’s opening build order. A couple posts ago I found no scouting inferences by LetaBot—I missed it. Martin Rooijackers had to tip me off. Thanks! It’s already there in the AIIDE 2015 version. There’s a ton of code in all the bots and I didn’t read most of it, so I may have missed many inferences in other bots too. This one is kind of fancy and breaks my earlier conclusion that no inferences were “deep or clever.”

AIIDE 2015 LetaBot declares terran and zerg build orders that an opponent may play. I imagine that the current version also knows protoss build orders. But in any case, at least for terran and zerg opponents LetaBot can compare what it sees against the different build orders and find the best match.

A build order declaration looks like this. A zerg build order from BuildOrderManager.cpp:

void BuildOrderManager::NinePoolSpeed(){
	BuildOrder newBo;
	newBo.YourRace = BWAPI::Races::Zerg;
	newBo.RaceEnemy = BWAPI::Races::Terran;
	newBo.Creator = "Dennis Soemers Text mining. Manual adjustments by Martin Rooijackers";
	newBo.Name = "9 Pool Speed";

	BOpiece addPiece;
	addPiece.supply = 9;
	addPiece.Building = BWAPI::UnitTypes::Zerg_Spawning_Pool;
	newBo.BOpieces.push_back( addPiece );
	addPiece.supply = 8;
	addPiece.Building = BWAPI::UnitTypes::Zerg_Drone;
	newBo.BOpieces.push_back( addPiece );
	addPiece.supply = 9;
	addPiece.Building = BWAPI::UnitTypes::Zerg_Extractor;
	newBo.BOpieces.push_back( addPiece );
	addPiece.supply = 8;
	addPiece.Building = BWAPI::UnitTypes::Zerg_Overlord;
	newBo.BOpieces.push_back( addPiece );

	newBo.WeakCounterBy.push_back( "2 Rax FE" );
	newBo.StrongCounterTo.push_back("14 CC");
	newBo.StrongCounterTo.push_back("BBS");
	newBo.WeakCounterTo.push_back("1 Rax FE");

	BOs.push_back(newBo);
}

Some counter-builds are declared near the bottom. The AIIDE 2015 version does not use them.

LetaBot draws the build order inference in BuildOrderManager.onFrame() so that the inference can change from moment to moment as more information turns up.

	for(int j=0; j<BOs.size(); j++){
		std::vector<BWAPI::UnitType>  EnemyBuildingsCopy;
	  for(int i=0; i<InfoMan->EnemyBuildings.size(); i++){
		  if( InfoMan->EnemyBuildings[i].building->getType() == BWAPI::UnitTypes::Zerg_Hatchery){
			  if( InfoMan->EnemyBase != BWAPI::TilePositions::Unknown ){
				  if(  InfoMan->EnemyBuildings[i].position.getDistance( BWAPI::Position(InfoMan->EnemyBase) ) > 4*32 ){
			        EnemyBuildingsCopy.push_back( InfoMan->EnemyBuildings[i].type );
				  }
			  }
		  } else {
			  EnemyBuildingsCopy.push_back( InfoMan->EnemyBuildings[i].type );
		  }
			  
	  }

	  int BuildAvailable = 0;
	  int BuildMissing = 0;
		  for(int k=0; k<BOs[j].BOpieces.size(); k++){
			  if( BOs[j].BOpieces[k].Building.isBuilding() ){
				  bool isThere = false;
				  for( int m=0; m<EnemyBuildingsCopy.size(); m++){
					  if( EnemyBuildingsCopy[m] == BOs[j].BOpieces[k].Building ){
						  isThere = true;
						  EnemyBuildingsCopy.erase( EnemyBuildingsCopy.begin() + m);
						  break;
					  }
				  }
				  if( isThere ){
					  BuildAvailable++;
				  } else {
					  BuildMissing++;
				  }
			  }
		  }


	  int score = BuildAvailable - BuildMissing;
	  if( BestScore < score){
		  BestScore = score;
		  EnemyBo = BOs[j].Name;
	  }
	}

Compute a score for each build order. Add to the score (BuildAvailable) for each part of the build order that LetaBot has seen, and subtract from the score (BuildMissing) for each part it has not seen. The enemy is (LetaBot concludes) following the build order that gets the highest score. In case of ties, the first high score gets it.

It’s simple and probably jumps to conclusions sometimes, but if the build orders are chosen and ordered correctly then I think it could avoid jumping to dangerous conclusions that make LetaBot do something foolish.

In the AIIDE 2015 version, LetaBot uses the inferred build order to decide how many marines to train for its marine-SCV rush, but not for any other purpose. Openings that give zerg a stronger early army need more marines. From TwoRaxSCVRush.cpp:

	if( Broodwar->enemy()->getRace() == BWAPI::Races::Zerg){
	//get marines to build based on BO
	if( BOMan->EnemyBo == "9 Pool"){
		MarinesToBuild = 8;
	}
	//get marines to build based on BO
	if( BOMan->EnemyBo == "OverPool"){
		MarinesToBuild = 6;
	}
	//get marines to build based on BO
	if( BOMan->EnemyBo == "12 Hatch"){
		MarinesToBuild = 6;
	}
	//get marines to build based on BO
	if( BOMan->EnemyBo == "9 Pool Speed"){
		MarinesToBuild = 10;
	}
	}

The latest version of LetaBot surely has many more uses for the inferred build order.

Bottom line: It looks to me like an excellent idea for adapting your opening strategy to the opponent’s, as long as the opponent is playing a recognized good strategy. If the opponent plays a bad strategy, why worry? Against zerg there should be few problems caused by unscouted buildings. Even against terran or protoss, I have the feeling that there are ways to manage the uncertainty from unscouted buildings or ambiguous build orders. For example, for build orders that branch you can declare one build order up to the branching point and further builds along each possible branch.

Who’s coming in with the next tip-off?

Update: If you catch LetaBot playing on the SSCAIT live stream you may be able to watch the build order inference in action. LetaBot reports its conclusion at the top center of the screen; at the start of the game it is “Unknown”. For some reason it doesn’t seem to show up every game (maybe only games versus zerg?). The conclusion can be way off when the opponent plays something LetaBot doesn’t know, like “1 Hatch Lurker” when it has seen two hatcheries and no gas. (I guess it should subtract from the score when it sees buildings that are outside the build order, or some other cleverness increment.)

Martin Rooijackers sent me some information about his creation LetaBot.

Up through AIIDE 2015 LetaBot selected builds by learning, but now it has jettisoned learning and selects builds based on scouting information. LetaBot opens with a build that is safe against rushes and transitions to counter whatever it scouts—at least up to a point, it’s a work in progress. LetaBot now has “an extensive flowchart” (that’s how he put it) of terran build orders from Liquipedia. That makes it sound like LetaBot will make more than one transition if it thinks it should.

Rooijackers credits Dennis Soemers (author of protoss bot MaasCraft, which played in AIIDE 2014 and CIG 2014) with pulling the build orders out of Liquipedia, and says he got more build order tips from mapmaker CardinalAllin.

You can see why he might have wanted to change—LetaBot didn’t really benefit from learning in AIIDE 2015. An advantage of prior knowledge over learning is that knowledge is available from the start; you don’t lose games figuring stuff out. A disadvantage is that you can’t take special advantage of surprise weaknesses in the opponent’s play. And I notice how much AIUR wins with strategies that are objectively bad.

Ideally bots should both have prior knowledge and learn during a competition, of course. Prior knowledge says “here are the builds or strategies that work” and learning adds “and these are the particular ones that you should pick to gain advantage over this opponent/this opponent on this map/etc.”

I think that offline learning would be a good way to gain knowledge of builds and strategies, especially if you have vast resources like most of us. You don’t want to go with builds that are good, you want to go with builds that are good for you, based on your skills; that’s true for any player. So every time you make a tweak to micro that may affect your choices, be sure to spend a few cpu-years on offline learning to re-learn your openings from scratch. Should be no problem if you’re as rich as Google, and who isn’t?