New model for the individuals

[GoogleCodeExporter]

I think you should make a better model of each individual. As it is now, it 
seems like the search space is extremely big, which makes for slower 
optimization.

I propose the following model:

The model of each individual is an array of times in seconds for when to do a 
particular action such as build the spawning pool:

TimeInSecToBuildSpawningPool
TimeInSecToBuildExtractor1
TimeInSecToBuildExtractor2
TimeInSecToBuildRoachWarren
TimeInSecToBuildLair
TimeInSecToUpgMetabolicBoost
TimeInSecToBuildHatchery1
TimeInSecToBuildHatchery2
WP1_TimeInSecToSaveLarva
WP2_TimeInSecToSaveLarva
WP1_TimeInSecToBeginBuildingZerglings
WP2_TimeInSecToBeginBuildingZerglings
WP1_TimeInSecToBeginBuildingRoaches
WP2_TimeInSecToBeginBuildingRoaches

etc.

Each individual solution will build drones as long as it is not waiting to do a 
particular action or saving larva. It will stop saving larva when the right 
number of units have been produced for a particular waypoint. It will start 
producing units of a particular type non-stop when it reaches the time to do 
so. For example, if WP1_TimeInSecToSaveLarva=140 and 
WP1_TimeInSecToBeginBuildingZerglings=160 and you want 8 zerglings, then it 
start saving larva at 140 seconds and it will produce zerglings with all the 
larva it has starting at 160 seconds, until it has started 8 zerglings. If a 
build action is queued meanwhile, then it should take precedence before the 
production of units (I think). So if TimeInSecToBuildRoachWarren=165, it will 
start a single zergling before saving up for the roach warren.

There are some solutions that are unreachable with this model but perhaps the 
numeric search space will be easier to search. Furthermore, the a solution will 
never do unnecessary actions such as building two spawning pools.

I've not though the model all the way through so it may have some issues. 

Original issue reported on code.google.com by Kolibria...@gmail.com on 3 Nov 2010 at 4:21

[GoogleCodeExporter]

Original comment by Frit...@gmail.com on 3 Nov 2010 at 6:32

• Changed state: Discuss
• Added labels: Discuss, Type-Enhancement
• Removed labels: Type-Defect

[GoogleCodeExporter]

The main issue may be that the builds this would come up with would most likely 
suck^^

Original comment by azzur...@gmail.com on 3 Nov 2010 at 8:07

[GoogleCodeExporter]

Why? I've spent some time with Evolution Chamber and when it boils down to it, 
the build orders are more or less as follows:

The units that you are trying to build are built at the very last moment. 
Otherwise, it spends most of its time droning up. Here is an example of a build 
order, with the build drones removed, where it tries to get 2 zerglings ready 
for the 3 min mark and 18 drones and 5 roaches ready at the 5 min mark:

@0:45   S:10/10 ExtractorTrick
@0:47   Spawned:    Extractor Trick Finished, Drone Restored
@1:10   S:11/10 BuildSpawningPool
@1:24   S:10/10 BuildOverlord
@1:39   S:10/10 BuildExtractor
@2:26   S:14/18 BuildQueen
@2:32   S:16/18 BuildZergling
@2:51   S:17/18 BuildRoachWarren
@3:05   S:16/18 Metabolic Boost
@3:33   S:18/18 BuildOverlord
@3:45   S:18/18 BuildOverlord
@3:58   S:18/26 BuildRoach
@4:02   S:20/26 BuildRoach
@4:11   S:22/34 BuildRoach
@4:20   S:24/34 BuildRoach
@4:28   S:26/34 BuildRoach
@4:34   S:28/34 BuildDrone
@4:40   S:29/34 BuildDrone

@4:55   Evolved:    Metabolic Boost
@4:55   Spawned:    Roach+1

My proposed model will most likely more quickly realize this fact and begin 
creating the necessary roaches at the very last moment. Another expected 
benefit is that the search space is numeric, which in my experience is much 
easier to search with Evolutionary Algorithms and also increases the number of 
available selection, crossover and mutation strategies.

Original comment by Kolibria...@gmail.com on 3 Nov 2010 at 8:14

[GoogleCodeExporter]

Maybe I'm misunderstanding you, but:

"The units that you are trying to build are built at the very last moment. 
Otherwise, it spends most of its time droning up."

This is a fairly rash assumption, in my opinion.

I don't know many times you've run this to observe what I quoted, but I'm 
guessing it's less than billions?  If so, your sample size isn't significant 
enough to really assert anything.

