Starcraft AI blog

BWTA provides 2 main features that Steamhammer relies on. Other features are minor and easy to replace. 1. It figures out where the bases are on the map. I’m implementing this myself right now (I have the basics written, but it doesn’t work right yet). This accounts for most uses of BWTA in the code. 2. It figures out regions and chokepoints between them. Steamhammer uses both, though not for many purposes. Later, when the bot starts doing tactical analysis, the feature will become critical. I’m always thinking ahead, so today I’m pondering how to implement regions and chokes.

The usual way of breaking the map into meaningful regions is to first identify chokes. A choke is meaningful in itself, because it is easier to defend than open ground where the enemy can come at you from every direction. Then a region is defined as a walkable area which is connected to other regions only by chokes. You end up with a graph of regions that you can use for pathfinding (as BWEM does), for recognizing threats (“there’s an enemy in my base region!”), for planning tactics (like MaasCraft), and no doubt more.

So we earn a high return if we know what a choke is. But what is a choke? Suppose we think of a choke first as a more defensible narrowing of the terrain. If you have a large army, then even a slight narrowing of the terrain makes an area more defensible. In the early game when you have only a few units, a wide choke is hardly different from open ground. If the potential choke is a ramp, then being on the high ground side makes it more defensible no matter what, while being on the low ground is sometimes worse than standing on open terrain. The defensibility of a choke is valuable information, and defining regions in terms of their defensibility seems useful, but it is also slippery. Defensibility depends on context.

Bots that are too rigid in defining a choke make characteristic mistakes. For example, on Andromeda many bots recognize a choke between the main base and the in-base mineral-only. The terrain is a little narrower there.

Bots that want to defend at the first choke and recognize the first choke as being between the main and mineral-only will misplace their defenders. Zia does this when in the upper left start position, as one example. It’s better to defend at the ramp, which is nearly as close, much narrower, and offers high ground to the defender.

Any rigid definition “this narrow or narrower and it is a choke” will cause this kind of mistake on some maps, or else the opposite kind where the bot fails to recognize a good defensive location. Of course you can tweak it so it works well on a given set of maps, like the SSCAIT maps. To completely solve it, you want to do a topological analysis of the map to find single points of defense, which is easy if you have the graph of regions. To guard the main on Andromeda, there are 3 single points of defense: The wide choke between the main and mineral-only, the ramp, and the outer choke between the gas natural and the rest of the map. Defending any one of those spots protects the main from ground attack. Of the 3, the ramp offers by far the best defensive location, which you might recognize by a score including the width, whether you hold a ramp down from high ground, and maybe closeness to the defended area or to production buildings. Of course if you want to guard both the main and the gas natural, there is only the outer choke.

For Steamhammer, I definitely want to be able to score every choke that the bot might care about during the game, whether I use it to divide regions or not. I’m thinking of scoring every tile on the map for width-between-walls, the length of the shortest bar you can place that blocks a path. I see a simple algorithm that I think is likely suitable. With that, you can decide “is this a good place to siege up, or will it block my other units?” With that and a knowledge of ramps, it should be possible to score any place on the map for “is this a good spot to make a stand?”

I haven’t decided what to do about regions. If I think of good uses, I might go with multiple sets of regions using different definitions of chokes. For example, I can imagine it might be useful to change the regions used for tactical analysis during the game. “I have a lot of tanks now, might as well treat this whole area as one big choke.”