Starcraft AI blog

TeamLiquid has posted an excellent interview with Flash—the #1 human player, of course, not the protoss Starcraft bot. The post is by BigFan, the interview is by lemmata. A lot of the interview is about the thought process behind optimizing opening builds.

I want to draw special attention to this bit:

Q: You mix the 1-1-1 with +1 5-rax quite effectively. Does this force Zerg to mix between 3-hatch and 18-hatch builds?

A: That is a given. You always have to mix well.

Flash is talking about the importance of choosing openings randomly. Some points the opponent can scout out before making important decisions, and some points cannot be scouted, leaving decisions to be made blindly. At all levels of play, forcing adaptation from the opponent who has seen what you are doing puts some pressure on, because the opponent’s adapted build order is not likely to be as optimized as the mainline build the opponent had in mind. Flash creates optimized alternatives to make it difficult for the opponent to respond as accurately. At pro level in particular, where both sides are aware of the known deviations and adaptations, making a random choice when the opponent cannot scout what happened until later can put heavy pressure on. In general, both players want mixed strategies, in the game theory sense.

A later line is related: “By increasing the number of possibilities the opponent has to worry about, I can cloud his judgment and induce decision paralysis.” It’s the same idea, with a psychological instead of a game theory rationale.

side story

The interview gives a handy zerg build order for a “2.5 hatch mutalisk” aka “18 hatch mutalisk” opening that Steamhammer does not have. I’ve grown tired of chasing too many bugs that are too hard to find, so I decided to code up the opening and try it out. That should be a nice break.

The build order calls for making units up to a supply limit of 18, then starting the third hatchery, then finally getting the necessary overlord as late as possible. It’s a cute optimization taking advantage of the supply freed up by the drone used to make the hatchery, and it’s necessary for the build to work as intended. When I tried it out, Steamhammer made the overlord early, and ended up with an extra overlord at a critical time. Not good enough.

“Hmm,” I thought, “the heuristic for adding in overlords is too crude, but I can do an exact simulation of supply in the queue to see if the next planned overlord is in time. It will be a useful improvement, and it’s not hard.” So I coded that up too, and fixed a couple problems in the first try. And... it still doesn’t work. There is another bug, and it is hard to find! Argh!

Update: The rest of the story continues to be funny. There were several bugs in the supply simulation, mostly edge cases. The decisive one was that unfinished hatchery supply was not counted as pending supply—deliberately, since hatcheries take a long time to finish and only provide 1 supply. I decided to count hatchery supply if the hatchery was within 300 frames of finishing; I think that should make it good in all cases. After fixing every bug, an overlord was still started too early! The cause turned out to be a mistiming in the opening itself. The extractor was built one step too late, so that there was not quite enough gas to start the lair immediately when it came up. The clever, clever production manager said “I can improve on this, just move the overlord forward and nothing else will be delayed.” It was a real improvement on the build order as written, but it was not the best possible improvement....

The annual AIIDE, CIG, and SSCAIT tournaments give us snapshots of bot strength at particular moments in time. The SSCAIT ladder used to let us gauge strength at other times as well, but then voting was added, and voting distorts the ratings so that we only get a general idea. To add voting made sense, because it helps keep people engaged, and that (as I see it) is SSCAIT’s main goal. Still, we lost a useful ability.

To me, following Steamhammer’s results, the elo distortion caused by voting is unmissable. Since November or earlier, and except during the tournament when voting wasn’t allowed, every time Steamhammer’s rating rose to around 2200, the voters soon took interest and fed it a sequence of opponents that it would lose to, hammering the rating back down. Then voters lost interest and its rating gradually rose again. Watching this process helped me make my correct prediction that Steamhammer would finish in the SSCAIT tournament between places #4 to #8, even though the bot could not maintain such a high rank outside the tournament.

BWAPI bots ladder fills the gap. (It doesn’t seem to have an official name.) There is no voting or streaming; it only plays games. Since it doesn’t slow down games to make them watchable, it also plays more games. The larger amount of data should also improve the ratings (though it depends on the K factor in the elo calculation).

