• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EDT 05:02
CEST 11:02
KST 18:02
  • 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
[ASL19] Finals Recap: Standing Tall10HomeStory Cup 27 - Info & Preview18Classic wins Code S Season 2 (2025)16Code S RO4 & Finals Preview: herO, Rogue, Classic, GuMiho0TL Team Map Contest #5: Presented by Monster Energy6
Community News
Firefly given lifetime ban by ESIC following match-fixing investigation5$25,000 Streamerzone StarCraft Pro Series announced4Weekly Cups (June 30 - July 6): Classic Doubles6[BSL20] Non-Korean Championship 4x BSL + 4x China9Flash Announces Hiatus From ASL66
StarCraft 2
General
Weekly Cups (June 30 - July 6): Classic Doubles The SCII GOAT: A statistical Evaluation The GOAT ranking of GOAT rankings Firefly given lifetime ban by ESIC following match-fixing investigation Jim claims he and Firefly were involved in match-fixing
Tourneys
$25,000 Streamerzone StarCraft Pro Series announced FEL Cracov 2025 (July 27) - $8000 live event Sparkling Tuna Cup - Weekly Open Tournament RSL: Revival, a new crowdfunded tournament series WardiTV Mondays
Strategy
How did i lose this ZvP, whats the proper response Simple Questions Simple Answers
Custom Maps
[UMS] Zillion Zerglings
External Content
Mutation # 481 Fear and Lava Mutation # 480 Moths to the Flame Mutation # 479 Worn Out Welcome Mutation # 478 Instant Karma
Brood War
General
[G] Progamer Settings i aint gon lie to u bruh... ASL20 Preliminary Maps BGH Auto Balance -> http://bghmmr.eu/ [ASL19] Finals Recap: Standing Tall
Tourneys
[BSL20] Non-Korean Championship 4x BSL + 4x China [BSL20] Grand Finals - Sunday 20:00 CET CSL Xiamen International Invitational The Casual Games of the Week Thread
Strategy
Simple Questions, Simple Answers I am doing this better than progamers do.
Other Games
General Games
Stormgate/Frost Giant Megathread Nintendo Switch Thread Path of Exile What do you want from future RTS games? Beyond All Reason
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
US Politics Mega-thread Things Aren’t Peaceful in Palestine Summer Games Done Quick 2025! Russo-Ukrainian War Thread Stop Killing Games - European Citizens Initiative
Fan Clubs
SKT1 Classic Fan Club! Maru Fan Club
Media & Entertainment
Anime Discussion Thread [Manga] One Piece [\m/] Heavy Metal Thread
Sports
2024 - 2025 Football Thread Formula 1 Discussion NBA General Discussion TeamLiquid Health and Fitness Initiative For 2023 NHL Playoffs 2024
World Cup 2022
Tech Support
Computer Build, Upgrade & Buying Resource Thread
TL Community
The Automated Ban List
Blogs
momentary artworks from des…
tankgirl
Culture Clash in Video Games…
TrAiDoS
from making sc maps to makin…
Husyelt
StarCraft improvement
iopq
Customize Sidebar...

Website Feedback

Closed Threads



Active: 637 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 States10670 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
Next event in 58m
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
JimRising 493
trigger 39
StarCraft: Brood War
Shuttle 1233
Stork 370
Larva 306
actioN 280
TY 268
Zeus 202
ToSsGirL 119
Soma 104
PianO 102
Nal_rA 53
[ Show more ]
sSak 47
Sharp 42
Noble 39
sorry 37
Yoon 35
JulyZerg 34
Sacsri 22
EffOrt 20
hero 17
Barracks 14
firebathero 12
Rush 11
IntoTheRainbow 7
ivOry 3
Dota 2
Gorgc561
XcaliburYe510
XaKoH 491
Fuzer 241
Counter-Strike
Stewie2K1135
Other Games
tarik_tv8456
shahzam913
ceh9481
Happy329
monkeys_forever180
crisheroes175
Pyrionflax85
Organizations
Other Games
gamesdonequick33798
StarCraft 2
Blizzard YouTube
StarCraft: Brood War
BSLTrovo
sctven
[ Show 13 non-featured ]
StarCraft 2
• Berry_CruncH396
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• LaughNgamezSOOP
• Migwel
• sooper7s
StarCraft: Brood War
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
Dota 2
• lizZardDota2183
League of Legends
• HappyZerGling118
Upcoming Events
The PondCast
58m
uThermal 2v2 Circuit
6h 58m
WardiTV European League
6h 58m
Jumy vs NightPhoenix
Percival vs Nicoract
ArT vs HiGhDrA
MaxPax vs Harstem
Scarlett vs Shameless
SKillous vs uThermal
Replay Cast
14h 58m
RSL Revival
1d
ByuN vs SHIN
Clem vs Reynor
OSC
1d 3h
Replay Cast
1d 14h
RSL Revival
2 days
Classic vs Cure
FEL
2 days
OSC
2 days
[ Show More ]
RSL Revival
3 days
FEL
3 days
FEL
3 days
CSO Cup
3 days
BSL20 Non-Korean Champi…
3 days
Bonyth vs QiaoGege
Dewalt vs Fengzi
Hawk vs Zhanhun
Sziky vs Mihu
Mihu vs QiaoGege
Zhanhun vs Sziky
Fengzi vs Hawk
Sparkling Tuna Cup
4 days
RSL Revival
4 days
FEL
4 days
BSL20 Non-Korean Champi…
4 days
Bonyth vs Dewalt
QiaoGege vs Dewalt
Hawk vs Bonyth
Sziky vs Fengzi
Mihu vs Zhanhun
QiaoGege vs Zhanhun
Fengzi vs Mihu
Replay Cast
6 days
Liquipedia Results

Completed

Proleague 2025-07-07
HSC XXVII
Heroes 10 EU

Ongoing

JPL Season 2
BSL 2v2 Season 3
Acropolis #3
KCM Race Survival 2025 Season 2
CSL 17: 2025 SUMMER
Copa Latinoamericana 4
Jiahua Invitational
Championship of Russia 2025
RSL Revival: Season 1
Murky Cup #2
BLAST.tv Austin Major 2025
ESL Impact League Season 7
IEM Dallas 2025
PGL Astana 2025
Asian Champions League '25
BLAST Rivals Spring 2025
MESA Nomadic Masters
CCT Season 2 Global Finals
IEM Melbourne 2025

Upcoming

2025 ACS Season 2: Qualifier
CSLPRO Last Chance 2025
CSL Xiamen Invitational
2025 ACS Season 2
CSLPRO Chat StarLAN 3
K-Championship
uThermal 2v2 Main Event
SEL Season 2 Championship
FEL Cracov 2025
Esports World Cup 2025
Underdog Cup #2
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
FISSURE Playground #1
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.