Starcraft AI blog

Today is an idea from the future work section of Dave Churchill’s thesis “Heuristic Search Techniques for Real-Time Strategy Games.” I don’t talk about it using the same words and I toss out a few side ideas that are not in the thesis, but the important points were all written down by Dave Churchill, author of UAlbertaBot. He even wrote up a preliminary experiment.

The idea is to, he wrote, “Perform a build-order search which does not attempt to achieve a given goal set of units, but instead attempts to maximize a given army value.” The BOSS build order search from UAlbertaBot can find near-optimal build orders if you tell it what units you want. It works in a general way, and with the right mods it can find build orders that, say, “make my army as big as possible at a given time, who cares what the units are” or “make my army beat this unit mix” or anything else you can turn into a number.

Of course if you ask something complicated it will take longer and you may not be able to run it in real time during a game. I think the natural course is to calculate a large catalog of good build orders (or even a catalog per map). Then on one side you can play the build orders, and on the other side match the opponent’s play to the catalog.

I’ll suggest a few recipes. You may think of tastier ones. Before we get cooking, here are the ingredients.

Ingredient: Build order search. You’ll have to insert your own evaluation function into the code. You may want to read the BOSS paper first and check whether any of BOSS’s optimizations and shortcuts gets in your way. Besides BOSS, I understand that tscmoo calculates build orders, though I haven’t looked into how it works and whether it would be good for cataloging.

Ingredient: Army comparison. An army does not have a strength in itself, it is strong or weak relative to the enemy. If you want to find counter-builds, not only builds, you need to compare armies. One way is with a battle simulator like SparCraft: Set the two armies down in some formation and have them wargame it out. MaasCraft used to do the same job faster but less accurately with a classic military formula. To estimate whether an advantage is enough to win, you might try a second war game giving the weak side a 20-second head start on its build, to represent that it is defending its base and doesn’t have to cross the map.

Recipe: Tech rushes, the kind of attack where you arrange for your army to be particularly strong at a given time, such as when you’ve teched up to a new unit type or when research finishes. Tech rushes are keystones of the build catalog because they are the strongest instantaneous attacks.

Step 1. List the unit combinations you care about: Zerglings, hydralisks, hydraling, lurkling, hydralurk, hydralurkling, mutaling—that might be all for zerg, maybe a few more. I don’t know any reason to precompute build orders into the late game. You can skip unit combinations that are too gas-heavy, like muta+lurker or tank+wraith—surely it’s better to include at least one unit that costs mostly minerals, so that you can spend efficiently.

Step 2. For each unit in one of your combinations, list the research and upgrades that you care about. For hydralisks you’ll list speed, range, missile attack, and carapace. +3 upgrades are for late game, and even +2 might be too late to be worth precomputing. Combine the units and upgrades into a longer list: Slowlings, speedlings, +1 speedlings, etc. Each is a target army that you might aim for in a tech rush.

Step 3. Brute force it. For each target army in the list, do the build order search to find out how fast you can build it. That’s the earliest timing you can hit. Then, for that time (fast tech rush) and later times (every n frames) until some time limit (slow but heavy tech rushes), search to find the largest target army you can make at that time, counting only the target military units and not the workers. That will give a curve of possible tech rushes versus time, from 4-pool to whatever upper time and tech limits you set.

Recipe: Timing attacks, where you recognize what the enemy is doing and strike while they are weak. I expect that strong tech rushes are likely to risk strong timing attacks.

For each tech rush that you want to counter, find timings when the build is weaker: Before units come out or before research finishes. For each potentially vulnerable timing, pull tech rushes from the catalog and for each one do the army comparison to see whether it’s a counter, in which case it is a timing attack too. And of course label the counters in the catalog.

The same if you want to counter any other known strategy, like what your opponent just beat you with. In that case you may be able to calculate a counter in game—after it’s hopeless and before the gg should be enough time.

Recipe: Universally safe builds are those safe against most or all tech rushes. Brute force it! Do you need static defense? The best safe build is the one that gives you the most workers. Some tech rushes may be safe, but maybe you should also consider how many workers are cut and seek out more economic builds. For universal safety you only have to fear early attacks, because later you can get practical safety.

Recipe: Practically safe builds are those safe against tech rushes that are consistent with your scouting info (ones the opponent could still play). One way to precompute them might be to mine replays for typical scouting info and brute force a range of safe builds so that you can switch into one from where you are. Again, the best safe build is the one that gives you the most workers.

More is possible, and by now you should get the idea. The catalog is a tree of builds, of course, in one representation. The branching structure of the tree tells you when you have to scout for what information.

I expect that PerfectBot will have some kind of knowledgebase created by large-scale search of strategy space. That doesn’t mean we should have it today, or that this way of making one will work well. It’s super simplified compared to real play, after all. I feel confident that some build catalog could be made useful, but I dunno how many new ideas it might hunger for.