• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EDT 22:18
CEST 04:18
KST 11:18
  • Home
  • Forum
  • Calendar
  • Streams
  • Liquipedia
  • Features
  • Store
  • EPT
  • TL+
  • StarCraft 2
  • Brood War
  • Smash
  • Heroes
  • Counter-Strike
  • Overwatch
  • Liquibet
  • Fantasy StarCraft
  • TLPD
  • StarCraft 2
  • Brood War
  • Blogs
Forum Sidebar
Events/Features
News
Featured News
RSL Season 1 - Final Week6[ASL19] Finals Recap: Standing Tall15HomeStory Cup 27 - Info & Preview18Classic wins Code S Season 2 (2025)16Code S RO4 & Finals Preview: herO, Rogue, Classic, GuMiho0
Community News
Esports World Cup 2025 - Brackets Revealed14Weekly Cups (July 7-13): Classic continues to roll8Team TLMC #5 - Submission extension3Firefly given lifetime ban by ESIC following match-fixing investigation17$25,000 Streamerzone StarCraft Pro Series announced7
StarCraft 2
General
Who will win EWC 2025? Server Blocker RSL Revival patreon money discussion thread Weekly Cups (July 7-13): Classic continues to roll The GOAT ranking of GOAT rankings
Tourneys
FEL Cracov 2025 (July 27) - $8000 live event Sea Duckling Open (Global, Bronze-Diamond) RSL: Revival, a new crowdfunded tournament series $5,100+ SEL Season 2 Championship (SC: Evo) WardiTV Mondays
Strategy
How did i lose this ZvP, whats the proper response
Custom Maps
External Content
Mutation # 482 Wheel of Misfortune Mutation # 481 Fear and Lava Mutation # 480 Moths to the Flame Mutation # 479 Worn Out Welcome
Brood War
General
Flash Announces (and Retracts) Hiatus From ASL BGH Auto Balance -> http://bghmmr.eu/ [ASL19] Finals Recap: Standing Tall BW General Discussion Help: rep cant save
Tourneys
[Megathread] Daily Proleagues Cosmonarchy Pro Showmatches CSL Xiamen International Invitational [BSL20] Non-Korean Championship 4x BSL + 4x China
Strategy
Simple Questions, Simple Answers I am doing this better than progamers do.
Other Games
General Games
Stormgate/Frost Giant Megathread Path of Exile Nintendo Switch Thread CCLP - Command & Conquer League Project The PlayStation 5
Dota 2
Official 'what is Dota anymore' discussion
League of Legends
Heroes of the Storm
Simple Questions, Simple Answers Heroes of the Storm 2.0
Hearthstone
Heroes of StarCraft mini-set
TL Mafia
TL Mafia Community Thread Vanilla Mini Mafia
Community
General
Russo-Ukrainian War Thread US Politics Mega-thread Things Aren’t Peaceful in Palestine Stop Killing Games - European Citizens Initiative Summer Games Done Quick 2025!
Fan Clubs
SKT1 Classic Fan Club! Maru Fan Club
Media & Entertainment
[Manga] One Piece Movie Discussion! Anime Discussion Thread [\m/] Heavy Metal Thread
Sports
2024 - 2025 Football Thread Formula 1 Discussion TeamLiquid Health and Fitness Initiative For 2023 NBA General Discussion NHL Playoffs 2024
World Cup 2022
Tech Support
Computer Build, Upgrade & Buying Resource Thread
TL Community
The Automated Ban List
Blogs
Men Take Risks, Women Win Ga…
TrAiDoS
momentary artworks from des…
tankgirl
from making sc maps to makin…
Husyelt
StarCraft improvement
iopq
Trip to the Zoo
micronesia
Customize Sidebar...

Website Feedback

Closed Threads



Active: 666 users

Cool AI: Pursuit and Evade

Forum Index > BW General
Post a Reply
1 2 Next All
evanthebouncy!
Profile Blog Joined June 2006
United States12796 Posts
Last Edited: 2011-12-16 02:26:08
December 16 2011 02:22 GMT
#1
@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.

Comments are welcome ^___^

--evan
Life is run, it is dance, it is fast, passionate and BAM!, you dance and sing and booze while you can for now is the time and time is mine. Smile and laugh when still can for now is the time and soon you die!
Froadac
Profile Blog Joined July 2009
United States6733 Posts
December 16 2011 02:46 GMT
#2
Are you the grad student at UC berkeley? This sure is darn impressive.
evanthebouncy!
Profile Blog Joined June 2006
United States12796 Posts
December 16 2011 02:57 GMT
#3
On December 16 2011 11:46 Froadac wrote:
Are you the grad student at UC berkeley? This sure is darn impressive.

