Starcraft AI blog

Here is another valuable new Dave Churchill tool. It doesn’t seem to come with a name, but it is a web build order visualizer which uses BOSS behind the scenes. (I’m told it is a new and more powerful version of BOSS.) You enter up to 3 build orders, BOSS simulates them to find their timings, and it diagrams each one. The picture shows how inserting a drone into a 9 pool gas build, to get back to 9 workers, can delay the initial zerglings.

Partial instructions: + and - move a selected item up and down in the build order. X erases. X* erases the whole build. * selects the whole build. The various > and < buttons copy items between locations. In a diagram, hover over an item for info about its cost and timing.

It’s unfinished, and yet already valuable. Despite many limitations (and one bug I found, which has been fixed), I have already used it to analyze and optimize over a dozen builds. It’s much quicker than entering a build into Steamhammer and playing a game to get the timings. Some of the drawbacks in its current state:

• No instructions. I’m told it will get instructions by the time it’s finished.
• It does not support upgrades or research. That’s a big one.
• It does not support stopping gas mining (like mining 100 gas for zergling speed).
• It does not support pulling workers, even one worker to scout.
• It does not support the zerg extractor trick.
• If any of the 3 builds is invalid, you get a blank picture. There are no hints about what is wrong.

I found it best for low-economy builds. For zerg builds I tested to up 9 pool, its timings match well with Steamhammer’s execution. In overpool builds, only slightly slower, Steamhammer is able to insert an occasional extra drone or zergling without slowing down the timings. I expect that is because mineral locking makes mining more efficient than BOSS assumes. On the other hand, BOSS seems to believe that gas mining is a little faster than Steamhammer accomplishes it. That might be an issue of the time it takes to get workers into the refinery when it finishes. Even so, I can optimize a build (if it’s within the limitations) in the visualizer and then drop it into Steamhammer to see if further improvements are possible. It’s easier.

From a quick glance through the page source, it looks as though BOSS has been compiled into javascript using emscripten, so it executes in your browser. The visualizer works offline.

Good stuff already. How much better will it get?

Dave Churchill is feeding his students Starcraft as educational food. And he is coming out with new software to make it even tastier.

True to his tradition of naming projects with puns on “Starcraft”, he created a minimal starter bot named STARTcraft. It’s in C++ for Windows; he promises a Linux version later. Its selling point is that it is extremely quick and easy to set up and start coding. Installing Visual Studio 2019 is the slowest part, and after that it should take only minutes to get the bot running: Download the repo, unpack Starcraft from a provided link, open a VS project to code, or run a batch file to launch Starcraft and the bot. A couple of long videos (2 hours each), linked right in front on github, go over Starcraft AI in general, and over STARTcraft and BWAPI programming in particular.

Lately, I have the impression that most new bot authors want to start from scratch and create a bot that is entirely their own. It looks to me like STARTcraft is ideal for that. When you run it, it sends its workers to mine minerals, builds supply when necessary—and that’s all. Well, it also does a little debug drawing on the screen, and some basic map analysis on startup, and keeps track of when each map tile was last seen. There are a small number of utility functions in MapTools and Tools. It is basically just enough to show that the bot is working and give small examples of how to do things. In fact, the few things it does, it does in a simple way rather than an excellent way. If you end up creating a strong bot, you will have rewritten the existing behaviors. It will be all yours.

I’m an old-timer, so I may not be the best at judging what’s good for a beginner. In the past I have recommended starting with an open source bot that is already capable and full of features, but today capable bots are complex and may be intimidating to start with. STARTcraft is simple. With the videos as documentation and the code as examples, and with a working starting point, it is almost as easy as it can be, and yet leaves nearly everything to you. Even if you have unique ideas about architecture, the bot is small and you can refactor it into the shape you like. Recommended.

Steamhammer’s new resource tracking code is short and largely independent of the rest of the program, so I decided to release it for anybody to borrow. If your bot is C++, you should be able to drop this in with little effort (using the results is up to you). If your bot is written in NeverHeardOfItScript, you can at least see how to do it. If you want, you may be able to get resource tracking into your bot before the next Steamhammer release.