The UI is sparse. Presumably the project is in an early stage of development, just finished enough to make public. The web page doesn’t provide information about plans. I’ve sent a list of questions to the contact address.

A few points:

• The ladder seems to have been pre-populated with SSCAIT bots. It is a decision that can be questioned: The bot authors did not give permission for this public use. An author who doesn’t like it can write to the contact address to have their bot removed.

• The maps are the SSCAIT maps.

• Minimal public information. The bot names and game results and replays are made public; nothing else is revealed. It is an intentional choice. I don’t even see a way to find out the upload time of a bot, so that you can try to distinguish versions.

• Random bots are allowed, but the tournament manager chooses the race so that the opponent knows it when the game starts. This is different from playing random. It reflects the opinion that playing random gives an unfair advantage.

I personally disagree with the treatment of random players. I think that decisions about fair balance should be made on the basis of data, not argument, and that we don’t have the data. One issue is that a random bot is more difficult to create (no matter whether it is taught its knowledge by hand or by machine learning), which you could take as counterbalancing any advantage it might gain by playing random. Another issue is that a bot which wants to play against random opponents is not able to on this ladder. Of course, in the end the organizers are doing the work, and they get to make the decisions.

Overall, the appearance of a new ladder is a good sign of the health of the community. It fills a gap: It provides a better continuous measure of how well different bots are doing than we have had before. Those who like the design decisions may prefer it over other competitions, and those who don’t also gain by living in a richer world.

Steamhammer is doing relatively poorly. The new version 1.4 is at about the same level as the tournament version 1.4a3, maybe a little worse. (It’s hard to tell, because the opponents have improved.) It is at the low end of my expectations. A slow start was only natural, since it had to learn for itself about many opponents that it previously was hand-configured to defeat, but it seems to be genuinely not improved. In reality, it is stronger in many ways, but it also has a few new weaknesses. The new weaknesses are from the opponent model’s mistakes and limitations.

The next opponent model feature, I’ve decided, should be fine-tuning the choice of openings against each opponent according to results. The opening recognition will provide instant counters when it successfully recognizes the opponent’s opening, and fine-tuning will sharpen the selection over time. Details still to be decided, though. After enough games to accumulate data, that should solve Steamhammer’s newly-added weaknesses.

More opponent model features will follow, as mentioned at the end of the original post on the opponent model’s workings and the post on a tree of openings.

Today’s overlong game against PurpleSwarm shows bugs on both sides. Steamhammer correctly predicted PurpleSwarm’s opening and played 5 pool, which put Steamhammer ahead and should have won. Instead of keeping the pressure on, Steamhammer droned up, went to 3 bases, and started to switch into mutalisks—it does that occasionally, it’s a choice. PurpleSwarm took advantage of the delay and recovered, overrunning Steamhammer’s bases with zerglings. Just after its natural fell, Steamhammer made an extractor there, which seemed wasteful but turned out to be key. Then, just before its main fell, Steamhammer hatched its first and only 2 mutalisks. There was not much play left for Steamhammer.

PurpleSwarm destroyed everything it found, but never found the extractor that was barely out of sight. Zerglings roamed the map checking bases, but didn’t look everywhere. PurpleSwarm also never mounted a defense against the 2 mutalisks. That makes 2 basic errors by PurpleSwarm. Steamhammer’s mutalisks slowly wore down drones and buildings, like water dripping on stone (watch the whole game if you have geological patience). The mutalisks sometimes went idle, which should never happen for more than 8 frames. And the mutalisks did not search for other bases, but only destroyed those already seen. That’s 2 bugs for Steamhammer. Steamhammer’s bugs proved less severe: Steamhammer won on points when the game timed out, since its mutalisks destroyed so much stuff over the long long endgame.

Steamhammer’s bugs appear to be in the tactical goal selection. These are features which usually work but failed this game (and I have seen other failures too). The code does not look that complicated, but I have fixed bugs in it before. I guess it is trickier than it appears. I did make one change to exploration: Air squads are now allowed to explore places which are not reachable by ground. That would not have helped this game, but it could help against an opponent whose last base is an island base, or which is hiding floating buildings in an inaccessible spot.

