Programmatic Strategies for Real-Time Strategy Games

Abstract

Search-based systems have shown to be effective for planning in zero-sum games. Although search algorithms are often stronger than strategies hard-coded in scripts, they have important disadvantages. First, the decisions of search algorithms are mostly non-interpretable, which is problematic in domains where predictability and trust are desired. Second, the computational complexity of search-based algorithms might limit their applicability, especially in commercial games where resources are shared among other tasks such as graphic rendering. In this work we introduce a system for synthesizing programmatic strategies for a real-time strategy (RTS) game. Our system uses a novel algorithm for simplifying domain-specific languages (DSLs) and a local search algorithm that synthesizes programs with self play. We evaluate our system on µRTS, a minimalist RTS game. We performed a user study where we enlisted four professional programmers to develop scripts for µRTS. Our results show that the scripts synthesized by our approach can outperform search algorithms and be competitive with scripts written by the programmers.