Starcraft AI blog

Time for another Steamhammer update. The key bug still has me frustrated. Some of my recent progress:

Base placement. The UAlbertaBot base placement algorithm that I borrowed works perfectly on most bases, but turns out to have a flaw. For some unusual base layouts, it places the resource depot far from the minerals. For example, all other bases are good on Moon Glaive, but the 1 o’clock base sets the geyser at an unusual angle to the intended base location. The algorithm places the base level with the geyser and far from the minerals, away from the intended location.

I’ll look into it more before deciding how to fix it. I might keep the algorithm as is and add an optimization step that slides the base to a better location. Or it might be simpler to ditch it and use a distance minimization measure directly.

New openings. Looking ahead to the near (ish) future when Steamhammer gets its tree of openings, I added 4 new openings. In the tree, they will be forks of existing openings and will offer opportunities to make late decisions based on scouting information. I added 1 ZvT, 1 ZvP, and 2 ZvZ choices. Before the tree arrives, I’m likely to add more forks. It would be natural to have a wide variety of overpool followups for different situations.

Even in the upcoming version, once I add fine-tuning of opening choice to the opponent model, the new openings should be worth having. They will counter some opponents more sharply.

Squad mixup bug. Today, tired of other things, I arbitrarily decided to fix a bug in squad membership. It’s not an important weakness, but it’s been bothering me for months, so I picked it.

The problem is that sometimes units that should be in the flying squad get stuck permanently in the ground squad. 3 unit types are special for squad assignment: Scourge, devourers, and carriers. If there is a flying squad with other flying units, then these types go into the flying squad, otherwise into the ground squad. The theory is that these units should coordinate with whatever squad exists—especially devourers, which are support units. The bug is that, if one of these units is assigned to the ground squad—usually because the flying squad was temporarily wiped out—it stays there. When the flying squad is reconstituted, it doesn’t move back.

The bug was easy to find, but I decided that the underlying problem was that the code was too complicated. I simplified and rewrote it until it was Obviously Correct and there could not be any bugs left. Nevertheless, there was one bug left, and I had to fix that too. Not quite simple enough; maybe next lifetime.

I’m not sure whether this fix improves strength. If you’re playing with mutalisks and zerglings and the two tend to act independently and go to different places, maybe scourge should not always be with the mutalisks. At least, stream watchers are not likely to notice the different behavior; it’s hard to see unless you know what to look for. Anyway, now it works as designed, and since the code is clearer it should be easier to change the behavior if it turns out to be weak. Still a net improvement.

I like the new protoss bot Locutus by Bruce Nielsen. It is a Steamhammer fork which uses BWEB for building placement. That means it includes BWEM, which BWEB depends on, though I don’t notice any use of BWEM for pathfinding. (If it used BWEM for pathfinding, probes would not have gotten stuck behind a mineral block in this game against Bereaver.) It also has some good extensions to Steamhammer.

Locutus has a favorite build order that it uses against all races, a forge expand build that was originally designed for use against zerg. It uses BWEB to place a reasonably good wall with forge, cannons, and gateway in front of the natural, not a wall that is optimized for the terrain but one that is about as good as the walls of other protoss bots. As a new bot, it has little ability to adapt its unit mix to the situation, so it follows up with universal units, dragoons. Like Steamhammer, it eventually adds reavers and observers and a few dark templar. The dragoon micro inherited from UAlbertaBot is one of Steamhammer’s best skills, so that’s another reason dragoons are a good choice.

Locutus does know other build orders, and uses certain ones against specific opponents. [Update: I misread the configuration! It does not actually play enemy-specific build orders; the feature is turned off.] It does not use Steamhammer’s opponent model.

The forge expand build was designed for zerg opponents, but in bot world it works well against other races too. Locutus has wins over strong opponents like Bereaver and TyrProtoss. Building cannons willy-nilly has an advantage: The cannons stop most early rushes, common bot strategies. For example, PurpleSpirit tried its SCV-marine rush and failed hard.