The new terran bot Rhonin (named after a character from Warcraft) appeared today, played 5 games, and disappeared in about an hour. “Just wanna test” says the description. The 5 games were 3 losses against strong opponents Krasi0, CherryPi, and Killerbot by Marian Devecka, plus 2 wins against weaker opponents Sparks and KaonBot.

Rhonin plays a marine and medic strategy, which might explain why it didn’t try any games against protoss. The marines set out in waves of ever-increasing size, which reminded me a bit of Black Crow’s zerglings. The marines don’t immediately rush to attack, but gather at a safe distance from the enemy, a location that appears to be decided dynamically depending on what Rhonin sees. Rhonin also expands quickly across the map, not as quickly as KaonBot, but still fast. The marine forces become huge.

I thought Rhonin was pretty capable for a brand new bot on its first outing. It has a limited unit mix, but it seems organized and not reckless. It knows how to scan, though it gets scan late. It seemed to get scan reactively against Killerbot’s lurkers, and very late in the game against KaonBot. It put pressure on Krasi0 and Killerbot, and I thought that an opponent which defended less firmly would be in trouble. The great masses of infantry later in the game will be dangerous unless you know how to counter them.

The sudden appearance and disappearance suggest that the test games found out what the author wanted to find out. I expect that Rhonin will be back with improvements.

Back when I played online regularly, one of the tricks I pulled sometimes was to build an expansion hatchery out of position, where it might escape being scouted. Main bases on many maps have space behind the gas geyser, and if the geyser is on the opposite side from the base entrance, I might put a hatchery there and mine gas and the edge minerals. Some maps, like Python, have space behind the minerals where a hatchery can go. If the base was defensible, I could add another hatchery in the usual position later.

Another reason to build out of position is that the position is blocked, for example by a pylon or a spider mine. Terran can build an offset command center and float it into place after the block is removed. Even zerg will sometimes build a hatchery in an offset position, especially if the expansion is desperately needed. (I don’t think I’ve seen a deliberately offset nexus in pro play. That’s a bigger investment.)

These tricks came to mind because Steamhammer doesn’t support them. I’ve been working on the base placement code, which assumes without question that there is One Correct Placement. It’s much easier to to code that way, and the results are good—special tricks are for special circumstances, not for most games.

Still, the thought reminded me again that bots need to be more flexible in their thinking. Placing a base should be like tactical analysis in that it considers different actions (at least in unusual situations) and compares them to choose the best.

Some special map features and pro maps which display them. The examples are not exhaustive. There are more features and more maps with them!

This post is to point out how much knowledge a comprehensive Brood War bot needs. Every one of these maps calls for special knowledge to exploit the special feature, and often more knowledge to defend against exploitation of the feature. Hand-coding all this knowledge, if anybody ever does it, will be a long process. Gaining the knowlege by machine learning is tough too; that’s a research project. That is probably why, as far as I know, only 1 bot exploits 1 of these features—see “cliffable natural” below. The other map features are virgin ground.

I’m in favor of tournament organizers incorporating more maps with special features, as long as ignorant bots can still play on the maps without gross blunders. It will encourage bot authors to work on the hard problems. On the other hand, some of these maps are totally unplayable by current bots, which would be unfair to authors who can’t keep up, and makes year-over-year comparisons difficult.

• cliffable natural - Lost Temple, Tau Cross
The natural can be attacked from above the cliff using drop. I’ve seen ICEbot take advantage on Tau Cross by dropping tanks on the cliff. I haven’t seen any other bot exploit the feature. Benzene has a similar feature: Tanks can be dropped outside the neutral buildings blocking the rear entrance, where they are in range of the natural mineral line and reachable by ground only by a long path (I’ve seen ICE do that too). No bot appears to know how to defend the cliff (use air units, or counterdrop, or place tanks below and do something to gain vision, such as float a building).

• base exposed from outside - Jade, Moon Glaive
The edge of the main can be attacked from outside by ranged units over a barrier, without the need to bring an air unit or scan for vision. A bot with the right attack and defense skills would have an advantage. It is rare to see bots do that, and I’ve never seen one appear to intentionally seek an attack from outside.

