Yesterday, I read a very interesting article about RTS bot architecture, which led me to read another article by the same professors on the problem of Build Order Optimization. The problem, in simple words, is about finding the series of actions needed (a) to achieve a certain build (b) in the minimum time (t). The paper, however, doesn’t talk about the algorithms that form the goal build in the first place, which is going to be my next point of interest, I presume.
David Churchill and Michael Buro
In recent years, real-time strategy (RTS) games have gained interest in the AI research community for their multitude of challenging subproblems — such as collaborative pathfinding, effective resource allocation and unit targeting, to name a few. In this paper we consider the build order problem in RTS games in which we need to find concurrent action sequences that, constrained by unit dependencies and resource availability, create a certain number of units and structures in the shortest possible time span. We present abstractions and heuristics that speed up the search for approximative solutions considerably in the game of StarCraft, and show the efficacy of our method by comparing its real-time performance with that of professional StarCraft players.
When you are planning a series of actions to form a build in real-time, usually, you would have to spend idle time between actions to accumulate its needed requirements. This causes the search tree to explode with null actions that are nothing but wait, which in turn makes the search harder to optimize. To solve this problem, a very smart set of functions is introduced to implement “Fast Forwarding!”:
Sim(S, t): Given the current state (S), and the amount of time or frames (t), the function Sim simulates the world, which is mainly the simulation of the income of resources over time, and it returns the state (S`) which is the state achieved from waiting (t) after (S).
When(S, R): Returns the time (t) which all the required resources (R) is gathered at.
Do(S, a): Initiates the action (a) and returns the state where the action (a) has started executing.
Now, watch how we can combine these functions to achieve “Fast Forwarding”:
S` = Do(Sim(S, When(S, R = Requirements of a)), a)
Finally, I wanted to note that the paper is a bit too technical, and would require good effort to understand the algorithms. But, in the end, I was satisfied because not I only learned about the paper, but I also taught myself about types of search I wasn’t aware of such as Branch and Bound algorithms.
The paper can be accessed here: http://www.cs.mun.ca/~dchurchill/pdf/aiide11-bo.pdf