ResourceInfo.zip includes ResourceInfo.cpp and its header ResourceInfo.h. The 2 files add up to 163 lines and have no dependencies beyond BWAPI (well, they are in namespace UAlbertaBot, but you can strip that out). One instance of ResourceInfo tracks the last known resource amount of one mineral patch or one geyser (for whatever reason, I chose to implement them both in the same class). I believe it handles all cases correctly. When a mineral patch mines out, its associated mineral patch unit disappears, and the code recognizes the missing patch and sets the amount to 0. A mineral patch that starts with 0 minerals causes no confusion. A geyser changes its unit type when a refinery is built on it, and then the associated unit changes entirely if the refinery is destroyed. The code understands all that. It correctly considers the gas amount inaccessible if there is an enemy refinery (I found a cute way to code it so that undoing the workaround is not a trivial one-line change).

There are different ways to integrate ResourceInfo into a program. In Steamhammer, I put it into the information manager. Here’s the declaration of the data structure to hold all the ResourceInfo instances:

// Track a resource container (mineral patch or geyser) by its initial static unit.
std::map<BWAPI::Unit, ResourceInfo> _resources;

It is a map from the static unit of each mineral patch or geyser to the corresponding ResourceInfo instance. It is initialized once on startup like this:

void InformationManager::initializeResources()
{
    for (BWAPI::Unit patch : BWAPI::Broodwar->getStaticMinerals())
    {
        _resources.insert(std::pair<BWAPI::Unit, ResourceInfo>(patch, ResourceInfo(patch)));
    }
    for (BWAPI::Unit geyser : BWAPI::Broodwar->getStaticGeysers())
    {
        _resources.insert(std::pair<BWAPI::Unit, ResourceInfo>(geyser, ResourceInfo(geyser)));
    }
}

Keeping separate data structures for minerals and gas would make as much sense, maybe more. Or you could associate each resource container with the base it belongs to, or however you want to organize it. For example, if all you want to know is how many minerals and gas were last known to exist at a given base, then you could give each base a vector of mineral ResourceInfo instances and another vector for gas, with no need for a map to look up individual patches and geysers. Steamhammer’s data structure is essentially global to allow central updating and general-purpose lookup.

Every frame, you have to update the ResourceInfo instances. It’s fast. With separate mineral and gas data structures, this step would be simpler.

// Update any visible mineral patches or vespene geysers with their remaining amounts.
void InformationManager::updateResources()
{
    for (BWAPI::Unit patch : BWAPI::Broodwar->getStaticMinerals())
    {
        auto it = _resources.find(patch);
        it->second.updateMinerals();
    }
    for (BWAPI::Unit geyser : BWAPI::Broodwar->getStaticGeysers())
    {
        auto it = _resources.find(geyser);
        it->second.updateGas();
    }
}

With Steamhammer’s _resources map, you look up a resource amount by its initial static unit. If you want error checking, throw instead of returning 0 on error.

// Return the last seen resource amount of a mineral patch or vespene geyser.
// NOTE Pass in the static unit of the resource container, or it won't work.
int InformationManager::getResourceAmount(BWAPI::Unit resource) const
{
    auto it = _resources.find(resource);
    if (it == _resources.end())
    {
        return 0;
    }
    return it->second.getAmount();
}

Each Base remembers its own mineral patches and geysers, and it can add up the values for you. No need to repeat that code. The only other piece is the debug drawing, so you can see what the subsystem knows. Might as well throw that in so you don’t have to write your own. It draws a currently visible resource’s amount in white, and an out-of-view resource’s last known amount in blue (mineral) or green (gas) with the last frame that the resource amount was updated.

void InformationManager::drawResourceAmounts() const
{
    const BWAPI::Position offset(-20, -16);
    const BWAPI::Position nextLineOffset(-24, -6);

    for (const std::pair<BWAPI::Unit, ResourceInfo> & r : _resources)
    {
        BWAPI::Position xy = r.first->getInitialPosition();
        if (r.second.isAccessible())
        {
            BWAPI::Broodwar->drawTextMap(xy + offset, "%c%d", white, r.second.getAmount());
        }
        else
        {
            char color = r.second.isMineralPatch() ? cyan : green;
            BWAPI::Broodwar->drawTextMap(xy + offset, "%c%d", color, r.second.getAmount());
            BWAPI::Broodwar->drawTextMap(xy + nextLineOffset, "%c@ %d", color, r.second.getFrame());
        }
    }
}

