Starcraft AI blog

Today there was a short string of comments about retreating. Steamhammer makes mistakes in retreating: It retreats to poor positions, and the purpose of retreating is to disengage so it issues a move command—but it doesn’t check whether it is moving to a safe place. It often loses by retreating into or through an enemy force without fighting. It’s such a severe weakness that I think almost every Steamhammer fork has implemented some improvement to the behavior.

I am planning a simple improvement for CIG. For the following AIIDE tournament, I should have time to implement actual factual honest-to-goodness tactical analysis and make maneuver decisions properly. So here are my thoughts on what has to go into tactical analysis.

1. Distinguish different kinds of tactics. Maneuvering is one kind: Deciding when and where to move, when and where to attack, what locations need static defense or mobile defenders or scouting units, all that stuff. In maneuvering tactics, you do planning to decide on goals, and then carrying out the goals requires reacting to the situation but doesn’t require planning as such. The planning is all up front; if the bot hits a problem, the solution is to replan and set new goals. There are also what I think of as sequencing tactics, like clearing a map block or carrying out a drop or performing a coordinated attack from different directions. They require a sequence of steps. The bot has to recognize a need—clear the neutral buildings to open the path to expand to that base; select and collect resources—use lurkers because the buildings are stacked, otherwise it will take too long; plan paths; and execute steps in order—first clear the neutral buildings, then send the drone to expand. The response to problems seems more complicated than “just replan from scratch;” minor problems can be solved by assigning more resources. I don’t think there’s necessarily a sharp line between maneuvering tactics and sequencing tactics, but they do seem to call for different planning skills.

2. I am increasingly thinking that the 3 levels of analysis strategy, tactics, micro are not enough. I think I want 4 levels, which I will call strategy, operations, tactics, and micro. To a certain extent, this already shows in Steamhammer, where decisions made at the squad level sometimes look like tactics and sometimes look like micro. Retreating is a perfect example: It is a tactical decision which is made by the squad based on local tactical analysis of the situation of that squad only. Roughly speaking, high level tactics are in the combat commander, low level tactics in the squad, and micro in the squad’s micro managers. I want to reorganize it somewhat so that it is clear what level each decision is made at.

Strategy is about resources. It decides on the drone count, how much gas to collect, when to expand, and what units to make. The unit count it achieves and the unit mix it chooses have big effects on the lower levels. Strategy also includes the highest-level understanding of the game situation, like “I need to stay defensive until I’ve built up a big enough force” or “I’m ahead in economy, so an even trade is good.”

Operations is about choosing high-level tactical goals and assigning units to achieve them. Raiding squad, go hit that enemy base; blocking squad, delay any enemies from arriving there. I think that attack and retreat should be decided at this level. Sometimes it is right to retreat the raiding squad when strong enemies arrive; sometimes it is right to sacrifice the raiding squad to do as much damage as possible. The decision is best made based on the whole situation. You want to be able to reason, “sacrificing the raiders to delay the enemy a little longer means the upcoming drop is more likely to work.”

Tactics tries to achieve the operational goals. It chooses roles for each unit in a squad, or perhaps subdivides the squad into subsquads with different subgoals: Hydras engage the cannons, lurkers run past and reach the mineral line as fast as possible.

Micro is individual unit control. Where should the lurkers aim to kill as much stuff as possible?

As always, the different levels of analysis should ideally feed information to each other. See levels of abstraction.

3. How to analyze maneuver tactics efficiently? MaasCraft showed the way: Cluster units together and analyze at the level of clusters. At the operational level, it doesn’t matter exactly where individual units are. The analysis has to remain valid for at least a few seconds, and units will move around in that time. Draw a bounding box or a circle around each cluster and represent the contents of the cluster as summary measures of unit count, total hit points, speed or range of speeds, or whatever other values are useful. I believe many bots do this kind of analysis, but Steamhammer doesn’t.

With that information in hand, you can make quick estimates of when an army can arrive, how much force can be brought to bear on a given point, who wins the fight, and so on. The estimates may not be accurate, but combat simulators aren’t accurate either. You just have to be good enough to improve your decisions.

4. What should tactical analysis look like? MaasCraft uses a form of MCTS, a logical choice of search algorithm. A simpler search would already improve Steamhammer’s tactics. I expect that, with a smart enough evaluation function, a brief search that looks ahead a short time would produce strong tactical play. Surely machine learning should be able to produce an evaluator that smart. But I have ideas about how to write one by hand, and I may try that first.

Still next: Oops, somehow Proxy slipped down a slot.