Evolving Action Abstractions for Real-Time Planning in Extensive-Form Games

A key challenge for planning systems in real-time multiagent domains is to search in large action spaces to decide an agent’s next action. Previous works showed that handcrafted action abstractions allow planning systems to focus their search on a subset of promising actions. In this paper we show that the problem of generating action abstractions can be cast as a problem of selecting a subset of pure strategies from a pool of options. We model the selection of a subset of pure strategies as a two-player game in which the strategy set of the players is the powerset of the pool of options— we call this game the subset selection game. We then present an evolutionary algorithm for solving such a game. Empirical results on small matches of µRTS show that our evolutionary approach is able to converge to a Nash equilibrium for the subset selection game. Also, results on larger matches show that search algorithms using action abstractions derived by our evolutionary approach are able to substantially outperform all state-of-the-art planning systems tested.

Acknowledgements

This research was partially supported by CNPq, Capes, and FAPEMIG. The research was carried out using the computational resources of the Center for Mathematical Sciences Applied to Industry (CeMEAI) funded by FAPESP (grant 2013/07375-0), and the cluster Jupiter from Universidade Federal de Vic¸osa. We thank the anonymous reviewers for great suggestions.