Starcraft AI blog

Steamhammer 2.0 is submitted for AIIDE 2018. All I have left is the waiting.

Since yesterday I fixed one bug, a newly introduced bug in the worker manager that could cause a small number of drones to temporarily go idle early in the game, when it matters a lot. I made an attempt to fix a lingering weakness related to cooperating with static defense, but had to roll it back. The fix was a 2-line change, but somehow it caused a hard-to-understand bug, and I can’t accept a risk like that so close to submission time. Also, since an entire day is too long to go without working on the openings, I added a new opening that helps Steamhammer sidestep weaknesses in ZvZ, allowing it to beat more opponents. And I ran all the tests I had time for, looking for new bugs, checking my fixes, and verifying that the new opening functions as intended and earns wins.

It’s hard to understand why, but now I feel tired....

New bot DaQin on SSCAIT matches an AIIDE entrant. It may be the AIIDE entry, or it may be a test version shortly before the entry is made. It looks like a Locutus fork. The .dll is larger than the Locutus .dll by about 24K out of 2.5M—a fair amount of code but no drastic rewrite. The play I’ve seen so far looks similar, lots of dragoons with strong Locutus micro, so without digging deeper I’m not sure what the changes are.

As one of my tests today, I ran a short match Steamhammer 2.0 - DaQin. Steamhammer took several games to find a way to win (not long at all), and after that it won every game, though I didn’t play many and one of the games was excitingly close. I didn’t try the old version Steamhammer 1.4.7, but with Locutus skills I expect that DaQin would have won every game. I don’t think Steamhammer 1.4.x has a way to beat DaQin. It was satisfying to see Steamhammer 2.0 score convincingly, and it helped my confidence.

We’ll see how much Locutus has improved since August!

Steamhammer is almost ready for AIIDE. I have fixed all the major bugs and weaknesses that I have time for—the last was a newly-introduced bug in mutalisks caused by tightening up the micro, it was a bad one. The rest will be simple low-risk fixes and testing to make sure I don’t have another disaster like in CIG (it’s a risk, I wrote a bunch of new code and my change log records over 80 items).

Steamhammer is still weaker against some opponents, though not by as wide a margin as in my last update. It still crushes some opponents that it used to lose to. I can’t foresee which way the balance will fall, definitely not in this tournament with so many new names. My ambition remains to finish in the top 3rd, about the same as last year, which will mean that I am keeping up with the blazing fast progress in the scene.

There are changes at all levels. I have the highest hopes for improvements to the opponent model (key for a long tournament), the squad structure (sounder in principle than the old one), and certain of the micro optimizations (not fully exploited yet, but a firmer foundation).

Regardless how well Steamhammer performs in AIIDE, looking back over the past year I feel I’ve gotten a good amount done. Steamhammer is still short on basic skills, but compared to a year ago it is smarter in most ways. There is a mountain left to move, but I am that much closer to having moved it.

Steamhammer 2.0 for AIIDE will be specialized for zerg only. There won’t be stuff for the other races in the config file, and I haven’t tested that terran and protoss work at all. I’ll upload it to SSCAIT shortly after the AIIDE deadline, only turning on a few of the screen drawing options. Since it plays so differently, I’ll erase the learned opponent data again. A few days after that, depending on how wiped out I feel and whether any surprises turn up, expect Steamhammer 2.1 and its identical twin Randomhammer that plays all races. Along with, of course, a series of posts about the details of my work, the unexpected problems that cropped up, and the known problems that I would have solved if only there were more time.

The good news is that I have definitely made enough changes to Steamhammer that the next release deserves to be called Steamhammer 2.0. In some situations it plays much more strongly. The bad news is that I still haven’t fixed all the bugs introduced in making such extensive changes. Changing the squad structure, which has little direct effect on unit control, had surprising indirect effects on the micro of different units—and I also made changes to micro itself. There are situations where it plays much worse, and some are difficult to debug. I may have bitten off more than I can chew.

