the overlord shuffle
Let’s suppose there are two safe spots where you want to station overlords to watch for enemy movement, a nearer one A (perhaps near the entrance to your natural) and a farther one B.
* A B
1
Overlord 1 hatches. Of course you send it toward A. It’s slow, so it takes a while to get there.
* A B
--> 1
Then overlord 2 hatches. You could send it toward the next spot B, but that’s silly.
* A B
2 1
It’s faster to send overlord 1 from A to B and replace it with overlord 2 at A.
* A B
--> 2 --> 1
Humans do this kind of overlord shuffling all the time. Here’s a TeamLiquid post showing the overlord repositioning patterns of a few pro games. I don’t know of any bots that do it. It seems like it might be tricky, no? But in fact the problem of assigning overlords, or scouting units in general, to locations is an example of the mathematical assignment problem, and there is no shortage of known algorithms to solve it either exactly or approximately. I’m still thinking about how I want to solve it in Steamhammer.
Scouting in the presence of an enemy is not as simple. To do it optimally you’d have to understand how scout timings interact with possible timings of the opponent’s build, and consider the risk to the overlord from early marines, and take into account that an enemy that sees your overlord learns something about you too—and they might actively look for the overlord, humans often do (“if you’re at that base and scouting the most efficient way to the closest natural, your overlord will be here at this time; if I see it I found you, and if not, I ruled out one base”). The optimal strategy is surely a mixed strategy, meaning that you don’t play the same every game, and there’s no way it’s possible to calculate it on the fly. You have to either pre-calculate a plan or figure it out heuristically.
Trackbacks
No Trackbacks
Comments
Dan on :
I've used the same heuristic approach for mostl of them: Greedy element-wise assignment, after sorting the elements (usually to assign the most needy element first), and sometimes with hysteresis to ensure stability. For example, I micro my units in order from closest-to-enemy-range to furthest, letting the most endangered units choose retreat paths first and then adding additional cost to highly-trafficked tiles when considering retreat paths for less-endangered units. This (in principle if not perfectly in practice) lets the most-threatened units take a beeline out of danger while safer units are encouraged to move to the side to let them through.
Gathering works similarly: It's most expensive for workers already on resources to get reassigned, so I greedily assign workers to the best resource starting with workers *closest* to starting their mining cycle. Hysteresis (encouraging workers to stay on the same patch) was necessary to avoid the occasional catastrophic waffling due to latency and due to workers taking wobbly paths when changing directions.
Jay Scott on :
jtolmar on :
My gut feeling is that it'd be an endless rabbithole of hysteresis problems, but maybe worth it.
Jay Scott on :
Jay Scott on :
Bryan on :
I currently randomly select locations based on distance from their perceived base and scout those.
If a scout hits its destination, I reassign it a new location, but it can't be currently seen or being scouted towards.