• back doors - Destination, Heartbreak Ridge
Your base has a rear entrance which the enemy can attack through with extra effort. On Destination, by a nearby mineral block that is easy to monitor. On Heartbreak Ridge, by a more distant mineral block. I have not seen any bot appear to intentionally take advantage of the rear entrances. Another map with a rear entrance is Bifrost, where nothing blocks the rear entrance but the path to reach it is long.

• openable central paths - Detonation, Monty Hall
On Detonation, you can take a long path to the enemy, or you can mine out blocking minerals and take a direct path. Each side has a row of minerals (30 minerals per patch) that they can mine out to reach the center of the map. On Monty Hall, you have to mine out minerals to get a ground army to the enemy base at all, and there is a choice of 3 paths. Another example map is Arkanoid.

• narrow entrances - 815, Blue Storm
Only small units can pass. 815 has a narrow ramp from the main; a dragoon or lurker or tank cannot go up or down. Blue Storm has a narrow entrance toward the center, and a wide entrance around the side with a longer path.

• passable blocks - Gold Rush, Outsider, Plasma
Blocks which can be passed by pushing units through the minerals, or by mineral walking through. Generally, a player must do that to have a good chance. On Outsider, some of the mineral lines can be mined from either side, so there is a choice of where to place your base.

• assimilator blocks - Gold Rush, Troy
Paths with double assimilators. Destroying the assimilators closes the path (except to ghosts, the narrowest unit).

• no natural gas - Nostalgia, Korhal of Ceres
No vespene geyser in the natural expansion. Without a safe second gas, strategies are different. Korhal of Ceres includes other odd features, such as 2 entrances into the main.

• neutral spells - Persona, Triathlon
Persona has permanent dark swarm spells cast over ramps and expansion mineral lines. Triathlon has neutral arbiters which cloak neutral zerg eggs which block the path to expansion bases (among other features).

• maps with islands - 815, Namja Iyagi
These are regular maps with many islands. They’re playable by ignorant bots, but a bot with island skills would have an advantage. In the SSCAIT map pool, these maps have 2 islands each: Andromeda, Empire of the Sun, Python.

• semi-island maps - Dream of Balhae, Indian Lament
Each player’s main is an island and the rest of the map is connected. You need to get drop quickly.

• island maps - Charity, Paradoxxx
Strategies are very different from land maps.

This came up (again) in comments to yesterday’s post. Steamhammer too often exceeds the time limit when playing a long game as protoss. It happens when the bot’s base fills up with buildings and there is no room for a new building. The building placer doesn’t understand the situation and keeps retrying, and meanwhile no buildings can be constructed. Building placement is slow so after a while it exceeds the time limit. Even if it didn’t exceed the time limit, the bot would likely lose the game because inability to place a building freezes the production queue so that nothing can be produced.

In principle. the same problem affects all races. In practice, terran can place buildings freely and zerg makes so few buildings that they almost always fit on available creep. If zerg wants a lot of sunkens, it doesn’t build them all at once, and each one extends the creep so that there is more space.

There are 3 different mitigations in the code that reduce the problem but don’t come close to solving it.

• Protoss buildings are allowed to touch each other vertically, blocking horizontal movement. This reduces the space taken, but occasionally causes units to get locked in enclosures.
• Steamhammer can randomly choose a new “main base” where future buildings will be placed. It considers doing this whenever a pylon is placed and more than one base is available to place it. This often causes buildings to spill unnecessarily into the center of the map.
• A special case in the production code recognizes when building construction is being retried, and retries less often.

Other simple mitigations that I have considered also don’t solve the problem.

A full solution, in my view, has 2 parts. The first part will be to make building placement much faster. I have 2 ideas that together I expect to speed up building placement by an order of magnitude or more. These ideas are made easier by the base data infrastructure that I’m writing now (see yesterday, new base placement code). I’m currently working on Steamhammer version 1.4.1. My plan is that building placement will be fast no later than version 1.4.3, I hope sooner. Expect a production freeze, but that is better than an instant loss.

