Starcraft AI blog

I want to draw attention to GHOST, a constrained optimization solver from 2014 that claims to be good for a wide variety of RTS problems. The lead is Florian Richoux, author of the protoss bot AIUR which was a strong contender in its day.

According to the description, GHOST should be good for Starcraft problems like designing a wall, placing static defense, choosing where to siege your tanks, planning build orders, optimizing your army composition, prioritizing targets to shoot at—a huge variety of things, actually. It claims to give answers not too far from optimal and to be fast enough to run within a single frame (though it will depend on what problem you’re solving).

• the paper: GHOST: A Combinatorial Optimization Framework for Real-Time Problems (pdf)
• the code: richoux/GHOST (github)

I haven’t tried GHOST and I don’t intend to, because it is under a GPL license, which rubs me the wrong way. But if is as good as the paper says, it could be a superb way to solve a lot of different Starcraft problems.

For the upcoming Steamhammer 1.2, I added a feature today to simplify the coding of similar middle game production for different openings. In older versions of Steamhammer, StrategyManager checked the name of the opening build order to decide what to build. There were a bunch of zergling openings, so I coded in: If the opening is this, or this, or this... build zerglings. If the opening is that, or that, or that... build mutalisks. It was bulky and hard to maintain, but I let it stand because I knew I was throwing the code away when the new strategy boss was ready (and I did).

I don’t want to write a new strategy boss for protoss and terran, so BOSS will be the way. BOSS works better for protoss and terran than for zerg, anyway. To solve the maintenance problem, you can add an optional OpeningGroup string to each opening, and check the OpeningGroup in the code instead of the opening name. If OpeningGroup is zealots, make zealots, and so on. It doesn’t matter how many zealot openings you write, StrategyManager doesn’t need to be updated. Of course nothing stops you from using the opening name too, if you want to fine-tune, but then keeping it in sync is up to you.

Here is the start of UAlbertaBot’s zealot rush:

