Asymmetric Action Abstractions for Planning in Domains with Very Large Action Spaces and Real-Time Constraints

摘要: Action abstractions restrict the number of legal actions available for real-time planning in multi-unit 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 we call asymmetric abstraction. Similarly to unabstracted spaces, asymmetrically-abstracted spaces can have theoretical advantages over regularly abstracted spaces while still allowing search algorithms to derive effective strategies in practice, even in large-scale games. Further, 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. An extensive set of experiments in a real-time strategy game developed for research purposes shows that search algorithms using asymmetric abstractions are able to outperform all other search algorithms tested.