Starcraft AI blog

ProductionManager::detectBuildOrderDeadlock() figures out when the bot is supply blocked so that it can order up supply if needed—for zerg, it orders an overlord. To tell whether the supply block is real, it needs to know not only current supply but pending supply—if supply is already being built, you’re not blocked. Here’s the critical code in UAlbertaBot:

  // are any supply providers being built currently                                                                        
  bool supplyInProgress = BuildingManager::Instance().isBeingBuilt(BWAPI::Broodwar->self()->getRace().getSupplyProvider());

  for (auto & unit : BWAPI::Broodwar->self()->getUnits())
  {
    if (unit->getType() == BWAPI::UnitTypes::Zerg_Egg)
    {
      if (unit->getBuildType() == BWAPI::UnitTypes::Zerg_Overlord)
      {
        supplyInProgress = true;
        break;
      }
    }
  }

Oh, but there is a tricky case for zerg. When an overlord is just hatched from its egg, it has unit type overlord but does not provide supply for a short time. The pending supply is unnoticed in the above code, the routine detects a supply block when there is none, and the bot orders 2 overlords in a row. The first overlord spawned turns into 2 overlords in around half of games. That is why Steamhammer 0.2 often finds itself with 3 overlords (providing 25 supply total, including the hatchery) when it is using 10 supply. The wasted minerals and larva ruin any opening that depends on precise timing, which is most zerg openings.

I solved it by counting supply by hand, including pending supply. Remember that BWAPI counts supply in units double what the game reports in the user interface.

	// If supply is being built now, there's no block. Return right away.
	// Terran and protoss calculation:
	if (BuildingManager::Instance().isBeingBuilt(BWAPI::Broodwar->self()->getRace().getSupplyProvider()))
	{
		return false;
	}

	// Terran and protoss calculation:
	int supplyAvailable = BWAPI::Broodwar->self()->supplyTotal() - BWAPI::Broodwar->self()->supplyUsed();

	// Zerg calculation:
	// Zerg can create an overlord that doesn't count toward supply until the next check.
	// To work around it, add up the supply by hand, including hatcheries.
	if (BWAPI::Broodwar->self()->getRace() == BWAPI::Races::Zerg) {
		supplyAvailable = -BWAPI::Broodwar->self()->supplyUsed();
		for (auto & unit : BWAPI::Broodwar->self()->getUnits())
		{
			if (unit->getType() == BWAPI::UnitTypes::Zerg_Overlord)
			{
				supplyAvailable += 16;
			}
			else if (unit->getType() == BWAPI::UnitTypes::Zerg_Egg &&
					 unit->getBuildType() == BWAPI::UnitTypes::Zerg_Overlord)
			{
				return false;    // supply is building, return immediately
				// supplyAvailable += 16;
			}
			else if ((unit->getType() == BWAPI::UnitTypes::Zerg_Hatchery && unit->isCompleted()) ||
					 unit->getType() == BWAPI::UnitTypes::Zerg_Lair || 
					 unit->getType() == BWAPI::UnitTypes::Zerg_Hive)
			{
				supplyAvailable += 2;
			}
		}
	}

I haven’t tried it to make sure, but I think another way to fix it would be to look for overlords for which unit->getOrder() returns BWAPI::Orders::ZergBirth and count them as pending supply.

I sent Dave Churchill 9 fixes (so far!). I’m planning to blog the rest 2 at a time, so I should be able to write up the remaining 6 over the next 3 days. Tomorrow: #4 has to do with squad orders and #5 with detecting building rushes.