Starcraft AI blog

The CoG 2021 proceedings includes one Starcraft paper. Sneak-Attacks in StarCraft using Influence Maps with Heuristic Search by Lucas Critch and Dave Churchill is an updated version of a paper from last year, “Combining Influence Maps with Heuristic Search for Executing Sneak-Attacks in RTS Games” by the same authors, which I wrote up as paper on dropship paths.

The dropship paths themselves appear identical to last year’s. The main news is an experiment to test how well the sneaky paths work against the built-in AI, as compared to straight-line paths. Somewhere in the world, hidden from our mortal eyes, there now exists a version of UAlbertaBot which does sneaky drops—at least in one restricted case, fast four-zealot drop by protoss. (The bot AIUR plays fast four-zealot drop too, but it doesn’t have the fancy shuttle pathfinding. Perhaps the authors will give us chances to play against this UAlbertaBot version?) The pathfinder replans the path on a fixed schedule, once per second, and stops replanning when it nears the drop point, because it has probably been seen by then anyway and it’s time to stop dodging and get on with it. The shuttle does not react to being shot at (though if the enemy wasn’t seen before then it may change course when the path is replanned). It’s clear that improvements are possible.

Results: A shuttle taking the direct path was somewhat more likely to be seen along the way, and was substantially more likely to be shot down before unloading (versus terran, way more likely to be shot down by marines). The direct path was faster, which had countervailing advantages in some situations. It’s not clear to me how well the results will generalize to other opponents, because they depend on details of the built-in AI’s play. A bot author, as opposed to a researcher, would rather find out whether the sneaky drops produce more wins in a tournament against a range of opponents.

Steamhammer’s skill kit system makes it relatively easy to record data about specific opponents, and to use the data for decisions. It wouldn’t be hard to record the kind of data shown in the paper—survival, damage taken, moving into enemy sight—and use the information to decide whether to drop and what category of path to follow if so. Steamhammer could figure out during a tournament what works against each opponent. I plan to eventually collect at least enough data to decide whether and when to drop.

A new idea in the paper is to use the sneaky pathfinder defensively, to place your buildings to prevent enemy sneak attack: If you find a good path for the enemy to attack you along, place a building that has vision of the path so you see the attack coming. This seems like overkill to me. I don’t think you gain much from a fancy pathfinding algorithm to place buildings for vision. If you want vision all around the edges of your base, then by the time drops are possible, you should have enough pylons, or supply depots, or zerg overlords, to have all the vision you can use. And besides, you have to weigh vision against the risk to the buildings, especially if you have a low-ground main base. I would prefer to spend the effort to react correctly to an incoming attack that you do spot.

If you want source code, you could try contacting the authors.

I looked through the CoG 2020 accepted papers and noted a couple that relate to Starcraft. One is Combining Influence Maps with Heuristic Search for Executing Sneak-Attacks in RTS Games by Lucas Critch and David Churchill.

This looks like a student Lucas Critch with advisor Dave Churchill. Including the advisor’s name on a student’s paper as second author is an academic convention, and does not give away how much work the advisor may have contributed to it; it may be a substantial effort not much less than the student’s, but it is often “OK, that’s good enough, you can add my name.” The advisor is generally better known than the student, which may draw attention to the paper and its first author. Alternatively, the advisor’s name may overshadow the student who is soon forgotten. I’m not sure which effect is bigger.

As usual, the title is bigger than the content. The paper is actually about how to route a dropship across the map so that the enemy is less likely to catch it along the way, so that the drop is not intercepted and comes as a surprise. It proposes to use the A* algorithm to find the dropship path, and assigns a higher cost to tiles which the enemy is thought to be more likely to see or shoot at; A* will find the lowest-cost path, trading off distance versus risk of being caught.

The paper proposes three influence maps to add up to figure the costs: An enemy vision map based on known or remembered enemy units and their vision range, to avoid being seen; an enemy damage map based on units that can shoot at the dropship, to avoid being shot down (if you are going to be seen, at least be seen by something that can’t kill you); and a weaker map of shortest paths between various bases, which the enemy is likely to be moving along. This figure from the paper shows a sample path:

The path looks fairly reasonable, except that the dropship should follow more diagonals and not exact horizontals and verticals. The paper says nothing about replanning the path when new information is discovered. Trying the system out in real games is future work, not yet done. Theoretically, the shorter safe paths might lead to faster drops which do more damage.

This is early stage work and not impressive so far. But I think it is a good reminder for bot authors: Most bots do not worry much about what the enemy sees, and pay attention mostly to what the enemy does. Finding good transport paths in real time is an important basic skill that bots will eventually have to master. The reaver-dropping protoss bots especially may want to think about that; aiming for the enemy army and aiming for the enemy base and workers call for different approaches.

Although a more important basic skill, that many bots also lack, is recognizing the danger and reacting properly when they do spot a transport moving across the map. Most bots are incurious and it never occurs to them that perhaps a drop is incoming, and perhaps defenders should be moved into position to intercept.