Starcraft AI blog

Let’s suppose there are two safe spots where you want to station overlords to watch for enemy movement, a nearer one A (perhaps near the entrance to your natural) and a farther one B.

    *     A     B
    1

Overlord 1 hatches. Of course you send it toward A. It’s slow, so it takes a while to get there.

    *     A     B
      --> 1

Then overlord 2 hatches. You could send it toward the next spot B, but that’s silly.

    *     A     B
    2     1

It’s faster to send overlord 1 from A to B and replace it with overlord 2 at A.

    *     A     B
      --> 2 --> 1

Humans do this kind of overlord shuffling all the time. Here’s a TeamLiquid post showing the overlord repositioning patterns of a few pro games. I don’t know of any bots that do it. It seems like it might be tricky, no? But in fact the problem of assigning overlords, or scouting units in general, to locations is an example of the mathematical assignment problem, and there is no shortage of known algorithms to solve it either exactly or approximately. I’m still thinking about how I want to solve it in Steamhammer.

Scouting in the presence of an enemy is not as simple. To do it optimally you’d have to understand how scout timings interact with possible timings of the opponent’s build, and consider the risk to the overlord from early marines, and take into account that an enemy that sees your overlord learns something about you too—and they might actively look for the overlord, humans often do (“if you’re at that base and scouting the most efficient way to the closest natural, your overlord will be here at this time; if I see it I found you, and if not, I ruled out one base”). The optimal strategy is surely a mixed strategy, meaning that you don’t play the same every game, and there’s no way it’s possible to calculate it on the fly. You have to either pre-calculate a plan or figure it out heuristically.

The major feature for Steamhammer 3.1 will be a new scout boss which will take care of scouting, detection, and providing vision. It’s next because it meets 2 needs: First, scouting must be improved for strategy adaption. You can only predict the opponent’s moves from what you have seen, and the current scouting does not see enough. As one example, the initial scouting overlord hovers in a fixed position over the enemy base, and some protoss bots are smart enough to hide buildings from it. Second, a major weakness in current Steamhammer is that it loses overlords at a high rate. Today, overlords for different purposes are controlled by different code, and only some of the code knows about avoiding dangers. An overlord being sent to watch over a distant base goes there in a straight line, and then so does its replacement and so on, and sometimes an overlord is unassigned from a task and simply stops in a random location. With unified control, overlords will both see more and expose themselves to fewer risks.

The scout boss will also simplify the codebase. It will centralize the functions of the current scout manager and the overlord squad, and of scattered code that controls squad detectors. I expect the 3.1 version to have less total code even though it will be more capable. It will definitely have simpler interfaces with the rest of the program, I have already implemented most of that aspect.

The current scout manager that handles early game scouting knows how to control one worker and one overlord, and that’s all. The scout boss will take command of all flying detectors (including overlords) and floating buildings (I want to add this feature soon), plus whatever units you assign to it. In the opening it will automatically send the second overlord to scout a different base. If you do BBS in the center of the map, you’ll be able to scout with both SCVs to find the enemy faster, as Liquipedia recommends. Many bots already have these skills, Steamhammer has lagged behind.

3.1 should not take as long as 3.0. Unless I fall to temptation and add more features.

When I rewrote Steamhammer’s scouting, I tested it widely and thoroughly. I’m disappointed to find out that it still hides bugs, though the bugs only show up in a few games here and there. I’ve seen a couple games where the scouting overlord stops in an empty base, when it should continue to seek the enemy. Plus there is one other bug.

Watch the game Steamhammer-Bryan Weber on the 4 player map Roadrunner, which shows a hard-to-notice but potentially fatal scouting blunder. Bryan Weber played 5 pool while Steamhammer made a hatchery first, which could lead to a build order loss. Bryan Weber’s overlord scouted the correct base first, while Steamhammer’s went in the wrong direction. The situation is bad so far, but Steamhammer’s scouting drone has a chance to make up for it. Watch it leave the base at 2:10 in the game, quickly spot the enemy overlord, and immediately turn around and go home. It looks like the smart inference paid off! The top base was known empty, and Steamhammer calculated that only 1 of the remaining bases was a possible origin for the overlord. The enemy base has been located, so the scout drone doesn’t need to look for it but can get back to mining.

