Starcraft AI blog

The planned post about strategy abstraction is delayed by a power outage at my house. Here’s a brief filler.

TeamLiquid has a post with analysis of new ASL maps Sparkle and Transistor by Australian protoss Legionnaire. Without drawing any strong conclusions about overall balance, Legionnaire points out how map features will affect play.

Current bots are poor at adapting to map features. More than that, it is beyond the state of the art for any AI system to adapt to maps with as few games as humans need. Humans reason out how map features affect play, and with experience they sharpen their reasoning. Machines, so far, mainly collect statistics about the course of events, and they need a vastly larger number of games to zero in on good strategy. Of course they may be able to play those many games faster, but we don’t know how to make a system that can combine reasoning with empirical learning like a human. I’m interested in Legionnaire’s expert analysis as an example that may offer clues.

I have a simple idea that will both make it easy to restructure Steamhammer’s openings as a tree of opening build orders, and at the same time make the opening lines shorter and easier to understand. There are 2 parts.

Part one: Add a touch of new syntax. If the first item in an opening build order is the name of another opening, then substitute in the other opening’s build in its place. This applies recursively, of course.

For example, I could then recode Steamhammer’s 12 hatch openings to factor out the 12 hatch part. These 3 openings

"ZvZ_12HatchExpo" : { "Race" : "Zerg", "OpeningBuildOrder" : ["4 x drone", "overlord", "4 x drone", "go scout once around", "hatchery", "spawning pool", "extractor", "3 x drone", "4 x zergling", "Lair", "drone", "creep colony @ natural", "metabolic boost", "2 x zergling", "spire", "9 x zergling"] },

"ZvT_2HatchMuta" : { "Race" : "Zerg", "OpeningBuildOrder" : ["4 x drone", "overlord", "4 x drone", "go scout once around", "hatchery", "spawning pool", "extractor", "4 x drone", "3 x zergling", "Lair", "drone", "metabolic boost", "2 x drone", "spire", "3 x drone", "hatchery", "drone", "extractor", "2 x overlord", "12 x mutalisk", "hydralisk den", "5 x drone"] },

"2HatchLurker" : { "Race" : "Zerg", "OpeningBuildOrder" : ["4 x drone", "overlord", "4 x drone", "go scout once around", "hatchery", "spawning pool", "extractor", "go gas until 1075", "3 x drone", "3 x zergling", "Lair", "2 x drone", "metabolic boost", "hydralisk den", "extractor", "drone", "lurker aspect", "drone", "2 x zergling", "5 x hydralisk", "overlord", "5 x lurker", "drone", "hatchery", "3 x zergling"] },

could become these 5 openings

"12Hatch" : { "Race" : "Zerg", "OpeningBuildOrder" : ["4 x drone", "overlord", "4 x drone", "go scout once around", "hatchery", "spawning pool", "extractor", "3 x drone"] },

"ZvZ_12HatchExpo" : { "Race" : "Zerg", "OpeningBuildOrder" : ["12Hatch", "4 x zergling", "Lair", "drone", "creep colony @ natural", "metabolic boost", "2 x zergling", "spire", "9 x zergling"] },

"12HatchTech" : { "Race" : "Zerg", "OpeningBuildOrder" : ["12Hatch", "drone", "3 x zergling", "Lair", "drone", "metabolic boost"] },

"ZvT_2HatchMuta" : { "Race" : "Zerg", "OpeningBuildOrder" : ["12HatchTech", "2 x drone", "spire", "3 x drone", "hatchery", "drone", "extractor", "2 x overlord", "12 x mutalisk", "hydralisk den", "5 x drone"] },

"2HatchLurker" : { "Race" : "Zerg", "OpeningBuildOrder" : ["12HatchTech", "go gas until 1075", "hydralisk den", "extractor", "drone", "lurker aspect", "drone", "2 x zergling", "5 x hydralisk", "overlord", "5 x lurker", "drone", "hatchery", "3 x zergling"] },

I think of it as stems plus branches. Currently, you have to repeat the opening stems in every opening. Doing it the new way, the stems will be factored out and only written once each. It’s shorter and could prevent mistakes.

If you read closely, you’ll see that one detail of the original 3 openings is lost: The ZvZ opening scouts earlier. After recoding, all openings scout at the same timing. I want to change scout timing to be decided by the opponent model rather than by the opening book, removing the decision from the opening altogether. Also the number of drones made in the lurker opening is changed in this version; it’s not quite the same opening, though it’s close. When I do it for real, I will probably recode the openings differently than in this example.

One other detail is changed in an unimportant way. The 2 hatch lurker opening limits how much gas it collects, because once it has its initial set of lurkers, it wants to make drones and hatcheries to transition into a longer game. The original version specifies "go gas until 1075" right after the extractor is started, while the stem-and-branch version gives it after the opening stem. The change doesn’t affect how the opening plays out in any way.

