|
On October 14 2010 10:37 gustavo wrote:Show nested quote +EDIT: Even Billions is a huge underestimation - not all units are buildable in the beginning but over the course of the game we can probably consider about 15 different possibilities for each supply point, when you build a spine crawler etc. it frees another supply, so the number is probably even bigger - but if we take this we are looking at a rough estimate of 15^200 possibilities... good luck at enforcing any rules on that number. Builds all derive one from another - I'm not going to simulate every build from scratch, and yes I think 25 minutes is probably going to take too long and really not that useful I'll be shooting for something smaller at first for sure.
That's a whole different matter - he was talking about simulating all possibilities over a course of 25 minutes and my point stands - while that might be processable in a reasonable amount of time (Which could be, tbh I don't really now how long it takes to simulate one) you will come out with a such a vast number of results that any set of rules won't make it much better.
|
It looks so potentially powerful- up to a point.
I don't think the program takes into consideration the outcomes of battle/micro.
Sure, you can get 7 roaches out at X time, and the fact that it can be applied elsewhere is ingenious, but ultimately it won't fight battles for you.
|
Hmm. Lets say on average at any given point there's 6 possible options (build drone/overlord/zergling/queen/roach warren/hatchery).. then at the 15th build option there's 6^15 = 470bn possible builds. Never mind the 25th minute in, I think you'd struggle to get to the the 6-7th...
Could be a quicker way at solving the first 3-5 minute builds if Lomilar isn't already caching results of known genomes however.
|
Well it would be 6^15 if you're considering building 9 hatcheries/roach warrens/spawning pools/queens/overlords , simple rules kill 90% of builds if not more, but yes 25 minutes will take way too long since the number of options really starts to scale up.
|
On October 14 2010 10:58 Almania wrote:
Hmm. Lets say on average at any given point there's 6 possible options (build drone/overlord/zergling/queen/roach warren/hatchery).. then at the 15th build option there's 6^15 = 470bn possible builds. Never mind the 25th minute in, I think you'd struggle to get to the the 6-7th...
Could be a quicker way at solving the first 3-5 minute builds if Lomilar isn't already caching results of known genomes however.
Thank you. That's exactly what I mean, it is possible to simulate builds if you apply rules beforehand (just like Lomilar did) but anything else is really not practicable after a couple of minutes. The possibilities grow exponentially with every additional build option, and when you reach lair/hive tech it only gets worse.
On October 14 2010 11:08 gustavo wrote:
Well it would be 6^15 if you're considering building 9 hatcheries/roach warrens/spawning pools/queens/overlords , simple rules kill 90% of builds if not more, but yes 25 minutes will take way too long since the number of options really starts to scale up.
Even if you could get out 90% or more - what does this matter in comparison to the huge numbers? He just said it would be 470 BN different builds after 15 build option, now 10% of that i still 47BN left... let's go further and say you apply better rules, killing of 99,9% of the possibilities (and you won't get to that number, believe me) that's about 470M possipilities you have to examine by yourself.
|
On October 14 2010 11:08 gustavo wrote:
Well it would be 6^15 if you're considering building 9 hatcheries/roach warrens/spawning pools/queens/overlords , simple rules kill 90% of builds if not more, but yes 25 minutes will take way too long since the number of options really starts to scale up.
No.
Drone/Overlord/Extractor/Evo Chamber/Spawning Pool/Hatchery (6 - starting position)
Drone/Overlord/Extractor/Queen/Zergling/Lair/Spine Crawler/Roach Warren/Evo Chamber/Hatchery (10 - after spawning pool is built)
Drone/Overlord/Queen/Zergling/Roach Warren/Spine Crawler/Hydralisk Den/Spire/Infestor Pit/Hatchery (10 - after lair and two extractors are built)
Drone/Overlord/Queen/Zergling/Roach/Hydralisk/Mutalisk/Infestor/Corruptor/Ultralisk/Spine Crawler/Spore Crawler (12 - after every single building is built)
6 is optimistic even with pretty heavy culling. Building more production buildings just offer you yet more production buildings and yet more units to choose from.
|
Yes 25 minutes is not doable you guys are right I think I can still make it up to 6min though
Drone/Overlord/Extractor/Evo Chamber/Spawning Pool/Hatchery
Drone
Overlord - option not always available.
Extractor - only 2 before lair seems reasonable
evo chamber - only 1 before lair seems reasonable
spawning pool - only 1 -> adds ling option and roach
roach warren - only 1 -> adds roach option
hatchery - only 2 maybe before lair (besides main)
|
On October 14 2010 11:37 gustavo wrote:
Yes 25 minutes is not doable you guys are right I think I can still make it up to 6min though
Drone/Overlord/Extractor/Evo Chamber/Spawning Pool/Hatchery
Drone
Overlord - option not always available.
Extractor - only 2 before lair seems reasonable
evo chamber - only 1 before lair seems reasonable
spawning pool - only 1 -> adds ling option and roach
roach warren - only 1 -> adds roach option
hatchery - only 2 maybe before lair (besides main)
He did the math already... and it's even worse - did you consider a baneling nest and the possibility to morph any zerglings into banelings at any time?
|
I totally looked at the math, as you can see by my last post, I already posted his math is grossly overestimating the number since most options are not spammable thus inflating the number, yes buildings open more options, but most of those options are also not spammable, or do you really think by the 10 supply you have 6^10 options?
gonna 6 pool into dual evo chamber into roaches into fast expo.
|
Knew there was a unit I was forgetting.. and then there's upgrades.
spawning pool - only 1 -> adds ling option and roach
Adding a spawning pool doesn't just add ling and roach warren, it also adds queen/lair/metabolic boost/baneling nest/spine crawler. Restricting people to just 1 building of each hardly simplifies the problem at all.
|
The number of pure permutations is absurd. But GAs are just one search algorithm, they kinda take the 'shoot, see how close you get, then change some parameters and see if you get closer' method. Doing a hard search with exclusion, while it seems impractical, can be done fairly efficiently. There are methods like tree pruning that can put it in the realm of feasibility, but what I like about GAs is that you need a simulator, a scoring algorithm, and a method of input, and the rules don't matter as much. Less coding.
Kinda like A*, which is a brute force search algorithm, that works very well for path-finding. Everything has its place.
And GAs have their downfalls. GAs can't do an exhaustive search, for instance.
There are only also a few reasonable points where you try to do something. When you can, is one of those points. After something else happens is another one. It isn't impossible to do an exhaustive search, but it is certainly much harder, in my opinion.
|
On October 14 2010 12:15 gustavo wrote:
I totally looked at the math, as you can see by my last post, I already posted his math is grossly overestimating the number since most options are not spammable thus inflating the number, yes buildings open more options, but most of those options are also not spammable, or do you really think by the 10 supply you have 6^10 options?
gonna 6 pool into dual evo chamber into roaches into fast expo.
Just because it's not reasonable doesn't mean the program won't spit that result out - so you have to apply really good filters. And if you do that you could just make a build by yourself. And no - obviously you didn't totally look at the math - banelings alone - that's a completely separate way from larvae. And larvae were the one thing that kept the amount of possibilities down to a more or less reasonable number, let's just say you get a baneling nest and 20 zerglings until 25 supply now you could at any time morph 1-20 banelings, changing everything really.
|
20 zerglings until 25 supply now you could at any time morph 1-20 banelings,
Any time I have 1000 gas and minerals.
But yes banelings are one of the 4 options that can be available all the time , all the rest you only press once early game.
By the time you can do that you're nearing 5min ingame anyhow.
PS: I already said 25 minutes is impossible, 6 minutes is possible tho. I'll try to make it.
|
On October 14 2010 12:31 gustavo wrote:Show nested quote +20 zerglings until 25 supply now you could at any time morph 1-20 banelings, Any time I have 1000 gas and minerals. But yes banelings are one of the 4 options that can be available all the time , all the rest you only press once early game. By the time you can do that you're nearing 5min ingame anyhow. PS: I already said 25 minutes is impossible, 6 minutes is possible tho. I'll try to make it.
Well 5 minutes probably is possible, I won't argue with that - but you will still face a huge number of different builds and it will be quite tough work to find out which ones are reasonable.
Sorry, got probably a bit too stuck on the math numbers after I argued the initial "every possible build up to 25 minutes". Just wish you good luck on that and tell us if you find any nice new builds.
And thank you for your opinion on that matter Lomilar, as well as your effort on the build order simulator, should be interesting for all of us.
|
There was a build order calculator for Brood war, and I don't think it ever worked perfectly, but I think it was pretty good. Overall I don't think it was too useful though.
Also, I am guessing this calculator doesn't currently consider gas trick an option. I made a roach rush build that went 12pool before overlord, and while I can't say it was for sure faster (also might not be exactly 7 roaches), it would have been fast.
I'm also interested to hear that that is the fastest way to get 7 roaches, because 10 overlord 10 pool sounds pretty bad due to larva wasting and low drone count early on. Yes I know it's calculating optimal build for the final goal which is fast (only 7 roaches), but one would think that an extra drone or two before pool would really help get the roaches out faster at the end. I suppose that's just an illusion though.
|
On October 14 2010 12:46 Xapti wrote:
Also, I am guessing this calculator doesn't currently consider gas trick an option. I made a roach rush build that went 12pool before overlord, and while I can't say it was for sure faster (also might not be exactly 7 roaches), it would have been fast.
No he said earlier that the calculator didn't consider gas trick when simulating the 7 roach build. He got it in later when he simulated the Muta builds but it seems it doesn't work properly yet.
|
If you are interested in whether C#/C/C++/Java is better in terms of performance or whatever metric, let me recommend this link:
http://stackoverflow.com/questions/145110/c-performance-vs-java-c
It's a peer-reviewed discussion with real programmers on the #1 site for programming questions.
Here is general consensus:
"But as far as I see it, C# or Java are all in all a better bet. Not because they are faster than C++, but because when you add up their qualities, they end up being more productive, needing less training, and having more complete standard libraries than C++. And as for most of programs, their speed differences (in one way or another) will be negligible..." -says paercebal who has a 12k reputation rating.
|
On October 14 2010 12:22 Lomilar wrote:
The number of pure permutations is absurd. But GAs are just one search algorithm,
Of course  . Brute forcing is quite impractical though...
Out of curiousity I thought I would try it (interested in the complexity of build orders).
With a few heuristics - no more than 18 supply ahead, no more than 1 of any building (or 1 additional hatchery), except for extractors where I'm only allowing two (think of it as 1 base play with possible 2 hatcheries), a subset of buildings - no Lair or baneling nests, and no upgrades other than metabolic boost, I came up with:
4 actions in: 1500 BOs.
6 actions in: 80000 BOs.
8 actions in: 4 million BOs.
9 actions in: 30 million BOs.
10 actions in: 200 million BOs.
Exponential growth is a scary thing..
(By comparison I count the popular 5 roach rush as a 35 action BO).
I'm not running these through any kind of game simulator (other than supply checking) and so many of these will go way past 5 minutes in (ie 6 Hatchery, 5 Pool, 4 Extractor, 3 Roach Warren BOs would take a long time to complete). And you could narrow the search space a lot by limiting it to 5 minutes, but it's still astonishing just how many BOs there are with just 10 actions in them..
|
On October 14 2010 09:40 tetracycloide wrote:Show nested quote +On October 14 2010 09:29 Eknoid4 wrote:On October 14 2010 08:54 Dionyseus wrote:On October 14 2010 08:48 Eknoid4 wrote:
this really is not as special or significant as this thread makes it seem.
It's not realistic. At best it would be a worse version of heal meters in WoW. "Yeah dude ur so bad u got ur 7th roach out at 4:42 instead of 4:40 that's why u lost" Believe it or not for pros 1 second can be enough time to be the reason why you won or lost. Believe it or not pros would still have to figure out how this build actually holds up in real combat which means practicing it regardless of the computer's "perfect timing" So they'd be back to where they are now. Working the kinks out of builds they've tried. Having a computer program spit out a time wouldn't help any pro more than playing it against another pro would. I think you're missing the point. If a pro wants to know 'can I squeeze an extra X in at Y time' then this is a way more cost efficient way to determine that then practicing it. It's like video taping movements in other sports and analyzing it to look for inefficiencies of movement you'd never notice without the aid of a machine. Which is, believe it or not, pretty common in many sports. It's not there to teach you how to read opponents or how to react in game or even to show what the 'best' build is for any given situation. It's simply a tool that, once polished enough to be useful, could reveal some efficiency flaws in any given set of play.
that totally wouldn't be the use of this at all. We already have replays that fulfill EXACTLY what you describe for every other game/sport.
this only serves to say "what time can i get ___ out by"
|
On October 14 2010 13:22 Almania wrote:Show nested quote +On October 14 2010 12:22 Lomilar wrote:
The number of pure permutations is absurd. But GAs are just one search algorithm, Of course . Brute forcing is quite impractical though... Out of curiousity I thought I would try it (interested in the complexity of build orders). With a few heuristics - no more than 18 supply ahead, no more than 1 of any building (or 1 additional hatchery), except for extractors where I'm only allowing two (think of it as 1 base play with possible 2 hatcheries), a subset of buildings - no Lair or baneling nests, and no upgrades other than metabolic boost, I came up with: 4 actions in: 1500 BOs. 6 actions in: 80000 BOs. 8 actions in: 4 million BOs. 9 actions in: 30 million BOs. 10 actions in: 200 million BOs. Exponential growth is a scary thing.. (By comparison I count the popular 5 roach rush as a 35 action BO). I'm not running these through any kind of game simulator (other than supply checking) and so many of these will go way past 5 minutes in (ie 6 Hatchery, 5 Pool, 4 Extractor, 3 Roach Warren BOs would take a long time to complete). And you could narrow the search space a lot by limiting it to 5 minutes, but it's still astonishing just how many BOs there are with just 10 actions in them..
Even some very simple logic could cut out quite a few million of those BOs. For instance many of them would be make 1-2 hatcheries right away, which simple logic would tell you is not cost efficient.
Also making tech structures you do not require for your build.
Optimally the program will know which tech structures it need for the requested units/upgrades and only build those. There is no point in testing builds where you get other un-needed structures. The only exception is to see if it is worth working in an expansion at some point. And if it is worth getting one expansion then check if it is worth getting two, no point in checking if it is worth getting two of them if it is not worth getting one.
So 10 actions in you can probably cut down from 200 million to less than 1000 "sensible" build orders with some basic logic. As all you really need to figure out is if it is worth to cut a drone to get supply/tech earlier or not. Or what should come first, supply or tech, etc...
There is no need to test "what if I build this drone X seconds later (while doing nothing)" or "what if I get gas on 5..." as those make no sense. Also stuff like "what if I rush to spire, maybe then I can get 7 roaches out faster" is also pointless to test. While it would be a valid build to get roaches we know that building tech we don't need will only slow down the optimal build.
It shouldn't even be that hard to code some basic rules into the application, not that I know exactly how he built this application but I have made similar applications before to test the optimal build for other games (LOU).
|
|
|
|
|
|
EPT
