Starcraft AI blog

I have sent in Steamhammer 2.2 to do battle in AIST S2. I think I’ll take several days to test with terran and protoss, and to fix up the terran and protoss openings and any new bugs I find, before I release 2.2.1 for SSCAIT.

The new map analysis does not change Steamhammer’s strength, or at least if it does, I can’t tell yet. Experience has to teach me. Also, in between working slowly, adding too many new openings, and fixing too many old bugs, I didn’t finish the useful tactical skill that I wanted to add (I did start on it). Nevertheless, a couple of the bugs I fixed were doozies, and one of the openings I added shreds certain difficult opponents. I’m expecting version 2.2 to be modestly stronger than the current 2.1.4.

The scouting path. One of the last changes I made—I finished it up today—was to fix the scouting worker’s path around the enemy base. The inherited code from UAlbertaBot did not work well with the new map analysis. I ripped out the amazingly complex code that calculated waypoints around the edge of the enemy base, producing a looping path, and replaced it with a simple exploration algorithm. The change reduced the DLL size by about 5K, which shows how complicated the old waypoint code was.

I had to choose something simple, because I didn’t have time. The exploration algorithm works pretty much the same as the algorithm for exploring the map to find the last enemy buildings. Instead of looking through the whole map for places that have not been seen recently, it looks around the enemy base, checking each 320x320 map grid square. If it is to scout “once around” the enemy base, then it leaves once every grid square has been seen.

The new behavior has advantages and disadvantages. On the one hand, since it actively explores it is less likely to miss important buildings. It is often able to leave the base sooner because it can see everything quickly, and it doesn’t have to look at anything that the scouting overlord has seen. On the other hand, leaving sooner means that it misses what happens next. Also the irregular path around the base is not as good for evading enemies; it’s harder to catch a scout that is moving in wide loops. The drone sometimes gets stuck on buildings or mineral patches. And it doesn’t peer into the corners, because the 320x320 cells are big (that’s 10x10 tiles). I’m curious to see how good the scouting is in serious games.

In coming days I’ll be writing up the map analysis with details and posting a change list—the usual new version posts. I guess longer-term plans will be after that. And I’m watching the spam attack so I can turn on comments as soon as it ebbs.

