|
Heya fine folks of TL,
I have finished making the controller for the Genetic Algorithm (Basically all the easy work is done). Now I have to get down and dirty with the fitness function and also replicate the Starcraft 2 game in mini form to evaluate timings, minerals, gas, etc... Wish me luck! If someone is interested in the bare bone Genetic Algorithm coded in python 2.7 which currently does nothing but find the optimal "Drone Only" build order, let me know and I can email it to you or provide a link.
Any inspiring ideas about the fitness function would be welcome  It has dawned on me that this is definitely the hardest part of the algorithm  I may however start with the Starcraft 2 simulator which would let people also just plug in a build order by hand and see the fastest execution time for it.
|
I have finished making a basic version of the Starcraft 2 game simulator. The first thing I told it to try is to give me the build time for a 6 pool (naturally ). Here are the timings it spits out:
0:38 - Spawning Pool
0:53 - Drone
1:08 - Drone
1:10 - Drone Completes
1:25 - Drone Completes
1:43 - Spawning Pool Completes
1:43 - Zergling
1:43 - Zergling
1:43 - Zergling
2:07 - Zergling Completes
2:07 - Zergling Completes
2:07 - Zergling Compeltes
This is of course in game time and I have made no variance based on time to get to mineral patches, etc... If someone know how fast they can get 6 zerglings in a 6-pool, I would appreciate the data. If you beat the listed timings you will be added to a special thanks section of the final algorithm
EDIT: Bear in mind, this is not the genetic algorithm giving a perfect build order for 6 zerglings. Rather this is just the timing function that is telling me how fast this build order can be done.
|
Just completed a build order "cleaner". It basically takes an arbitrary build order (even if its an illegal one) and goes through it and checks to make sure basic requirements are fulfilled for each step. For instance, if Zerglings are to be made, it checks to see if there is already a spawning pool in the build order. Also, it checks to make sure enough pop is available given the overlords produced beforehand in the build order. If something illegal is found, it simply removes it from the list and increments a penalty counter. At the end it returns a cleansed build order that is legal and a penalty count that tells you how many incorrect units were removed from the original build order. This is mainly a preprocessing tool for my genetic algorithm to keep the input to the Starcraft 2 simulator legal (preventing an infinite loop).
|
Interesting stuff; I may be able to provide some input. I can probably take a look at the code, too, to see if any ideas spark for me and I can help you with the algorithm.
|
the objective function is to maximize the probability of winning, but this depends on what your opponent is doing, and that could be a number of things, depending on what you see. so I don't see how you can manage the problem.
the best you could do maybe is to maximize the size of your army at 20 minutes, subject to the constraints that you must have at least such and such units and upgrades at particular timepoints.
fun project, and good luck, but I'm not sure if this will be useful for players
|
Even though it may not be useful to players, it may still be useful in the context that you're able to see what times certain things can be done (though of course, I'm sure there will always be something more efficient).
This will probably be of no use to most people, but if you're just messing around with build orders and certain timing attacks, knowing that you can have X amount of Zerglings out in an X amount of time can help you in some ways.
|
So I have extended the code to now include Queens (with larva injection), as well as extractors (with drones moving to extractor) and Roaches and the Roach Warren. I have been able to replicate some results by users for a 7 Roach Rush:
+ Show Spoiler +7 Roach Rush
00:00 - Drone
00:13 - Drone
00:15 - Larva Spawn
00:17 - Drone Complete
00:24 - Drone
00:30 - Larva Spawn
00:30 - Drone Complete
00:33 - Drone
00:41 - Drone Complete
00:45 - Larva Spawn
00:50 - Drone Complete
00:50 - Overlord
01:00 - Larva Spawn
01:15 - Larva Spawn
01:15 - Overlord Complete
01:19 - Spawning Pool
01:27 - Drone
01:35 - Drone
01:42 - Larva Spawn
01:44 - Drone Complete
01:44 - Drone
01:51 - Drone
01:52 - Drone Complete
01:57 - Larva Spawn
01:57 - Drone
02:01 - Drone Complete
02:08 - Drone Complete
02:12 - Larva Spawn
02:12 - Drone
02:12 - Extractor
02:14 - Drone Complete
02:24 - Spawning Pool Complete
02:27 - Larva Spawn
02:27 - Drone
02:29 - Drone Complete
02:30 - Queen
02:42 - Larva Spawn
02:42 - Extractor Complete
02:42 - Drone
02:44 - Drone Complete
02:51 - Roach Warren
02:57 - Larva Spawn
02:58 - Drone
02:59 - Drone Complete
03:12 - Larva Spawn
03:12 - Overlord
03:15 - Drone Complete
03:20 - Queen Complete
03:27 - Larva Spawn
03:27 - Overlord
03:37 - Overlord Complete
03:42 - Larva Spawn
03:46 - Roach Warren Complete
03:46 - Roach
03:52 - Overlord Complete
03:57 - Larva Spawn
03:57 - Roach
04:00 - 4x Larva from Inject
04:00 - Roach
04:00 - Roach
04:03 - Roach
04:12 - Larva Spawn
04:12 - Roach
04:13 - Roach Complete
04:20 - Roach
04:24 - Roach Complete
04:27 - Larva Spawn
04:27 - Roach Complete
04:27 - Roach Complete
04:30 - Roach Complete
04:39 - Roach Complete
04:42 - Larva Spawn
04:45 - 4x Larva from Inject
04:47 - Roach Complete
Build finishes at 04:48 minutes.
Minerals at end: 255.0
Gas at end: 75.0
The algorithm has some built in timing issues with the transfer of workers between minerals to gas and from spawning to minerals. But I believe these are negligent and you should be able to almost replicate these times to the second. Playing on normal speed to try it out first might help with training it. This is a very aggressive build. If anyone has some other Zerg build orders they would like me to time and compare with your own play time, please feel free to post them (or pm me if you feel it might be embarrassing or secretive ).
|
What kind of performance are you seeing on the algorithm for something about as complex as a 7 roach rush? Does the fitness level converge relatively quickly?
|
|
|
|
|
|
EPT
