Starcraft AI blog

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.