The scout overlord of course wants to see what is in the enemy base. Check its path: At the same moment that the drone turned around, the overlord changed direction from the actual enemy base toward the empty bottom base. Steamhammer drew the wrong conclusion from the enemy overlord’s position. Somehow the “can this overlord have gotten from A to B by this time?” calculation ruled out the actual base A that the overlord came from to reach point B. A minute later, Steamhammer’s zerglings also aimed for the empty base, leaving its own base defenseless.

While this nonsense was going on, Bryan Weber skipped out on a chance to win over breakfast, then a chance to win over lunch, then a chance to win over dinner. It wasn’t hungry at all and chose to wait around instead. Steamhammer won the game despite a build order disadvantage and a scouting bug because the opponent played worse.

Why are there so many bugs? The overlord position inference worked (or correctly drew no inference) in every test I threw at it.

I decided to write up Steamhammer’s changes in parts. Scouting today, more stuff tomorrow. I wrote briefly about scouting improvements in September; here are the details. The scouting changes affect all races, though of course only zerg has an overlord to help. The overall effect of the changes is that Steamhammer collects more information sooner and makes better decisions, so it was worth the effort.

Steamhammer has suffered its usual ratings crash in the new version. I think the voters have the journalistic instinct to comfort the afflicted and afflict the comfortable, and top bots and new versions of well-known opponents count as comfortable. They say to themselves, “Let’s vote in a good challenge,” and in Steamhammer’s case succeed.

Even so, I’m satisfied with early results. I see plenty of familiar misbehaviors, and no surprise bugs. And play improvements are showing. For example, Microwave has opening learning, and learned that 5 pool usually beats Steamhammer’s default ZvZ opening mix. In Steamhammer-Microwave, Steamhammer played a gas-first opening that formerly would have lost instantly to the rush, but this time saw it coming and built a sunken in time to stay alive. It became a good game instead of a smash.

early game scouting

Classic Steamhammer scouting, from December 2016: Pick a base on the map, and send both the first overlord and the scouting drone to that base. It was a hack. The overlord waits there for the rest of its life whether the enemy is there or not, and the scouting drone keeps looking if necessary.

Good scouting: Send the overlord and drone to different bases. Redirect one or both depending on what is seen. Send later overlords to good locations to collect further information.

Steamhammer’s current scouting is in between. It uses only the first overlord and the scouting drone, and against terran doesn’t send the overlord because it still doesn’t understand how to keep it safe from marines. The overlord and drone go to different bases, so that the enemy is often found sooner. When the enemy base is located, the overlord changes its path if necessary to go there, so there is often a better view of the enemy’s play for a long time. If the overlord finds the base first, the drone either goes home or stops by to visit the base, depending on its orders.

I added only one clever feature, inference of the enemy zerg’s location from seeing its overlord. When Steamhammer sees an enemy overlord early in the game and the enemy base has not been located, it considers “what bases have I not yet scouted?” It calculates which of those bases the overlord might have come from, based on its position and top speed. If that narrows it down to one base, then “Bingo! Found you!” This doesn’t quite extract all the available information; it’s possible that seeing the overlord could eliminate one base and leave two possibilities, and Steamhammer doesn’t realize that. But that’s a rare case, and in practice the overlord sighting speeds up scouting fairly often. The feature was definitely worth adding, and it helps terran and protoss too.

I want a more general scout manager instead of the current one that is able to scout with one worker and one overlord. It should be: Dump whatever units you feel are free into the scout manager, and it will figure out how to employ them. I decided it was too much for now, but I’ll probably do it later.

middle game scouting

Most bots, I have noticed, scout only to see what’s up. Even Zia, which scouts in the middle game with a zergling, only sends the zergling to see stuff and doesn’t attack with it.

