Asymmetric Action Abstractions for Planning in Real-Time Strategy Games

• Published in: The Journal of artificial intelligence research 2022-01, Vol.75, p.1103-1137
• Main Authors: Moraes, Rubens O., Nascimento, Mario A., Lelis, Levi H.S.
• Format: Article
• Language: English
• Subjects: Algorithms; Artificial intelligence; Asymmetry; Game theory; Games; Litigation; Real time; Search algorithms; Strategy
• ISSN: 1076-9757; 1076-9757; 1943-5037
• DOI: 10.1613/jair.1.13769

Action abstractions restrict the number of legal actions available for real-time planning in zero-sum extensive-form games, thus allowing algorithms to focus their search on a set of promising actions. Even though unabstracted game trees can lead to optimal policies, due to real-time constraints and the tree size, they are not a practical choice. In this context, we introduce an action abstraction scheme which we call asymmetric action abstraction. Asymmetric abstractions allow search algorithms to “pay more attention” to some aspects of the game by unevenly dividing the algorithm’s search effort amongst different aspects of the game. We also introduce four algorithms that search in asymmetrically abstracted game trees to evaluate the effectiveness of our abstraction schemes. Two of our algorithms are adaptations of algorithms developed for searching in action-abstracted spaces, Portfolio Greedy Search and Stratified Strategy Selection, and the other two are adaptations of an algorithm developed for searching in unabstracted spaces, NaïveMCTS. An extensive set of experiments in a real-time strategy game shows that search algorithms using asymmetric abstractions are able to outperform all other search algorithms tested.