Strategic reasoning in complex zero-sum computer games

Abstract

Complex computer games, with high-resolution state representations, a large number of actions and the need of reasoning in different temporal scales against an opponent, present many unsolved challenges to artificial intelligence. Those challenges gave rise to a variety of algorithms, specialized in different aspects of a game. Human players succeed at such games by resorting to previously trained strategies, or lines of actions, and excel at generalizing responses by analogy between unforeseen and familiar situations. This thesis presents a computational version of the human behavior: first, we replace the human repertoire of strategies by a portfolio of algorithms, modeling game-playing as an adversarial algorithm selection problem in a reinforcement learning framework. Second, we use known function approximation schemes to promote similar responses to similar game states. Our hierarchical decision-making framework makes use of existing algorithms, aiming to discover the best in each game situation, potentially resulting in a stronger performance than a single algorithm could reach. We demonstrate the advantages of algorithm selection according to the number of actions in the domain, the portfolio size, and algorithms' strength, via experiments in a synthetic problem. Moreover, we instantiate our framework in real-time strategy games - possibly the most complex type of computer game - where a player must strategically develop its economy and quickly maneuver its units in combat. Our framework allows the discussion of game-theoretic aspects of algorithm selection, in the sense of anticipating the choices of an algorithm-selector opponent, and leverages the performance of artificial intelligence in real-time strategy games by consistently outperforming state-of-the-art game-tree search approaches.