Purely out of orneriness, I decided to do middle game scouting differently. Steamhammer’s middle game scouting is reconnaissance in force.

When there are “enough” ground combat units for the main ground squad, Steamhammer redirects a small number of them into a squad named Recon. The choice of units depends on race, of course, but only certain ground unit types are considered suitable for Recon. The terran Recon squad can include medics, and there are actually remaining bugs in that. If the main squad loses too many units, Recon may be disbanded to join it.

Recon is another combat squad, and it gets orders to attack bases where the enemy is not known to be. Usually it discovers that the enemy is still not there, and it gets new attack orders. But if it sees enemy presence, then its orders remain the same; the combat simulator decides whether to attack or hold ground. Stray enemy units and naked expansions are at risk. If Recon holds ground too long, then its orders time out and it is given a new location to attack.

I added a couple parameters to squad behavior so that Recon can do its job better, while the main combat squad does its job as always. I’ll write that up tomorrow.

Recon usually moves around pretty fast and travels over most of the map, though it does get stuck sometimes holding ground. The effect of the Recon squad is that Steamhammer finds enemy expansions quickly and has much more vision of enemy army movement. It occasionally prevents expansions or catches enemy scouts or tears down misplaced buildings in the middle of the map, but my feeling is that that is less important. I’m curious to see how Recon copes with terrans that sow the map with spider mines. Recon does get dedicated detection when it is available, but the detector often lags behind. I may need to make changes if it struggles against spider mines.

other scouting-related stuff

• A new feature controls the damage of scouting misses, when the scout worker is lost before finding the enemy base. In past versions, that caused disastrously bad play when the early combat units came out: They scoured the map indiscriminately looking for enemy presence in unlikely corners, and were often out of position when the enemy came knocking. Now Steamhammer recognizes that is is likely to find the enemy in a starting base location, and looks there first. The enemy is found much sooner and the combat squad is out of position for a short time or not at all. It is more aggressive than Killerbot’s approach of leaving the combat units at home until the enemy is found.

• The gas steal works, though this version doesn’t use it. You can configure "go steal gas" and Steamhammer will find the enemy base and try to steal the geyser. Or "go scout" and "go steal gas", and the scout will steal gas and, if it still exists, continue to circle the enemy base. And some other combinations. Getting the gas steal to work for all races and cases was time consuming; the number of bugs was incredible.

• The previous Steamhammer version has a misbehavior when the scouting worker is on its way home: It stops to attack anything stationary that it runs across. It is the standard worker self-defense behavior popping up at an inappropriate time. Fixed.

• When doing worker harass on a map with other than 1 geyser in each main, there was a potential crash. It never happened, but I fixed it.

I wrote a couple posts ago about dissatisfaction with Steamhammer’s primitive way of inferring the enemy’s opening plan from scouting information. What is the right way to draw inferences from scouting? One kind is the hard inference or deduction from what you have seen, like “I saw the lair start, so the earliest mutalisks can be out is lair completion time + spire morphing time + mutalisk morphing time.” You can also draw soft inferences or likely guesses about what the opponent is planning, based on your knowledge of good play. “The opponent is blocking its ramp with a probe, I bet something cheesy is coming.” Maybe the opponent is incompetent and left a probe there by mistake, or maybe it is trying to fool you into scouting for a proxy gate, but cheese is likely.

Well, drawing soft inferences based on good play is beyond the state of the art for bots, because bots have little knowledge of good play. But there is a theoretically sound way to make every possible deduction from scouting information. It could even be useful, if you have a theoretical computer with infinite speed and memory.

It’s simple: Brute force it. There are only a finite number of build orders, and you can enumerate them. Cross out the build orders which are inconsistent with your scouting information, the ones where the enemy has fewer workers than you saw or doesn’t have an academy yet or whatever. Counting up the minerals mined places a particularly strong constraint. You’re left with a much smaller set of build orders that the enemy might be following. If you have a question like “what’s the earliest mutalisks could be out?” or “how many dragoons do I have to be ready for at time t?” then you look through the consistent build orders and find the one with the earliest mutalisks or the most dragoons.