I’m also thinking of factoring the openings into 3 subsections, one for each race. Then you don’t have to repeatedly specify the race. Instead of

"2HatchLurker" : { "Race" : "Zerg", "OpeningBuildOrder" : ["12HatchTech", "go gas until 1075", "hydralisk den", "extractor", "drone", "lurker aspect", "drone", "2 x zergling", "5 x hydralisk", "overlord", "5 x lurker", "drone", "hatchery", "3 x zergling"] },

it would become

"2HatchLurker" : { "OpeningBuildOrder" : ["12HatchTech", "go gas until 1075", "hydralisk den", "extractor", "drone", "lurker aspect", "drone", "2 x zergling", "5 x hydralisk", "overlord", "5 x lurker", "drone", "hatchery", "3 x zergling"] },

I can’t reduce it to a bare list until I change how terran and protoss openings work. They specify an opening group that says what unit mix to build in the middle game. Someday, they’ll have their own strategy boss that figures that out for them. Though I can think of other reasons to add tags to opening lines.

Part two: Interpret the stems and branches as a tree. Why allow opening names only in the first item of the build order? Because then you get a tree of openings.

Here’s how Steamhammer will make opening decisions. There will be a bunch of initial opening stems, 4 pool, 5 pool, 9 pool, and so on up through 3 hatch before pool. Steamhammer can choose an opening stem first, and go from there. Alternately, it can pick any opening it wants, just as it does now, and backtrack to the stem as a starting point. Anyway, at first it plays only the stem of the opening, then it is time for another decision: It can follow any of the opening lines branching from that stem, or it can stop following any opening and let the strategy boss take over.

Suppose it starts off choosing 2 hatch lurker. First it plays out the 12 hatch opening stem, then it thinks: “I found out that my random opponent is terran and not zerg, so I’ll continue down my original path.” It plays from there, treating the 12 hatch tech branch as the stem of an opening subtree. At the end of the 12 hatch tech branch, it thinks again: “I see an early factory, so lurkers might be bad. Better follow the mutalisk branch.” (I think the best reaction to an early factory is to get a hydralisk den and a few hydras for defense against vultures and/or wraiths, then continue into mutalisks. Steamhammer won’t be that smart at first.)

Or it reaches the end of the 12 hatch opening stem, then “Uh oh! Marines already!” It can bail out immediately instead of following any branch, and let the strategy boss take over and try to survive. Whatever opening line the bot finished on will be recorded in the data for the opponent model. Every opening line, stem or branch, can be treated identically, except that some of them have further branches and some don’t. In effect, at the end of each line is an implicit branch “now let the strategy boss do its job,” and that branch can be chosen like any other. The idea of treating every opening line identically is key; it gives the learning algorithms flat data that is easy to digest.

Using scouting information at each decision point will make Steamhammer’s openings much more reactive. Making decisions later, when more information is available, means the decisions will be better. (Project management works the same way!)

I’ll implement this in the 1.4.x series. It won’t be in 1.4.1 or 1.4.2, but it might be the version immediately after. The idea is simple and it provides necessary flexibility that Steamhammer has always missed. At first, only the zerg strategy boss will have the smarts to make decisions between branches of the opening tree, though. Terran and protoss will have to wait until they have more software infrastructure.

Some time in the future I’ll add an abstraction layer to openings, and cleanly distinguish between specific opening build orders and general opening strategies. Next: Abstract opening strategies.

Instead of configuring all of Steamhammer’s opening probabilities by hand, I want it to figure them out for itself. The starting point is data: For each matchup, keep overall statistics of all the openings in a file. Another goal is to have Steamhammer adapt its strategy to maps based on experience. So I thought, why not combine the two? For each matchup and map, keep a file with numbers for all the openings. Or for each matchup, keep a file for all the pairs (map, opening)—that way the bot has the data to generalize between maps.

Someday I also want Steamhammer to adapt its strategy reactions and its tactics to the map. At first it will analyze the map and decide what looks good (“look at that cliff over the mineral line—I should go air or drop”); later it will learn from experience what works well. I don’t expect to get to that for a long time, though.

Steamhammer has over 60 zerg openings (it doesn’t play all of them), and the count will increase. SSCAIT has 14 maps and other tournaments use fewer, so I think I should be ready for on the order of 1000 pairs (map, opening) if I keep them in one file. Each pair would be one line of data, something like “<opening> <map> <# games> <# wins>” and maybe a few more numbers like mean game length, or a statistical summary of evaluations once there is an evaluation function, or whatever else. If I want a cache of map data like number of starting positions and rush distances and so on, to use in generalizing across maps, that would be in a separate file.

