Improving mineral gathering rate in Brood War (using BWAPI)
As some of you may know, the default behaviour of worker units is not optimal. The most common example is a worker unit that goes to a mineral field far away because the one it originally wanted to go to was occupied (even if it had only 1 millisecond remaining).
Techniques to overcome these problems require some APM and multi tasking, so they are only feasible for a human in the early game. But if you are developing a bot (with the BWAPI), you can turn some of these techniques into an algorithm such that your bot can gather more minerals per second.
For my master thesis I considered the following techniques:
- Built-In - Mineral Lock - Queue System - Co-operative Pathfinding - Co-operative Pathfinding + Queue System
Built-In:
This algorithm/technique describes the default behaviour of worker units. In essence each worker unit gathering minerals works as follows:
- If a worker units arrives at a mineral field from which it wants to mine, but the mineral field is occupied. It will go to the nearest unoccupied mineral field (it will only check mineral fields nearby). - If the worker unit has minerals, it will deliver them back to the nearest resource depot. - Once the worker unit has delivered the resources, it will go back to the last mineral field it tried to mine from.
The technique/algorithm simply assigns each worker unit to the closest (unoccupied) mineral field and leaves the default technique to manage the worker unit. This is the technique used by most humans. Most BWAPI bots also still use this.
Mineral Lock:
This technique/algorithm assigns a worker unit to a mineral field and assures that it stays there by continuously giving the worker unit a gather command to the mineral field every time that it tries to go to another mineral field.
Used sometimes by humans in the early stages of the game to gain a mineral lead on their opponent. Used more often by several bots because they have the APM and multitasking capabilities to continuously do it for every worker for the entire game. Example of bots that use it: LetaBot. (I have seen other bots that uses it as well, but I cannot remember which ones).
Queue System (Christensen et al.):
Instead of letting the worker unit return to the last mineral field it gathered from, the queue system calculates for each mineral field how long it will take before the worker unit will return again (with minerals of course).
This calculation is based on:
1. how long it takes to travel to the mineral field 2. How long the other worker units assigned to the mineral field will occupy the field 3. How long it takes to travel back to the resource depot
For the second calculation ,the queue system maintains a queue for each mineral field. Given the travel time, the queue system can determine for how long the mineral field will still be occupied when the worker unit arrives.
Not used by any human that I know of. Christensen et al. originally developed this system and experimented with it, but it hasn't been put in any BWAPI bot that I know of.
Co-operative Pathfinding:
Another trick that humans use (besides mineral lock) to increase the mineral gathering rate. When a worker unit approaches a mineral field that it wants to gather from, it will start to brake when it comes close to the mineral field.
This behaviour can be prevented by telling the worker unit to move to a location beyond the mineral field and switching back to the mineral field when the SCV nearly touches the mineral field. This way the SCV won't slowly break, but go full speed all the way to the mineral field.
Two examples are given in the picture above. In the first option, the worker unit want to get to the leftmost mineral field (indicated by a red circle with a square inside). To arrive there faster, it gets an order to mine the mineral field beyond its original target (indicated by a green circle with a triangle inside). When close enough, it switches back to the original intended mineral field.
In the second option, the worker unit wants to get to the uppermost mineral field (indicated by a red circle with a filled circle inside). Instead of using another mineral field, it uses a move command that goes beyond the mineral field (indicated by a filled green circle above the mineral field). When close enough, it switches back to the original indented mineral field.
When using a move command, the collision detection for the worker unit is turned on again. So co-operative pathfinding is used to avoid collisions (details of this will be in my master thesis).
Used sometimes by humans in the early stages of the game to gain a mineral lead on their opponent. Not used by any bot that I know of. It will be put in the next version of LetaBot.
Co-operative Pathfinding + Queue system:
Combination of the two techniques mentioned above. The Queue System takes the reduced travel time resulting from the Co-operative Pathfinding into account.
Not used by any bot that I know of. Is on the TODO list for LetaBot.
Experiments:
The experimental setup is based on the paper “A Data-Driven Approach for Resource Gathering in Real-Time Strategy Games” written by Christensen et al.
In this setup the algorithm is given control of a Command Center with 4 SCV's on the top right starting location of the map "Astral Balance". During the entire experiment, the command center will produce SCV's until the supply limit is reached. The algorithm is in control of scheduling each SCV's. After the supply counter reaches 9/10, 1 SCV is taken away to build a supply depot (which raises the supply limit to 18). Once this SCV finished building, it is given back to the algorithm. So the algorithm eventually ends up with 18 SCV's to control.
Each algorithm is scored based on how many minerals it can collect in 8000 frames.
Final results at the 8000 frame mark: Built-in: 4098 Mineral lock: 4578 Queue: 4634 Co-operative Pathfinding: 4666 Co-operative Pathfinding + Queue: 4706
A more detailed recording (excel table with data points at every 500 frames) of the experiment can be found here.
A video of the experiments in action (number on the mineral field indicates the default round trip times in #frames):
Note that the video shows the mineral count at 8005 frames instead of the 8000 mark above.
Future work:
- Besides going to the mineral field, it is also possible to go full speed when going back to the resource depot. I haven't figured out how to do that systematically though - The Queue system schedules the worker units with a so called "greedy" algorithm because it doesn't look ahead. The queue system can be enhanced by a (tree) search technique.
Would there be a way to calculate it for all 3 races in terms of their standard best economic openings? for example for zerg the 12h, 14cc for terran and 12nex for toss?
This seems like an awesome topic for master thesis
Can you just clarify how much time 8,000 frames is? Seems pretty short (a couple of minutes?), which makes it pretty impressive that the Co-operative Pathfinding + Queue algorithm manages to gather ~600 more minerals than the default one.
I'm sure there's people using a variation of the "Queue system". If I understood correctly what you mean, I'm using it (when I'm not lazy) - I cycle 3 workers on 2 minerals. When I'm feeling uber-wannabe, I do it with 6 workers. You can cycle them this way, and there's still a small time when the minerals are unoccupied, until there's more workers to cover it.
BW runs in 25 FPS, so 8000 frames is 5:20 min.
You might want to edit/change the "Build-In" to "Built-In", if I understood you correctly. Built-in refers to something being already a part of the product from the start, whereas build-in doesn't really have any special meaning as far as I know.
On May 07 2015 10:15 art_of_turtle wrote: Would there be a way to calculate it for all 3 races in terms of their standard best economic openings? for example for zerg the 12h, 14cc for terran and 12nex for toss?
Currently the experimental setup is only for one base. Doing it for multiple bases is possible, but that will involve calculating the optimal worker units to maynard from the main to the natural. An interesting project/idea for future work.
On May 07 2015 22:06 2Pacalypse- wrote: This seems like an awesome topic for master thesis
Can you just clarify how much time 8,000 frames is? Seems pretty short (a couple of minutes?), which makes it pretty impressive that the Co-operative Pathfinding + Queue algorithm manages to gather ~600 more minerals than the default one.
On the fastest game speed setting (the default game speed for most multi-player games) the game runs 24 frames per second. So 8000/24 = +- 333 seconds = +- 5 minutes and 33 seconds
Do keep in mind that the SCV production stops at 18/18 in the experiment. In a normal game with constant supply depot and SCV production, there will be less of a difference (but still a significant one).
Master on starcraft? :o Which department is letting you do that?
Cool work btw, well done.
Btw, suggestion on improvement you could do to the queue system: Sometimes a worker will decide to go to an occupied close-by patch and wait a short while, rather than going to an open patch further away, because it'll still come back faster than going to the slow patch. And this is all good. But if there is another scv arriving to the cc just after (), it'll be better for the first one to go to the far patch, and let the second one take the closer patch with less waiting time. So instead of optimising for each scv, you can optimise for two scvs after each other. I guess you'd do the same calculations (1 to 3) for the next incoming scv, and then optimise based on 1 to 3 of both scvs. In principle you could continue to do 3 or more scvs as well, but not sure how much further that'd improve it.
I agree that what you mean is definitely "built-in". "Build-In" actually reads as if you'd want to "build it in" yourself, which is exactly the opposite of what you mean.
I also agree that (necessarily tuned-down) variations of the "queue" system (i.e. active reassignment of workers to free mineral patches) are probably used by many players in the early game (probably even the most common method of economy mircro).
Other things to keep in mind: Can your algorithm actually determine accurately how long a certain worker trip would take? Because minimizing both, average waiting and travelling times, is necessary to really get the optimal outcome. Does your algorithm take different mining rates from different patches into consideration? Are splits always optimal (i.e. can the 6th worker be produced at the earliest feasible time)? These are not necessarily the same, as the four patches with the highest theoretical income rates over prolonged periods are not necessarily the fastest four patches to split to (because they may be further away from the initial position of the workers at game start).
More importantly, though, does your algorithm take into account that some mineral patches (and also gas geysers) are actually buggy and workers will sometimes take the weirdest detours on their trips (instead of travelling along the shortest, straight line between resource depot and geyser/mineral patch), and even for non-bugged patches, the pathfinding is often not optimal. If your algorithm is to yield optimal results, fixing these kinds of worker behaviours is pretty much a requirement (I guess cooperative pathfinding may, as a by-product, take care of some of this).
Another known issue is terran specific (and therefore very relevant for letabot, I guess): Comsat stations actually screw up worker pathfinding a lot, making mining trips (worker traveling times) a lot longer. Some of it, with correct mineral setup even most of it, can be mitigated with good building placement (supply depot below CC to limit worker paths), but an AI that can actually control all workers individually should be able to avoid this effect almost entirely.
On May 08 2015 18:35 Cascade wrote: Master on starcraft? :o Which department is letting you do that?
Cool work btw, well done.
Btw, suggestion on improvement you could do to the queue system: Sometimes a worker will decide to go to an occupied close-by patch and wait a short while, rather than going to an open patch further away, because it'll still come back faster than going to the slow patch. And this is all good. But if there is another scv arriving to the cc just after (), it'll be better for the first one to go to the far patch, and let the second one take the closer patch with less waiting time. So instead of optimising for each scv, you can optimise for two scvs after each other. I guess you'd do the same calculations (1 to 3) for the next incoming scv, and then optimise based on 1 to 3 of both scvs. In principle you could continue to do 3 or more scvs as well, but not sure how much further that'd improve it.
The research is done at the Games and AI group of Maastricht University.
The improvement that you mentioned is exactly what the search technique mentioned in the future work does. Due to the real time constraint it will have a limit in its lookahead capabilities. But it is possible to generate an optimized schedule offline (as in before the game starts).
On May 09 2015 02:14 Freakling wrote: Interesting.
I agree that what you mean is definitely "built-in". "Build-In" actually reads as if you'd want to "build it in" yourself, which is exactly the opposite of what you mean.
I also agree that (necessarily tuned-down) variations of the "queue" system (i.e. active reassignment of workers to free mineral patches) are probably used by many players in the early game (probably even the most common method of economy mircro).
Other things to keep in mind: Can your algorithm actually determine accurately how long a certain worker trip would take? Because minimizing both, average waiting and travelling times, is necessary to really get the optimal outcome. Does your algorithm take different mining rates from different patches into consideration? Are splits always optimal (i.e. can the 6th worker be produced at the earliest feasible time)? These are not necessarily the same, as the four patches with the highest theoretical income rates over prolonged periods are not necessarily the fastest four patches to split to (because they may be further away from the initial position of the workers at game start).
More importantly, though, does your algorithm take into account that some mineral patches (and also gas geysers) are actually buggy and workers will sometimes take the weirdest detours on their trips (instead of travelling along the shortest, straight line between resource depot and geyser/mineral patch), and even for non-bugged patches, the pathfinding is often not optimal. If your algorithm is to yield optimal results, fixing these kinds of worker behaviours is pretty much a requirement (I guess cooperative pathfinding may, as a by-product, take care of some of this).
Another known issue is terran specific (and therefore very relevant for letabot, I guess): Comsat stations actually screw up worker pathfinding a lot, making mining trips (worker traveling times) a lot longer. Some of it, with correct mineral setup even most of it, can be mitigated with good building placement (supply depot below CC to limit worker paths), but an AI that can actually control all workers individually should be able to avoid this effect almost entirely.
In the experiment I record for each SCV its starting position and the mineral patch/resource depot it wants to go to. So in the next iteration of the experiment, this data can be loaded to determine the time it takes for a SCV to get to a certain mineral patch given its location. From the initial 4 mineral patches that get assigned, there is usually 1 SCV that will take a different one after the first resource delivery.
I mainly build the Co-operative Pathfinding so that worker units go full speed to a mineral patch. Calculating the optimal path requires some more in depth knowledge on how the worker units work when gathering minerals/gas.
I haven't looked into Comsat related problems yet. The experiment is more of a general approach that works with the other two races as well.
How good is the very best bot/AI in the world compared to human players right now?
I dunno... for me, it would be kind of disappointing if there were a 'Deep Blue' of BW out there, better than any human player could ever possibly be, even Flash or JD at their peaks.
I mean, yah, interesting, but you still gotta root for your home team, i.e. humans. Unless you're a bot reading this.
On May 11 2015 14:55 [[Starlight]] wrote: How good is the very best bot/AI in the world compared to human players right now?
I dunno... for me, it would be kind of disappointing if there were a 'Deep Blue' of BW out there, better than any human player could ever possibly be, even Flash or JD at their peaks.
I mean, yah, interesting, but you still gotta root for your home team, i.e. humans. Unless you're a bot reading this.
LetaBot just won the Student StarCracft Artificial Intelligence Tournament SSCAIT2014) 2014, beating 40-ish other bots. Versus humans I think at the moment tscmoo would be the best pick, as it is better rounded. Other good picks would be the Japanese team effort ICEBot or Florian Richoux' bot.
EPT![[image loading]](http://i.imgur.com/0XL9dKI.png)