The effect is big: Some formerly difficult opponents are easy, some formerly beatable opponents are difficult. With all the new names in the AIIDE entrant list, it’s impossible to guess whether Steamhammer will face opponents it finds easy or difficult.

Steamhammer also has new skills like defiler use, a new layer of micro infrastructure, more smarts in the opponent model (time-consuming to test), improvements to the strategy boss, and a bunch of new, fixed, or retuned openings. And stuff. Special preparations against Steamhammer might backfire.

Well, regardless of how well Steamhammer performs in AIIDE, I feel that I’ve made progress that I can believe in. The new squad structure is more complex so it allows more ways to go wrong, but it fixes fundamental weakesses that are inherent to the legacy design and it does not create new fundamental weaknesses. What I mean is that, in principle and if polished enough, it could be superior in many situations and worse in none. It’s not that polished yet....

Anyway, there is still over a week left. I have other things to do too, but I should be able to make fixes. Outlook: Moderately good.

Steamhammer still has occasional devastating bugs in its reactions. Steamhammer-Sungguk Cha is an example. Sungguk Cha is an opponent Steamhammer usually has little trouble against. In this game, zerg played a not-very-appropriate lurker rush and handily held the initial marines. The zerg economy was weak, but the tech was there to cope with the next phase of vultures and wraiths, and zerg was in position to fight on. Instead Steamhammer fell into a loop, spawning zergling-overlord-zergling-overlord etc. With massive oversupply of overlords, a broken unit mix, and money piling up with no second hatchery in sight, only terran was in the game.

There are actually 2 bugs. The main bug is that an emergency reaction (“Oh no I have no army hurry hurry spawn stuff”) didn’t recognize that it had already occurred and fired repeatedly, dumping the long sequence of zergling-overlord into the queue. There are checks to prevent that sort of thing, and I haven’t spotted the mistake yet. If I don’t find it soon I’ll let it go until after the AIIDE deadline, because there are more urgent fixes to make.

As often happens, the primary bug triggered a secondary bug—bugs tend to cause unusual conditions, and unusual conditions tend to bring out more bugs. After a few extra overlords, any further overlords should have been recognized as excess and dropped—the idea is to drop planned overlords that are no longer needed after the army is destroyed in battle. That bug I have fixed. The issue is that Steamhammer was still technically in its opening book, though it was nearly at the end of the opening line. The opening book sometimes deliberately makes extra overlords (to save up larvas and produce mutalisks or lurkers in number all at once), so the check was turned off in that case. It was easy enough to add back a check that is loose enough that it doesn’t break openings.

As Willy Wonka said, so much time and so little to do. That must be why I haven’t posted in a week.

The development Steamhammer version still makes many facepalm-level mistakes—the guardians press forward into enemy corsairs while the devourers run away, that level. Even so, testing today shows that its tactical play has improved so much that it can win long difficult macro games against opponents that used to smash it every time in those games. The old blunders where Steamhammer might at any moment throw away its army by suddenly retreating through the enemy, or the like—those blunders are completely gone. In restructuring squads I introduced an all-new stockpile of different mistakes, and those mistakes I have cleaned up enough that they are minor by comparison. Defense squads especially needed a lot of attention.

Since late last year, Steamhammer has been able to play with strong macro. It has finally gained the ability to use the large number of units it can make without wasting too many. It can freely enter into situations that formerly I tuned its openings to avoid. The work took a tremendous amount of time, but the time was well spent.

I still have stuff to fix and features to add, and the time is wearing on. In AIIDE, I hope that Steamhammer can keep up with the field and finish about as high as it did last year. Progress has been blistering, and if I can keep up with it then I feel I’m doing great.

Today, trying to track down a mysterious regression, I noticed this condition in an if in CombatCommander::getAttackOrder():

enemy.type == enemy.type == BWAPI::UnitTypes::Protoss_High_Templar

Hmm, it looks a little different than I intended. == is left-associative, so this always evaluates to true. The effect is that Steamhammer might make a poor decision of which enemy base to attack. The decision is pretty rough anyway, though, so the buggy decision is not much worse.

