Asymmetric Action Abstractions for Real-Time Strategy Games

Abstract

Action abstractions restrict the number of legal actions available for real-time plan- ning in zero-sum extensive-form games, thus allowing algorithms to focus their search on a set of promising actions. Optimal strategies derived from un-abstracted game trees are guaranteed to be no worse than optimal strategies derived from action-abstracted game trees. In practice, however, due to real-time constraints and the game tree size, one is only able to derive good strategies in un-abstracted trees in small-scale games. In this paper, we introduce an action abstraction scheme we call asymmetric abstraction. Asymmetric abstractions can retain the un-abstracted trees’ theoretical advantage over regularly abstracted trees while still allowing search algorithms to derive effective strategies, even in large-scale games. Further, asym- metric abstractions allow search algorithms to “pay more attention” in some aspects of the game by unevenly dividing the algorithm’s search effort amongst different as- pects of the game. In this paper we also introduce four algorithms that search in asymmetrically-abstracted game trees to evaluate the effectiveness of our abstrac- tion schemes. Two of those are greedy-search approaches and they are called Greedy Alpha-Beta Search and Stratified Alpha-Beta Search. The other two are versions of an algorithm we call Asymmetrically Action-Abstracted NaïveMCTS (A2N and A3N) and combine Monte Carlo Tree Search (MCTS) algorithms, naïve sampling strategy for select actions’ samples, and asymmetric abstraction scheme. In addi- tion to the search algorithms, we also introduce several strategies for generating asymmetric abstractions. An extensive set of experiments in a real-time strategy game developed for research purposes shows that search algorithms using asymmet- ric abstractions are able to outperform all other search algorithms tested.