Also visible in the PurpleSpirit game is Locutus’s changed probe micro. Probes come to defend the wall when necessary, a critical skill that Steamhammer does not have. Unfortunately, they also come to defend when it is not necessary, and Locutus tends to send too many probes and delay mining too much. Sometimes Locutus pulls probes into the middle of the map and loses them for no apparent reason.

Locutus appears to still be using BOSS for production, because it adds more gateways than it can keep busy, a typical BOSS misbehavior. But Locutus has good macro, so if so, it is using BOSS more carefully than Steamhammer (I’m going to dump BOSS so I don’t care about using BOSS carefully). Locutus can almost keep up with BananaBrain in macro, which points to good skill.

Using BWEB for building placement means that buildings are laid our more nicely than in Steamhammer. Locutus’s base is more pleasant to look at and fits more buildings. It is still possible for dragoons to get trapped between buildings, though. It may be a bug in BWEB, or in Locutus’s use of it. The 2 dragoons on the left in the picture cannot get out.

Locutus retains Steamhammer’s recon squad that performs reconnaissance in force. It’s usually good at finding and knocking down undefended expansions. Locutus also retains Steamhammer’s inability to defend its own expansions, leaving it vulnerable to an opponent that also scouts and destroys bases.

Looking into the configuration file, I see 2 nice extensions to Steamhammer’s configuration syntax. The build order is given in the usual concrete Steamhammer way, but a new location allows it to place buildings in its wall. I may adopt the same syntax for Steamhammer itself, when I get to walls.

"pylon @ wall"

There is also new “then” syntax that lets you chain actions together. I take it to mean “then with the same probe, do this next action.” Otherwise the code will assign a new probe, causing inefficient probe movement. You can chain as many actions as you like (or at least, I see an example where Locutus chains 3 actions). I can only assume that it is smart enough to assign a new probe if the first one is lost in the middle of the chain. This is a cool idea that I didn’t think of. It only seems useful for protoss, though.

"pylon @ wall then go scout location"

or

"photon cannon @ wall then photon cannon @ wall"

Overall, Locutus is a promising new bot. It has good ideas and good execution, and it already plays well. The author’s note says that new builds are coming. As Locutus gains more skills, it could become fearsome.

Steamhammer has 2 favorite lurker dysfunctions. One of them is kind of interesting.

Its #1 favorite blunder happens versus protoss. Lurkers act somewhat independently of the squad they belong to, because their burrowing ability lets them be more aggressive. But they’re not clever about it; they don’t understand detection. When a lurker sees a photon cannon, it understands it as a high priority target, walks up to it, and burrows in range. Then the cannon kills it. Not very interesting. I haven’t thought of a way to fix it without adding or rewriting too much code, so I put it off. I’ll fix it when I work on micro, likely in the 1.5.x series while I’m doing mutalisk stuff.

The second favorite blunder is less common but more interesting. It usually comes up versus terran. Lurkers approach a ramp with a bunker on top. They can’t see uphill, but when they get in range the bunker starts firing, so the lurkers can see the bunker and they burrow and start shooting back. Then the bunker can no longer see the lurkers, so it stops firing. The lurkers no longer see their target, so they unburrow, becoming visible... and the cycle repeats. Terrans that know how to place a bunker on top of a ramp generally know how to repair it, so the bunker usually wins. If the overlord catches up to provide vision, the overlord flies into bunker range and holds position... and doesn’t provide vision for long. This game versus Ecgberht shows it happening twice, before another lurker attack finally breaks the ramp because there were enough zerglings.

To fix the overlord behavior, overlords have to worry about threats. That’s on my menu for soon-ish. I may fix the lurker misbehavior with a rule like “if you’re on low ground and the target is on high ground and you want to burrow, move to burrow on high ground if possible,” that is, on the ramp. Ideally, the combat simulator would be able to tell whether the lurker can burrow successfully. Eventually I want to teach Steamhammer how to reason about visibility, instead of following rules.

