Adversarial search and spatial reasoning in real time strategy games
Alberto Uriarte, Santiago Ontañón · 2017
For many years, Chess was the standard game to test new Artificial Intelligence (AI) algorithms for achieving robust game-playing agents capable of defeating the best human players. Nowadays, games like Go or Poker are used since they offer new challenges like larger state spaces, or non-determinism. Among these testbed games, Real-Time Strategy (RTS) games have raised as one of the most challenging. The unique properties of RTS games (simultaneous and durative actions, large state spaces, partial observability) make them a perfect scenario to test algorithms able to make decisions in dynamic and complex situations. This thesis makes a contribution towards achieving human-level AI in these complex games. Specifically, I focus on the problems of performing adversarial search in domains (1) with extremely large decision and state spaces, (2) where no forward model is available, and (3) the game state is partially observable. Additionally, I also study how spatial reasoning can be used to reduce the search space and to improve the RTS playing bots.