The idea goes back to precomputing a catalog of build orders, which I wrote about in April 2016.

Can this theory be made practical? I think it can, by cutting it down and dropping the theoretical promise of finding guaranteed correct answers for all possible questions. Instead of all builds, keep a catalog of a small number good openings for each race, maybe between 10 and 50. Instead of exact build orders, you could store ranges of variation, like “second gateway between frames x and y,” or store preferred values and check goodness of fit—or some other simple abstraction. When you have enough scouting information, it will rule out most openings from your catalog, and goodness of fit may narrow it down further. Also, you know what questions you want to ask, so you can store the answers with each build, so that when you know what builds match what you see, there’s not much computing to do. Well, it’s a vague idea, but I hope you can make it out.

LetaBot uses, or formerly used, a related idea with a catalog of build orders. See LetaBot’s build order inference (also April 2016). A weakness of LetaBot’s approach at the time is that, when it saw something that the build order expected, it increased the score of that build order—but when it saw something outside the build order, it did not decrease the score. It might see 3 hatcheries and conclude that the opponent was following a one-hatchery build, because the extra hatcheries did not cause a mismatch. If LetaBot still uses this method, then I imagine it has been improved since then.

Next: Early experience with opening plan recognition.

I’ve been adding recognition of the enemy’s opening plan to Steamhammer, as part of the opponent model. Besides making the opponent model smarter, the OpponentPlan is directly valuable to the strategy boss. I’ve been concentrating on enemy plans that the strategy boss is clumsy in reacting to.

After writing recognition code for several plans, I already felt dissatisfied with how it works. It looks at buildings and timings, it counts bases, it notices if zerglings are out suspiciously early, all extremely basic stuff. “2 barracks and no gas, I know what’s coming next.” There is no “You should have a second pylon by now, where is it hiding?” and no “I see more zerglings than you can get from 1 hatchery, you must have 2.” Rich and complex inferences can be drawn from the game information, and the primitive code I wrote draws only simple ones.

So I looked at PurpleWave, which does opening recognition under the name of “fingerprinting”. PurpleWave tries to recognize specific openings for zerg and protoss: This is 4 pool, this is 12 pool, this is 10 hatch, etc. And the way it works is, at heart, the same as what I wrote in Steamhammer. It is written in a different style, but it checks almost exactly the same information.

The biggest difference is that Steamhammer does not try to recognize specific opening builds. I think there are too many, and some of the differences don’t matter. The OpponentPlan groups enemy openings into categories, like “this is a fast rush,” without distinguishing between 5 pool and other early pools, or even between 5 pool and 5 barracks and 5 gateway. 2 barracks no gas gets the same plan label as 2 gateways no gas. If you want to react differently to 2 barracks than to 2 gateways, that is for the strategy boss to figure out. I think the plan categories extract more information from the game and compress it into fewer labels for the rest of the code to handle.

Well, if PurpleWave gets away with it then I guess the primitive recognizers are good enough for now. Someday I hope to write a cleverer plan recognizer that draws the deep inferences, that (like a pro) knows when you’re trying to hide a base and triggers a goal to go look for it. Or that says “You’re proxying something and I don’t know what, but I don’t need to see it because the answer is to build turrets.”

I have improved Steamhammer’s early game scouting and added midgame scouting. It’s far short of human scouting skill, but much improved. The first overlord and the drone scout cooperate to locate the enemy base as quickly as possible, and the overlord moves there to watch as long as it can. I also taught it to notice the enemy’s overlord and try to infer the enemy’s base location (ZZZKBot is the only other bot that I know has that skill). The effect is that Steamhammer finds the enemy sooner and collects more information. The midgame scouting ensures that enemy expansions are found, and in my testing often destroyed quickly.