You see an enemy unit. Sometimes it tells you what else the enemy has; for example, if you see a marine, you know there is a barracks even if you haven’t seen it. Drawing the inferences makes it easier to figure out the opponent’s plan. I thought it would be trivial to calculate the inferences, since BWAPI provides UnitType::requiredUnits() that tells what you need to create a unit of a given type. But it took me some head scratching; inference does not equal creation in reverse. Here’s what I ended up with. I edited the code slightly for readability; the real version is a little more obscure.

The code should be close to correct, and it works in tests so far, but I won’t be surprised if I’ve missed cases. There are a lot of cases.

// Trace back the tech tree to see what tech buildings the enemy required in order to have
// produced a unit of type t. Record any requirements that we haven't yet seen.
// Don't record required units. An SCV is required for a barracks, but don't count the SCV.
// A hydralisk is required for a lurker, but it is used up in the making.
void PlayerSnapshot::inferUnseenRequirements(const PlayerSnapshot & ever, BWAPI::UnitType t)
{
    if (t == BWAPI::UnitTypes::Zerg_Larva)
    {
        // Required because BWAPI believes that a larva costs 1 gas.
        return;
    }
    std::map<BWAPI::UnitType, int> requirements = t.requiredUnits();
    if (t == BWAPI::UnitTypes::Terran_Vulture_Spider_Mine)
    {
        requirements[BWAPI::UnitTypes::Terran_Factory] = 1;
        requirements[BWAPI::UnitTypes::Terran_Machine_Shop] = 1;
    }
    if (t.gasPrice() > 0)
    {
        requirements[the.enemyRace.getRefinery()] = 1;
    }
    for (std::pair<BWAPI::UnitType, int> requirement : requirements)
    {
        BWAPI::UnitType requiredType = requirement.first;
        if (!ever.contains(requiredType))
        {
            if (requiredType.isBuilding() && !UnitUtil::BuildingIsMorphedFrom(requiredType, t))
            {
                unitExists[requiredType] = true;
            }
            inferUnseenRequirements(ever, requiredType);
        }
    }
}

The code recursively traces back all the requirements to the root of the tech tree, if necessary. If you see an arbiter, you may learn about the stargate, the arbiter tribunal, the templar archives, the citadel, the core, and the gateway. In practice, an early scout which is turned back by a dragoon and sees nothing else concludes that protoss has a gateway, assimilator, and cyber core. It should infer a reaver from a scarab and a carrier from an interceptor. An opponent plan recognition rule does not have to say “if they have a cyber core, or some unit that requires a cyber core...” it can say “if they have a seen or inferred cyber core....”

The parameter ever remembers what enemy unit types we have ever directly seen, at any time in the game, even if all the examples have been destroyed since. That is because, if you see a vulture, all you know is that at some point in the game a factory existed to make the vulture. You have to remember. ever is filled in at the beginning of the game (or at the latest when we see the first enemy, if they went random) with the units that exist at the beginning of the game: The resource depot and worker types, plus for zerg, the larva and overlord types. That prevents loops: According to UnitType::requiredUnits(), it takes a nexus to create a probe and it takes a probe to create a nexus. True, but you have to ground the recursion!

Notice the bit !UnitUtil::BuildingIsMorphedFrom(requiredType, t): A lair requires a hatchery, but that doesn’t mean that when you see a lair you can infer a hatchery somewhere on the map. You can only infer the spawning pool. I think this serves essentially the same purpose as UnitType::isSuccessorOf() in BWAPI 4.2.0, but I haven’t switched yet. Non-building units are tricky to infer without isSuccessorOf(), so I didn’t. I don’t try to infer the vulture from the spider mine. A sunken colony requires a creep colony, but the creep colony disappears. An archon requires 2 high templar, ditto.

I filled in a couple of special cases. Spider mines: As far as UnitType::requiredUnits() is concerned, even though spider mines are units, they do not require units to create but only tech. Gas: If we see anything that requires gas, infer a refinery building. It may help early in the game. I haven’t tried to draw inferences from tech. You should be able to infer a control tower from seeing a cloaked wraith, an academy from seeing a scan occur, a lair from seeing a lurker, and so on. But one step at a time!

We interrupt your regularly scheduled AIIDE analysis for software releases that you may want to know about. These are both under MIT license, meaning the main requirement is that you pass along the license file if you include the code.

