|
On October 15 2010 07:00 Cyber_Cheese wrote:
theres a full 25 seconds in the 7rr build where the pool is done where the roachwarren hasnt started, so its probably better to be doing ~12/13 pool
infact where the spawning pool starts there is after the overlord pops, and the 13th drone is 24s after the pool starts
it might be just as fast to overpool but the 13 pool can do the 7rr with more economy
earlier pool = earlier queen
not just a earlier roach warren.
|
On October 15 2010 07:00 Cyber_Cheese wrote:
theres a full 25 seconds in the 7rr build where the pool is done where the roachwarren hasnt started, so its probably better to be doing ~12/13 pool
no, the pool is needed for queen ASAP, and the later warren is so drone economy is good. Building the roach warren at 18 supply has nice timing benefits, since overlord goes right after.
Overall the only improvement I've made on this build (although I haven't tried hard) is doing a gas trick to 11 supply before building the overlord and pool. I don't know if it's a real improvement, but it seemed good for me. 12pool before ovie wasn't as successful, because it really seemed to slow many things down.
On October 14 2010 19:07 666pool wrote:Anyway I did this in a VS computer Very Hard Terran and uploaded a replay for you guys. I rallied the first 7 roaches to their front and attacked, wiping out their marine army with ease. My apologies it's not an actual ladder game. http://replayfu.com/r/jbgnqp I didn't watch the replay, but I know of a few common builds the very hard computer does:
- marines (into marine-tank, or marine-tank-marauder I think)
- and marine-marauder (into marine-marauder-medivac)
- also when I was preparing for a tournament I saw mass reapers from the computer which I thought was really strange and new. It must have been because I was building stuff extremely slowly since I was tweaking controls, because comp never does that vs my normal BOs.
You should try the build vs the marine-marauder build. As far as I know (I tried it myself) it gets killed. I played on blistering sands, so steppes of war it would be better, but steppes is an exceptional map compared to all others (jungle basin is a bit short too I guess, but not as much I think)
|
On October 14 2010 12:22 Lomilar wrote:
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.
Using your analogy, imagine if there were multiple targets that are all "good" but only one is the best.. GA's have another downfall that when they shoot they may hit and subsequently hone in on a target that is good, but not the best. (local maxima/minima).
Have you noticed any possibility that your build order optimizer could be running into this issue?
On the flip side, it may actually be a benefit - if you design it to hone in on all targets, even if you have several local maxima/minima, if they are all somewhere close to the target, it would mean you could say "It's produced X builds that produce Y within Z minutes, plus or minutes 15 seconds" or something similar. That way it gives some flexibility, adapatibility based on scouting, etc..
|
On October 15 2010 07:07 metaldragon wrote:Show nested quote +On October 15 2010 07:00 Cyber_Cheese wrote:
theres a full 25 seconds in the 7rr build where the pool is done where the roachwarren hasnt started, so its probably better to be doing ~12/13 pool
infact where the spawning pool starts there is after the overlord pops, and the 13th drone is 24s after the pool starts
it might be just as fast to overpool but the 13 pool can do the 7rr with more economy earlier pool = earlier queen not just a earlier roach warren.
i stand corrected
could the program be directed to run via a 13 pool into 7 roaches and see how much slower i am?
|
Wow. Crazy to see that this is still going.
I did some work on a UI last night, but ran out of time. Today was spent mostly out of town, so it will be tomorrow night before I can do some more work on it. There's also about 20 PMs to reply to, so I will get to those tomorrow as well.
Thanks guys for the great support, I'll get you something as soon as I can!
As for answers: Cyber_cheese, as it stands, not yet. I hope to put in waypoints, like, have X by Y time, and more into the engine. Right now I am getting a UI slapped onto it though, so that people can start playing with it.
You CAN do it a little bit slower with far better economy, but that's not the goal I gave it. I wouldn't have cared if I had 6 drones and 7 roaches. Luckily, when the app comes out, you can specify you want some semblance of economy and fast roaches, and see what it gives you.
Seeing this being used on the ladder both makes me happy and sad, as I know how annoying it is to hold off this opening.
puzzl: My background is in AI, not search. Plus, I wanted an organic approach so I could utilize my epic amount of computing power instead of having to write endless pruning rules that may or may not lead to assumptions. For instance, going for a 50 zergling rush, without speed, it is best to open 6 pool, not for the zerglings, but for the fast queen, then drone, expo, queen, and then blast out lings. You don't even need that many drones to maintain full ling production on two queen'd hatches.
Kinda wicked. But some econ based rules could have seriously hampered that discovery, if I were naive and greedy enough to implement them.
I'm kinda interested to see where the 8 seconds is lost. I could see 2 for doing the initial drone mine/split, and 1-2 for moving drones/inefficient mining, and maybe 1-2 for moving the drone to build buildings... Maybe compare the build order spitout of a replay to the 'optimal', and see where the time is lost? Lag might account for the other couple seconds, or maybe other animations.
|
On October 15 2010 15:54 Lomilar wrote:
Wow. Crazy to see that this is still going.
I did some work on a UI last night, but ran out of time. Today was spent mostly out of town, so it will be tomorrow night before I can do some more work on it. There's also about 20 PMs to reply to, so I will get to those tomorrow as well.
Thanks guys for the great support, I'll get you something as soon as I can!
As for answers: Cyber_cheese, as it stands, not yet. I hope to put in waypoints, like, have X by Y time, and more into the engine. Right now I am getting a UI slapped onto it though, so that people can start playing with it.
You CAN do it a little bit slower with far better economy, but that's not the goal I gave it. I wouldn't have cared if I had 6 drones and 7 roaches. Luckily, when the app comes out, you can specify you want some semblance of economy and fast roaches, and see what it gives you.
Seeing this being used on the ladder both makes me happy and sad, as I know how annoying it is to hold off this opening.
puzzl: My background is in AI, not search. Plus, I wanted an organic approach so I could utilize my epic amount of computing power instead of having to write endless pruning rules that may or may not lead to assumptions. For instance, going for a 50 zergling rush, without speed, it is best to open 6 pool, not for the zerglings, but for the fast queen, then drone, expo, queen, and then blast out lings. You don't even need that many drones to maintain full ling production on two queen'd hatches.
Kinda wicked. But some econ based rules could have seriously hampered that discovery, if I were naive and greedy enough to implement them.
I'm kinda interested to see where the 8 seconds is lost. I could see 2 for doing the initial drone mine/split, and 1-2 for moving drones/inefficient mining, and maybe 1-2 for moving the drone to build buildings... Maybe compare the build order spitout of a replay to the 'optimal', and see where the time is lost? Lag might account for the other couple seconds, or maybe other animations.
I can't wait to try out your program. Any plans on making a protoss and terran version?
|
On October 15 2010 16:45 Dionyseus wrote:Show nested quote +On October 15 2010 15:54 Lomilar wrote:
Wow. Crazy to see that this is still going.
I did some work on a UI last night, but ran out of time. Today was spent mostly out of town, so it will be tomorrow night before I can do some more work on it. There's also about 20 PMs to reply to, so I will get to those tomorrow as well.
Thanks guys for the great support, I'll get you something as soon as I can!
As for answers: Cyber_cheese, as it stands, not yet. I hope to put in waypoints, like, have X by Y time, and more into the engine. Right now I am getting a UI slapped onto it though, so that people can start playing with it.
You CAN do it a little bit slower with far better economy, but that's not the goal I gave it. I wouldn't have cared if I had 6 drones and 7 roaches. Luckily, when the app comes out, you can specify you want some semblance of economy and fast roaches, and see what it gives you.
Seeing this being used on the ladder both makes me happy and sad, as I know how annoying it is to hold off this opening.
puzzl: My background is in AI, not search. Plus, I wanted an organic approach so I could utilize my epic amount of computing power instead of having to write endless pruning rules that may or may not lead to assumptions. For instance, going for a 50 zergling rush, without speed, it is best to open 6 pool, not for the zerglings, but for the fast queen, then drone, expo, queen, and then blast out lings. You don't even need that many drones to maintain full ling production on two queen'd hatches.
Kinda wicked. But some econ based rules could have seriously hampered that discovery, if I were naive and greedy enough to implement them.
I'm kinda interested to see where the 8 seconds is lost. I could see 2 for doing the initial drone mine/split, and 1-2 for moving drones/inefficient mining, and maybe 1-2 for moving the drone to build buildings... Maybe compare the build order spitout of a replay to the 'optimal', and see where the time is lost? Lag might account for the other couple seconds, or maybe other animations.
I can't wait to try out your program. Any plans on making a protoss and terran version?
This!
Although I am currently a Zerg player, I want to switch to random and this would really help, as I have real trouble with Terran and Protoss build orders (yeah I know, I suck, just a gold player).
Also: add the possibility for us to donate something via paypal to you for your effort. I am guessing you could get a nice bit o' cash if you implemented this ;-)
|
Fyi this 7 roach rush posted earlier here just got amazingly fucking stronger.
4 range 7 roaches can you say nice choke mr. protoss ima be bustin it
|
wrote something similar to optimize BOs quickly, however currently i have to provide the BO myself. Plan on implementing a minmax algorithm to create perfect build orders with a given timing and army target. However some things are idealized e.g. the time a drone requires to move to expo is not counted
Example:
Buildorder (3-hatch-late gas [12 pool seems to be better at 5:00 because of early queen if played perfectly]):
BasicBO.BO( new Object[][] {
{ 10, 9, "BuildOvie" },
{ 18, 12, "BuildPool" },
{ 18, 14, "BuildQueen" },
{ 18, 16, "BuildHatch" },
{ 18, 16, "BuildExtractor" },
{ 18, 16, "BuildOvie" },
{ 18, 18, "DroneToGas" },
{ 18, 18, "DroneToGas" },
{ 18, 18, "DroneToGas" },
{ 26, 22, "BuildOvie" },
{ 34, 25, "BuildHatch" },
{ 36, 28, "BuildOvie" },
}
output:
Min:00:00 Player{supply=10, units=6, mins=54.32, gas=0.0, gameobjects=[Hatchery{larva=3, timer=15, state=1, drones=6}] actions:[BuildDrone]}
execute BuildDrone
Min:00:11 Player{supply=10, units=7, mins=51.84, gas=0.0, gameobjects=[Hatchery{larva=2, timer=4, state=1, drones=6}, Egg{action=BuildDrone}] actions:[BuildDrone]}
execute BuildDrone
00:17 ** finished ** sc2calc.Egg
Min:00:22 Player{supply=10, units=8, mins=52.24, gas=0.0, gameobjects=[Hatchery{larva=2, timer=8, state=1, drones=7}, Egg{action=BuildDrone}] actions:[BuildDrone]}
execute BuildDrone
00:29 ** finished ** sc2calc.Egg
00:40 ** finished ** sc2calc.Egg
Min:00:40 Player{supply=10, units=9, mins=100.16000000000003, gas=0.0, gameobjects=[Hatchery{larva=2, timer=5, state=1, drones=8}, Egg{action=BuildDrone}] actions:[BuildExtractor, BuildDrone, BuildOvie]}
execute BuildOvie
[..snip ..]
Min:05:06 Player{supply=36, units=32, mins=51.25520000000001, gas=228.89999999999958, gameobjects=[Hatchery{larva=2, timer=12, state=1, drones=19}, Pool, Queen{energy=6.25}, Hatchery{larva=1, timer=1, state=1, drones=4}, Extractor{drones=3, maxDrones=3}, Hatchery{larva=1, timer=15, state=1, drones=0}, Egg{action=BuildOvie}, Egg{action=BuildDrone}, Egg{action=BuildDrone}, Egg{action=BuildDrone}, Egg{action=BuildDrone}] actions:[BuildExtractor, BuildDrone, DroneFromGas]}
execute BuildDrone
Player{supply=36, units=33, mins=49.8984, gas=235.19999999999956, gameobjects=[Hatchery{larva=1, timer=9, state=1, drones=19}, Pool, Queen{energy=7.9375}, Hatchery{larva=2, timer=13, state=1, drones=4}, Extractor{drones=3, maxDrones=3}, Hatchery{larva=1, timer=15, state=1, drones=0}, Egg{action=BuildOvie}, Egg{action=BuildDrone}, Egg{action=BuildDrone}, Egg{action=BuildDrone}, Egg{action=BuildDrone}, Egg{action=BuildDrone}] actions:[BuildExtractor, DroneFromGas]}
edit: BTW this program computes that 9 ovie is best for 13,14 pool, and double extractor trick is best for 12 pool. However the difference is minimal (<10 minerals).
edit 1: actually queen 16 is better in the BO above ..
edit 2: a roach eco build:
BasicBO.BO( new Object[][] {
{ 10, 9, "BuildOvie" },
{ 18, 12, "BuildPool" },
{ 18, 16, "BuildQueen" },
{ 18, 18, "BuildHatch" },
{ 18, 18, "BuildExtractor" },
{ 18, 18, "BuildOvie" },
{ 18, 18, "DroneToGas" },
{ 18, 18, "DroneToGas" },
{ 18, 18, "DroneToGas" },
{ 26, 18, "BuildRoachWarren" },
{ 26, 22, "BuildOvie" },
{ 36, 30, "BuildOvie" },
}
results in
05:19 ** finished ** sc2calc.Egg
Player{
supply=44,
units=38,
mins=272.12000000000035,
gas=243.59999999999954,
gameobjects=[
Hatchery{larva=0, timer=4, state=1, drones=20},
Pool,
Queen{energy=13.5625},
Hatchery{larva=0, timer=11, state=1, drones=10},
Extractor{drones=3, maxDrones=3},
RoachWarren,
Egg{action=BuildDrone},
Egg{action=BuildDrone},
Egg{action=BuildDrone}]
}
however if a human plays this timings are worse ..
|
This is really cool. i would love to know how it works.
|
On October 15 2010 21:46 daywiss wrote:
This is really cool. i would love to know how it works.
If i know my genetic algorithms properly, it goes sorta like this:
First it creates random openings.
Then it ranks them according to their performance against a set objective. In this case objective is have 7 roaches earliest possible.
The best scorers are kept, and part of them is combined with other successful scorers to create more openings. Then it ranks them again.
It keeps doing this for hours, then it keeps the best ranker.
|
On October 15 2010 22:02 SwampZero wrote:Show nested quote +On October 15 2010 21:46 daywiss wrote:
This is really cool. i would love to know how it works. If i know my genetic algorithms properly, it goes sorta like this: First it creates random openings. Then it ranks them according to their performance against a set objective. In this case objective is have 7 roaches earliest possible. The best scorers are kept, and part of them is combined with other successful scorers to create more openings. Then it ranks them again. It keeps doing this for hours, then it keeps the best ranker.
I would guess he'd be going for a deterministic approach since it takes so long. Basically brute force it rather than feeding it with certificates.
|
On October 15 2010 22:18 Rosvall wrote:Show nested quote +On October 15 2010 22:02 SwampZero wrote:On October 15 2010 21:46 daywiss wrote:
This is really cool. i would love to know how it works. If i know my genetic algorithms properly, it goes sorta like this: First it creates random openings. Then it ranks them according to their performance against a set objective. In this case objective is have 7 roaches earliest possible. The best scorers are kept, and part of them is combined with other successful scorers to create more openings. Then it ranks them again. It keeps doing this for hours, then it keeps the best ranker. I would guess he'd be going for a deterministic approach since it takes so long. Basically brute force it rather than feeding it with certificates.
A deterministic approach is possible, i am computing for each second in the game the list of possible actions (e.g. buildqueen, build spine, build roach, send drone to gas ..). In chess you have like 20 .. 40 different moves at a point in the game, so the number of different openings is huge, in sc2 the number of possible moves is much lower, additionally it is easy to cut nonsense (e.g. build 5 ovies in the beginning ..). Therefore a minmax algorithm is applicable and likely to run faster than a genetic algorithm .. however it strongly depends on the efficiency of the code performing the SC2 simulation computation. I think computing times with min max algorithm and some tweaks will run < hour, given that you compute the first 6 minutes only and cut non-sense BO's from the set of computed variants. Its somewhat similar to genetic algorithm, however it simply runs every meaningful variant.
|
Wow, this is actually very similar to the roach rush I had developed. That's awesome.
You should put in some variant build orders like 'with an expansion' (although I suppose you could just build it once you have the roaches), 'with Roach Speed', 'with spinecrawler', or 'with a Nydus Worm/Nydus Exit'. Then you could see just how much these things delay a build.
|
Is it possible to have a secondary filter to clean up that code to make it easier to read?
|
On October 15 2010 23:21 DoubleReed wrote:
Wow, this is actually very similar to the roach rush I had developed. That's awesome.
You should put in some variant build orders like 'with an expansion' (although I suppose you could just build it once you have the roaches), 'with Roach Speed', 'with spinecrawler', or 'with a Nydus Worm/Nydus Exit'. Then you could see just how much these things delay a build.
Its still in early development stage, however one can specify arbitrary build orders and let them run.
I am currently implenting "army-building". Upgrades are still not implemented.
The end goal is to let the program read builds from replays and compute optimal counterbuilds regarding army, timing and eco :-D.
I already played around a bit. It is sometimes really astonishing to see the economy cost e.g. of fast speedlings (early gas). Another interesting finding was that a 14 pool is not that much better than a 12 pool, even worse because of late queen.
However i am not 100% sure if the results are complete realistic .. still will have to tweak some numbers. I played some of the builds and they worked like computed (but 10-15 seconds later because of some additional delays such as a drone walking to the extractor and human sloppyness in executing the build).
|
On October 16 2010 01:42 mlbrandow wrote:
Is it possible to have a secondary filter to clean up that code to make it easier to read?
Ofc, it is just early development phase ..
|
|
|
|
|
This tool would probably be handy for alot of lower level players but I don't understand the concern about ruining the game, it's not like it can factor in how many zerglings you need to build to defend when you see reactor hellion vs gasless 5 rax marine all in. I think it's pretty cool for refining specific timing attacks but im not sure if its very useful past the early game since you're not trying to have some preset amount of something, but rather respond to your opponent and stay ahead of him.
|
|
|
|
|
|
EPT