I already find it hard to watch the release Steamhammer play on SSCAIT, since the new one is so much less clumsy at finding things. I think that Steamhammer 1.4 will be stronger than the current Steamhammer even with opponent modeling turned off, because of the improved scouting, slightly more flexible tactics to take advantage of the improved scouting, and a couple of key bug fixes.

It still doesn’t overlord scout versus terran, though. It has no concept that marines are dangerous or that cliffs are useful.

Overlord scouting, by the way, is a deep topic. Pros often send their first overlord straight to the closest possible enemy natural base. But they sometimes move the overlord on a complex path, trying to catch proxies, or avoid the enemy scout, or spot activity without being seen, or just to stay flexible so the overlord can move to its choice of locations depending on the situation. An overlord that always follows the most efficient scouting path is predictable, and the enemy may be able to save time by scouting for your overlord instead of directly for your base.

Working on scouting reminded me: There is a trick that terran can play to mightily confuse the opponent’s early scout. At the start of the game, make SCVs as usual, then when it nears time for the opponent’s scout to approach, lift off the command center and move it out of sight. Of course you have to build any supply depots or other buildings out of sight too, or away from your base (you could proxy 8 rax, or build your first depot in an empty main base). It can only conceivably be a good idea if there is another base close by to land the command center at, so the trick should be saved for maps like Electric Circuit which have an inside “backdoor” base near the main.

The opponent will scout every main base and see you at none of them.

This trick has been used in one pro game to my knowledge, Boxer versus Yellow from 2003, where the CC move was meant to keep the proxy barracks unknown; a base without barracks would have given it away. If it were a good trick it would have been used since then. It’s objectively bad, and human players who see that all bases are empty are able to figure out what happened. But in bot play, you might fool your opponent into doing something nonsensical or even cause it to crash.

When UAlbertaBot’s scout is looking for the enemy base and finds an enemy building in a starting base region, is assumes that that marks the location of the enemy base. Steamhammer inherited the heuristic and still uses it. So a low-cost way to fool these bots is to build a supply depot or pylon next to the ramp of an empty main base before it is scouted. Zerg could build an extractor at the empty base, if the gas is toward the ramp. 50% of the time, the scouting worker will find the decoy building first and will not scout other bases. Nobody has tried this trick yet, as far as I have seen.

PurpleTickles is a new bot in the Purple family. It plays a 4 probe rush, mining only with the 1 probe it makes with its initial 50 minerals. It never sets more probes mining, either, so the 4 probe rush hits hard but builds slowly.

On a 2 player map it’s a dangerous rush that gives trouble to strong defenders like Krasi0. The 4 probes arrive in a group and stick together to fight in coordination, so the defender needs skill to hold. The style is quite different from Stone’s SCVs, which act independently most of the time and gang up only when they spot an opportunity.

I haven’t seen a game on a 3 player map. On a 4 player map, the rush is naturally much weaker. PurpleTickles scouts with 2 probes and leaves 2 in the center to join in faster when the enemy base is located. Consider the 4 player scouting options for a 4 probe rush; there are 3 bases to scout:

1. Scout with 2 probes and leave 2 at home mining until the enemy is located. The worst case is when the enemy is at the unscouted base. That happens 1/3 of the time and has 4 probes arriving more or less simultaneously at the enemy. The extra minerals make the followup stronger.
2. Scout with 3 probes and leave 1 at home mining. This always gets 1 probe to the enemy base as soon as possible, and the others arrive more or less simultaneously. Compared to option 1 it hits a little harder 1/3 of the time in exchange for a slightly weaker followup.
3. Scout with 4 probes, sending 2 to one base. Compared to option 2, it hits harder 1/3 of the time when the double probes reach the enemy first, and the followup is a little weaker again.
4. Scout with 2 probes and leave 2 in the center, the PurpleTickles option. The center probes can join the fight sooner than a probe at a base, whether it is the home base or an empty base. So there’s a 2/3 chance that the enemy is hit by 1 probe, then 2 more after, then another; and a 1/3 chance that the enemy is hit a little later by 2 probes, then 2 more after.
5. Scout with 3 probes and leave 1 in the center. The enemy is hit by 1 probe, then 1 after, then the final 2 probes.