MCRS combat simulator library

MCRS is a combat simulator by Christian McCrave, author of McRave. My latest info is that it should be considered beta quality, not fully tested. It follows a different philosophy than SparCraft and FAP, which ask you to provide sets of friendly and enemy units and then simulate a fight with all the units. MCRS wants to know all the visible units all the time—friendly and enemy, every frame. Optionally, you can also inform it of a friendly unit’s target unit, telling it more about the bot’s intentions. When it’s time to simulate a combat, you say how long a simulation you want and pick out one of your units as the seed of the engagement. MCRS figures out for itself which friendly and enemy units should be involved. I gather that it is intended to work well for short durations only: “Do I gain if I fight right now?” not “Will I eventually win this fight if I pour it on?”

Here is the output struct you get back from a simulation. There’s missing capitalization in attackGroundasGround, a sign of the beta status. Scanning through the code, I see that it doesn’t do what I would call a simulation—there are no nested loops—it’s more of a strength comparison. That means it should be quite fast. Personally, I would call it a combat estimator instead of a combat simulator.

struct MCRSOutput {
	double attackAirAsAir = 0.0;
	double attackAirAsGround = 0.0;
	double attackGroundAsAir = 0.0;
	double attackGroundasGround = 0.0;
	bool shouldSynch = false;
}

Without documentation, I’m n0t entirely sure what this is supposed to mean. I’m guessing that the doubles tell you whether it is better to shoot enemy ground units first, or enemy air units. shouldSynch I guess means that, if true, your air and ground units should do the same thing: Both attack or both run away. That sounds useful!

The estimate takes into account DPS, HP, and armor including upgrades, the time to reach engagement range, and high/low ground. It recognizes some spell effects; for example, it knows that a unit under maelstrom can do nothing. But there is no provision for most spell effects. There are adjustments for splash damage, including protoss high templar but not zerg devourers. I don’t see any attempt to understand cloaked units and detection; that might be the biggest missing point.

aWeaponCooldown() looks wrong. It usually returns an air weapon cooldown duration, but for high templar and suicide unit types instead returns a damage amount. Hmm, but a long cooldown means that the unit will not attack again during the simulation, so I think it should work correctly that way. It’s still odd. Also, infested terrans can only attack ground, so that detail looks wrong too. Continuing, I see spider mines being given a ground strength of 0.0. Are those handled by some other means?

Is MCRS a good idea? That depends on how well it works in your bot! Since it behaves differently than other combat simulators, if you already use one then to switch to MCRS you need to revamp your decision making. I haven’t tried it myself, so I can’t speak to how accurate it is... but you could watch McRave play.

TorchCraftAI framework from CherryPi

TorchCraftAI (front page with big tutorial links and small other links) builds on TorchCraft to provide a machine learning framework for Brood War bots. TorchCraftAI is a framework, not a library. You don’t include it as part of your bot, you include your bot as part of it: You take it as a starting point and build your bot inside it by adding pieces and training machine learning models.

As a full framework, TorchCraftAI is big and complex. The high level documentation looks pretty good, but it is not deep; you will probably have to learn a lot by looking around. Apparently the machine learning stuff uses CUDA for both training and play, so it requires an invidious, I mean NVIDIA GPU due to successful proprietarianization of the community. There are instructions for Windows, Linux, and OS X, but I gather that Linux is TorchCraftAI’s native environment, and life should be easier there. There is way more stuff than I can dig into for this post, so that’s enough for now.

TorchCraftAI includes code for CherryPi. It looks as though CherryPi’s learned data files are optional, but “recommended”; they have to be downloaded separately (see instructions under Getting Started). You’ll need CUDA to use them. As I mentioned at the start, it’s MIT licensed, so if you want, you can fork CherryPi and start from there.

Here is Steamhammer's new C++ MapPartitions class, which calculates ground connectivity. This is a donation to the community. Feel free to borrow it for your own bot, if you like. The download is a zip which contains 4 files: MapPartitions.cpp, MapPartitions.h, and 2 license files. The class contains some code derived from UAlbertaBot, so there is a UAlbertaBot license plus Steamhammer’s license. They are both MIT style licenses, which basically make no requirement beyond including the license file. (It’s irritating that the licensing considerations are as complex as the code, but that’s the world we live in.)