I made an improvement to overlord production in Steamhammer, and it reminded me: Making overlords is a difficult skill. Supply is tricky for terran and protoss too, but zerg overlords are trickier because overlords have more uses and are more vulnerable.

When to make overlords. If you know ahead of time what units you will produce when, you can plan overlords at exactly the right times. Of course, you usually have only a general idea. If you scout that the enemy is getting mutalisks much earlier than you, then you have to make spores and that is that; an overlord in the egg will turn out to be unnecessary.

The tactical situation matters: Are corsairs out? Are you planning a doom drop? If you’re at risk of losing overlords, you may want extras to avoid being supply blocked. Ideally, bots should weigh the risk of supply blockage (which depends on events in the game) against the cost of extra overlords. I don’t know whether any bots do that; Steamhammer certainly doesn’t. When CherryPi loses overlords and gets supply blocked, it likes to hugely overproduce overlords and try to stay ahead by sheer volume. I don’t think that’s good play, but it seems at least as successful as Steamhammer’s method of producing the minimum number of overlords.

Conversely, if you find yourself ahead in supply, you may be able to take bigger risks with your overlords, at least for a while. Sacrifice one to scout and you won’t miss it.

The strategic situation also weighs in on overlord production. If you get supply blocked, instead of producing overlords, you could start a fight to reduce your army size. You want to compare the cost of the fight versus the cost of the overlords. Even if you’re not supply blocked, the cost of buying supply to feed your growing army can provide some impetus to attack. If you suddenly lose a lot of army in battle, you may even want to cancel overlords in the egg.

The result of all the complications is that bots have to rely on heuristics or approximations. Most bots do well enough with overlord production despite living by simple rules of thumb. But the stronger the bot, the more the fine details matter.

Where to make overlords. Since overlords have uses, it also matters where you produce them, especially before overlord speed is researched. In the early game, strong players plan ahead where to place and how to maneuver overlords to see as much as possible of key areas. Where each overlord is produced figures into the plan. Later, bases and armies may need overlord coverage to spot dark templar or to gain vision of high ground. New overlords should be made near where they will be needed—unless other units are higher priority. If corsairs are marauding, most overlords may have to be produced near air defenses (lacking this skill hurts Steamhammer).

Overlords are a tiny aspect of the game. It’s dizzying how complicated it all is.

A heuristic: If the enemy has one medic and some marines, target the medic first. Nobody will heal the medic, and the marines will be softer targets. If the enemy has more than one medic, target the marines. Medics have armor and more hit points, they are happy to heal each other and they do no damage. The heuristic is not always right, but it seems good most of the time.

Another heuristic: If you are tearing down a base and may be interrupted, then a building that the enemy has only 1 of is more important than otherwise. If you find 2 x gateway and 1 x nexus, it may be better to target the nexus. If you find 2 x nexus and 1 x gateway, maybe the gateway is a better target. It’s not as firm as the first heuristic, but it seems to point in the right direction.

A similar idea is taking out one pylon that powers more than one enemy building. These can all be seen as special cases of key point analysis, where you recognize key points that are especially valuable to take out—or, if they are yours, to protect. The general idea is to understand what depends on what. You want to destroy the enemy dependencies that are the most important and take the least effort: The one medic, the one gateway, the one pylon.

Well, I happened to think of the first 2 heuristics and realized that they were related. It’s probably not time to implement this kind of reasoning in bots; I think for now it is enough to implement a few special cases as heuristics. But someday bots will be strong and will get into late game situations where precise reasoning makes a big difference: When to use your last minerals to make a cannon and surround it with dark templar, when to hide a pylon on a cliff, when to shepherd your probes with an arbiter for long-distance mining—that way of protecting your key points.

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.