The second part is to reason about building placement. The absolute minimum is to recognize: “Oh, building placement failed. It’s going to keep failing until a pylon finishes.” Then at a minimum it can stop adding buildings. Better, it could find a good place with space around it, and put a pylon there. I should be able to do that in the 1.4.x series, and it will solve the problem for good. There are complications that I will have to deal with. For example, if there is free supply then Steamhammer shouldn’t let unit production stop just because building construction is stopped or delayed.

Another step could be to recognize when a base is full, and stop trying to place buildings there. Put them somewhere else. The new base data should make that easier, too.

I want to go further, and write a general placement planner to optimize the placement of buildings and units. You specify goals: Place buildings compactly, while leaving space for units to pass. Form a wall at the front with as few gaps as possible. Place static defense to defend both the natural and the ramp to the main. Set lurkers just far enough apart that only 1 at a time gets hit by storm. Set tanks out of sunken range and in siege range and vision range. Spread out tanks to defend this choke. Prefer to put tanks on high ground. The placement planner figures out good places. It will be complicated, but I expect that with the speedups I have in mind it will be fast enough.

Time control in general is an issue that Steamhammer should tackle eventually. As it stands, near the start of the game the maximum time per frame is commonly at least 25 times greater than the mean time per frame, and it tends to increase as the game goes on. Steamhammer gets by because it does almost everything fast enough, so that it doesn’t have to worry much about breaking the time limit. When I add tactical analysis and other expensive features, that will probably change. It will become necessary to check whether there is time for each task, and defer or suspend or abort tasks that threaten to go over. I’ll figure that out when I get there.

Today I tested Steamhammer’s new base placement code, a major step in getting rid of BWTA2. There are still a couple of big bugs, but it works well most of the time. It’s getting close to ready.

As I mentioned when I first wrote about map analysis plans last June, Dave Churchill removed BWTA as a dependency from UAlbertaBot after Steamhammer forked from it. Newer UAlbertaBot versions do the necessary map analysis themselves, and when it comes to unnecessary map analysis, they simply delete some less important features that BWTA used to provide. I won’t delete features that add strength, but for the necessary features my plan has always been to borrow from UAlbertaBot.

Here’s how placing bases works in general. A base consists of a location for the resource depot, plus a set of minerals and vespene geysers belonging to the base (plus any other info you find useful). For starting positions that a player may begin the game in, the map specifies where the resource depot goes. BWAPI passes the information through. You still have to figure out which resources belong to the base. I had Steamhammer assign all the resources within a fixed distance to each starting base, and it works fine.

For other bases, software is on its own. First, group the resources on the map into clusters, expecting that each cluster will become a base location. You probably want to skip over blocking minerals and any clusters that don’t provide enough resources to be worth placing a base at, or at least handle them differently. Then, for each cluster, figure out the best place to put the resource depot so that mining will be efficient. Details matter, but it’s not complicated, at least if you ignore weird maps like Crystallis.

I wrote my own clustering, which is simpler than UAlbertaBot’s (though I wonder if I made it too simple and crude). For placing the resource depot, I followed UAlbertaBot’s way. UAlbertaBot provides 2 methods, one of which is commented out. The commented out method finds the center of the resources by averaging their locations. (Technically, it’s the centroid.) It then uses UAlbertaBot’s building placement code to find the nearest location to the center at which it is legal to build a resource depot—you have to be at a minimum distance from any minerals and gas. The building placement code calculates a spiral of tiles centered at the desired location and tries each one until it finds one that works.

The active method in UAlbertaBot, which I took for Steamhammer, is to find the center of the bounding box of the resources. That’s the desired location, and UAlbertaBot proceeds as above.

In practice, Steamhammer’s new code usually finds exactly the same base locations as BWTA. There are some exceptions. It finds 2 bases in the center base of Fighting Spirit (as some other bots do), which I think is due to a bug that assigns the same mineral patch to more than one base. I don’t expect it to be hard to fix.

Good progress so far.

The new protoss bot BananaBrain has been scoring about 50% in its first day online at SSCAIT. That’s quite good for a brand new bot. I also commend it for not having “bot” in its name.

