• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EDT 17:32
CEST 23:32
KST 06:32
  • 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 Tall10HomeStory Cup 27 - Info & Preview18Classic wins Code S Season 2 (2025)16Code S RO4 & Finals Preview: herO, Rogue, Classic, GuMiho0
Community News
Firefly given lifetime ban by ESIC following match-fixing investigation17$25,000 Streamerzone StarCraft Pro Series announced7Weekly Cups (June 30 - July 6): Classic Doubles7[BSL20] Non-Korean Championship 4x BSL + 4x China10Flash Announces Hiatus From ASL73
StarCraft 2
General
The GOAT ranking of GOAT rankings RSL Revival patreon money discussion thread Weekly Cups (June 30 - July 6): Classic Doubles Server Blocker RSL Season 1 - Final Week
Tourneys
RSL: Revival, a new crowdfunded tournament series FEL Cracov 2025 (July 27) - $8000 live event $5,100+ SEL Season 2 Championship (SC: Evo) $25,000 Streamerzone StarCraft Pro Series announced Sparkling Tuna Cup - Weekly Open Tournament
Strategy
How did i lose this ZvP, whats the proper response Simple Questions Simple Answers
Custom Maps
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
Flash Announces Hiatus From ASL BW General Discussion A cwal.gg Extension - Easily keep track of anyone Script to open stream directly using middle click ASL20 Preliminary Maps
Tourneys
2025 ACS Season 2 Qualifier [Megathread] Daily Proleagues Small VOD Thread 2.0 Last Minute Live-Report Thread Resource!
Strategy
Simple Questions, Simple Answers I am doing this better than progamers do.
Other Games
General Games
Path of Exile Stormgate/Frost Giant Megathread CCLP - Command & Conquer League Project The PlayStation 5 Nintendo Switch Thread
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 Russo-Ukrainian War Thread Things Aren’t Peaceful in Palestine The Accidental Video Game Porn Archive Stop Killing Games - European Citizens Initiative
Fan Clubs
SKT1 Classic Fan Club! Maru Fan Club
Media & Entertainment
Movie Discussion! [Manga] One Piece Anime Discussion Thread [\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
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: 697 users

Day 3: A word on Brute Force

Blogs > Revilo
Post a Reply
Revilo
Profile Blog Joined October 2010
Germany23 Posts
October 23 2010 14:52 GMT
#1
I had a number of people suggest brute force as a viable option in solving these short build order problems. I was skeptical, since the number of possible moves in a build order quickly explode in complexity. However, I was not content just thinking about it and so I tried it out for myself. The results are not too surprising...

I based my algorithm on the game as much as possible. This means that I run a simulation of the game for each build order with a minimum time unit of 1 game second. This allows me to bound the searches I make for optimal build orders by declaring my goal units and a maximum time limit for them to be reached. Since I know how long a 6-pool should take to be optimal, I can set a limit below this by 1 second and let the algorithm compute all elements in the search tree as a benchmark for the worst case. Sadly this number becomes quite staggering as the algorithm goes on.

Before you hit the 18 second mark the only things that are really possible are drones, spawning pool, overlords, hatcheries, extractors, moving drones to scout... So there are not that many options but nevertheless quite a few. However, as soon as you add a spawning pool or any other tech units this number of options grows to 20, then 30, and finally 62. This means that at each leaf of the tree, a set of 62 new actions have to be checked for validity and whether they achieve the goal. Of course I am not doing blind brute force (that would be even more horrendous), instead I only allow a small set of options based on the currently available technology to the Zerg simulation. Still, a run of the algorithm over all possible moves up to game time 10 seconds takes 1000ms to calculate. Setting the limit to 16 game seconds takes over 26000ms, and going beyond 30 game seconds is too long to wait for.

In conclusion:
Don't use brute force for this problem unless you can narrow down your tech A LOT! By this I mean, if you want to get a build for X number of zerglings, make sure you only allow the algorithm to use direct paths of tech (drones, overlords, spawning pool, queen) and ditch anything that you know will not help (extractors, roach warren, etc...)

*****
Looking for practice partners on EU! Message me if you like :) "I dont wtach porn anymore, I watch Socke" - Rotterdam
Weasel-
Profile Joined June 2009
Canada1556 Posts
October 23 2010 15:50 GMT
#2
You don't have to check for something every second, I think it would be easier for your algorithm to simply order all of the things it can currently make and just make those things in some specific order whenever it has the cash to afford them.
gods_basement
Profile Blog Joined August 2010
United States305 Posts
October 23 2010 17:38 GMT
#3
On October 24 2010 00:50 Weasel- wrote:
You don't have to check for something every second, I think it would be easier for your algorithm to simply order all of the things it can currently make and just make those things in some specific order whenever it has the cash to afford them.