I’ll quote the comment describing it:

// Partition the map into connected walkable areas.
// The grain size is the walk tile, 8x8 pixels, the granularity the map provides.
// Unwalkable walk tiles are partition ID 0.
// Walkable partitions get partition IDs 1 and up.

// This class provides two features:
// 1. Walkability for all walk tiles, taking into account the immobile neutral
//    units at the start of the game.
// 2. Ground connectivity: What points are reachable by ground?

// If two walk tiles are in the same partition, it MIGHT be possible for a unit
// to walk between them. To know for sure, you have to find a path and verify
// that it is wide enough at every point for the unit to pass.
// If two walk tiles are not in the same partition, no unit can walk between them.

Concretely, the interface lets you directly test the walkability of a position, find the partition ID of a position, or check whether 2 positions are connected by ground. You can find out the total number of partitions (some maps have hundreds due to small holes), and you can draw partitions on the screen for debugging. There’s not that much to it.

A few notes:

• There is a separate initialize() method that is not called by the constructor. You have to call it yourself, in or after your main onStart(). Depending on your use case, this is sometimes necessary to avoid making BWAPI calls before BWAPI is initialized itself.
• Maps often have little side bits attached by a single walk tile. No unit is small enough to walk there, but this class doesn’t know it.
• The little side bits are not important, at least not in Steamhammer’s play. Units don’t want to go there.
• The class does not update when neutral units are destroyed, opening paths that used to be closed. But the walkability data structure is designed to be easy to update in that case.
• This version is slightly different from Steamhammer’s code. I changed the error handling so that I could remove one last dependency and make it completely standalone (except for BWAPI, of course). Only a handful of lines are different.

I’ve suggested before that authors should package up reusable code as libraries. BWEM, BWEB, and FAP are great examples. MapPartitions is more modest. When I’ve looked at breaking out Steamhammer code, until now I’ve always felt that the parts were too integrated with each other, with too many dependencies. MapPartitions is the first exception. I hope some people find it useful.

Comments pointed out the new C++ combat simulator FastAPproximation (FAP) by N00byEdge. It’s included in the source of the bot Neohuman, but it has virtually no dependencies and can be easily ported to use in another bot. It is under an MIT license, like UAlbertaBot and Steamhammer, so it also has light legal constraints.

I haven’t tried it yet. No time! Here are my impressions after reading the code.

• I think it’s not quite finished. For one thing, the parent bot that it is part of doesn’t use it yet. For another, it’s still under rapid development. In the last 2 days it has gotten support for stim and medics, and has had at least 2 bug fixes and other changes.

• Even so, bftjoe uses it, so it is in a usable state.

• It’s simple and short and easy to understand. You can read through and easily see its abilities, and its bugs and limitations. SparCraft is large and complex and difficult to understand and modify. I think understandability is a major advantage. If it has problems that affect your bot’s play, you can fix it yourself.

• It supports more stuff than SparCraft. This is a big deal. Unlike SparCraft, FAP explicitly supports bunkers, reavers, and carriers. Overall, SparCraft has major omissions and makes a lot of mistakes with units it does support—for example, the new version claims to handle mutalisks versus spore colonies, but in practice doesn’t do an acceptable job. A combat simulator which handles those things even halfway correctly could have big advantages.

• Its combat simulation is extremely simple. Each unit finds the closest enemy and attacks it as possible, moving toward it until it can. SparCraft has “scripts” that allow much more flexible specification of behavior.

• No support for terrain. SparCraft constrains ground units to walkable terrain. FAP doesn’t read the map at all. Both pretend that units are allowed to freely overlap each other when they move (which in Brood War is only true for air units). Neither understands high ground, which affects visibility and hit probability and makes a giant difference. So SparCraft has a theoretical advantage in simulating ground battles that are in chokes or otherwise affected by terrain obstacles, while both are weak in coping with high versus low ground.

• It ought to be reasonably fast due to its simplicity. With the addition of a location-indexed data structure to find nearest targets quickly, it could be made very fast.

• Other limitations: I didn’t notice any support for suicide units (scourge, infested terrans, spider mines). No splash damage. No support for most spells, not even repair (only stim and medic healing). Details for bunkers, carriers, and reavers are simplified.

