AI Magazine - Spring 2018

In this article, we will describe μRTS, emphasizing the research questions it raises, the rules of the competition, the bots submitted to the competition, and an analysis of the competition results.

μRTS
μRTS1 is a minimalist implementation of a two-play-
er RTS game designed specifically for AI research. Fig-
ure 1 shows a screenshot of μRTS. Players in μRTS
play in a rectangular grid-based map of arbitrary size
and control a set of units with the goal of destroying
all the units of the opponent. μRTS features a reduced
set of units compared to other RTS games such as
StarCraft, but this is configurable, so more unit types
can be added if desired. The basic unit types include
bases and barracks (shown as square units in the fig-
ure), which are buildings that cannot move but that
can produce other units; workers (shown as small cir-
cular units in the figure), which can gather resources
and create new buildings; and military units (shown
as larger circular units in the figure). Players need to
gather resources (green squares in the figure) and use
them to expand either their economy (build more
workers, bases, or barracks) or their military force.

From an AI point of view, μRTS raises some of the
same theoretical challenges raised by other, more
complex RTS games. μRTS has a huge decision space.
The branching factor of games like Chess or Go has
been estimated to be about 35 and 180, respectively.
By contrast, in μRTS, branching factors of over 1022
have been reported (Ontañón 2017) for 16 ; 16
maps. The branching factor in the game state shown
in figure 1, for example, is 1,008,288 for the max
player and 1,680,550 for the min player. μRTS also
has real-time constraints, meaning that the game is
designed to execute about 10 decision cycles per sec-
ond, leaving players with just a fraction of a second
to decide the next action. Moreover, players can issue
actions simultaneously, and actions are durative.

μRTS can be configured to be deterministic or non-deterministic. When it is configured to be nondeterministic, if two units issue contradicting actions simultaneously, one action is executed at random and the other is canceled. The damage that units deal each other when attacking is also stochastic.

μRTS can be configured to be fully or only partially observable. When it is configured to be partially observable, each unit has a predefined sight range, and a player can see only those parts of the map that her units can see. This is often referred to as the fog of war.

Finally, μRTS comes with a built-in forward model that can be used by the bots to simulate the effect of actions. This simplifies the development of search-based techniques (as explored, for example, by Churchill and Buro [2013]; Justesen et al. [2014]; Ontañón [2017]; Barriga, Stanescu, and Buro [2017b]; Lelis [2017]). However, while μRTS does not encourage learning forward models (as shown, for example, by Uriarte and Ontañón [2017]) for domains where they are not already available or developing techniques that do away with the need for forward models altogether, we would like to point out that these lines of work are important research directions both for RTS game AI and for game AI in general. This is the case because in most real-world situations where these algorithms might find application, it is likely that those forward models will not be available.

Previous research in μRTS has focused on areas such as Monte Carlo tree search (MCTS) (Ontañón 2013; Ontañón 2017, 2016; Shleyfman, Komenda, and Domshlak 2014; Komenda, Shleyfman, and Domshlak 2014); adversarial search algorithms that perform search at some level of abstraction, such as Puppet Search (Barriga, Stanescu, and Buro 2017b) or adversarial HTN planning (Erol, Hendler, and Nau 1994); and even deep learning for RTS games ( Stanescu et al. 2016).

In summary, we can see that μRTS has been used mainly to study the scalability problems that arise in RTS games. The goal of having several tracks in the μRTS competition was to also spur research into two of the other main problems in RTS games: nondeterminism and partial observability. We detail the tracks

Figure 1. A Screenshot of the μRTS Simulator.

Square units correspond to bases (light grey) that can produce workers, barracks (dark grey) that can produce military units, and resource mines (green) from which workers can extract resources to produce more units. Circular units correspond to workers (small, dark grey) and military units (large, yellow or light blue).