Starcraft AI blog

Since yesterday I’ve been fighting a mystery bug, one of those “should never happen” bugs that happen in unsafe languages like C++. Under some narrow set of circumstances, fetching the top item from the production queue fails with symptoms which indicate that the queue is both empty (so you can’t get the top item) and not empty (so that you try to). In other words, something stepped on the data structure and broke it. I haven’t touched the queue lately, so it might be anything.

Luckily it’s reproducible, at least usually, so I can narrow it down step by step. It’s not due to the new ops boss, it’s not due to changes in the combat commander, etc. The narrowing down process eats time as if time were the world’s most luscious burrito. I’ve now determined that it has something to do with the hydralisk den in the queue, so I may be getting close.

See bizarre bug for my May experience in being called stupid by the language. Coding in a safe language is 10 times nicer. :-/

I’m not disciplined enough! I have too many ideas!

Each time I add a piece of basic infrastructure, which I do because I foresee its valuable uses, I feel overwhelmed by the valuable uses and start thinking of new ones. Then I need to write the ideas down and give them an initial evaluation. If there’s a better plan, shouldn’t I switch to it? I keep changing my plans, and it is slowing me down. Well, I always change my plans a lot, but now I’m doing different stuff that (at least psychologically) allows more room for changes.

When I implemented unit clustering, I had a plan f0r how to use it at the operational level (so I put it in a new class OpsBoss) and a plan for how to use it one level down for squad control tactics. Having seen my code in action and thought about it more, I find a lot more uses, including everything that touches on pathing. I also thought of a more complicated but clearly better plan to use it for squad control.

I’m still thinking through the new plan. While that is percolating, yesterday I added another bit of basic infrastructure, target tracking so I can keep tabs on who wants to shoot at me. And I wrote its first use, reacting to spider mines. Obviously it has many more uses; it should factor into combat micro throughout... along with other information that Steamhammer doesn’t collect yet. The possibilities are slowing me down just by being so numerous. It’s easy to get distracted, and it takes time to set priorities.

I’m not disciplined enough to keep my to-do list short and manageable!

Your bot got 5 pooled and lost. Well, you can fix that, you just need a strong reaction to the rush. Maybe scout early so you can see it coming (Iron does this), and if so, get the barracks earlier and have a bunker up in time. Then stay at home until you’ve built up enough forces to move out against the ever-increasing number of zerglings at your doorstep. And it works! The early pool set your enemy back, and with your reaction you smash those cheap rushbots!

Then along comes the bot named 5 Pool. (It last played on SSCAIT over a year ago, and not in its most sophisticated version.) It opens with 5 pool as its name says, you see the rush coming, you are completely safe—but there is no stream of zerglings looking for a way to break in. After a handful of zerglings to scare your bot into reacting, 5 Pool switched into drones and tech while you unnecessarily built up your forces to safely move out. Marines and medics step into the map and... mutalisks annihilate the force and move on to pick apart your base. Somehow your reaction to being rushed set you further back than playing 5 pool set your enemy back! How did that happen?

Zergling rushes are successful in bot world because they are easier to code than to defend against. In fact, rushes like that are very difficult to defend accurately against; it is much easier to overreact to the rush and be safe for the moment than to react with exactly enough defense, and especially so if your bot is new and lacking in skills. If you see the rush coming in time and react accurately, you are ahead because the early pool set your opponent back. If you overreact and spend too much on defense, you may fall behind. The bot 5 Pool exploited the fact that most opponents either didn’t react and lost, or overreacted and fell behind. Exploiting overreaction is a fancier trick, but it is also easier to code than to defend against, and 5 Pool ranked high.

