Starcraft AI blog

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!