@Mod: If possible should this be in the General forum? It is not inherently BW related. See what fits.
Can the drone run for his life?
algorithm and publication: Haomiao Huang, Wei Zhang, Jerry Ding, Dusan M. Stipanovic, and Claire J. Tomlin. Guaranteed Decentralized Pursuit-Evasion in the Plane with Multiple Pursuers. In the Proceedings of the 2011 IEEE International Conference on Decision and Control, Orlando, Florida, December, 2011.
Implementation in bwapi for starcraft: evanthebouncy
Cast: Narrator: Haomiao Huang Zerglings: The algorithm Drone: evanthebouncy
This thing is about a year old when I worked with the graduate student Haomiao on some pursuit and evade algorithms for research.
The game is as follows: We have some pursuit agents that want to capture the evade agent, all agents have the same speed. How should the pursuer best flank the evader so to guarantee capture?
The brief answer is to carve the map up into regions, the area where the evader can safely reach, and the area denied safety by the pursuer. The pursuer will try to keep shrink the safe region, until the evader is caught (have no safe region left). How to best minimize the safe region of the evader? You'd have to read the paper.
That's awesome! Though this has little to do with the actual algorithm and more with the efficiency, I noticed that in general there is always 1 zergling in the back that is kind of just tagging along hoping that he gets used soon enough. Could you take him and have him run out towards the open part of your green shape as to try to shrink the line on the side with the largest line, which would kind of act like a preemptive interception. Or in other words, one guy is trialing behind, and there is a huge gap where the drone is going towards, could you have your straggler run an alternative path in order to try to intercept the drone.
On a side note, do you think the lings would ever get a Bisu probe?
I often see progamers use probes/zealots constantly block other units' paths. This AI seems to just attack as soon as it can hit the evader but I think it could be better if it kept moving the nearest unit to constantly block the escape root while the other units catch up and attack. For example in 1:20, the drone was stopped so the ling could have kept running forward to block and surround the drone but it chose to attack and let the drone get away.
On December 18 2011 08:29 littlefighter wrote: I often see progamers use probes/zealots constantly block other units' paths. This AI seems to just attack as soon as it can hit the evader but I think it could be better if it kept moving the nearest unit to constantly block the escape root while the other units catch up and attack. For example in 1:20, the drone was stopped so the ling could have kept running forward to block and surround the drone but it chose to attack and let the drone get away.
that is true. The persuit and evade game says the game is over when the pursuer touch the evader for the first time. The attacking of the drone is just an addition to starcraft. Technically speaking the game is done the first time the zergling touch the drone. As you can see, the algorithm in the publication is not meant to directly play the game you are watching.
On December 18 2011 11:41 Antisocialmunky wrote: Is it better than those genetic algorithms?
Ofc. Genetic algorithm, if you look more into them, finds some approximated heuristic that vaguely optimallyh solve a problem. This is the proven optimal solution. so yes, strictly better.
On December 20 2011 09:25 Froadac wrote: Naw, undergrad.
then there's prolly not much more than good SAT scores and GPA I'm afraid. However, regardless of where you end up it's really up to you to make the most out of it.
EPT
Applying for grad school now though.