• Bugs: The range bonus for a bunker is added on only 1 of 2 #ifdef paths. When a bunker is destroyed, it seems that the 4 fictional marines which are assumed to be in the bunker also disappear, so bunkers will be underestimated.

Historically, the BWTA library (for Brood War Terrain Analysis) was the solution. Here’s what I learned about the situation nowadays.

roll your own

Of the 13 bots whose source I had handy, these do not use BWTA but apparently roll their own map analysis: MaasCraft, Skynet, Tscmoo. In some cases it may be a vote of no confidence in the BWTA library; in some it may mean that that author wanted to do it on their own. UAlbertaBot uses BWTA for some tasks and its own map analysis for others, and likely some other bots do too.

Ratiotile has a sequence of 6 posts from 2012 analyzing region and choke detection in Skynet and BWTA and reimplements Skynet’s algorithm with tweaks.

BWTA2

The BWTA2 library in C++ is the maintained version of the abandoned original BWTA. I assume this is the version that BWMirror for Java “mirrors”.

I see complaints online that BWTA was slow and crashed on some maps. BWTA2 should at least reduce those problems.

It looks like BWTA2 does pathfinding using a navigation mesh, one of the fancy algorithms that I left for later consideration in this post. I’m thinking that I won’t return to the fancy algorithms because they’re not necessary for Starcraft. It’s easy to guess how a complex data structure leads to a slow and buggy map analysis.

BWEM

The BWEM C++ library (for Brood War Easy Map) by Igor Dimitrijevic is an alternative to BWTA. It claims to provide comparable information and to be more reliable and much faster. It also lets you send events to register that a map building or mineral patch has been removed, and updates its information to match.

I’m not aware of any bot that uses BWEM other than Igor Dimitrijevic’s own Stone and Iron, but I wouldn’t be surprised to find out that a few new bots do. BWEM 1.0 was released in September 2015, and BWEM 1.2 in February.

BWEM calculates ground distances and similar info in O(1) time using grids of data that are written by simple flood-fill algorithms. It’s similar to how Skynet does it (I haven’t looked into MaasCraft or Tscmoo). It makes sense that it should be fast and reliable.

For pathfinding specifically, BWEM returns a high-level path as a list of chokepoints to pass through. Paths are precomputed when the map is analyzed, so the operation is a lookup. If you want low-level pathfinding too, you need to do it another way.

BWEM knows about mineral patches which block the building of a base, usually a base on an island. Base::BlockingMinerals returns a list of blocking minerals for a given base, so you can mine them out first.

what to do?

Take advice about what library to use from people who have used them, not from me. But if I were evaluating them, I’d start with BWEM as the more modern choice.

Next: Really now, what is pathfinding?

Starcraft is hard, therefore bot coding is also hard. A bot needs complex behavior to play a reasonable game without too many gross blunders. Bot authors who start from scratch have a ton of work to do to catch up with the state of the art. I’m thinking of Sungguk Cha’s new terran bot, though I don’t know whether it was coded from scratch. It has a bunch of smart behaviors, but it is scoring poorly so far. It plays well in some ways, but to score well it has to play adequately in more ways yet.

I think the community understands the problem and has done a good job of reducing it. We have starter bots that people can modify (UAlbertaBot is popular, but most bots are open source), and frameworks and libraries that solve common problems (Atlantis, BWTA2, Igor Dimitrijevic’s terrain analysis BWEM, BWSAL, SparCraft and BOSS which are both included with UAlbertaBot). To get well underway in bot coding is still hard, but it’s not for lack of support from the community.

I’m hoping even more people will contribute reusables. If you think you have a good solution to a common problem, why not package it up as a library? It’s good coding practice to have a clear API between modules, so it could help you grow your bot. If the API is light enough, as it should be in good code, then coding the module as an independent library enforces a kind of cleanliness. Then you can distribute it separately to make it easier for others to use. With documentation, of course (that may be the hard part for a lot of people).

As I think about the right way to structure a bot, I keep returning to composable software ideas. For example, the blackboard architecture is an AI classic. (Nova claims to have a blackboard architecture.) Modules are relatively independent of each other because they share data only through the blackboard; it’s easy for different people to work on different modules at the same time; it’s easy to add or replace modules. If it’s done right, it’s even easy to pull out a selection of the blackboard modules and reuse them in another bot that maybe has a different overall architecture. Maybe a modular idea along those lines would help.