"Protoss_ZealotRush" : { "Race" : "Protoss", "OpeningBuildOrder" : ["Probe", "Probe", "Probe", "Probe", "Pylon", "Probe", "Gateway", "Gateway", ...

Here is the same part of the identical opening in Steamhammer 1.2 development version. There is also a “10-12Gate” opening in the zealots OpeningGroup. Liquipedia lists other two gate zealot openings if you want to code them in yourself.

"9-9Gate" : { "Race" : "Protoss", "OpeningGroup" : "zealots", "OpeningBuildOrder" :
    ["4 x probe", "pylon", "go scout location", "probe", "2 x gateway", ...

I made a couple of simple and necessary improvements to the followup, too. When it transitions to dragoons, Steamhammer (unlike UAlbertaBot) gets dragoon range and eventually zealot legs. If given the same openings, Steamhammer will play them better than UAlbertaBot does. I intend to give it random openings that are a little different, though.

Steamhammer got its first win against Krasi0 after many many tries. The map was Python, where starting positions are important, and the two bots got neighboring positions. Steamhammer went 9 pool speed, as it does 10% of the time versus terran, and Krasi0 was unlucky and scouted the wrong way around the map. Zerglings ran past the scouting SCV before it could reach the zerg base. The bunker in the terran natural was late and never finished (a bunker in the main could still have saved the game). Once zergling speed completed there was no hope for terran.

That apparently used up Steamhammer’s supply of luck, because it was immediately tied up in a string of losses. The loss against XIMP showed a bug I hadn’t seen, where Steamhammer repeatedly tried to take the third base that is a crucial part of its build order, but each time the drone lost interest and went home. Some weird macro bugs are lurking.

The most informative loss was another game against Krasi0, where Steamhammer first gained a winning advantage, then lined up its bugs and limitations in a row and held a parade. This time Steamhammer opened 12 hatch into 2 hatch muta. The bunker was again late, this time without excuse (is it a newly-introduced error?). The initial 6 zerglings got SCV kills that they did not fully deserve and, more importantly, slowed mining for a time as SCVs were pulled. With more smarts they could have stayed in the terran base and marauded for a time.

When the mutalisks came out, Steamhammer’s eyes lit up with crazed aggression. It flew over the bunker to kill every SCV that came near while ignoring the bunker itself and probably laughing maniacally. If it knew to fly to the mineral lines instead it could have won on the spot, but as it was the loss of workers set terran far back for the middle game. It was a decisive advantage and would have been a sure win with good followup.

Krasi0 countered the mutas with goliaths, which Steamhammer countered with hydralisks, which Krasi0 countered with tanks. That’s how you play the game. Steamhammer went up to 4 bases and brought out ultralisks while Krasi0 was still on 2 bases. Here you can see that Steamhammer has a larger army and more workers, and the production tab shows that zerg is outproducing terran even though minerals are accumulating. The terran 3rd command center is under construction in the lower left natural.

In the later game, Steamhammer, showing the other side of its mad streak, made 3 deadly mistakes and a bunch of smaller mistakes. Avoiding any of the 3 deadly mistakes might have been enough to win.

1. Steamhammer chose the unit mix hydra-ultra and became pinched for gas and unable to spend all its minerals. I overlooked a couple of important factors in the calculation. Hydra-ultra is useful in rare situations, and especially in situations nothing like this one. With zerglings instead, the zerg army would have been larger and deadlier and there was likely nothing Krasi0 could have done to hold it off.

2. Due to a bug, zerg was unable to take a 5th base. This bug I’ve seen before; it is not the same one as against XIMP. Getting the 5th gas would have made hydra-ultra more playable.

3. Zerg never scouted the terran 3rd base. It’s a limitation; I haven’t gotten around to middle game scouting yet though it’s a basic skill. See the expansion attempt, kick it down before it starts with a few units, starve out the terran. The hydra-ultra army should have been enough to keep the terran army bottled up if a few zerglings spotted expansion attempts.

Here’s another weakness: This is the 4th pair of scourge to chase this dropship, and the scourge is veering away for no reason. The 5th pair finally caught it. Suicide missions are hard to recruit for. Steamhammer showed hesitation with scourge and in shutting down vulture harass. In this picture, Krasi0 has turned it around and is winning by a mile.

documentation

1. I uploaded documentation for Steamhammer 1.1.1’s configuration file.

2. Next I’ll write a short document “getting oriented to the code”.

3. In future versions I’ll update the existing documents to that version and slowly add new documents. Documentation links for each version will be alongside the download links on the bottom of Steamhammer’s web page.

Steamhammer 1.2

Steamhammer 1.2 will be tested to play any race. I have promised it will be ready by the Ides of March, as a bad omen for everybody else. I will have it play random on SSCAIT as a test.

So far, my initial prediction is holding up: Terran and protoss play seem to show a small number of bugs. I will fix those and also add a small number of features to better support random play. There will also be a small number of other bug fixes and minor features, and that will be all.

Curious fact: Steamhammer versions 1.1 and 1.1.1 are currently 3-0 versus Bereaver and 0-3 versus Killerbot by Marian Devecka. I don’t think it deserves either of those numbers.

The wins over Bereaver are exploiting a weakness. Early in the game, Bereaver techs too hard and doesn’t defend itself adequately, and some of Steamhammer’s openings mass-produce zerglings at a timing that exploits the weakness. I don’t expect all the openings to win; Steamhammer got lucky so far.

The losses to Killerbot are due to scouting wrong (in the most recent game) or taking poor tactical engagements (in the other two). Against Killerbot, these Steamhammer versions play a more solid counter to Killerbot’s overpool +1 opening. Steamhammer now goes overpool with an early second hatchery to outproduce Killerbot in zerglings for a while, occasionally winning outright but usually buying time to transition into spire, which Killerbot can’t defend. I think Steamhammer’s strategy advantage at least equals Killerbot’s skill advantage in tactics and crisis management. Steamhammer’s long term score versus Killerbot should be 50% or more.

You can’t tell how two bots fare against each other from a few games. You especially can’t tell how Steamhammer fares, because the bot plays so many different openings. I propose new wording for the law of small numbers: Small numbers speak small.

On 2-player maps, some games of Steamhammer against strong bio terrans, LetaBot and Tyr by Simon Prins, have gone like this: Steamhammer opens with mutalisks and, seeing defenses at the front and not knowing how to fly around them, falls into a standoff. Both sides build up for a while. The terran moves out with an infantry force. That’s a head-to-head fight that the zerg flyers understand, and they clean up the terrans before serious damage is done to zerg bases—not without losses, of course. Meanwhile, Steamhammer has long since sent out a drone to take a 3rd base, but the drone was confused by the blocking buildings on Benzene, or the blocking minerals on Destination or Heartbreak Ridge, and is still wandering back and forth looking for the way. Steamhammer has a mineral excess but does not make macro hatcheries because it is waiting for the new base to start. Zerg can’t keep up in production and loses to the next attack.

Map blocks are causing too many losses. I have to do something soon. Most bots stronger than Steamhammer already take measures (I think only Bereaver still suffers losses to map block issues). What are the options?

1. Fix pathing: Go around the blocks.
1. Goal monitoring: Detect units which seem stuck and reroute them.
2. Detect that paths may go through blocks and (somehow) take extra care.
3. Switch to BWEM. I want to, but maybe later?
2. Clear the blocks.
1. Clear blocks near our bases unconditionally. I think some bots do.
2. Clear blocks which are adjacent to the main, or to an expansion we want.
3. Goal monitoring: Clear blocks near stuck units. The units themselves can often do it.
4. Hypothetical path analysis: Clear a block if it makes a path that we want to take shorter.
5. Strategic analysis: Open paths which are more valuable to us than to the enemy.
3. Work around it in some cheesy way.
1. Take bases in an order that doesn’t run into map blocks.
2. Hardcode, or add to the config file, a list of maps with blocks and what to do about them.
3. Get vision of the base first, and then mineral walk to it, passing through blocks.

Obviously the ideal is to both fix pathing and clear the blocks, as in 1C plus 2E. Goal monitoring has some value, but not much value if the goals hardly fail.

To analyze from general principles whether it’s a good idea to clear a given block, you need hypothetical reasoning: If I clear this block, then that path opens, or that shorter route becomes available. I don’t notice direct support for hypothetical reasoning in either BWTA2 or BWEM. It doesn’t seem all too difficult to cobble something together if you can find out what choke each blocking mineral/building blocks and the choke-to-choke distances.

For now I don’t want an ideal solution, I want something simple that solves enough of the problem. I expect I’ll start with 2B and adjust as needed.

What do others do? Are there tricks or pitfalls?

Update: I should have talked about mineral walking. Quite a few competitive maps are designed with small mineral patches on one or both sides of a block. A worker at the block can see the minerals on the other side, right-click on them, and pass through the block, but another kind of unit cannot. Electric Circuit in the SSCAIT map pool has the feature, but the map is not used, because too many bots get units trapped behind the blocks. Of course, as long as the map is not used there is no incentive to fix the bugs....

And that suggests an idea for zerg bots: First send an overlord to any base that you want to take. With vision of the minerals, you can mineral walk the expansion drone to the base. Having vision also gives some assurance that the base is safe and worth taking, and it lets you deal with spider mines. I’ve added the idea to the post as 3C. I hadn’t thought of it before, but now I’m seriously considering it.

Steamhammer’s web page is updated through version 1.1.1. Download source there. I’ll write two bits of documentation, one for the configuration file in this version and one “getting oriented to the code.” Stand by; it may take a few days.

By the way, version 1.0 scored 151-82 (65%) over its active lifetime. Version 1.1 scored 8-14 (35%) in the one day before the bugfix version 1.1.1. Version 1.1.1 has scored 11-5 (68%) so far. I let a big big bug slip in!