you're right. you should make your brute force build order optimizer to use build orders. i cant believe anyone didnt try this previously
(TT~TT)
Revilo
Profile Blog Joined October 2010
Germany23 Posts
October 23 2010 21:13 GMT
#4
The whole idea behind this is to set some target composition of units, say... 6 zerglings, and have the algorithm spit out the shortest way to get to that (in other words, a build order that is as fast as possible to get to 6 zerglings). And I do only do a set number of possible moves at the end of each build order. However, my simulator that checks how long each of those build orders takes in game time has to evaluate on some scale. That scale is the game second. Thats why the algorithm only starts getting slow beyond 18 game seconds (since it takes 17 game seconds to spawn a drone). The first move can only be one of maybe 6 or 7 moves. So here the search space is relatively small. Now once you reach the end of simulation for those 6 or 7 moves, each can now append another 6 or 7 (or more if tech has been unlocked) moves. This makes 36 to 49 buildorders to evaluate. A lot of these are illegal ones, and these I already filter out. However, once you hit the next level down you are already at 200 to 350 build orders. And that, although I have only 3 things building in the build orders.

As I stated before, you can make the algorithm more intelligent to speed things up by removing possible moves based on logic. However, you run the risk of excluding a possibility for a better solution in doing so and it no longer is "truly" brute force. This was only an experiment, but it has shown the core stats of the problem at hand. I will be revisiting Genetic Algorithms with more determination, since it seems the search space truly is IMMENSE!

I hope to release some code soon too Hold on tight!
Looking for practice partners on EU! Message me if you like :) "I dont wtach porn anymore, I watch Socke" - Rotterdam
Please log in or register to reply.
Live Events Refresh
DaveTesta Events
18:00
Kirktown Ready Room #3
davetesta110
Liquipedia
BSL20 Non-Korean Champi…
18:00
RO8 Round Robin Group - Day 1
Bonyth vs QiaoGege
Dewalt vs Fengzi
Hawk vs Zhanhun
Sziky vs Mihu
Mihu vs QiaoGege
Zhanhun vs Sziky
Fengzi vs Hawk
ZZZero.O267
LiquipediaDiscussion
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
SpeCial 180
Livibee 61
StarCraft: Brood War
ZZZero.O 267
HiyA 77
Dota 2
syndereN373
monkeys_forever292
Pyrionflax114
League of Legends
Grubby4946
Dendi1257
Counter-Strike
fl0m1693
Stewie2K1067
Heroes of the Storm
Khaldor415
Trikslyr61
Other Games
summit1g6374
mouzStarbuck260
ToD136
ViBE123
Organizations
Other Games
gamesdonequick54636
StarCraft 2
angryscii 39
Blizzard YouTube
StarCraft: Brood War
BSLTrovo
sctven
[ Show 21 non-featured ]
StarCraft 2
• kabyraGe 218
• printf 42
• musti20045 27
• tFFMrPink 16
• OhrlRock 1
• sooper7s
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• LaughNgamezSOOP
• Migwel
StarCraft: Brood War
• Michael_bg 4
• STPLYoutube
• ZZZeroYoutube
• BSLYoutube
Dota 2
• masondota21716
League of Legends
• Doublelift4480
• Jankos2592
Other Games
• imaqtpie2219
• Shiphtur488
Upcoming Events
Sparkling Tuna Cup
12h 28m
RSL Revival
12h 28m
Classic vs Clem
FEL
17h 28m
Elazer vs Spirit
Gerald vs MaNa
BSL20 Non-Korean Champi…
20h 28m
Bonyth vs Dewalt
QiaoGege vs Dewalt
Hawk vs Bonyth
Sziky vs Fengzi
Mihu vs Zhanhun
QiaoGege vs Zhanhun
Fengzi vs Mihu
Wardi Open
1d 13h
Replay Cast
2 days
WardiTV European League
2 days
PiGosaur Monday
3 days
uThermal 2v2 Circuit
3 days
Replay Cast
4 days
[ Show More ]
The PondCast
4 days
Replay Cast
5 days
Epic.LAN
5 days
CranKy Ducklings
6 days
Epic.LAN
6 days
BSL20 Non-Korean Champi…
6 days
Bonyth vs Sziky
Dewalt vs Hawk
Hawk vs QiaoGege
Sziky vs Dewalt
Mihu vs Bonyth
Zhanhun vs QiaoGege
QiaoGege vs Fengzi
Liquipedia Results

Completed

KCM Race Survival 2025 Season 2
HSC XXVII
NC Random Cup

Ongoing

JPL Season 2
BSL 2v2 Season 3
Acropolis #3
CSL 17: 2025 SUMMER
Copa Latinoamericana 4
Jiahua Invitational
2025 ACS Season 2: Qualifier
CSLPRO Last Chance 2025
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

Upcoming

CSL Xiamen Invitational
CSL Xiamen Invitational: ShowMatche
2025 ACS Season 2
CSLPRO Chat StarLAN 3
BSL Season 21
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.