The blog is under massive spam attack. I’ve temporarily turned off commenting. :-(

I’ll turn it back on as soon as possible. Spam waves usually don’t last long..

I’m not entirely satisfied with Steamhammer’s zones and chokes. The bot plays reasonably enough, but I’ve started to think that the data structure is not an ideal fit.

Steamhammer uses zones for recognizing proxies and figuring out areas that are in need of defense. This is essentially a heuristic, “these locations are in some way close to each other for practical play purposes.” But nothing in the definition of a zone (or, as best I understand, BWTA’s definition of a region, or BWEM’s definition of an area) says that its parts are “close together”—they’re only connected without any intervening choke. It seems to me that to reason about things like “where do I need to defend?” it is better to analyze paths and distances rather than use zones as a rough shortcut. And in fact Steamhammer does check distances as part of its calculations; the zone is not enough information by itself.

Properly, zones and chokes are for reasoning about the topology of the map. “I can go this way,” meaning through this sequence of chokes, “or go around the long way.” Or on Andromeda “I can block this ramp and protect both the main and mineral only.” Steamhammer has the familiar graph data structure so you can do that reasoning, but it feels a little lacking to me, a little awkward and low-level.

I’m thinking that different or additional data structures might be better than what I chose. It’s easy to think of practical situations where it might be convenient to have more or different information pre-computed. What are zones, as such, the right abstraction for? If you’re following a high-level path, the zones are just places you happen to pass through, and you only care about them if something interesting is there. But you don’t care whether the “interesting thing” (like an enemy army) is in the zone, you care whether it affects your concrete path through the zone; maybe it’s too far away to matter; maybe it’s on the other side of your army, and you are sending reinforcements to join up. If you’re defending a choke, you commonly want to set up units to hit enemies as they exit the choke on your side, so you want to know distances from the choke exit. Similarly if you are deciding how far to retreat before making a stand. You want to know the defensibility of a choke, and it may vary depending on which side you’re defending (up the ramp is better) and other factors. And you want be able to do it fast if you’re making a complex calculation, like finding the best set of chokes to defend (in graph theory terms, determining an optimal cut set).

Well, when I get that far I’ll see it more clearly. I won’t rush into decisions that don’t matter yet. Just note that, though I put a lot of work into Steamhammer’s map analysis, if I find a better plan I will happily throw stuff away and do it over. I’ll probably throw away strategy boss work first, though!

I’ve been trying out Steamhammer’s new map analysis for a while. It’s time to talk about it a little.

When I removed BWTA, the DLL file dropped to less than half its size. BWTA and its dependencies are big. It feels like a burden lifted. When I can get rid of BOSS too, the size will shrink again.

I settled on Zone as the name. The most straightforward replacement of BWTA::Region * is with const Zone *; I kept the pointer representation so I wouldn’t have to redesign any other data structures. Some uses only care about zone IDs and can be slightly simpler (and microscopically faster). Zones don’t have as many features as regions. A zone data structure has only a few fields; I don’t need anything fancy.

Unlike BWTA, there is no separate data structure to represent chokes. If you want to know how choke-like a place is, call the.tileRoom.at(const TilePosition & tile), which looks up the approximate distance between the walls around a given tile (as measured in 8x8 walk tiles, at least in the current version). At a main base entrance, a typical tileRoom is 9; at a natural base entrance, a typical tileRoom is 21; in an open area, tileRoom is much larger. The tile room is calculated at game start from the inset of each walk tile, accessible via the.inset.at(), which is the distance from the walk tile to the nearest unwalkable walk tile (BWEM calls this the “altitude”). The tile room algorithm uses a simple approximation to estimate the room from the inset in one pass.

After dropping BWTA, the first thing I did was run test games on random, mostly large and irregular, Blizzard maps. It was delightful to start up quickly without cached data.

There are still bugs on some maps, affecting the plan recognizer and the scouting worker’s looping path. The scout path needs to be rewritten anyway, it was never very good, but it will take time. I’m not entirely surprised, but still I didn’t realize how closely Steamhammer’s behavior is tuned to the exact regions returned by BWTA.

Still still next: Longer-term Steamhammer plans. Apparently “next” means at some point this year.

I spent a little time poking at CUBOT. I guess the name is a reference to the Sonic the Hedgehog character Cubot rather than the Android phone brand Cubot. It could also be an acronym for China University of Boring Ore Technology... or something like that. The author is given in the configuration file as Tommy Tang, and the name Zhentao Tang appears in the binary; they are likely the same person (choosing a Western name in a Western context is a Chinese custom, just as foreigners in China are expected to choose a Chinese name). I think this is the author:Zhentao Tang of the familiar Chinese Academy of Sciences, the institution that brought us CasiaBot among others. Yuanheng Zhu, author of the cannon bot Juno, is listed as a co-author on a few academic papers. I do not know what connection may exist between CAS and the China University of Mining and Technology that the author claims to be a student of at SSCAIT, but I get the impression that CAS is an umbrella organization so I’m not surprised if there is one (or he could have moved to CAS later). It’s hilarious that ResearchGate labels Zhentao Tang a Doctor of Theology, despite all his skills being in AI—it reminds me of the old joke where people create a series of ever more powerful computers and ask each the question “is there a god?” The last computer answers “Now there is.”

CUBOT is a Steamhammer fork, though there seem to be widespread changes. Or possibly it is a UAlbertaBot fork with extensive borrowings from Steamhammer. I can see from the configuration file and from text messages in the binary that a lot of Steamhammer 2.something code is included. Since the DLL is 3.5MB instead of Steamhammer’s 2MB, I looked inside. I see SparCraft (dropped from Steamhammer long before 2.0, one of the hints that it might actually be a UAlbertaBot fork), both BWTA and BWEM, Boost, and indications of machine learning code. Items that look like machine learning feature names suggest that the strategy boss has been swapped out for a learned version, something we’ve seen before in CAS Starcraft projects.

At the moment, CUBOT is ranked #42 with elo 1999, well below Steamhammer and UAlbertaBot by Dave Churchill. CUBOT’s play is... not very rich, strategically. If my interpretation of the binary is right, then the learned strategy boss does not learn diverse strategies. CUBOT does know 9 openings defined in the configuration file. It claims to choose among them by UCB like UAlbertaBot rather than with Steamhammer’s complex opponent model, and when I ran test games (and looked at the learned data), the claim looked correct (another hint). I think that is what the description means by “Adaptive weights toward different opponents.”

CUBOT is strangely sloppy in some ways. Some of the debug options, still included in the configuration file, do not work (including the basic game info inherited from UAlbertaBot). The openings like to collect 400 gas, no matter whether the opening needs 200 gas or 900. There are bugs both subtle and obvious. A subtle bug is that CUBOT will send a drone that is carrying minerals to mine gas, losing its 8 minerals; UAlbertaBot does that (a third hint), but Steamhammer carefully avoids it. An obvious bug is that it sometimes has trouble finding the last building on the map, even when it has already seen the building; neither Steamhammer nor UAlbertaBot has that bug.

I think I detect a family resemblance among the Chinese Starcraft projects that we have seen. They tend to have some machine learning feature, perhaps because of the national AI push. I get the idea that each project has a specific narrow goal, and aspects unrelated to the goal can be given short shrift. I see it in the way that the projects tend to display impressive amounts of hard work and ingenuity in some parts, and generous corner-cutting in others. It also seems that carrying on the project over time is not a goal. But this is all, of course, just my impression.

As I write, SAIDA has fallen to #4 on SSCAIT; more and more opponents are finding the limits of SAIDA’s build adaptation. It seems that the secret to defeating SAIDA is to find a timing that SAIDA is not ready for. Apparently it matters less what units you make, and more whether SAIDA knows how to adapt its build to counter the timing you intend to hit—whether early or late.

Krasi0 in December was the first terran to find a reliable plan, a tank push timed before SAIDA was ready. Another idea to try would be the scary fast 8-8-10 vulture rush with a proxy factory, which I think ought to get a vulture into SAIDA’s base at around the same time that SAIDA’s own factory finishes. So far I haven’t seen any terran bot build a proxy factory.

Top protoss bots found holes in time to beat SAIDA in the SSCAIT annual tournament. Locutus denied scouting and sent dark templar from proxy gates, while PurpleWave alternated between arbiter rush and carrier rush, both successful. The variety of plans makes me wonder how many other plans would work!

Now zergs have started to catch up. Tscmoo zerg and Velicorandom zerg have beaten SAIDA with different early hydralisk rushes, and today Microwave beat SAIDA with 3 hatches before pool into hydralisks, a late timing. SAIDA did its vulture runby and killed a bunch of drones because Microwave had only drones to defend, but did not recognize its golden opportunity for a bunker rush—I guess it only does that against protoss nexus first. So Microwave overran it with too many hydras. Has anybody repurposed a ZvZ 1-base mutalisk build? I haven’t, but I suspect it might work too.

The SAIDA team’s stated goal is “to develop the first starcraft AI which can defeat a professional human starcraft player so as to improve our AI technology.” They haven’t succeeded yet, so I have to assume that they are still working. (Here is a game Best offracing as zerg versus SAIDA that shows they have far to go.) I am guessing that SAIDA’s next appearance will be in AIIDE 2019, and that they will have a deep learning plan recognizer or plan adapter whose holes will be smaller and much harder to exploit. I’m sure they will be collecting the opponents that beat them as test victims. Hmm, defeat SAIDA now or save up your secret weapons in hope that they will still work in AIIDE?

Something is different this year.

Around February 2017 a rush of new bots swept in, inspired by the tournament that had just finished. Toward the end of the year, another rush arrived in time for the next tournament to start. But this SSCAIT edition doesn’t seem to come with many brand new bots, either before or after.

Why is that? Has something else become more popular? Has the level of competition risen so high that it makes beginners feel unable to compete? Or what?

Tscmoo zerg was reuploaded today and plays at least 2 crazy new rushes. The one that caught my eye was a hydralisk rush that has defeated SAIDA 3-0 so far: Tscmoo opens spawning pool on 8 supply, then 7 gas, 6 hydra den, and sends 1 drone to scout (which may or may not ever return), leaving 4 to mine both minerals and gas. Then it sends out unupgraded hydras as fast as it can! It constantly juggles drones onto and off of gas, stopping gas as soon as the available vespine goes over 50. 4 mining drones are not quite enough to produce hydralisks without losing the occasional larva spawning opportunity, but Tscmoo comes as close as it can. (I have a source that claims you need 6 on minerals and 1 on gas to produce hydras non-stop from 1 hatchery. I haven’t done the measurement myself, but I’m pretty sure that 5 or 6 drones total are enough if you can juggle the gas like Tscmoo.)

Here are the 3 wins over SAIDA. Maybe SAIDA looks at Tscmoo’s base and concludes “I see a hydra den, therefore it is not a fast rush and I have nothing to worry about.” Or maybe SAIDA doesn’t worry about fast rushes at all, since its worker defense is so strong, and concludes “the drone count is low, I have nothing to worry about.” In any case, SAIDA continues with its usual greedy build and falls into a hole when the hydras appear and sweep away the first marine and first vulture. The worker defense skills against zerglings are no use, and SAIDA does not appear to adapt its build order at all. In the one game where SAIDA was not overrun altogether, its build got discombobulated and it let thousands of minerals stack up as it tried to counter the hydras with tanks—then lost to mutalisks. The 3 games show no sign that SAIDA was trying to adapt to the danger.

• 1. on Heartbreak Ridge - the first game, where SAIDA massed tanks
• 2. on La Mancha
• 3. on Jade - the latest and shortest game

The hydra rush is genuinely crazy. It can only work against a greedy build like the one SAIDA thinks it can get away with (and usually can), and then only if the opponent doesn’t understand what’s happening and adapt. Tscmoo also tried the rush against terran Tyr by Simon Prins, which played a slightly less greedy build and won. All that was needed was to keep making marines.

The hydra rush is unlike any strategy I have seen before. It is also not efficient as played. It didn’t take me long to code up a small family of related rushes to try out in Steamhammer. I got one version that starts the hydras at the same time as Tscmoo and produces them faster, and another that starts them earlier and still produces them faster (at the cost of needing to do more damage to be able to transition to a midgame build). Plus in some circumstances you can increase the punch by mixing in a few zerglings. I will likely end up keeping 2 or 3 variants permanently, for occasional use. It will be a fun challenge to get strategy adaptation to use them at appropriate times.

Still next: Longer-term plans for Steamhammer. It is taking me longer than I expected to gather my thoughts.

Update: I tested one of my variants, which I named 7-7HydraLingRush, against a few opponents. Though stronger than Tscmoo’s build, it scores less than 50% against the built-in terran AI—it is utterly weak against an opponent that makes units early. But—I love the contrast—it also breaks Iron bot like a toothpick. In a typical game, Iron smells it coming and walls in. Steamhammer hammers through the wall, killing the barracks and/or both supply depots and any SCVs that come to repair, then repeats the performance on the mineral line and command center while Iron’s few units shy out of range, unable to engage. Even in a test game where Steamhammer got confused and failed to attack, it held Iron in its base and won. I’ve configured it as a regular counter-factory opening; the development version of Steamhammer now has 6, up from 4 in the current release.

I’m accomplishing things slowly for now, but that doesn’t stop me from laying plans—or rethinking my past plans. Rather than working hard, I’ve been adding new openings, including a couple that are quite different in idea from anything else in Steamhammer’s repertoire. New openings don’t help in the short run (they mainly make it harder to find the right opening), but I am looking ahead.

Anyway, given my slow progress and the decision to participate in AIST S2, here’s my changed plan for the near future (it should be stable at least until tomorrow). Rather than get Steamhammer 2.2 out at the end of SSCAIT, which I missed by a mile, I’ll release it after AIST S2 submission at the end of this month. Or possibly I’ll skip 2.2 and release 2.2.1 slightly later, because I’m again concentrating on zerg for the tournament and there may be fixes needed for terran and protoss. With people worried about shallow forks, I’m thinking about releasing source less often anyway.

As far as visible play changes goes, the tournament version has bug fixes, including a fix for the debilitating command jam bug that makes macro games ugly. And it has the usual fleet of minor improvements, and a couple which are not as minor. For a tournament I have to bring something more, so I’m aiming to add at least one strong and unexpected tactical feature. I have a shortlist.

In AIST S1 I lost a lot of time coping with the map Sparkle, and other maps caused trouble too. I’m not expecting difficulties in this edition. So far, I haven’t run into problems with any of the AIST S2 maps (well, not beyond the usual). I will run a lot more tests, but so far so good. Not that my expectations are particularly accurate, but I expect to be ready in good time.

Next: Longer range plans.

The name of the new bot Velicorandom is hard to interpret. It’s not “velocirandom”, which would refer to velociraptors. “Velico” might be from Bulgarian (though that would be properly transliterated as “veliko”), or might be from a romance language.

Whatever the name means, the bot looks like it is by the same author as Newbie Zerg. It follows the recent trend of random bots which play as differently as possible with each race (ChimeraBot, legacy). The trend is already starting to feel stale to me, but I don’t mind. The bots will make good tests of Steamhammer’s strategy adaptation as I implement it.

As terran, Velicorandom makes 3 barracks on 10 supply and tries to overrun you with mass unupgraded marines. It looks like it first attacks when it has 15. I’m not familiar with that specific build, but it’s similar in idea to MarineHell or UAlbertaBot’s mass marines.

As protoss, Velicorandom plays 10-12 gate zealots. That one should be familiar; Skynet plays it strongly against zerg, and other protoss bots also know the build. It’s slower to get moving but brings more zealots than UAlbertaBot’s 9-9 gate zealots.

As zerg, Velicorandom plays differently in each matchup. In ZvT, it goes 9 hatch 9 pool 9 gas and makes zerglings with speed. In ZvP, it does that build 50% of the time, and the rest follows another build I don’t know: 9 hatch 12 pool 13 gas, sunken up the natural, and try to win with mass mutalisks. I’m not sure what the point of 9 hatch 12 pool is; maybe I’ll play with it and see if I can find an advantage to the seemingly inefficient build order. In ZvZ, Velicorandom goes with the same 9 hatch 9 pool build as versus terran.

Versus a random opponent, and also versus the specific opponents Krasi0P, JumpyDoggoBot, and Newbie Zerg, Velicorandom answers with 7 pool 12 hatch, the hatchery coming after 5 pairs of zerglings. Newbie Zergrush used to play that build, and Steamhammer knows it too. The 7 pool should work well against random bots that go with a fast rush, and also against the 3 named rushbots, but I doubt it will see much success against the more solid ChimeraBot.

Of course, this is only today’s description. Past bots by this author have had frequent updates.