EPTI based my algorithm on the game as much as possible. This means that I run a simulation of the game for each build order with a minimum time unit of 1 game second. This allows me to bound the searches I make for optimal build orders by declaring my goal units and a maximum time limit for them to be reached. Since I know how long a 6-pool should take to be optimal, I can set a limit below this by 1 second and let the algorithm compute all elements in the search tree as a benchmark for the worst case. Sadly this number becomes quite staggering as the algorithm goes on.
Before you hit the 18 second mark the only things that are really possible are drones, spawning pool, overlords, hatcheries, extractors, moving drones to scout... So there are not that many options but nevertheless quite a few. However, as soon as you add a spawning pool or any other tech units this number of options grows to 20, then 30, and finally 62. This means that at each leaf of the tree, a set of 62 new actions have to be checked for validity and whether they achieve the goal. Of course I am not doing blind brute force (that would be even more horrendous), instead I only allow a small set of options based on the currently available technology to the Zerg simulation. Still, a run of the algorithm over all possible moves up to game time 10 seconds takes 1000ms to calculate. Setting the limit to 16 game seconds takes over 26000ms, and going beyond 30 game seconds is too long to wait for.
In conclusion:
Don't use brute force for this problem unless you can narrow down your tech A LOT! By this I mean, if you want to get a build for X number of zerglings, make sure you only allow the algorithm to use direct paths of tech (drones, overlords, spawning pool, queen) and ditch anything that you know will not help (extractors, roach warren, etc...)
Hold on tight!
