Day 3: A word on Brute Force

Revilo

Germany23 Posts

October 23 2010 14:52 GMT

I had a number of people suggest brute force as a viable option in solving these short build order problems. I was skeptical, since the number of possible moves in a build order quickly explode in complexity. However, I was not content just thinking about it and so I tried it out for myself. The results are not too surprising...

I 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...)

Weasel-

Canada1556 Posts

October 23 2010 15:50 GMT

You don't have to check for something every second, I think it would be easier for your algorithm to simply order all of the things it can currently make and just make those things in some specific order whenever it has the cash to afford them.

gods_basement

United States305 Posts

October 23 2010 17:38 GMT

On October 24 2010 00:50 Weasel- wrote:
You don't have to check for something every second, I think it would be easier for your algorithm to simply order all of the things it can currently make and just make those things in some specific order whenever it has the cash to afford them.

you're right. you should make your brute force build order optimizer to use build orders. i cant believe anyone didnt try this previously

Revilo

Germany23 Posts

October 23 2010 21:13 GMT

The whole idea behind this is to set some target composition of units, say... 6 zerglings, and have the algorithm spit out the shortest way to get to that (in other words, a build order that is as fast as possible to get to 6 zerglings). And I do only do a set number of possible moves at the end of each build order. However, my simulator that checks how long each of those build orders takes in game time has to evaluate on some scale. That scale is the game second. Thats why the algorithm only starts getting slow beyond 18 game seconds (since it takes 17 game seconds to spawn a drone). The first move can only be one of maybe 6 or 7 moves. So here the search space is relatively small. Now once you reach the end of simulation for those 6 or 7 moves, each can now append another 6 or 7 (or more if tech has been unlocked) moves. This makes 36 to 49 buildorders to evaluate. A lot of these are illegal ones, and these I already filter out. However, once you hit the next level down you are already at 200 to 350 build orders. And that, although I have only 3 things building in the build orders.

As I stated before, you can make the algorithm more intelligent to speed things up by removing possible moves based on logic. However, you run the risk of excluding a possibility for a better solution in doing so and it no longer is "truly" brute force. This was only an experiment, but it has shown the core stats of the problem at hand. I will be revisiting Genetic Algorithms with more determination, since it seems the search space truly is IMMENSE!

I hope to release some code soon too

Hold on tight!

Please or register to reply.

Day 3: A word on Brute Force

Completed

Ongoing

Upcoming