Starcraft AI blog

Squad unit clustering is the Steamhammer 2.0 change with the biggest effect on play. It was also the change that took the most effort to get working well, because it adds flexibility, which means more ways to go wrong.

Many bots form squads dynamically by clustering: Each cluster is a squad. Steamhammer forms squads as usual, and clusters the units in each squad into groups which act somewhat independently. The two arrangements are not necessarily different in effect; what matters is how decisions are made. Steamhammer’s system is meant to keep a clean distinction between levels of abstraction, the operational level at which squads are formed and given orders, and the tactical level at which units are maneuvered to carry out the orders. Each cluster in the squad makes decisions based on its local situation, but it is ultimately trying to carry out the same order as the other clusters in the squad.

Clustering is driven by a simple imperative: Units must react to their local environment. In the unified squad structure that Steamhammer inherited from UAlbertaBot, the squad runs a single combat simulation for front-line units which are in contact with the enemy, and the entire squad is told to advance or retreat based on the result. Units which are away from the front lines, but in contact with the enemy, are given nonsensical orders as often as not. For example, if the front line is advancing because the enemy army is away from home, then small groups of reinforcing units which run into the enemy army are also told to attack, and they end up dying. And conversely, if the front line is afraid to attack, then units behind the scenes which meet lone enemies are also afraid of them. Units must react to the situation they are in, not the situation some other unit is in.

With clustered squad units, each cluster that comes into contact with the enemy runs its own combat simulation, and advances or retreats independently depending on the result. When the army is large, the squad members tend to be spread over a wide area, and independent behavior is a necessity. The full set of cluster behaviors is complex; keep reading.

the clustering algorithm

The clustering algorithm itself is implemented in OpsBoss (intended to eventually replace CombatCommander), which is probably not the right place for it. Methods cluster either a given set of units (like the members of a squad) or all units of a player. The feature to cluster all units is intended for clustering enemy units, and not currently used, but I expect it will be valuable for deeper tactical analysis when I get that far.

A cluster is either an air cluster or a ground cluster. Air units and ground units have different movement possibilities—different decisions available—so they should be treated differently. Only an air cluster can retreat over a cliff.

Steamhammer makes circular clusters. I expect that rectangular clusters are as good, and probably a tad cheaper to calculate, but also a tad more complex. Pick an arbitrary unit as the seed of a cluster, find nearby units, calculate the center and radius of the cluster so far, and expand the radius by a fixed amount to see if that draws in any more units. If so, recalculate the center and radius, and so on; if not, the cluster is complete. Repeat until all units are in clusters. A cluster of size 1 is fine.

clustering in squads

Each squad reclusters its units every frame. That means that clusters have no continuity; there is no such thing as “the same cluster” the next frame. It’s a limitation. Some units, like overlords and defilers, are left out of clusters and handled separately. To save time, not every cluster makes decisions on every frame, especially in the late game when there may be many clusters. See Squad::update() for all this stuff.

The clusters then make decisions independently. Each is trying to reach the squad’s order position, and decides what to do based on its local situation. The clusters know that they are working together, so if they see a way, they will try to join up into larger clusters. If you turn on Config::Debug::DrawClusters in the configuration file (it is currently turned on for the SSCAIT stream), you’ll see (among other things) a status string for each cluster: Join Up, Advance, Attack, Retreat, and so on. The decisions work like this:

• If there is no enemy nearby that the cluster can attack, or that can attack the cluster, then the cluster is in a “no fight” situation—combat is impossible for the moment.

• If a “no fight” cluster finds itself in the vanguard, its status string is “Advance” and it moves toward the squad’s order position.

• If a “no fight” cluster is behind other clusters, its status string is “Join Up” and it tries to merge with a cluster that is ahead of it. If the cluster ahead is advancing, they will form a train; if the cluster ahead is stopped or in combat, the trailing cluster may be able to join it.

• Other clusters have to decide whether to attack or retreat (aka regroup). First, the code checks several shortcuts to see if combat sim can be skipped.

• If Steamhammer is near max supply, the status string is “Banzai!” and the decision is to attack..Every cluster of every squad with an attack order will try to get into the fight.

• If the cluster is near a static defense building that can help in the fight, the decision is to attack. There are a couple of different cases, which get different strings mentioning static defense. The behavior is not as good as it could be (most zerg units should move behind the static defense before turning around to fight, instead of standing in front), but it’s an improvement over past versions.

• If the cluster has retreated as far as it can, back into its base which is now under attack, the decision is to attack and the string is “Back to the wall”.

