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....