Intermediate plans are possible, with probes mining part of the time and staged in different locations depending on the map distances, but these 5 seem to be the main options. I don’t see much difference between them, but the PurpleTickles option seems plausible if you believe that hitting as hard and early as you can is best, and that the followup is less important.

I noticed that the rushing probes choose their attack goals along a straight line from the base entrance. They are more successful when they arrive at one end of the mineral line and attack from one end to the other, when they face few enemy workers at a time. They are less successful when the minerals lie at right angles to the line from the base entrance, so that the probes aim for the center of the mineral line and meet many enemy workers at once. An injection of smarts might improve that.

PurpleTickles is moderately successful overall, but it does have wins versus Iron (Iron apparently suffered a bug and never built a barracks) and versus Krasi0. Notice Krasi0’s trick of building its depot and barracks in an out-of-the-way location so that the attacking probes never bother them. It seems like a clever idea versus a probe rush.

Yuanheng Zhu coincidentally uploaded shortly after with nearly the same strategy, though the code is unrelated. On a 4 player map, it scouts with option 3 above. It also crashes when its probes arrive at their scout locations, so we haven’t seen how well it plays yet.

Update: Yuanheng Zhu succeeded in playing one game versus Sungguk Cha. Maybe it works on 2 player maps? The strategy turns out to be quite different from other worker rushes: 1. The 4 rush probes initially attack mostly buildings, not workers, presumably to stay safe for the followup. 2. The bot does not send more probes to attack, but sets new probes mining. 3. It builds a pylon and forge in its main, then adds a pylon and cannons in the enemy base, switching into a cannon rush. Most cool.

Other good stuff to build in or near the enemy base are a shield battery and gateways. I’m sure bots will do that too one of these days.

Wow, it’s down to the wire on whether Steamhammer will make it into the final 16. Steamhammer has been scoring a little lower in the final third of the tournament, and as I write it is standing on the edge at rank 16. With 10 games left, I look at the opponents and expect 4 losses and 6 wins, probably not enough to hold rank 16.

But we don’t know until we know. In an unexpected loss to PeregrineBot (which it easily beat in their first game), Steamhammer suffered at least 2 different play bugs, including one caused by losing its initial scout before finding the enemy base. Gotta fix more bugs. Then it followed up with an unexpected win against Bereaver; the protoss had easily won the first game. Bereaver was careless with its early probe scout and lost it before zerglings spawned, and Steamhammer’s aggressive play caught it off guard. Without information on what zerg was doing, Bereaver did not make enough zealots to hold. Moral: That scout is important!

We’ll see what happens! Steamhammer plays sharply and is prone to upsets in both directions.

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

Yesterday I wondered what bots concluded from their scouting info. Today I try to find out.

I grabbed the AIIDE 2015 sources of 10 bots from Starcraft AI Competition - Data Archive. What inferences could I catch them drawing from scouting data? There’s a ton of code and I didn’t read most of it, so I may have missed a lot. Here’s what I failed to miss.

Bots that I did not catch making any inferences: AIUR, GarmBot, LetaBot, Overkill, Skynet, tscmoo (though it’s hard to read), Xelnaga. I think all these bots are adaptive (except possibly Xelnaga), but they seem to adapt based on directly observed data tied to decision code, not based on separately drawn inferences. You could take adaptation choices as implicit inferences, if you like.

One inference I intentionally skipped over was inference of where the enemy base is, given that all but one starting spot has been scouted. I think it’s a common ability.

Bottom line: Adaptivity is common, but explicit inferences seem scarce, and those that I found are not deep or clever. Certain bots have special-purpose “You are XIMP, I will beat you like this” code or settings, but I want some bot to say, “You built that much static defense? Are you nuts or what? Please excuse me while I take the map... hmm, siege down the front or drop?” Maybe Killerbot does that?