No I'm undergrad who worked with a grad student. Applying for grad school now though.
Life is run, it is dance, it is fast, passionate and BAM!, you dance and sing and booze while you can for now is the time and time is mine. Smile and laugh when still can for now is the time and soon you die!
Golgotha
Profile Blog Joined January 2011
Korea (South)8418 Posts
December 16 2011 03:00 GMT
#4
awesome stuff!
CakeOrI)eath
Profile Blog Joined September 2009
United States327 Posts
December 16 2011 03:37 GMT
#5
Very cool work!
Opportunities multiply as they are seized.
Dullahan
Profile Blog Joined April 2009
United States248 Posts
December 16 2011 03:52 GMT
#6
Very neat!
TelecoM
Profile Blog Joined January 2010
United States10671 Posts
December 16 2011 04:08 GMT
#7
Thats really awesome, nice job with that, I don't think stuff like that is possible with SC2, atleast not like this ^_^
AKA: TelecoM[WHITE] Protoss fighting
Chimpalimp
Profile Joined May 2010
United States1135 Posts
Last Edited: 2011-12-16 04:37:05
December 16 2011 04:34 GMT
#8
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 like money. You like money too? We should hang out.
Froadac
Profile Blog Joined July 2009
United States6733 Posts
Last Edited: 2011-12-16 05:33:39
December 16 2011 05:33 GMT
#9
CS though? I applied for CS at berkeley, mind if I ask any questions? XD

Still, this is darn impressive.
Darksoldierr
Profile Joined May 2010
Hungary2012 Posts
December 16 2011 06:57 GMT
#10
Nice, i really like the fact you implemented a real algorythm into SC, looks really intresting.
What do humans know of our pain? We have sung songs of lament since before your ancestors crawled on their bellies from the sea.
evanthebouncy!
Profile Blog Joined June 2006
United States12796 Posts
December 17 2011 21:34 GMT
#11
On December 16 2011 14:33 Froadac wrote:
CS though? I applied for CS at berkeley, mind if I ask any questions? XD

Still, this is darn impressive.