Gotta love edit slip bugs, they are so creative. In this case, the original intention is also wrong, because high templar are excluded by an earlier check—the condition would have always been false.

If only I could find the bugs that matter, instead of the bugs that don’t hurt much....

One of the earliest improvements I made for the upcoming Steamhammer 2.0 for AIIDE was superior zergling micro. In an equal fight, zerglings on zerglings, Steamhammer tended to come out ahead of Killerbot more often than behind. Now, after many other changes, I have somehow broken it, and Steamhammer loses equal fights. I tried undoing all the changes that seem as though they could be related, but no go. I don’t know what I have done wrong. It’s amazing how fragile some skills are.

Weaknesses are stubborn. The first wipe doesn’t clear away the dirt, you have to scrub repeatedly. I made changes to improve kiting, and hydralisk play is noticeably sharper. But mutalisk micro is worse, because the changes caused seemingly unrelated code to misbehave. I think it will be easy to fix, but what weaknesses did I introduce without noticing?

In another example. I have been systematically working through Steamhammer’s openings to fix faults that have crept in because of other changes: Queue reordering, queue jam clearing rules, mineral locking, and so on. Most openings are OK, but a surprising number need minor adjustments. I also found a subtle one-frame-late timing bug in the interaction between the building manager and the strategy boss that broke a single rarely-played opening. Everything is connected.

Strong interdependence seems to characterize Starcraft skills. When you change one point, it doesn’t matter if it’s a big improvement, you have to also align other points to realize the improvement. As Dan Gant expressed it, a bot is usually at a local maximum in skill. When you nudge it in any direction, it is no longer at a maximum, and you have to hunt around for a new local peak, which you hope is higher.

It makes progress bumpy. On the one hand, that drives me to machine learning: I don’t want to get all these details right by hand! It’s too much! On the other hand, it poses tough problems for machine learning algorithms, too, whether learning holistically or piecemeal. Such a complex and difficult fitness landscape is hard to optimize over, whether by hand or by machine.

Yesterday I changed Steamhammer’s Micro namespace into a class. Instead of Micro::Move(unit, position) or whatever, I write the.micro.Move(unit, position) (because I didn’t update the capitalization, at least not yet). The technical difference is that the class can remember state.

It is part of the process of rewiring Steamhammer with goals and goal monitoring throughout. Micro::Move(unit, position) is a command for the unit to move to a position. the.micro.Move(unit, position) will be, once I’ve finished the implementation, giving the unit a goal to move to a position. My immediate purpose is to make Micro unstick stuck units—this way hides the details from the rest of the code. Eventually, with its knowledge of what each unit is trying to do, Micro might take on many other jobs: Find paths, follow specified paths, evade enemies on the way, coordinate kiting units, and in general notice and work around all kinds of unit level goal failures, or notify the rest of the program if the failure cannot be worked around (“you can’t get there, a pylon wall is in the way”).

I’m not sure what jobs I’ll end up actually assigning to Micro. At a minimum, it will have the lowest-level unit control stuff. Path following seems likely; because implementing it this way looks clean and simple.

One step at a time!

I am still working on squad tactics, as I mentioned some days ago. I wouldn’t say the tactical play is adept (I’m not far enough along to test for strength), but as I fix problems it is slowly starting to resemble decent play. There is more to straighten out, but the strange Steamhammer misbehaviors of darting sideways for no reason, trying to retreat through the enemy, hanging back from the front, or losing groups of rear units in bad fights—those problems are all gone. The potential for tactical skill is much higher, and the question is how much of the potential I can realize. More polishing to do!

As I make progress with the play, the code is growing messier. There were already too many special cases (see Steamhammer’s squad structure 1: awkward points), and I had plans to rewrite squads entirely (see the followup post Steamhammer’s squad structure 2: design ideas). Now the special cases need to be carefully stacked in the right order to stand up at all, and the structure is growing dangerously shaky. The rewrite is needed more than ever, and I have a firmer idea of what is needed.

