Planning in RTS Games with Incomplete Action Definitions via Answer Set Programming

Abstract

Standard game tree search algorithms, such as minimax or Monte Carlo Tree Search, assume the existence of an accurate forward model that simulates the effects of actions in the game. Creating such model, however, is a challenge in itself.One cause of the complexity of the task is the gap in level of abstraction between the informal specification of the model and its implementation language. To overcome this issue, we propose a technique for the implementation of forward models that relies on the Answer Set Programming paradigm and on well-established knowledge representation techniques from defeasible reasoning and reasoning about actions and change. We evaluate our approach in the context of Real-Time Strategy games using a collection of StarCraft scenarios.