Asymmetric Action Abstractions for Multi-Unit Control in Adversarial
  Real-Time Games
  Action abstractions restrict the number of legal actions available during
search in multi-unit real-time adversarial games, thus allowing algorithms to
focus their search on a set of promising actions. Optimal strategies derived
from un-abstracted spaces are guaranteed to be no worse than optimal strategies
derived from action-abstracted spaces. In practice, however, due to real-time
constraints and the state space size, one is only able to derive good
strategies in un-abstracted spaces in small-scale games. In this paper we
introduce search algorithms that use an action abstraction scheme we call
asymmetric abstraction. Asymmetric abstractions retain the un-abstracted
spaces' theoretical advantage over regularly abstracted spaces while still
allowing the search algorithms to derive effective strategies, even in
large-scale games. Empirical results on combat scenarios that arise in a
real-time strategy game show that our search algorithms are able to
substantially outperform state-of-the-art approaches.
