EPTZerg Build Order optimizer. - Page 8
| Forum Index > SC2 General |
|
Deleted_143
Australia256 Posts
| ||
|
Almania
145 Posts
| ||
|
Revilo
Germany23 Posts
On October 13 2010 18:04 Almania wrote: And never will be... That'd be the fitness test. ie maximize fitness where fitness is the negative of the time taken. How would you factor in the actual achievement of the required number of units/buildings? i.e. what score does a build get that only builds 6 roaches in 4:20 compared to one that builds 7 roaches in 4:40. I mean do we just toss out the builds that dont achieve our required number of roaches or can we perhaps put them in a pool for additional gene concatenation if their build order time is lower than the current build order timing of the best strategy that fulfills the requirement. This might actually make the algorithm more malleable and allow for various "close" ways of getting 7 roaches of being recorded. Like the top 5 BO's to get 7 roaches that are all within 10 game seconds of each other. This way one can really see whether there are some more pro econ or pro harass builds in there. Not to mention this would work well with the intermittent constraint problems people want to see. i.e. first i want to pump 2 fast roaches, then i want to transition into 5 hydras + 5 roaches, finally i want to get 2 infestors + 10 hydras + 10 roaches, etc... | ||
|
Almania
145 Posts
 .I do like the idea of having several build orders displayed.. for instance I'd take overpool over 10 pool if the difference is 1 second on the roaches, yet the BO finder can't (and shouldn't) make that decision for me. | ||
|
HFR-TV
France21 Posts
| ||
|
Noxie
United States2227 Posts
| ||
|
Shikyo
Finland33997 Posts
On October 13 2010 09:28 Lomilar wrote: Give me a desired build. Something like, the fastest way to some mutalisks, or something like that. There are indeed an extreme number of variables in that equation. I have programmed some tricks in there, such as waiting for a building to pop before doing anything more. I haven't done others, like building a second queen at your main while waiting for your expo. My claim is, you give me a desired destination (10 lings, 5 roaches, 7 mutalisks), and within an hour or two, or maybe less, I will give you a build like the above, telling you how to do it very quickly. What's the fastest way to get 8 mutalisks while having sufficient defense against hellion harrass, cloaked banshees, and afterwards the fastest way to get enough roaches to defend against the thor-hellion push at 14 minutes? If it's in a vacuum, this is, in fact, entirely useless for everything other than sophisticated rushes. | ||
|
Ropid
Germany3557 Posts
On October 13 2010 19:14 Shikyo wrote: What's the fastest way to get 8 mutalisks while having sufficient defense against hellion harrass, cloaked banshees, and afterwards the fastest way to get enough roaches to defend against the thor-hellion push at 14 minutes? If it's in a vacuum, this is, in fact, entirely useless for everything other than sophisticated rushes. From the explanations in this thread, the program uses as input a starting state and an end state. You could run it two times, first for your desired defenses: zerglings with speed or roaches, or whatever you deem as sufficient defense. After that, you can use that situation as the start state for a second run, with the 8 mutalisks situation as the new end state. | ||
|
Revilo
Germany23 Posts
On October 13 2010 18:33 Almania wrote: I can't speak for what Lomilar has done, but yes you could just attach a high negative value (ie 2 minutes) to those genomes that don't meet the criteria rather then just culling them directly. You'd have to experiment to find what convergences fastest.. same as every thing else. Would love for this to be open sourced (nudge nudge .I do like the idea of having several build orders displayed.. for instance I'd take overpool over 10 pool if the difference is 1 second on the roaches, yet the BO finder can't (and shouldn't) make that decision for me. So I just had lunch with a buddy of mine (he is working towards his PhD in Computer Science soon) and he thought about the idea and said it would work quite well. In fact, you dont have to worry about a lot of details when you use Genetic Algorithms since the algorithm should do the work and not you. So any human post-processing should be kept minimal (for example, looking through multiple almost equal builds). However I think it should be not too hard to put constraints up that will get you what you want. Instead, i think it would be awesome to just give particular starting points for the algorithm. Like, what is the fastest route to 5 roaches given that i did a 10 overlord instead of 9 overlord. I myself am finishing my Masters in Bioinformatics. I have been exposed to these optimization algorithms but i have never made a big project out of them. So I think it would be great to start implementing it and then giving it to the world as open source software. I plan on starting the project tonight, I will be implementing it in python since its the language i am most comfortable with and it has some useful stuff to make it easier to program. It most probably will run slower than the C or Java implementations, but I am certain it will be fast enough and just as good. Since in the end it really only matters about tweaking the parameters to help the algorithm find solutions faster. I will post with updates as soon as I get this off the ground. Probably I will open a blog and encourage people to help answer some questions which will no doubt come up during development. If all goes well, I will make a simple GUI and installer for all OS's, since python is platform independent (if you program correctly  ). PM me if you have any interesting considerations or ideas about it, but also post here in case others are also going to attempt this stuff. I am open to suggestions | ||
|
jdobrev
Bulgaria162 Posts
A nice tool to have but nothing more. if you want to see how fast you can get 2 colossi you just go, test some BOs and compare the times. then have a friend do throw all kind of shit at you until you find the fastest build where you actually survive. | ||
|
Eluadyl
Turkey364 Posts
Therefore, I think you should optimize it as best as you can so people can customize their own input, including extractor tricks and shit, then release it opensource (better free software) so others can work on it too. :D TL;DR: release it opensource. | ||
|
hns
Germany609 Posts
On October 13 2010 12:36 kevmo wrote: + Show Spoiler + On October 13 2010 12:09 BladeRunner wrote: I have a friend who's a genius at CS, worked on the AI they put in robots sent to the moon, and I've had many interesting conversations with him about Machine Learning (a topic he is quite interested in). I, being a meer CS bachelor's degree holder was of course familiar with genetic algorithms, but I learned by talking to him that they're widely considered suboptimal to experts in the field.. They tend to get stuck on local maxima/minima. According to him (and unfortunately I can't really back this up as I'm not an expert), support vector regression is better in almost every case. From my experience, genetic algorithms are cool for finding unsuspected solutions to a problem, and many various solutions... not exactly the best way to find the BEST solution reliably. I think you could take advantage of this with your tool is to look at a longer target and the result would be a handful of optimal solutions that the player could choose between in the early-game based on scouting, etc. Support vector machines are used for classification problems (given an input and a set of data, produce a function which most reliably predicts that data). Genetic algorithms are used for search problems (given a solution space, find the "best" solution for some definition of best). That said, genetic algorithms usually are not the best solution for a given search problem. The advantage lies in the ease of implementation, as well as general applicability. Essentially, I consider genetic algorithm the go to algorithm when you don't really know a better way to solve a search problem. Often in complicated problems (such as build order optimization) genetic algorithms are a good way to get something working. I obviously don't know the details of the OP's implementation, but there are possibly optimizations to be done even with genetic algorithms. For instance, you can prune solutions early that don't meet certain easily calculable metrics. The easiest are required buildings/units for a given set of goals. In the 7 roach example, you know that you will need at the LEAST a spawning pool, roach warren, extractor, 1 overlord (because 6 drones - 3 for buildings + 14 supply of roaches = 17 supply), and 7 roaches in the build. Any build that does not contain these items simply is not valid, and does not need to be considered as a solution. Furthermore, you can probably speed up evaluation with some simple formulas based on required minerals. For example, you know you need a certain amount of minerals and gas to get all the required buildings and units, and there are easy heuristics for computing payoff time for building workers. Using these numbers, it should be easy to prune off say, a 6 pool as being clearly inferior to a 7 pool, etc. In terms of implementation, the latter optimization can be thought of as keeping track of the best builds you have seen so far, and immediately rejecting anything that is slower by a certain margin using simple heuristics (e.g. I have seen 7 roaches in 5:00 so starting my spawning pool at 4:30 is clearly not going to be any better). This would involve finding any critical paths and resource requirements for a given goal, but that can be precomputed once and then used over and over again as you evaluate solutions. I have to agree here. I don't know if your post was motivated by the famous branch&bound-algorithms (wiki), but you give essentially the idea of those here. This would definately give one hell of a speedup, although I have no clue if this is useful/implementable in the context of genetic algorithms. @Lomilar: Does your algorithm keep track of certain "keypoints" during the build or do you have only the fitness value (that is, overall build time I guess) to compare with? Even in the latter case you could, as kevmo suggested, just add something like "if [current-build-time] + [build-time-of-missing-stuff] > [best-known-build-time] => stop". That means you'd have to know what's missing and take building multiple stuff at the same time into account etc, but I guess it'd already help speed up the whole thing a lot. Don't know if it's too much work for too little benefit, though. Very interesting topic, and obviously very nice programming! | ||
|
Invictus
Singapore2697 Posts
Although it still is impressive as it gives people a general idea on how builds are optimised and would allow for some rough calculation of timing rushes(that is, if one was made for terran and protoss) since timing rushes usually consists of an early +1 or a set number of high tier units(thor hellion push, colossus push) | ||
|
theSAiNT
United States726 Posts
| ||
|
Shikyo
Finland33997 Posts
| ||
|
SwampZero
Greece350 Posts
| ||
|
archy
Norway22 Posts
Would be very interested to see this released. It would be a great consultant program like Rawr is for WoW players. | ||
|
Glacius0
Netherlands66 Posts
I'm thinking of taking my drones off gas after reaching 7x25=175 gas and getting an expo. | ||
|
dejavue
Germany47 Posts
Just my two cents, I myself have no idea about programming of any sort, would however LOVE to see this program released... | ||
|
Risen
United States7927 Posts
On October 13 2010 21:45 archy wrote: Is there something wrong with the mineral counter? I noticed it lists alot of wierd mineral values. In the example you have for example 51, 52, 53 or 106 minerals, and minerals are collected 5 at a time.. Would be very interested to see this released. It would be a great consultant program like Rawr is for WoW players. Minerals ARE collected 5 at a time... | ||
| ||
