Understanding Depth-First Branch and Bound implementation to StarCraft 2

Starting Status S is the initial state at the start of the game. I believe you have 100 minearls and Command center and 12? SCVs, so that’s your start.

The Goal here is the list of building you want to have. The satisfies condition is are all building in goal also in S.

The time limit is the amount of time you are willing to spend to get the result. If yous set it to 5 seconds it will probably give you a sub-optimal solution, but it will do it in 5 seconds. If the algorithm finishes the search it will return earlier. If you don’t care leave it out, but make sure you write solutions to a file in case something happens.

Bound b is the in-game time limit for building everything. You initially set it to infinite or some obvious value (like 10 minutes?). When you find a solution the b gets updated so every new solution you find MUST be faster (in-game) than the previous one.

A few notes. Make sure that the possible action (children in step 9) includes doing nothing (wait for more resources) and building an SCV.

Another thing that might be missing is a correct modelling of SCV movement speed. The units need to move to a place to build something and it also takes time for them to get back to mining.

CLICK HERE to find out more related problems solutions.

Leave a Comment

Your email address will not be published.

Scroll to Top