yeah go ahead you applied for grad school in berkeley?
Life is run, it is dance, it is fast, passionate and BAM!, you dance and sing and booze while you can for now is the time and time is mine. Smile and laugh when still can for now is the time and soon you die!
Vuk_91
Profile Joined September 2010
Serbia1690 Posts
December 17 2011 21:47 GMT
#12
Very interesting...
littlefighter
Profile Joined February 2011
43 Posts
December 17 2011 23:29 GMT
#13
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.
evanthebouncy!
Profile Blog Joined June 2006
United States12796 Posts
December 18 2011 01:06 GMT
#14
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.
Life is run, it is dance, it is fast, passionate and BAM!, you dance and sing and booze while you can for now is the time and time is mine. Smile and laugh when still can for now is the time and soon you die!
Antisocialmunky
Profile Blog Joined March 2010
United States5912 Posts
December 18 2011 02:41 GMT
#15
Is it better than those genetic algorithms?
[゚n゚] SSSSssssssSSsss ¯\_(ツ)_/¯
Marine/Raven Guide:http://www.teamliquid.net/forum/viewmessage.php?topic_id=163605
snakeeyez
Profile Joined May 2011
United States1231 Posts
December 18 2011 18:29 GMT
#16
It seems all the BWAPI bots could find a use for this like maybe flanking enemy armies or to kill off scouting probes in early game.
Xiphos
Profile Blog Joined July 2009
Canada7507 Posts
December 18 2011 18:32 GMT
#17
Don't think that Bisu's probe can survive that.
2014 - ᕙ( •̀ل͜•́) ϡ Raise your bows brood warriors! ᕙ( •̀ل͜•́) ϡ
evanthebouncy!
Profile Blog Joined June 2006
United States12796 Posts
December 18 2011 19:33 GMT
#18
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.
Life is run, it is dance, it is fast, passionate and BAM!, you dance and sing and booze while you can for now is the time and time is mine. Smile and laugh when still can for now is the time and soon you die!
Froadac
Profile Blog Joined July 2009
United States6733 Posts
December 20 2011 00:25 GMT
#19
Naw, undergrad.
evanthebouncy!
Profile Blog Joined June 2006
United States12796 Posts
December 21 2011 04:19 GMT
#20
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.
Life is run, it is dance, it is fast, passionate and BAM!, you dance and sing and booze while you can for now is the time and time is mine. Smile and laugh when still can for now is the time and soon you die!
1 2 Next All
Please log in or register to reply.
Live Events Refresh
OSC
00:00
OSC Elite Rising Star #15
Jumy vs NicoractLIVE!
xJustxJordanx26
Liquipedia
Replay Cast
00:00
SEL S2 Last Chance Qualifier 1
CranKy Ducklings124
Liquipedia
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
Nina 233
SpeCial 197
RuFF_SC2 119
CosmosSc2 37
feardragon 16
StarCraft: Brood War
Sharp 63
Bale 17
Icarus 12
Dota 2
monkeys_forever904
Counter-Strike
Stewie2K634
Other Games
summit1g12992
tarik_tv8343
shahzam1191
JimRising 387
ViBE240
NeuroSwarm129
Trikslyr78
Organizations
Other Games
gamesdonequick2485
StarCraft 2
Blizzard YouTube
StarCraft: Brood War
BSLTrovo
sctven
[ Show 15 non-featured ]
StarCraft 2
• Berry_CruncH237
• Hupsaiya 66
• practicex 1
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• LaughNgamezSOOP
• Migwel
• sooper7s
StarCraft: Brood War
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
League of Legends
• Scarra2414
• Rush1070
Upcoming Events
Epic.LAN
9h 42m
Big Brain Bouts
13h 42m
sebesdes vs SpeCial
Harstem vs YoungYakov
GgMaChine vs uThermal
CranKy Ducklings
1d 7h
Epic.LAN
1d 9h
CSO Contender
1d 14h
BSL20 Non-Korean Champi…
1d 15h
Bonyth vs Sziky
Dewalt vs Hawk
Hawk vs QiaoGege
Sziky vs Dewalt
Mihu vs Bonyth
Zhanhun vs QiaoGege
QiaoGege vs Fengzi
Sparkling Tuna Cup
2 days
Online Event
2 days
BSL20 Non-Korean Champi…
2 days
Bonyth vs Zhanhun
Dewalt vs Mihu
Hawk vs Sziky
Sziky vs QiaoGege
Mihu vs Hawk
Zhanhun vs Dewalt
Fengzi vs Bonyth
Esports World Cup
4 days
ByuN vs Astrea
Lambo vs HeRoMaRinE
Clem vs TBD
Solar vs Zoun
SHIN vs Reynor
Maru vs TriGGeR
herO vs Lancer
Cure vs ShoWTimE
[ Show More ]
Esports World Cup
5 days
Esports World Cup
6 days
Liquipedia Results

Completed

JPL Season 2
RSL Revival: Season 1
Murky Cup #2

Ongoing

BSL 2v2 Season 3
Copa Latinoamericana 4
Jiahua Invitational
BSL20 Non-Korean Championship
CSL Xiamen Invitational
CSL Xiamen Invitational: ShowMatche
Championship of Russia 2025
FISSURE Playground #1
BLAST.tv Austin Major 2025
ESL Impact League Season 7
IEM Dallas 2025
PGL Astana 2025
Asian Champions League '25

Upcoming

2025 ACS Season 2
CSLPRO Last Chance 2025
CSLPRO Chat StarLAN 3
BSL Season 21
K-Championship
RSL Revival: Season 2
SEL Season 2 Championship
uThermal 2v2 Main Event
FEL Cracov 2025
Esports World Cup 2025
Underdog Cup #2
ESL Pro League S22
StarSeries Fall 2025
FISSURE Playground #2
BLAST Open Fall 2025
BLAST Open Fall Qual
Esports World Cup 2025
BLAST Bounty Fall 2025
BLAST Bounty Fall Qual
IEM Cologne 2025
TLPD

1. ByuN
2. TY
3. Dark
4. Solar
5. Stats
6. Nerchio
7. sOs
8. soO
9. INnoVation
10. Elazer
1. Rain
2. Flash
3. EffOrt
4. Last
5. Bisu
6. Soulkey
7. Mini
8. Sharp
Sidebar Settings...

Advertising | Privacy Policy | Terms Of Use | Contact Us

Original banner artwork: Jim Warren
The contents of this webpage are copyright © 2025 TLnet. All Rights Reserved.