This has me thinking of plans and priorities for after the AIIDE deadline on 1 October. I feel a need to return to basic infrastructure work. Steamhammer 2.0 for AIIDE will be zerg only, because I am deliberately ignoring terran and protoss skills. So the first order of business will be version 2.1 that can play all races again—it will take some work, I’d guess a few days. After that, probably the top infrastructure priority is to finish the map analysis work and drop BWTA. There’s only one big feature to go, chokes and regions, and I think I can finish it in one more step in version 2.2. After that, the major infrastructure needs are the squad rewrite and getting rid of BOSS, both of which will take longer and should probably be done in stages.

I hope that the AIIDE Steamhammer will be the strongest ever by a good margin. But after that I have to get into plumbing repairs. The version for the SSCAIT tournament in December should have cleaner code and be easier to work with, but it is not likely to be much stronger than the AIIDE version.

2 recent events with a connection to Krasi0.

Krasi0 updated

Krasi0 has been updated with terran wall skills. Locutus doesn’t understand the wall, and Krasi0 is winning against Locutus again. Bruce predicted it would happen before AIIDE, and here it is. With a wall, Locutus cannot run by into the terran main, and Locutus does not have the skills to pressure the wall.

I think Krasi0’s wall build versus Locutus leaves protoss with an advantage, because the terran natural is delayed. But Locutus, showing its Steamhammer heritage, is impatient and presses too hard early, falling behind. Krasi0 has been winning most games easily.

I’m sure that in time we’ll see a Locutus version addressing the weaknesses. For now, the elo ratings of the 2 bots are converging. Will Krasi0 be able to pass Locutus in elo? Even with wins head-to-head, that might be hard.

Steamhammer strange crash

Here’s a new one. In Krasi0-Steamhammer on Icarus, Steamhammer lost its main and natural and was left with only its third. It’s a situation Steamhammer has been in many times, and zerg normally recovers if given time. It can win the game if the opponent never finds the base, or is also crippled.

This time something went wrong that I’ve never seen: Steamhammer rebuilt drones up to 14, which is abnormal. It is coded to replace the spawning pool at 9 drones. Then, even stranger, with an idle drone because there were too many and its minerals piling up, it got into a loop where it made nothing but overlords. It seemed to be in Plato’s cave, watching a bad movie that had nothing to do with the game.