The entire point of EAs is to NOT constrain the search space.  One of the most 
interesting things about these algorithms is that they often find solutions 
that are non-intuitive precisely because they don't assume things like you're 
assuming.  If you need proof of this, just consider the double overlord 
construction for the 7RR build.  That isn't intuitive to most of us; you rarely 
ever do that early in a game.  

Can you assert with 100% certainty that the optimal path to this build will 
ALWAYS build a Warren before a Lair?  Or upgrade Lair before Metabolic Boost?  
No, you can't.  I would have expected someone who seems passably comfortable 
with the nomenclature of these approaches to understand this, honestly.

Original comment by SCb...@gmail.com on 3 Nov 2010 at 9:56

[GoogleCodeExporter]

"The entire point of EAs is to NOT constrain the search space."

As a matter of fact, by analyzing the search space you can greatly improve the 
performance of evolutionary algorithms by using the knowledge of the search 
space to influence the efficacy of the run. I've some experience with 
evolutionary algorithms, and analyzing the search space to influence the design 
of the model is a text book example of how to improve your algorithm.

It is true, that I don't know for certainty that waiting to build at the latest 
moment is best. But I'm pretty sure it is true, I'll give you a complete 
argument if you want, but basically there is no point to build non-drone units 
later than earlier (there is a point in saving for minerals, gas and larva for 
building them, though). In any case, the model I propose does not prevent the 
the solutions from building the units earlier instead of later. But by making 
the value for when to start building the units numeric it does make it more 
likely that the EA will improve upon it quickly, I believe. But it would of 
course need to be tested.

"Can you assert with 100% certainty that the optimal path to this build will 
ALWAYS build a Warren before a Lair?"

The model I propose does not in any way prevent a solution from building lair 
before roach warren. What it does is that it basically takes the BuildDrone 
action out of the equation. And it ensures that the solutions never try to 
build two spawning pools. And it makes the search space numeric (N^d).

Original comment by Kolibria...@gmail.com on 3 Nov 2010 at 10:38

[GoogleCodeExporter]

I think some score modifications to reduce the score for a gross oversupply of 
food would be beneficial as well.  I've noticed a lot of my build orders are 
failing their time, with 2x the food supply needed. Right now it's hitting a 
74/182 limit.

I don't think that we should restrict its ability to create overloards, or more 
overloards than needed, but we should do something to provide a penalty for 
building an insane number of something that is not needed.

The same could be said for pools. 

Original comment by mikejoco...@gmail.com on 5 Nov 2010 at 12:57

[GoogleCodeExporter]

I agree with mike to some degree. I completely understand what scbiff is saying 
about how non-intuitive stuff should be ruled out, but there are some things 
that honestly SHOULD be ruled out. 

a surprising number of my build orders have spent at least 5 minutes with "7 
queens" or "6 hatches 2 spawning pools" before whittling away the excess 
buildings. In the cases of hatches I can understand, because that can 
potentially effect the build order. But 7 queens on 2 hatches? until you 
incorporate creep tumors, the number of queens shouldnt exceed 1 more than your 
number of hatches, and that only because queens only regen 23.5 or so mana 
during the 25 seconds creep injecting.

same thing goes for tech structures. Theres no way you can argue that building 
2 spawning pools would be useful, (though in the case of spire, evo chambers, 
infestation pit and roach warren, this could be allowed if their build requires 
multiple upgrades from that tech structure). In the case of pool and roach 
warren on an upgradeless waypoint, it should never attempt to build more than 
one. 

When I see a build like that STAY as the "optimal" build for quite some time 
when its running thousands of builds a second, it makes me wonder how many of 
these runs are wasting cpu time trying 3 pool 7 queen builds and the like. Just 
food for thought ^^

**disclaimer** I only have basic programming knowledge (JUST starting CSS, 
though I've been messing with computers and mincing code for a long time) and I 
only have a general grasp of genetic mutation algorithms, but im eager to learn 
more, so if anything I said seemed retarded PLEASE correct me with as much 
detail as possible :D

Original comment by EKlip...@gmail.com on 8 Nov 2010 at 11:30

[GoogleCodeExporter]

That second sentence should read "I completely understand what scbiff is saying 
about how non-intuitive stuff SHOULDN'T be ruled out, but there are some things 
that honestly SHOULD be ruled out."

Sorry about that >>

Original comment by EKlip...@gmail.com on 8 Nov 2010 at 11:32