Hierarchical Portfolio Search: Prismata's Robust AI Architecture for Games with Large Search Spaces

Abstract

Online strategy video games offer several unique challenges to the field of AI research. Due to their large state and action spaces, existing search algorithms have difficulties in making strategically strong decisions. Additionally, the nature of competitive on-line video games adds the requirement that game designers be able to tweak game properties regularly when strategic imbalances are found. This means that an AI system for a game like this needs to be robust to such changes and less reliant on expert knowledge. This paper makes two main contributions to advancing the state of the art for AI in modern strategy video games which have large state and action spaces. The first is a novel method for performing hierarchical search using a portfolio of algorithms to reduce the search space while maintaining strong action candidates. The second contribution is an overall AI architecture for strategy video games using this portfolio search method. The proposed methods are used as the AI system for Prismata, an online turn-based strategy game by Lunarch Studios. This system is evaluated using three experiments: on-line play vs.~human players, off-line AI tournaments to test the relative strengths of the AI bots, and a survey to determine user satisfaction of the system so far. Our result show that this system achieves a skill level in the top 25% of human players on the ranked ladder, can be modified quickly to create different difficulty settings, is robust to changes in game unit properties, and creates an overall AI experience which is user rated more enjoyable than those currently found in similar video games.