Then it crashed. Some data structure must have broken. :-(

There are 2 changes I want to make to Steamhammer’s opponent model. Both of them will take some reading up and thinking.

1. The exploration algorithm is not good enough in practice. Its purpose is to try different openings to counter the opponent. Steamhammer uses epsilon-greedy (that is, a fixed probability) to decide when to explore, and to decide what to explore it uses an ad hoc strategy of at first trying openings to counter the opponent’s recognized plan, then with more games casting a wider net.

The problem with deciding when to explore is that Steamhammer knows more openings than it has time to try. With more choices than games, we can model the situation as an infinite-arm bandit. I haven’t read up on it yet. Here are a couple papers I found in a quick look for infinite-arm bandit solutions, if you want to get ahead of me.

Algorithms for Infinitely Many-Armed Bandits (Wang, Audibert, and Munos, 2009)

Simple regret for infinitely many armed bandits (Carpentier and Valko, 2015)

The problem with deciding what to explore can be solved with opening data. Data telling which openings work across all opponents (versus different races, on different maps, with opponents following different plans) can be used in solving both problems. But it will take a long time to collect the data; expect it late this year at the earliest, likely later.

2. It doesn’t mix up its openings enough. Steamhammer’s classic randomized openings were effective. Now it often chooses an opening depending on what the opponent has done in recent games, and can get stuck on fixed responses after the opponent has switched. For example, Proxy was updated to follow a mutalisk plan instead of a zergling plan in ZvZ, but Steamhammer is still responding to the zergling plan, and losing every game because of it.

Steamhammer tries to tell whether the opponent follows a fixed plan, or varies. It doesn’t matter whether the variation is random, or reacts to past games, or reacts to events in the current game, or is due to the bot being updated; the opponent is playing a fixed plan, or not. For example, if Steamhammer tries a 5 pool and Bereaver reacts with its cannon defense, Steamhammer will conclude “Oh, Bereaver doesn’t do the same thing every game.”

Right now, the “my opponent is a constant” recognition is used in a tiny way. I have always wanted to use it to optimize opening choices, like so:

If the opponent plays a fixed plan, Steamhammer should seek a fixed counter. Most bots with opening learning, including Steamhammer so far, seek the best fixed counter; it’s easier and works faster. If the opponent varies its plan, Steamhammer should in general follow a mixed strategy, which is to say, it should choose randomly among some of the effective counters. This is not as easy to code and takes longer to converge on a good solution, but it makes life difficult for opponents which try to learn or adapt.

Steamhammer crashed in the game Steamhammer-Middle School Strats. The game itself is not interesting. Middle School Strats is a rushbot, and Steamhammer had played it twice before, according to its game records. In the second game, Steamhammer misdiagnosed the opponent’s opening, so in this third game it played the wrong counter and got run over. Since Steamhammer crashed, it did not save a game record and will likely lose the fourth game in a similar way.

From the timing of the crash, it looks as though it was caused by the “impossible” bug that I recently fixed. The underlying crashing bug has been there since version 1.4.1 in April, and this is the first time it has manifested in public. I only discovered the crashing bug because I introduced another bug in my development version that brought about the infrequent conditions needed to trigger the crash!

Reliability is hard. Another bug is that Steamhammer’s reaction to having a mutalisk irradiated is broken—it has been broken since last year, and I still haven’t found the cause. An irradiated mutalisk is supposed to move away to save other zerg units. The code worked when written, and to my eye it looks as though it should still work, but somehow it has bitrotted—mutalisks don’t seem to react at all to being irradiated. How am I supposed to handle an interesting case like an irradiated ultralisk when I can’t handle an easy case?

I habitually take a top-down view of things (I’m a lumper, not a splitter), and I want to use an example to draw a comparison. The example is: Steamhammer’s production queue data structure is inherited from UAlbertaBot. It looks like this (I left out the constructors).

struct BuildOrderItem
{
    MacroAct macroAct;  // the thing we want to produce
    bool isGasSteal; 
}

Steamhammer renames UAlbertaBot’s MetaType (which might mean anything) to MacroAct, and extends it with a MacroLocation to specify where things are to be built (and other changes).

I want to simplify this, and it should be easy to understand why. Stealing gas amounts to building a refinery at a given location—it should be specified as a MacroLocation, not as a separate flag outside the MacroAct. I can drop the wrapping BuildOrderItem data structure and keep a queue of straight MacroAct values. There will be one less level to the data structure, a distinct improvement.

On the one hand, it simplifies the code and it’s a straightforward, low-risk refactoring. There are many uses of BuildOrderItem and it will take time to handle them all, but the compiler will tell me if I forget to rewrite one of the uses. On the other hand, it doesn’t affect play in the least. The production queue will behave the same, and it is not a heavily used data structure that affects performance.

So from a project management perspective, what’s the best time to carry out the work? The sooner you do a code simplification, the longer you benefit from it. But it will take time, and I want to concentrate on play improvements for AIIDE. What’s the best timing?

Well, it’s not an important question. I might do it before AIIDE or after, and it won’t make a big difference either way. But I find it interesting to think about. Optimizing the development process is similar in concept to optimizing Starcraft play: It is about taking actions, sometimes tiny actions, that improve efficiency over time. It requires similar subtle judgment calls. Take actions with big enough cumulative effect, and you pull ahead; you have to decide which actions are worth your limited time. To me, taking the abstract view, the big difference is that in software development you get more time to think about it—coding is a slower-moving game.

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!

After defilers, I did smaller micro and tactics fixes, corrected a few openings, and made other quick improvements. Then I looked over my to-do list and marked the items that would benefit from having on hand the results of a tactical analysis—wow, that’s quite a few, tactics are next! So far I have implemented clustering as mentioned here. I think that within a few days I should be getting practical results like decisions on which direction to retreat in, and then I’ll start seeing where my tactics plan needs revisions.

spider mines

In the meantime, I am also thinking about spider mines. In spider mine placement I wrote about the complicated considerations behind laying mines. Coping with the enemy’s mines is also complicated. These 5 counters to spider mines are all common in pro games.

1. Sweep the mines. The most obvious counter is to bring a detector and ranged units to safely clear the mines.

2. Force the mines. With good micro and the right choice of units, you can try to get by without a detector: You can shoot down spider mines after they pop up. It’s the most common way for terrans to cross a minefield. Dragoons and hydralisks can do it too, with more care, and so can dark templar, or zealots with high enough attack upgrade (+2 for 20 damage, enough to kill a mine in one hit), or in fact any combination of units which are quick and coordinated enough to do the damage in time. One risk that too many mines will pop up at the same time, and you’ll have to dodge them to reduce the damage. Another risk is that the enemy may appear, possibly forcing you back since you won’t be able to cope with mines and enemy units at once.

3. Dodge the mines. Find out which unit of yours the mine is targeting (the mine’s getOrderTarget() will tell you, as Purple Dan pointed out). Simply move the target unit away from the mine—and ideally away from any other units of yours which might be in splash damage range. There is a delay between when the mine decides to stop and explode and when the explosion occurs, and if you are moving away during that delay then you can suffer only splash damage instead of the full effect. (The same idea works for scarabs.) It makes a big difference.

4. Sacrifice to clear the mines. If you want to attack through a minefield, or if you are otherwise in a big hurry to destroy the mines, you won’t be able to do any of the above counters. Send a few zealots or zerglings through the minefield on move command, to trigger as many mines as possible. Being on move command is important; a unit that fires on a mine will stop moving and won’t trigger as many mines. The mine clearing units will be lost, but attackers can follow behind. I’ve occasionally seen terrans sacrifice marines to clear mines, but it is not as common or as effective. This technique is probably worth using during an attack when there is any suspicion of a minefield.

5. Drag the mines. If you are sacrificing a unit on move command to clear mines, what is the best place for your unit to end up? Right next to the enemy, making the enemy’s weapon backfire. A great mine drag can blow up a mass of tanks in moments. Pros know to place spider mines away from where their units intend to go, and to destroy their own mines when their units go there anyway. Bots tend to be careless about mine placement, and are acutely vulnerable to mine drags. Zealots from a shuttle can drag mines too; I think that variation is most valuable when you already know where the mines are.

Less common counters to spider mines exist. You can clear mines without damage by dropping units from a transport and picking them up again with exact timing. Psionic storm will clear mines from an area, but is generally not worth it. Disruption web stops mines from triggering, a use that I have never seen.

One other idea comes to mind, not a common technique as far as I have seen: Play tricks with the mines. You can deliberately leave mines in place and use them to show the enemy what you want the enemy to see. For example, an observer can spot mines without being seen in turn. Notice some mines and leave them unmolested and seemingly undiscovered. Then, when you need a diversion, send an empty shuttle over the mines and it will look convincingly like a drop (a fun use for hallucinate). Someday bots will be smart enough to be fooled!

Knowing that there are spider mines on the map affects your tactical planning from the beginning. Even units like workers that don’t trigger mines will be seen by them, giving away information. Some mines you may spot ahead of time; some you will not. If you’re smart, maybe you can guess where mines are likely. No matter what, you know that moving around the map will rely on the 5 counters.

I would like to get all 5 into Steamhammer for AIIDE, but I’m not sure how much progress I’ll make. I guess mine dodging will be first, since it is so similar to scarab dodging that it can probably be done at the same time.