IceBot

IceBot recognizes enemy strategies in MentalState.cpp (I love the name). Here it recognizes terran marine rushes based on the game time, the scv count, the marine count, and the buildings it sees. The bb == 0 check (no barracks has been seen) presumably recognizes that no useful scouting happened, or that it’s facing proxy barracks.

        bc = enemyInfo->CountEunitNum(UnitTypes::Terran_Command_Center);
        bb = enemyInfo->CountEunitNum(UnitTypes::Terran_Barracks);
        ba = enemyInfo->CountEunitNum(UnitTypes::Terran_Academy);
        vf = enemyInfo->CountEunitNum(UnitTypes::Terran_Factory);
        vs = enemyInfo->CountEunitNum(UnitTypes::Terran_Starport);
        scv = enemyInfo->CountEunitNum(UnitTypes::Terran_SCV);
        marine = enemyInfo->CountEunitNum(UnitTypes::Terran_Marine);
        tank = enemyInfo->CountEunitNum(UnitTypes::Terran_Siege_Tank_Tank_Mode);
        vulture = enemyInfo->CountEunitNum(UnitTypes::Terran_Vulture);

        if (Broodwar->getFrameCount() <= 24*60*2)
        {
            if (bb > 0) STflag = TrushMarine;
        }
        if (Broodwar->getFrameCount() <= 24*60*2 + 24*30)
        {
            if (marine > 0) STflag = TrushMarine;
        }
        if (Broodwar->getFrameCount() >= 24*60*3)
        {
            if (bb == 0
                ||
                (bb >= 2 && (vf == 0 || bc == 1))
                ||
                (scv > 0 && scv <= 11))
            {
                STflag = TrushMarine;
            }
        }

IceBot has similar code to recognize zergling rushes. The protoss code is the most elaborate, recognizing 6 different protoss strategies. In MentalState.h is the enumeration of all strategies it knows of, though it doesn’t seem to recognize or use all of them.

	enum eStrategyType
	{
		NotSure = 1,
		PrushZealot,
		PrushDragoon,
		PtechDK,
		PtechReaver,
		BeCareful,
		P2Base,
		PtechCarrier,
		ZrushZergling,
		Ztech,
		Zexpansion,
		TrushMarine,
		Ttech,
		Texpansion,
	};

Tyr

Tyr makes an attempt to infer something about its opponent’s strategy, though it doesn’t try hard. The possible strategy classes, from ScoutGroup.java:

	public static int unknown = 0;
	public static int zealotPush = 1;
	public static int cannons = 2;
	public static int tech = 3;
	public static int defensive = 4;
	public static int besiege = 5;

With several rules like this to detect protoss strategies:

				if(gatewayCount >= 2)
					opponentStrategy = zealotPush;

Curiously, an expanding opponent is under the “tech” strategy class.

				if(nexusCount >= 2)
					opponentStrategy = tech;

This version of Tyr can classify a terran strategy as “defensive” or “unknown”. It doesn’t have any rules for zerg strategy. The “besiege” strategy class is referred to once in the rest of the code but is never recognized.

UAlbertaBot

UAlbertaBot seems to draw few inferences, but it knows to suspect cloaked units as soon as it sees a Citadel of Adun—it doesn’t wait for the Templar Archives. I didn’t notice any sign that it suspects mines when it sees vultures or lurkers when it sees hydra den + lair. From InformationManager.cpp:

bool InformationManager::enemyHasCloakedUnits()
{
    for (const auto & kv : getUnitData(_enemy).getUnits())
	{
		const UnitInfo & ui(kv.second);

        if (ui.type.isCloakable())
        {
            return true;
        }

        // assume they're going dts
        if (ui.type == BWAPI::UnitTypes::Protoss_Citadel_of_Adun)
        {
            return true;
        }

        if (ui.type == BWAPI::UnitTypes::Protoss_Observatory)
        {
            return true;
        }
    }

	return false;
}