I remember the struggle of Steamhammer versus 5 Pool. As zerg, it is relatively easy to avoid overreacting to a rush: Just go 9 pool, and if your worker defense is sub-par, add one sunken. You are in the lead. At first, 5 Pool could not make headway against Steamhammer’s strong ZvZ (well, strong by bot standards). Eventually, the author developed a sunken turtle into 3 hatch ling strategy that overwhelmed Steamhammer’s fixed middlegame plan. Later came a tougher strategy, sunken turtle into mutalisks, that beat Steamhammer reliably. Steamhammer understood what was happening and tried to react correctly, but overreacted to the enemy sunkens, went overboard on drones, and got its mutalisks too late. It is very difficult to react perfectly. More recently, CasiaBot adopted an optimized version of the same opening to beat Steamhammer, and CherryPi can play a similar strategy. It was months before Steamhammer’s openings and reactions were crisp enough to avoid overreaction.

Overreactions are exploitable weaknesses, and exploiting them is generally easier to code than to defend against. Bots overreact often, and to various events.

Steamhammer was possibly the first zerg bot to make a small number of zerglings to keep tabs on the enemy while teching to mutalisks (it’s standard in human play). In early months, Steamhammer won a lot of games when opponents overreacted to the zerglings, seeming to assume that they were facing a mass zergling threat. Even Iron often made an unnecessary bunker. Today most opponents have become more circumspect, but I think LetaBot overreacts to the early zerglings even now.

Locutus's pylon harassment skill (which is so strange that I could not understand it at first) is another example of exploiting overreactions. The skill amounts to simply building pylons in plain sight in the enemy base. It was first used against Iron, which overreacts extremely to proxy buildings and sets itself far back. Many other bots overreact to a lesser degree, including Steamhammer (I made a change recently to reduce the overreaction, but it’s not gone yet). How is your bot supposed to know that it’s only a pylon, and no cannons or gateways are going to appear in your base? You have to react, and it is difficult to react just enough to be safe against a proxy while not so much that you fall behind when it turns out to be a bluff.

Most forms of deception do not work against bots, because bots are not smart enough to fall for them. Exploitation of overreactions is a form of deception that often does work, at least against bots that react at all. I think bot authors should be on the lookout for other cases of overreaction to exploit. Since eliminating overreactions is difficult, exploiting overreactions will force a lot of progress.

Protoss is going strong right now. Locutus is #1 by a mile. Both PurpleWave and BananaBrain have moved up the chart. Among the other races, only zerg Proxy has shown a similar rise in strength lately, and Proxy remains lower in the ranking.

Does this mean that it is easier to reach the top with a protoss bot? Maybe it is; I can’t disprove it. But I notice that, as years go by, the dominant race keeps changing. Protoss has been on top before, and rotated out. Terran and zerg have had their turns looking down on the other races, and I suppose they will again.

I think the story is that the protoss authors have been working harder on the important skills. As the community learns, bot skills that once took creativity and sweat to implement have become familiar and simple. Some beginner bots, like Bereaver and Proxy when they were brand new, started out above the level of champions of earlier years, which is possible only by building on the past. The upshot is that the skills a winner needs—the ones you spend creativity and sweat on—change over time. To score better you need to invent new skills, or polish old skills so highly that it amounts to the same thing. The points on which it is most important to make progress change as we make progress.

Steamhammer, by the way, is another bot that saw early success, in part because it built on UAlbertaBot and in part because it was one of the first zergs to play efficient pressure openings. An early version with only a few weeks of work finished #16 in the SSCAIT 2016 finals, and version 1.2 from March 2017 (a little more than 3 months after I started) was ranked a stable #3 on SSCAIT. After the first several months I begin to pay more attention to the destination than to the road, and other racers slowly passed me by. (I of course believe that my plan is the high road that will get me ahead in the end.)

Anyway, the moral sounds self-evident: You have to be strong in 2 areas. First, get the basics down, and keep up with the current level of play (this is what Steamhammer has been neglecting). And second, think up the right new ideas for today, the ones that other bots will react incorrectly to or will not be able to keep up with. Whoever does it the best wins, and right now protoss is doing it the best.

Alternately, you could try for a breakthrough idea. Nobody has succeeded at that yet, but eventually somebody will. I think that in every game where computers started out weak and became strong, one time or more an author implemented a breakthrough idea which set a new paradigm, laying the foundation for a taller building. Starcraft will see a breakthrough too.