| Forum Index > SC2 General |
|
Strajder
60 Posts
On December 17 2010 00:45 falstag wrote: When are the toss and terran versions coming out, you claim they are now in the advance stages, any ETA? I am interested in this too. Is there at least any 'nightly/alpha build' available for Protoss and Terran? If not, when will it be available? | ||
|
trumansc
Australia4 Posts
 | ||
|
Nickkelbackk
United States15 Posts
| ||
|
osten
Sweden316 Posts
| ||
|
Zzoram
Canada7115 Posts
| ||
|
Reithan
United States360 Posts
| ||
|
kmh
Finland351 Posts
On April 15 2011 23:42 Reithan wrote: I'm not a professional programmer on this level, but I am an amateur one, and I program things for ecommerce and some web applications professional (not not, but I have). Why would using a genetic algorithm like this be better than something akin to a A-Star like pathfinding algorithm, treating each build option as a 'path' to a certain goal state? A* is not an algorithm suitable for these kinds of optimization problems, at all. The goal here is to find the build that satisfies the requirements in the shortest time possible, without any knowledge of what the landscape might look like. In path-finding, you know the entire graph describing your territory before you set off to find the shortest path. It is not even remotely the same thing. | ||
|
Bumblebees
United States328 Posts
On April 18 2011 18:50 kmh wrote: A* is not an algorithm suitable for these kinds of optimization problems, at all. The goal here is to find the build that satisfies the requirements in the shortest time possible, without any knowledge of what the landscape might look like. In path-finding, you know the entire graph describing your territory before you set off to find the shortest path. It is not even remotely the same thing. Except you DO know the entire path in build order optimizing. You are simply optimizing the path. A* is not unsuitable because it wouldn't work (in fact, it's been done months ago), but because there are much better methods. | ||
|
kmh
Finland351 Posts
| ||
|
Reithan
United States360 Posts
Genetic Algorithms seem like a fairly inelegant and brute-force approach to this problem. | ||
|
Bumblebees
United States328 Posts
On April 19 2011 02:47 Reithan wrote: Alright, then the continuation of that question would be, given that you CAN solve this as a pathing problem, if A* is not suitable because it's not efficient enough, what algorithms would be? Genetic Algorithms seem like a fairly inelegant and brute-force approach to this problem. This project wasn't about having the most elegant solution, although GA certainly has some benefits. How to best solve the problem depends on how you define the "problem". Build order optimizers can be optimizing a number of things. This is where the benefit of GA comes in. It allows a wider range of user input for 'what is optimal'. A* is just unnecessarily complicated. "solving" build orders is a fairly trivial task due to the many limitations of tech trees and economy. Think of it almost as a chess game where knights can ONLY move after pawns, rooks only after a knight moves, queen only after a rook moves etc... Then, the knight can only move after move 16, rooks after move 25, queens after 35 etc... The limitations and tiers make solving significantly easier. There isn't a wide open field in starcraft build orders. If you simply wanted to know the fastest way to get X, a simple DFS should be able to do any build in a matter of seconds on even a mediocre machine. Nothing more complicated is really needed. All you need to do is generate the absolute necessary building and worker count then traverse the tree to find shortcuts (very simply, cut or add workers). This was discussed and tested (i.e. programmed incompletely) in the EC chat on IRC many months ago. Someone had a program that did just zerglings (queens, drones and overlords) which could find the fastest route to X zerglings in less than a few milliseconds Honestly, build order optimizers are fairly useless when it comes down to actual gameplay. The motivation to pursue this stuff is really minimal even among those who you may consider interested in it. | ||
|
Reithan
United States360 Posts
On April 19 2011 03:05 Bumblebees wrote: If you simply wanted to know the fastest way to get X, a simple DFS should be able to do any build in a matter of seconds on even a mediocre machine. Nothing more complicated is really needed. All you need to do is generate the absolute necessary building and worker count then traverse the tree to find shortcuts (very simply, cut or add workers). This was discussed and tested (i.e. programmed incompletely) in the EC chat on IRC many months ago. Someone had a program that did just zerglings (queens, drones and overlords) which could find the fastest route to X zerglings in less than a few milliseconds Honestly, build order optimizers are fairly useless when it comes down to actual gameplay. The motivation to pursue this stuff is really minimal even among those who you may consider interested in it. Well, for me the motivation is 2 things: 1: I know given the organic nature of a game of starcraft any pre-programmed build order "solver" that works anythign past basic openings will be only marginally useful at best, and completely useless at worst, but the things it spits out, in terms of working THEORY and knowledge of optimal building is useful in itself, even if you can't DIRECTLY use it, imo. 2: I'm kind of a programming geek. (though out of practice) lol SO, then, the matter remains, could you create a simple DFS (not an algorithm I know...?) to solve for a given end state while satisfying interim states like EvoChamber can do? I assume that provided the answer would be 'yes' - then wouldn't it be more efficient? | ||
|
Reithan
United States360 Posts
Replay vs AI I entered at 6:30, 3 bases, 3 queens, 25 drones, 2 spines (had only one, but could have had 2), and 20 lings (had 15 but a few died), spawning pool, metabolic boost. With 8:30 as that, except 30 lings & 30 drones and 3 spines. Evo Chamber CANNOT figure this out....why?? | ||
|
Reithan
United States360 Posts
| ||
|
Bumblebees
United States328 Posts
| ||
|
Reithan
United States360 Posts
| ||
|
Duban
United States548 Posts
P.S. When I say "at best matched the timing of my own builds" I mean after I fix the obvious flaws in them, like the 6 overlord and 9 extractor trick. Also, they're much less practical. | ||
|
FrostedMiniWeet
United States636 Posts
On April 07 2011 09:28 trumansc wrote: I don't know if anyone else has brought this up but I've been messing around with this program, it's amazing by the way keep up the good work, however there is one slight problem where the program is unable to take into account the whole "feel" of economy and timing. I realise this is just one of the drawbacks of the genetic algorithm but I believe the simplest way to fix this would be to allow the input of some arbitrary waypoint independent of the program that could be a forced starting point. For example often the program makes a 10 overlord, I know for a fact that 9 overlord is the best economy opener as has been detailed on this forum before, also often the program makes both a 9 and 10 overlord because presumably there are spare minerals. If you could force the program to start with say a 9 overlord, 13 pool and then let it take over from there I think people could use the program with alot more finesse that may save time instead of brute forcing through another 1 million games. I do not know either the complications of the math or the programming but if this feature could be added I think the program would work a bit better, also a mineral gas and larva setting would be great. thank you 9 Overlord is only better than 10 overlord if you put down your pool or hatch after 13 or so. If you go 9 overlord and then do an early pool at or less than 12, then 10 overlord would have been better. I won't explain why this is at it is clear to anybody with basic understanding of mathematics. | ||
|
Aerodynamic27
Canada115 Posts
for example, any time it makes a build it sometimes starts to make 2 or 3 spawning pools or like lairs, which is very annoying. Can you put a code so it makes only 1 spawning pool, hydra den, ect, instead of ending up with 2 or 3 spawning pools at the end? not only would this speed up the process (as it doesnt need to test multiple buildings) the builds will make more sense | ||
|
trumansc
Australia4 Posts
On April 24 2011 11:34 FrostedMiniWeet wrote: 9 Overlord is only better than 10 overlord if you put down your pool or hatch after 13 or so. If you go 9 overlord and then do an early pool at or less than 12, then 10 overlord would have been better. I won't explain why this is at it is clear to anybody with basic understanding of mathematics. I don't understand how that would be clear to anyone with a basic understanding of mathematics, unless you assume a basic understanding of mathematics means an obsessive compulsion to use mathematical modelling to solve every problem you encounter. However you are right, 10 overlord, 9 overlord, overpool etc. all provide different benefits that can lead to an optimal build order depending on what you want to build, this is something that I did not know at the time and by looking through the forums/wiki more it is clear that no one knows the optimal standard zerg build order or if one exists. As far as I know a 9 followed by a 10 overlord is never optimal except for the most convoluted build orders. I was asking if it was possible to make a workaround that eliminates what is obviously unnecessary, evolution creates systems that meet requirements, design is the ability to purposefully direct a system to a desired outcome I don't see how combining the two could lead to anything worse than evolution alone. | ||
| ||
|
|
GSL
Epic.LAN
Big Brain Bouts
OSC
Replay Cast
Sparkling Tuna Cup
WardiTV Invitational
Epic.LAN
IPSL
eOnzErG vs McRibbed
LancerX vs StRyKeR
AI Arena Tournament
[ Show More ] |
|
|
EPT
