|
On November 17 2010 14:45 30to1 wrote: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.
Right? Given the already-known tech order for any combination of units, and therefore the necessary minimum income, just have it calculate the most cost efficient (and therefore the fastest) build pattern. Almost everything is fixed or predetermined.
I've been doing this on paper which is unfortunately very slow, but it's really just a math problem that's "solved" by rearranging the variables logically until income requirements at key intervals are achieved as early as possible. The only variables I've found necessary are SCV mining times (to calculate income for any given situation), and SCV travel speed, and obviously building/training times. It's a simple and straightforward matter of adding SCVs/refineries/orbital commands/expansions whenever A) you have surplus bank, and B) it wont interrupt the tech. Finally, account for income difference this will cause however it pleases you personally, perhaps by teching earlier if it's therefore possible, or by adding more units, by adding upgrades, etc.
This way almost everything is known and fixed, so unnecessary/inefficient patterns are never considered. It's just common sense, but once you actually consider the math behind it all then it's almost like you can almost see in your head the mathematically correct fastest build order. A brute force application sounds perfect for this, and this method (given i know nothing about programming) seems simpler and more efficient. You give it the answer, it gives you the equation. Perhaps it can crank out the necessarily-fastest build order in a matter of seconds or microseconds, instead of having to learn the already-known, necessary build order/requirements over time...
I could just be rambling because I literally know nothing about programming or the types of things you guys have already considered.
On November 17 2010 14:45 30to1 wrote:Maybe I'll write the terran version Maybe there IS a god after all!
EDIT: How are you guys calculating income? I've been doing it using average per-second incomes for various amounts of harvesters, which i determined through real trial and error. For example, having 6 SCVs is likely to generate 5.8200692 minerals per second, etc etc...
|
On November 17 2010 17:26 Almania wrote:
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.
It's not the algorithms, they'll be almost identical (at least in terms of complexity). C++ definitely is more efficient than Java - very few people will argue about that. For most apps, the relative difference isn't as much as my app demonstrates. The reason why my app is so much faster is that C++ allows direct memory control which means I can completely eliminate dynamic memory allocation during the algorithm's execution (something that's basically impossible in Java), which is why mine is so much faster. Also the structures you can define in C++ can be a lot smaller / simpler, which means my app uses far less memory than EC.
Also, Java has a lot more error & exception handling that isn't necessary and creates a lot of overhead that you don't get with C++.
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.
Not quite, at least, it can't be a single line with the same accuracy, however it can be reduced to eliminate loops. For example, here's the code I just wrote to calculate the income rate for the next version coming:
+ Show Spoiler + static double sumIncome[] = {0.0, 4*45/60.0, (4*45+4*39)/60.0, (8*45+4*39)/60.0, (8*45+8*39)/60.0, (8*45+8*39+4*34)/60.0, (8*45+8*39+4*34+4*12)/60.0}; // Sum of income rates
static double incomeRate[] = {45/60.0, 39/60.0, 45/60.0, 39/60.0, 34/60.0, 12/60.0, 0}; // Income rates
size_t patchCount = 4 * baseCount;
workerCount = mymin(workerCount, 24*baseCount);
size_t incomeRateIndex = workerCount/patchCount;
return baseCount*sumIncome[incomeRateIndex] + (workerCount % patchCount)*incomeRate[incomeRateIndex];
|
On November 17 2010 18:26 calculator wrote:
Right? Given the already-known tech order for any combination of units, and therefore the necessary minimum income, just have it calculate the most cost efficient (and therefore the fastest) build pattern. Almost everything is fixed or predetermined.
I've been doing this on paper which is unfortunately very slow, but it's really just a math problem that's "solved" by rearranging the variables logically until income requirements at key intervals are achieved as early as possible. The only variables I've found necessary are SCV mining times (to calculate income for any given situation), and SCV travel speed, and obviously building/training times. It's a simple and straightforward matter of adding SCVs/refineries/orbital commands/expansions whenever A) you have surplus bank, and B) it wont interrupt the tech. Finally, account for income difference this will cause however it pleases you personally, perhaps by teching earlier if it's therefore possible, or by adding more units, by adding upgrades, etc.
This way almost everything is known and fixed, so unnecessary/inefficient patterns are never considered. It's just common sense, but once you actually consider the math behind it all then it's almost like you can almost see in your head the mathematically correct fastest build order. A brute force application sounds perfect for this, and this method (given i know nothing about programming) seems simpler and more efficient. You give it the answer, it gives you the equation. Perhaps it can crank out the necessarily-fastest build order in a matter of seconds or microseconds, instead of having to learn the already-known, necessary build order/requirements over time...
I could just be rambling because I literally know nothing about programming or the types of things you guys have already considered.
There's a huge difference between Terran build orders, which are actually very simple, and Zerg & Protoss build orders which are a lot more complicated due to larva and chrono boost. These two factors have a huge impact on when things are done, so it really isn't going to be straight forward to create a depth searching algorithm to solve these BOs.
Maybe there IS a god after all!
 People doubt that I'll get to doing Terran with my app?
EDIT: How are you guys calculating income? I've been doing it using average per-second incomes for various amounts of harvesters, which i determined through real trial and error. For example, having 6 SCVs is likely to generate 5.8200692 minerals per second, etc etc...
Yeah, my code uses an approximation based on measured averages (measurements were taken by PiousFlea - his thread is on these forums somewhere). I posted the code for the new income rate calculator above.
|
On November 17 2010 19:41 CarbonTwelve wrote:Show nested quote +On November 17 2010 14:45 30to1 wrote:Maybe I'll write the terran version Maybe there IS a god after all! People doubt that I'll get to doing Terran with my app?
I don't think everyone knows you're planning a terran version.
I'm really looking forward to the terran and zerg version. I already think your app is superior to EC both in terms of readability and efficiency. Even though I can think of loads of new features, I think you should prioritize getting the terran and zerg version done. Because then everyone could switch to using your more efficient program, and you'll gain even more community support.
Future features I can think of:
- The ability to choose different evolutionary strategies, such as one very experimental with a high mutation rate, another less risky with low mutation, maybe also different settings of village sizes/styles. I'm aware you can already choose mutation rate, but would be cool to have more variables here to control the evolution, and add some predefined settings to start from.
- The ability to start from a pre-defined build order, either one you define yourself or one you've previously generated (most important). Maybe even combine different build orders and let them breed and try the result. In combination with the first, this allows you to first use an experimental strategy to find a basic strategy, then run it with lower mutation or another strategy to optimize it further. It also gives you the ability to paus and resume.
- Related to the previous point, it would be cool to have the ability to "help" the program discover specific builds, by allowing you to manually edit the build order (e.g. by moving one line up or down, or simply edit it in raw text) and then let it evolve from there.
- A few more display/rendering options, such as Simple and YABOT mode from EC.
I don't think you need to work much more on the GUI, it already looks great - clean and simple.
And like I said, I think you should prioritize getting terran and zerg version finished before starting any new features.
Keep it coming, you rock!
|
Even though people are talking about "make a terran/zerg version!!". I'd like to share my opinion that I really hope you read. This program is ok, it isn't really good, it isn't really great.. Why? Because honestly... you cannot really use any of the build orders that the program suggest. There are 2 flaws.
First and mainly, there should be an option where you can set the resource value in income. As it is now, if I set "i want 4 zealots and 5 stalkers." Sure I get a build that makes that the fastest, but no way near economical, so that small army is an all-in attack.
Also, the way the program/game works is that it makes huge amounts of probes in the beginning, to mass every unit extremly late. Making you very vunrable to any sort of early aggression. So making it so that "I want atleast this amount of units at this specific time".
By doing these 2 steps, you will suddenly be able to accually get some serious valid strategies, not some wierd all-ins with assimilator on 10 and 2 gates of 15 and stuff like that...
|
On November 17 2010 20:40 413X wrote:
Even though people are talking about "make a terran/zerg version!!". I'd like to share my opinion that I really hope you read. This program is ok, it isn't really good, it isn't really great.. Why? Because honestly... you cannot really use any of the build orders that the program suggest. There are 2 flaws.
First and mainly, there should be an option where you can set the resource value in income. As it is now, if I set "i want 4 zealots and 5 stalkers." Sure I get a build that makes that the fastest, but no way near economical, so that small army is an all-in attack.
Also, the way the program/game works is that it makes huge amounts of probes in the beginning, to mass every unit extremly late. Making you very vunrable to any sort of early aggression. So making it so that "I want atleast this amount of units at this specific time".
By doing these 2 steps, you will suddenly be able to accually get some serious valid strategies, not some wierd all-ins with assimilator on 10 and 2 gates of 15 and stuff like that...
That's because you don't know how to use the app correctly. You must learn to use waypoints and set up a goal after your initial goal that decide how much production you want your income to be able to sustain at this point. Such as that you want to be able to produce 10 stalkers in the next 3 minutes, after your first goal is met. And if you don't want it to go too income heavy in the beginning, you set an earlier waypoint where you define how much production you want in the early stages.
I also thought I saw great flaws in the app first, but it's only because it tries to reach your goal the quickest possible without regard to the future. But if you also define future goals, then it'll take this into consideration. And I think that's exactly how we want it to behave. Now you can use it both for extreme all-in builds, very economic builds, or average mid-game builds.
|
On November 17 2010 20:29 Aneon wrote:
I'm really looking forward to the terran and zerg version. I already think your app is superior to EC both in terms of readability and efficiency. Even though I can think of loads of new features, I think you should prioritize getting the terran and zerg version done. Because then everyone could switch to using your more efficient program, and you'll gain even more community support.
Yeah, I'm beginning to think that's probably a good idea. Most of the Protoss features are there, just need to release the constant probe production (already done) and the scouting probe features.
Future features I can think of:
[*]The ability to choose different evolutionary strategies, such as one very experimental with a high mutation rate, another less risky with low mutation, maybe also different settings of village sizes/styles. I'm aware you can already choose mutation rate, but would be cool to have more variables here to control the evolution, and add some predefined settings to start from.
More variables for the GA is planned, such as the ability to control the village count & sizes (hence that list control in the settings that doesn't actually do anything atm), and a few other things I had planned that I can't think of atm.
[*]The ability to start from a pre-defined build order, either one you define yourself or one you've previously generated (most important). Maybe even combine different build orders and let them breed and try the result. In combination with the first, this allows you to first use an experimental strategy to find a basic strategy, then run it with lower mutation or another strategy to optimize it further. It also gives you the ability to paus and resume.
[*]Related to the previous point, it would be cool to have the ability to "help" the program discover specific builds, by allowing you to manually edit the build order (e.g. by moving one line up or down, or simply edit it in raw text) and then let it evolve from there.
The next version will remember the last build order and seed any future build requests with it (already implemented). I do have plans to allow custom build orders to be defined and used as a seed, but that'll probably be a fair way off.
[*]A few more display/rendering options, such as Simple and YABOT mode from EC.
Yep, will do that probably the version after next (so v6).
I don't think you need to work much more on the GUI, it already looks great - clean and simple.
And like I said, I think you should prioritize getting terran and zerg version finished before starting any new features.
Keep it coming, you rock!
Cheers 
|
Been following this thread since the moment I saw it, been playing with the program nonstop.. Great work, amazing program, thank you!!
The only thing I really want to see from it would be a way to tell it, "I want the fastest possible two Gateways capable of nonstop zealot production." I could see this being implemented possibly as a checkbox for each structure for if you want constant production and then with another box where you could put what unit you constantly want... Sure sounds ugly though lol
Just my suggestion for a feature I'm sure would be a huge addition to the program.
Thank you for all your hard work so far!
|
On November 17 2010 20:40 413X wrote:
Even though people are talking about "make a terran/zerg version!!". I'd like to share my opinion that I really hope you read. This program is ok, it isn't really good, it isn't really great.. Why? Because honestly... you cannot really use any of the build orders that the program suggest. There are 2 flaws.
First and mainly, there should be an option where you can set the resource value in income. As it is now, if I set "i want 4 zealots and 5 stalkers." Sure I get a build that makes that the fastest, but no way near economical, so that small army is an all-in attack.
Also, the way the program/game works is that it makes huge amounts of probes in the beginning, to mass every unit extremly late. Making you very vunrable to any sort of early aggression. So making it so that "I want atleast this amount of units at this specific time".
By doing these 2 steps, you will suddenly be able to accually get some serious valid strategies, not some wierd all-ins with assimilator on 10 and 2 gates of 15 and stuff like that...
As Aneon has said, what you're after can be achieved through the use of the waypoints.
I appreciate what you're suggesting, but for an algorithm like this you have to give it very clear 'instructions' if you will so that it can give you exactly what you asked for. In this case, the instructions I give it are to build what you asked for (in this case 4 zealots and 5 stalkers) as fast as possible - there's no uncertainty in that for the algorithm to make mistakes. If you want more economy, you can say build 16 probes, 4 zealots and 5 stalkers as fast as possible. And if you want early defense, tell it 'I want 1 zealot at 2 mins 30, and then 16 probes, 4 zealots and 5 stalkers as fast as possible'. There's no way for me to give the algorithm a clear understanding of 'I want a good economy and early defense while getting 4 zealots and 5 stalkers', basically because 'good economy' and 'early defense' are very ambiguous and even highly debateable terms.
Incidentally, there is a 'Constant Probe Production' feature that will be available in the next version. The way this works is to take the approach that it should try and have a probe built for every 11s (slightly faster than a chrono probe build time), and it gets a 3s time penalty for every probe it's short of this. So basically, if it can get an extra probe by delaying the completion less than 3s, it'll take it.
|
On November 17 2010 21:33 CarbonTwelve wrote:
Incidentally, there is a 'Constant Probe Production' feature that will be available in the next version. The way this works is to take the approach that it should try and have a probe built for every 11s (slightly faster than a chrono probe build time), and it gets a 3s time penalty for every probe it's short of this. So basically, if it can get an extra probe by delaying the completion less than 3s, it'll take it.
Please allow an option to change this, if it doesn't mess anything up.
|
Fantastic application CarbonTwelve. Thanks for all the work and future work. I would be glad to donate some cash for your time on this.
|
On November 17 2010 17:13 CarbonTwelve wrote: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.
Protoss is perfect! :-)) Waiting for zerg :D That will win me over 
Thanks for all the good work!
|
You did an awesome job on this application. You released it free for everyone to use, without expecting a thing. I think it rocks.
Thanks a ton. I'm sure you've got a great career programming.
|
Quick question: What is a reasonable game count to stop at and safely assume you have near best optimization??
|
Started using it this morning, works beautifully. It is so much faster than the zerg java program.
One feature request: could you insert time stamps for when an item will finish, next to when it starts? This will help with getting a sense of what is finished and where things could be squeezed in.
Others have already mentioned adding a print out format for stuff like yabot or the build timing testers posted on TL, so I'll just second them.
Thanks for releasing this, and I'll post more feedback as I spend more time with it.
|
Oh yeah, I remember the big thing I wanted to ask:
Is it possible to write it so that you can insert a starting point for the build, and it will iterate from there? I'm not sure how your algorithm works, so this may not be feasible, but if possible it would be extremely useful and speed up the testing.
|
Keep up the good work, Carbon!
About Probes: I think there must be an option to include a scouting Probe/worker.
Something like "Send scout at [xxx] seconds" where the worker stops mining. Otherwise, the builds are still becoming somewhat unrealistic.
|
Hey Carbon, I was going to send a PM but I figured it would be interesting to see what everyone else thought of this. I'm a Master's student in cs right now, and one of my friends (TL lurker) and I were thinking about optimizing this for parallel systems that can take advantage of CUDA. We were just going to download the source and see what we could modify, but what did you think? Does anyone else on here want to be a part of this or have any ideas? Keep in mind we're doing this part for fun and part for a proof-of-concept for a parallel programming class to show how everyday programs can take advantage of modern GPGPUs. Originally we were looking at Lomilar's program, but C++ is so much more CUDA friendly than Java.
|
On November 17 2010 19:41 CarbonTwelve wrote: People doubt that I'll get to doing Terran with my app?
No not at all dude! Your ambition and generosity are solid, and if you say you'll go Terran than by god that's good enough for me. But more and different types of these build optimizers just opens up even more doors for collaboration and idea farming. Plus I play Terran so that's the one I'm interested in :D. I am, and I think we all are, super grateful for your efforts!!
If I was a programmer I'd be on top of this with you guys, but I've been doing everything 100% by myself on paper so far lol, so you can see I'm stoked to see a Terran version, particularly one that's in line with the logic I've settled on (if it is indeed more efficient, at least for Terran).
You definitely have my respect and gratitude! Like I said you guys are working on something huge so don't let people bring you down.
|
On November 18 2010 03:49 Antedelerium wrote:
Hey Carbon, I was going to send a PM but I figured it would be interesting to see what everyone else thought of this. I'm a Master's student in cs right now, and one of my friends (TL lurker) and I were thinking about optimizing this for parallel systems that can take advantage of CUDA. We were just going to download the source and see what we could modify, but what did you think? Does anyone else on here want to be a part of this or have any ideas? Keep in mind we're doing this part for fun and part for a proof-of-concept for a parallel programming class to show how everyday programs can take advantage of modern GPGPUs. Originally we were looking at Lomilar's program, but C++ is so much more CUDA friendly than Java.
That sounds awesome. I'm no CUDA expert, so how much faster do you think the program would execute? Massively parallel GA BO generation seems like a perfect fit for CUDA.
|
|
|
|
|
|
EPT