The outstanding skill of BananaBrain is its macro. It has a seemingly excellent implementation of mineral locking, and likes to oversaturate its main and natural with probes so that when further bases are founded, they come online immediately. With that skill, BananaBrain often has a larger army than its opponent, and that can be the most important factor in winning. BananaBrain’s only macro flaw, as far as I can see, is that sometimes it wants to spend more gas than it has, with the result that it can’t spend all its minerals. It recovers after a while.

BananaBrain plays a fixed build against each race. The versus zerg build goes with mass zealots and and later adds corsairs, dark templar, and storm, but strangely never makes observers. That’s a wide range of units for a new bot (though MadMix is still the champion of making the most unit types when new). The versus terran and versus protoss openings are more generic, with a lot of dragoons. I haven’t seen a game versus random yet. Bots that learn will soon learn to exploit BananaBrain’s fixed openings.

BananaBrain’s skills other than macro are much weaker. Against zerg, the corsairs eagerly attack overlords without noticing whether they are under fire themselves. The game versus Tyr by Simon Prins shows that it is willing to ram a large army into prepared defenses and unwilling to retreat when losing. The strange battle with KaonBot shows that it is not aggressive enough to stop mass expansions and does not adapt to its opponent’s unit mix. BananaBrain also tends to neglect upgrades and research. Versus protoss it gets dragoon range only after zealot leg speed, even though it makes mostly dragoons (usually you should get dragoon range almost immediately). Versus terran it also makes many dragoons, and I didn’t see it get dragoon range at all.

Don’t be fooled by my complaints about its weaknesses. BananaBrain is doing well for a new bot. It even has a win over CherryPi.

A few thoughts on the map Transistor after watching the ASL5 games today.

“Transistor” is a clever name for the map. On the one hand, the bases are laid out like the standard diagram of a transistor: Source, gate, drain. On the other hand, the middle “gate” base can act strategically as a gate that blocks or allows movement between the two other bases.

The underlying idea of the map is to create strategic variety between games where both sides have corner bases and games where one side is in the middle base. If both sides have corner bases, the situation is symmetrical and balanced. If one player has the center base, the intent is that the 2 base positions will have offsetting advantages and disadvantages so that each player has different goals while neither has a big overall advantage. The center base is more vulnerable to harass, but is also in position to block access between the top and bottom halves of the map, achieving a favorable map split later in the game.

I’m not sure how successful the intent will turn out to be, but it is a sophisticated design. Map making has come a long way since Lost Temple.

Bots so far seem to be totally incapable of the strategic analysis or adaptation needed to play differently depending on the positions that the players end up in. Another map which is deliberately designed so that play varies depending on starting positions is Fantasy, a 4 player map in which each start location is laid out differently. When Fantasy was current, some pros played specialized strategies for specific starting positions.

This is an idea I’ve talked about before. As I get closer to starting the implementation, I’ve worked out a little more detail.

It’s getting close to the time to start distinguishing between build orders and opening strategies. Steamhammer today only knows exact build orders: Spawning pool exactly now, then exactly 3 drones, then exactly 3 pairs of zerglings, etc. It has some ability to vary the build order; it can insert static defense, and react to emergencies, and a few other things. The variations are shallow and Steamhammer does not know how to adjust the build order to compensate for them. For example, Steamhammer will often substitute drones for zerglings that it believes it does not need, and suffer from a mineral excess as the build order continues. The opening build order reaches its end, and suddenly Steamhammer comes to life and starts 4 hatcheries simultaneously to get enough larvas to burn off the extra minerals. Ouch!

A pro can easily do things like open with 9 pool and then transition into the usual 3 hatch mutalisk play. (Strategically, the intent is that the 9 pool should delay the opponent enough to make up for the delay in the zerg build.) Steamhammer only knows the standard 12 hatchery into 3 hatch mutalisk build order. I would like to give Steamhammer the ability to start with any opening stem and then transition into any reasonable middlegame followup. It should keep its ability to follow an exact build order when it knows one, and add the ability to devise a build order to reach a goal situation like 3 hatch mutalisk. I think the flexibility is necessary.

