“ProBO Engine works by decoupling the search space into two regimes: economic decisions and military decisions. The military regime is solved using a global branch and bound technique with several significant restructurings of the search space, whereas the economic portion is solved using a heuristic-based local search assisted by a neural network trained on simulated data. These two regimes are iterated through repeatedly until convergence is achieved, and the iteration then restarts from a new initial condition.”
Further details here: http://www.proboengine.com/About.aspx
For those not familiar with RTS and build orders, a build order is a sequence of build commands that gets you to a game state. They are a means to and end to get to where you want in the game. The goal of a build order is to get you to a game state as fast as possible. At the highest levels of StarCraft, people abuse their opponent’s build order and try to attack when they are weakest (called a timed attack).
The search space for StarCraft is incredibly large, each game state has a range of [4, 35], which produces a very large search space very quickly. It is very exciting to see such an optimal search of such a large search space.