I only let it run for 15-30 minutes. I'll let it run overnight and see what it turns out. The other weird thing that I'm seeing is that it's getting "air weapons" type upgrades - perhaps because it's got extra minerals it can't spend anywhere else? (I didn't request the upgrade or any air units)
SCFusion - WoL, HotS & LotV Build Order Optimizer - Page 13
Forum Index > SC2 General |
croupier
United States92 Posts
I only let it run for 15-30 minutes. I'll let it run overnight and see what it turns out. The other weird thing that I'm seeing is that it's getting "air weapons" type upgrades - perhaps because it's got extra minerals it can't spend anywhere else? (I didn't request the upgrade or any air units) | ||
CarbonTwelve
Australia525 Posts
On November 17 2010 07:26 quillian wrote: Awesome! I've been waiting for someone to make one for protoss. Is there any way to get it compiled for mac? if you haven't done it yourself I might be able to suggest a way, if the source is pure c++. It's only C++ (no other languages) however there are quite a few Windows specific calls made in the code, so I'm not sure how easy they'll be to translate to Mac calls. There's an issue on the project page to deal with converting to a cross platform gui though, so once we get some progress with that then we can look at making the whole program cross platform. | ||
quillian
United States318 Posts
On November 17 2010 07:37 CarbonTwelve wrote: It's only C++ (no other languages) however there are quite a few Windows specific calls made in the code, so I'm not sure how easy they'll be to translate to Mac calls. There's an issue on the project page to deal with converting to a cross platform gui though, so once we get some progress with that then we can look at making the whole program cross platform. great, glad you guys are on it. I'll be content running it in bootcamp for now. Thanks for the quick response! | ||
Aneon
14 Posts
What does the "Mutation Rate" variable do? Is there a point in increasing/decreasing it if we want more experimental builds? Or will it always reach the same end result? | ||
lowlypawn
United States241 Posts
* "Running for" and "Last updated" time * I also prefer the output of EC and how you can view "simple", "detailed" and "copy to clipboard". I haven't used the YABOT feature but that sounds like a really useful feature. But the SPEED of this over EC simply can't be beat. The difference between Java vs C++ is amazing. Lastly I thought the program was too bright on the eyes so I decided to hack it and make the UI closer to my liking + Show Spoiler + Uploaded with ImageShack.us + Show Spoiler + Haha, just kidding, I'm no hacker or programmer! I just photoshopped it | ||
CarbonTwelve
Australia525 Posts
On November 17 2010 08:58 Aneon wrote: What does the "Mutation Rate" variable do? Is there a point in increasing/decreasing it if we want more experimental builds? Or will it always reach the same end result? The mutation rate is something that affects the underlying GA. The way that works is that after it breeds new build orders, it goes through every single command and does a random roll to see if it should mutate it, and it does this for each mutation operator (insert, duplicate, delete, mutate, random swap, immediate swap, move). A higher mutation rate means that each command is more likely to mutate at each step. The benefits of having a higher mutation rate is that it comes up with different builds a lot more quickly, so usually this helps out early on because it tests out things more regularly. However, when you get to much later evolutions it has already tested out most combinations and will likely only get benefits from small changes, in which case a lower mutation rate is probably better. I'm playing around with the mutation rates and how they're used at the moment, so things might change with the next version. | ||
CarbonTwelve
Australia525 Posts
On November 17 2010 10:27 lowlypawn wrote: I really like how this program is evolving. Overall I still like Evolution Chamber's layout a little better and it has some features that should be implemented like: * "Running for" and "Last updated" time * I also prefer the output of EC and how you can view "simple", "detailed" and "copy to clipboard". I haven't used the YABOT feature but that sounds like a really useful feature. Sounds like I need to implement these soon to win you over Lastly I thought the program was too bright on the eyes so I decided to hack it and make the UI closer to my liking + Show Spoiler + Uploaded with ImageShack.us + Show Spoiler + Haha, just kidding, I'm no hacker or programmer! I just photoshopped it LOL nice. I must admit, my capabilities as a graphics & UI designer are limited, so maybe I should get you to design the interface | ||
iSTime
1579 Posts
On November 17 2010 11:28 CarbonTwelve wrote: The mutation rate is something that affects the underlying GA. The way that works is that after it breeds new build orders, it goes through every single command and does a random roll to see if it should mutate it, and it does this for each mutation operator (insert, duplicate, delete, mutate, random swap, immediate swap, move). A higher mutation rate means that each command is more likely to mutate at each step. The benefits of having a higher mutation rate is that it comes up with different builds a lot more quickly, so usually this helps out early on because it tests out things more regularly. However, when you get to much later evolutions it has already tested out most combinations and will likely only get benefits from small changes, in which case a lower mutation rate is probably better. I'm playing around with the mutation rates and how they're used at the moment, so things might change with the next version. It's pretty normal in algorithms to find maxima/minima of unknown functions to basically have a variable similar to your mutation rate decrease at some rate while you are doing the search. You've probably already thought of that, though. Some other similar ideas could be gotten from algorithms such as: http://en.wikipedia.org/wiki/Simulated_annealing. Basically, you could take some build order, make random changes, see if it is faster. If faster, take that build order for the next step in the process and continue. If slower, take that build order for the next step with some probability that drops off as a function of how much slower it is. This way you won't get stuck at some local minimum when there could possibly be a much faster build order. | ||
CarbonTwelve
Australia525 Posts
On November 17 2010 13:13 PJA wrote: It's pretty normal in algorithms to find maxima/minima of unknown functions to basically have a variable similar to your mutation rate decrease at some rate while you are doing the search. You've probably already thought of that, though. Yeah, this is one of the things I've been playing with. Some other similar ideas could be gotten from algorithms such as: http://en.wikipedia.org/wiki/Simulated_annealing. Basically, you could take some build order, make random changes, see if it is faster. If faster, take that build order for the next step in the process and continue. If slower, take that build order for the next step with some probability that drops off as a function of how much slower it is. This way you won't get stuck at some local minimum when there could possibly be a much faster build order. The process I'm using already accounts for getting out of local minimums. It 'saves' 1/8 of the builds between evolutions, so that it can keep processing ones that aren't as good but might lead to better results (in GAs it's called 'elitism'). It also resets (culls) the villages after a certain period of stagnation (and that period gets longer as it keeps running) so that they can evolve again, possibly leading in different directions to get better results. So basically there's quite a few things there to assist in it getting to an optimal result. I'll still be constantly tweaking a lot of it though. | ||
CarbonTwelve
Australia525 Posts
| ||
[HalcyoN]
United States163 Posts
Also, this tool is really cool, thanks for sharing this with the community (: | ||
30to1
105 Posts
After getting pretty good at getting decent results out of it. The main weakness seems to be short term losses for longer term gains. Funny, because creationists use this argument against evolution all the time (annoying). For instance, I have a waypoint that contains 12 zealots / 6 stalker / 2 sentry and 4 warpgates. The warpgate conversion is very close to the end of the list, despite it chronoboosting out two zealots ~20 seconds earlier (note this is not researching warpgate - this is the actual conversion to warpgate). I'm on game 823million and the longer term value of warpgate is just not being realized over the shorter term value of build unit. This makes sense, all else being equal the its very hard without 'mutation' for it to stumble into the value, it needs to try replace a single unit build action, with a convert to warp gate AND a unit build action subsequently - if it is just a one step comparison, build unit will always be better. Same problem I think in it determining how to build refineries. After something like 500,000,000 - it avoided taking a second refinery until very late, despite clearly failing because of lack of gas. It makes sense in the short term again i guess - since building the refinery alone may not count towards goal - you need a combination of three things to happen to move it closer to goal: build refinery, assign worker, build unit - then and only then may you eventually improve fitness. I've tested it with either a mutation rate of default .02 - or .1 - both seem to take forever with this stuff. I've looked over the code on this guy and evolution chamber - and I sort of think that a much more finite state approach may be better for this kind of problem rather than GA - almost exactly how most chess engines work. What are your thoughts on taking a more 'absolute' approach and just brute forcing every possibility in a directed manner (throwing in some heuristics for quicker useful results)? The hardest part I can think of would be optimizing out 'transpositions' into identical state from different branches. Maybe I'll write the terran version -- but I really hate friggin terran :D *edit - if you think the GA approach would really yield better results - what are your thoughts on the strengths and weaknesses of your/EC's approach to fitness (I believe yours was almost identical to ECs - but I did a pretty loose read of the code for both - and I'm not that strong with either language). | ||
Amui
Canada10558 Posts
| ||
jabaes
12 Posts
On November 16 2010 19:53 jabaes wrote: Bugs carriers have 120sec build time and mothership has 180sec chronoboosting them all throughout their build time will result to them being built at 80secs(carrier) and 120secs(mothership) the program finishes the carrier and mothership at both 50secs. On November 16 2010 19:57 Barook wrote: Mothership build-time is actually 160 seconds. ah right, but still 50sec is still off, i think it should be 106secs? | ||
gotlucky
United States60 Posts
On November 17 2010 15:02 Amui wrote: One of the functions that I feel would be VERY useful is fastest way to get X while also being able to delay it until a stalker comes out. Otherwise any competent player will know exactly what is going on because it is impossible to kill workers with zealot's. Sure I can get 9 blink stalkers before 7 min, but it also tells me to do some things including throwing down a TC right after cyber core, while the scout is most likely still in my base. Especially with the way that protoss macro and warpgates work, throwing down 2 gates at the same time 10 seconds later is almost the same as throwing a gate up then another 10 seconds later, but if in those 10 seconds, you can chase the scout out, it is very very worth it. While a computer can do the 3 warpgates on 3 timers perfectly, it is better for a human to have 3 warpgates synced up simply be able to have one timer to count. Use the waypoint function...it processes each waypoint in order. Use more than one waypoint if you have to. | ||
CarbonTwelve
Australia525 Posts
On November 17 2010 14:44 FurySparks wrote: So I've been reading throughout this thread and Fitness is a term that appeared often. What exactly does fitness represent in this simulator? I'm under the impression that higher fitness is better, so how exactly would i go about altering builds to increase the fitness? Also, this tool is really cool, thanks for sharing this with the community (: "Fitness" is a term used when describing Genetic Algorithms, which is what this app uses to come up with the build orders. It's basically just a value to represent how good the build order is to do what you want. So it's not actually something that you alter your targets to make it higher as there's no point comparing the fitness for two different targets. | ||
CarbonTwelve
Australia525 Posts
On November 17 2010 14:45 30to1 wrote: After getting pretty good at getting decent results out of it. The main weakness seems to be short term losses for longer term gains. Funny, because creationists use this argument against evolution all the time (annoying). For instance, I have a waypoint that contains 12 zealots / 6 stalker / 2 sentry and 4 warpgates. The warpgate conversion is very close to the end of the list, despite it chronoboosting out two zealots ~20 seconds earlier (note this is not researching warpgate - this is the actual conversion to warpgate). I'm on game 823million and the longer term value of warpgate is just not being realized over the shorter term value of build unit. Are you sure that the warpgate research was ready 20s earlier? This makes sense, all else being equal the its very hard without 'mutation' for it to stumble into the value, it needs to try replace a single unit build action, with a convert to warp gate AND a unit build action subsequently - if it is just a one step comparison, build unit will always be better. Yes, that's true, and indeed this is a weakness of GAs that's difficult to solve. I do have a few more tricks up my sleeve yet to be implemented, so hopefully that'll help, but it'll never be perfect. Same problem I think in it determining how to build refineries. After something like 500,000,000 - it avoided taking a second refinery until very late, despite clearly failing because of lack of gas. It makes sense in the short term again i guess - since building the refinery alone may not count towards goal - you need a combination of three things to happen to move it closer to goal: build refinery, assign worker, build unit - then and only then may you eventually improve fitness. This is something I wouldn't expect it to struggle as badly with. It's something that the villages should be able to help out with - by taking a fresh start, you're much more likely to end up with a village that evolved with 2 assimilators and then discovers that ultimately that's better. I've looked over the code on this guy and evolution chamber - and I sort of think that a much more finite state approach may be better for this kind of problem rather than GA - almost exactly how most chess engines work. What are your thoughts on taking a more 'absolute' approach and just brute forcing every possibility in a directed manner (throwing in some heuristics for quicker useful results)? The hardest part I can think of would be optimizing out 'transpositions' into identical state from different branches. Depth searching is something that works well for chess engines because they don't actually need to find the end result. All they need to find out is which path will ensure they have the best possible chance of victory some point later on. I think you'll find that most chess programs can only see about 13-14 moves ahead because after that the exponential growth just leads to too many options. This is despite most chess positions only have ~20 viable moves at a time. Meanwhile for my app it's having to consider 71 different 'moves' (commands) at each step, and it has to predict something that's generally 30+ commands long. There's absolutely no way you'd be able to depth search anything but the most basic of builds. Maybe I'll write the terran version -- but I really hate friggin terran :D I do actually plan to implement both Zerg and Terran in my app too - this certainly won't stay Protoss only forever Having said that, Zerg will probably come before Terran because a lot of the ground work for that is already done. *edit - if you think the GA approach would really yield better results - what are your thoughts on the strengths and weaknesses of your/EC's approach to fitness (I believe yours was almost identical to ECs - but I did a pretty loose read of the code for both - and I'm not that strong with either language). To be honest, I haven't paid too much attention to how EC's fitness works. I looked into the EC code before I started my version, but I was mainly trying to look at the underlying code for the GA. Took me quite a while to realise that the reason I couldn't find it was because EC uses a library (JGAP) and hence there wasn't any GA code, just his operators and fitness code, which I figured I could work out pretty easily on my own. I did copy his code for calculating income rates (which I never did remember to specifically credit him for, sorry Lomilar!), but I've just rewritten that for the next version to make it more efficient. From what I understand from talking to him & others on IRC, EC uses a time based build order rather than just a command based one. So everything he does is split up into the second it occurs at. He believes this is a better approach as it allows for junk DNA (commands that aren't possible) to be hidden in the build order which can come to light as the build order changes, and believes an order based BO is too rigid. Personally I disagree and prefer the approach I've taken. Either way, it's actually not too critical I think - clearly they're both getting to pretty solid build orders most of the time, and while mine does struggle with getting things like chrono and warpgates, I think that's more due to the complexity of using those than the underlying algorithm. I believe this will become very evident when I implement the Zerg version so that true comparisons can be made. | ||
CarbonTwelve
Australia525 Posts
On November 17 2010 15:02 Amui wrote: One of the functions that I feel would be VERY useful is fastest way to get X while also being able to delay it until a stalker comes out. Otherwise any competent player will know exactly what is going on because it is impossible to kill workers with zealot's. Sure I can get 9 blink stalkers before 7 min, but it also tells me to do some things including throwing down a TC right after cyber core, while the scout is most likely still in my base. Especially with the way that protoss macro and warpgates work, throwing down 2 gates at the same time 10 seconds later is almost the same as throwing a gate up then another 10 seconds later, but if in those 10 seconds, you can chase the scout out, it is very very worth it. While a computer can do the 3 warpgates on 3 timers perfectly, it is better for a human to have 3 warpgates synced up simply be able to have one timer to count. I plan to implement maximum counts sometime soon (probably v6 or v7), so what you could do is have waypoint 1 as a stalker, 1 warpgate (min and max), and then have waypoint 2 with the 9 blink stalkers. On November 17 2010 16:01 jabaes wrote: ah right, but still 50sec is still off, i think it should be 106secs? Yep, I've acknowledged this is a bug and will be fixed in the next version Thanks again for pointing it out. | ||
Almania
145 Posts
On November 17 2010 10:27 lowlypawn wrote: But the SPEED of this over EC simply can't be beat. The difference between Java vs C++ is amazing. I'm one of the last people to defend Java, but I think this is incorrect. It's moreso the difference in algorithms - there's not an order of magnitude difference between Java and C++ speed in any comparison I've ever seen. You'll note that Carbon's already sped his up by well over double since the first release - showing that algorithms are as important as ever. Simulating build orders is simply hard work - and Lomilar's EC makes many sacrifices for readability over speed. Particularly with regards to income rates - what he has as a large block of code creating arrays etc could be reduced to a single derived numerical expression. | ||
Lmui
Canada6155 Posts
For example, setting: Target time: 85 seconds 11 probes Helps the game get to 9 pylon extremely fast To get 9 pylon 12 gateway, Waypoint 1 as above, Waypoint 2: Target Time: 160 1 Gateway Generally, in most builds as protoss I get my zealot out by 210 seconds and especially for fast blink(my favourite build) I write down a core by 210, zealot by 210 for waypoint 3. Forcing the program to use what looks to be an optimal build order and target times that are very tight to what you want will help the program get the order you want. FWIW, 9 blink stalkers walking up a ramp by 6:30, getting a stalker in time to chase out the scouting probe. | ||
| ||