I think of the goal situations as abstract opening strategies. They are abstract and not concrete, because many details have to be decided to turn the strategy description into a specific build order. “3 hatch muta” is how humans talk about strategy, so we know it’s a useful level of abstraction.

What does it do? First, you need a way to specify a goal situation, like “3 hatch mutalisk.” At a minimum, you need to be able to specify the required tech and the number of production buildings, so you can ask for things like “2 port wraith with cloak.”

The goal will look somewhat like a BOSS goal—not surprising, since BOSS’s purpose is to devise build orders to reach goal situations. For BOSS, you give the number you want of each unit and building and tech to research. That’s too specific, and not good enough for my intention. For example, normally terran should build SCVs whenever possible in the early game, but if playing BBS you want marines to have priority over SCVs. For another example, if you’re going pure lurker-ling, then your ratio of lurkers to zerglings should not be fixed but should depend on the situation: Typically, spend all gas on lurkers, any remaining minerals on zerglings. In the goal, you usually want to specify exact numbers of only a few things and priorities of other things (“SCVs first” and “gas goes to lurkers”). It’s complicated, and I won’t be surprised if the final goal specification ends up more complicated.

Planning is still at an early stage. Right now, I’m imagining that the configuration file will declare a set of goals separate from the opening lines. An opening line may implement a goal: For example, the current 3 hatch muta line will follow the 12 hatchery opening stem and implement the 3 hatch muta goal in a specific way. There will have to be notation to declare that. Or the opening line may stop short at the stem. In that case, the strategy boss (consulting with the opponent model) will be responsible for choosing or inventing a followup goal.

When this is done, the tree of openings will become much bushier, which is to say, Steamhammer will have many more choices at each point. At each choice point, it could choose any compatible goal (an opening stem that makes 3 hatcheries is not compatible with a goal that calls for 2 hatcheries). Even if a goal is already underway, in case of surprise the bot could change its mind. If the strategy boss is smart enough to keep up, then Steamhammer should gain much, much greater ability to adapt.

How does it work? Steamhammer retains UAlbertaBot’s production system, which assumes a uniform list of items to produce. This system, or one like it, must be kept if Steamhammer is to play hand-optimized opening lines, which is a useful skill (humans do it too). I may rewrite it, because it has limitations that harm performance: It can produce only 1 item per frame, and it requires latency compensation. Goals do not fit into the uniform production queue. The exact production sequence to achieve a goal has to be re-evaluated every time the situation changes unexpectedly—even the rate of mineral mining can’t be predicted exactly, because there is a random component, and you never know when you might have to suddenly spend money on an emergency response. The natural implementation is to create a separate software layer, the production boss, which turns goals into production queues.

Turning goals into production queues is also what BOSS does. BOSS tends to react slowly to changes, because BOSS likes to create a long detailed production queue (though of course it depends on what goal you feed it). The production boss (it’s funny, but it will be keeping nearly the same name) needs to avoid that problem. It will have to look ahead to make good plans, but at the same time it will have to feed items one or a few at a time to the queue. Either that, or it will have to be prepared to frequently clear and recalculate a longer queue. In any case, the natural implementation is as a separate software layer. I may rename the current ProductionManager to ProductionPeon and add a component ProductionBoss... that should make the layering clear. :-)

I’ll implement it piece by piece. The first piece will come during the 1.4.x series, but it will be a tiny part. I’ll have the production system take care of the trivial prerequisites for terran addons and zerg static defense: If you ask for a machine shop, it will build the factory if necessary and add the machine shop when it can and without blocking other production unnecessarily. Similarly if you ask for a spore colony. The system will replace zerg automatic sunken morphing, moving it from the strategy boss to the production system where it belongs, and extend the benefits to a few more buildings. It will help terran significantly. Terran openings that build an addon deliberately include extra production and produce the addon later than they usually can, because a bug messes up production if the addon can’t be completed when ordered.

With that done, it should be easy to add more goals. As the production system gets more capable, the zerg strategy boss will become smarter to match. It will become much easier to write strategy bosses for terran and protoss, so I’ll do that and dump BOSS, which should bring a big jump in skills for terran and protoss. The whole process will take a long time.

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.