• If none of those checks fires, there is nothing for it but to run the combat sim. Depending on the result, the status string will be “Attack” or “Retreat”. On the enemy side, all the nearby enemies are added to the combat sim, as usual. On the friendly side, only the cluster’s own units are added; clusters assume that they are unable to cooperate. This works better than adding all nearby friendly units, because in fact different friendly units often do not cooperate. The downside is that clusters cannot cooperate when they should, for example to carry out a sandwich maneuver. A better system would be to identify top-down which clusters have the same enemies in their sights, and run one combat sim for all those clusters. I expect to do that at some point after I turn on enemy unit clustering.

• If the decision is to retreat, where should the cluster retreat to? There are several rules for this, checked in Squad::calcRegroupPosition(). I have said that Steamhammer’s old tactical misbehaviors are gone, but it’s not true: Clusters sometimes still try to retreat through the enemy force. There is plenty of room to improve retreating. At some point after I turn on enemy unit clustering, I’ll teach the retreat calculation more.

• Retreating: If there is nearby static defense in any direction, retreat toward it.

• Retreating: If part of the cluster is in range of the enemy (so we did a combat sim) and part is out of range (so it is a safe place to retreat to), retreat to the position of the cluster unit out of enemy range which is closest to the squad’s order position. This is a cluster variant of the classic UAlbertaBot retreat behavior. Restricting it to one cluster at a time makes it behave much more nicely—no more retreating to a random position because some reinforcing unit happens to be approaching from an unexpected angle.

• Retreating: Look for another cluster nearby to join up with. Favor nearby clusters that are closer to the order position and clusters which are attacking. It’s good in general for clusters to join up, but this rule also tries to fix a specific weakness: If a small cluster does its combat sim with its few units, it may be told to retreat, even though a large cluster in front of it has done its combat sim and decided to attack. It is much better for the small cluster to join the large one in its attack, so in this case Steamhammer tries to merge the clusters, or in other words, it retreats toward the enemy. It doesn’t always work; cases still occur of small clusters which are needlessly fearful.

• Retreating: If all else fails, retreat toward the main base.

other details

The call Squad::unitNearEnemy() decides whether a unit is “in range” of the enemy. In the past, Steamhammer often did not retreat far enough for safety, especially if the enemy had sieged tanks. I improved it in 2 ways:

• It uses the information manager’s records of all enemy units last known positions to decide whether an enemy is near, instead of using the MapGrid information about visible enemies only. Having to see the enemy to know to stay out of its firing range was especially bad for zerglings, which have a short sight range. It was also bad against sieged tanks, which can hit from out of sight range.

• If the enemy is known to have tanks with siege mode, then ground units make sure they stay outside of sieged tank range. Before, the assumed safe retreat distance was simply not far enough to be safe from tanks! It was painful to see a squad retreat to just inside siege range, lose the frontmost units to tank fire, and—move forward to stay centered on the retreat point. Ouch!

I made the minimum changes to Squad to get all this to work. The code is getting increasingly messy with special cases. For example, the micro managers which handle clustered units have to be told about the cluster and do a set intersection to figure out which units they should issue commands to, and the micro managers that handle unclustered units do not—squad code and micro code have to be coordinated, making refactoring more difficult. I will eventually rewrite the squads with a new and cleaner design, but probably not this year.

overall

This was a needed change. Units simply must pay attention to their own situations, there is no way around it.

Play versus protoss is vastly stronger. Voters have been feeding Steamhammer a lot of games against top protoss bots, which zerg mostly loses. Even in these losing games, it is easy to see that Steamhammer is putting up a much tougher fight than it used to. Since my home tests against DaQin, which Steamhammer learned to defeat, DaQin has been updated to be more aggressive and Steamhammer can no longer win (and I don’t know what version was entered into AIIDE, so we’ll see how the tournament goes). I can see the path to stronger zerg play, to earning wins over Locutus and PurpleWave. I can tell what needs to be done and I have confidence that it will succeed.

Play versus terran varies, and play versus zerg is weaker because of poor zergling behavior. A large part of the poor zergling behavior is due to clustering changes. In the past, when Steamhammer retreated a squad, it would not rerun the combat sim and consider attacking again until a time limit had passed (I changed the details thoroughly, but the behavior was inherited from UAlbertaBot). Since clusters do not persist from one frame to the next, it was impossible to retain this feature. The result is more indecision, and the indecision strongly affects zergling play, and causes other harm as well. It’s not easy to fix, and I’m still thinking about ways.

Part of the weakness is in retreating from a superior force that then advances. Not all of the enemy force is in sight range, and the rest is assumed to be still in its last-seen positions, so the combat sim says “ha, we can turn around and fight now!” With no retreat time limit, and the short sight range of zerglings, this happens fast and causes serious losses. The weakness was always there, and now it is worse.

Next: The big change list with everything else.