Strategic reasoning in complex zero-sum computer games

Detalhes bibliográficos
Ano de defesa: 2018
Autor(a) principal: Anderson Rocha Tavares
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
Tipo de documento: Tese
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Universidade Federal de Minas Gerais
UFMG
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: http://hdl.handle.net/1843/SLSC-BBWPRR
Resumo: 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.