In that case there would be 12 matchup files, including data for when the opponent went random: TvT TvP TvZ TvR, PvT PvP PvZ PvR, ZvT ZvP ZvZ ZvR. With up to 1000 lines per file, it seems like a reasonable amount of data. In every game, Steamhammer would read one file in onStart() and write it in onEnd(), which doesn’t seem excessive. There is one complication. If the opponent goes random, and after I give Steamhammer the ability to change its mind on the fly (which I will do), then when Steamhammer finds out the opponent’s race it may want to read that matchup file too. Reading and analyzing that much data may take more than one frame time, so it might have to go into a separate thread. Another solution for when the opponent goes random might be to read 4 matchup files during onStart() when we are allowed more time. Well, when it comes up I’ll figure out a plan. Maybe nothing special will be needed (seek time for a hard drive could exceed one frame time, but reading from SSD is faster).

That’s the data. How to use it? I haven’t decided on details. The opponent model keeps detailed records for each game against a given opponent, including the map. When we play the opponent for the first time, decisions have to be made without the opponent model, solely on the basis of the matchup+map+opening statistics. I’ll figure out a more-or-less sound way to turn the raw numbers into probability-to-play-this values, including an exploration policy. There are choices. After we’ve played an opponent many times, the opponent model will have more information (since it records more data, and it is specific to the opponent), so it can decide on its own. In between, I’ll need some kind of evidence combination procedure to blend the 2 sources of information together. I expect that a simple procedure would work fine, even weighted averaging of probabilities.

Steamhammer’s configuration file will become much shorter. I expect I’ll retain the manual configuration options for openings, for those bot authors who want to do it that way, but Steamhammer itself will rely on the data it collects. Once I have a good set, I’ll distribute it with the bot.

I’m not sure when I’ll get to all this stuff. Maybe or maybe not in the 1.4.x series.

Next: A tree of openings. It ties in.

This blog is 2 years old today. The introductory post was on 4 March 2016. Also, this is the 500th post. I didn’t plan it, it just turned out that way! Honest!

There are slightly under 2000 comments. There is a post on more days than not, and close to 4 comments per post on average. I have exactly 1 guest post so far; the others are all by me.

Really, really still next: Adapting to maps.

Wuli was “updated” on 1 March, but only the description was changed to point to the github repository. The repository has a last update date in 2016 and the bot binary on SSCAIT is the 2016 version (I did a bytewise comparison against my archived version to make sure).

I thought Wuli really had been updated, because Steamhammer has lost a few games against Wuli lately—despite having learned that Wuli is a zealot rusher and playing a counter. In local testing, Steamhammer scores over 90% against Wuli, so I can’t explain the losses except as a run of bad luck.

Still next: Adapting to maps.

Today I tested a 12 hatchery in main opening for ZvZ. 12 hatch gets zerglings late, and it is risky against 9 pool openings, which are common in both human and bot play. Steamhammer in the past (after version 0.2 from 2016) rarely plays even the faster 12 spawning pool, because its poor defensive skills leave it vulnerable to normal play. I only added a 12 hatchery opening for ZvZ in version 1.4, to be played when the opponent model predicts that the opponent will also open slowly. Otherwise it seemed too risky.

The hatchery on 12 lets the player get more drones than any other opening that is playable in ZvZ. I realized that you can make a sunken colony and still end up with 11 drones, a strong count for ZvZ. So I made a 12 hatchery in main opening with a creep colony timed to finish a little before the spawning pool finishes (a deliberate production delay would make it more efficient). The sunken colony gives it a chance to survive early aggression despite poor drone defense skills. It uses the 2 hatcheries to make many zerglings, threatening any 1 hatchery opening, and at the same time techs to mutalisks fairly quickly, threatening zergling openings.

How did it work out? I tested with self-play versus different openings.

I started with Steamhammer’s 9 pool speed opening, which builds up to 3 hatcheries as it gets the money, going all-in on zerglings. Would the 12 hatchery survive? On 2 player maps, the 9 pool zerglings could arrive too early and win. On 3 player maps, the 12 hatchery seemed risky. On 4 player maps, the 12 hatchery usually won: It survived the early attack, matched zergling numbers later, and won with mutalisks. The plan worked.

It also got a plus score versus fast mutalisk openings like overgas 9 pool and 11 gas 10 pool. The 12 hatchery could not catch up in mutalisks and struggled to defend in the air, but still won the majority of games with mass zerglings. The one hatchery openings could not keep up in zergling count. The plan worked here too.

I didn’t bother to test against in-between openings like 9 hatchery, or overhatch, or the various overpool openings. The 12 hatch survived more extreme openings, and it has a superior economy to middle-of-the-road openings, so it should be competitive. I will try a few tests against other opponents, to see how it stands up against bots with different skills.

I already configured Steamhammer to play the 12 hatchery in main opening, on 4 player maps only, at a fairly high rate. I predict it will help. I also configured it for all maps as an alternative to the 12 hatch at natural opening when the opponent model says that it is playable.

I want Steamhammer to learn to select its own openings not only to suit the opponent, but to suit the maps. Next: Ideas for adapting to specific maps.