PhD’s Thesis Project Defense, Anderson Rocha Tavares
We would like to congratulate Anderson Rocha Tavares about the defense of his Thesis project at UFMG.
Title:Strategic reasoning in digital zero-sum games
Abstract
Artificial Intelligence programs succeeded, achieving super-human performance, in traditional zero-sum games such as Checkers, Chess and Go. In digital games, however, programs are not as successful, because these games have huge state spaces and dynamic and real-time environments. Methods for traditional games fail under these circumstances.
To handle the challenge imposed by digital games, we present a new approach, based on an abstract layer of reasoning over the game: the layer of algorithms. Algorithms determine player behavior during a match and also specify changes in this behavior with gained experience.
We name the abstract layer of reasoning as the algorithm selection metagame. At each choice point in the metagame, players select algorithms to dictate their behavior in the underlying game. If we consider a reasonably small set of algorithms and choice points, we can solve the metagame and discuss important game theory concepts, which is unfeasible on the underlying game’s original representation.
Among the contributions of this work, we propose a new model of incomplete information stochastic games, which corresponds to the most complex metagame variant: a sequential decision problem without knowledge of the algorithms and decision points of the opponent. Besides, we propose a new method to deal with this problem.
We instantiate simpler variants of the metagame (with a single choice point) upon StarCraft, a digital game regarded as one of the current greatest artificial intelligence challenges. We confirmed that the metagame allows the discussion of game theory concepts and we obtain playing strategies with theoretical guarantees, which was unfeasible on the game’s original representation.
To handle the challenge imposed by digital games, we present a new approach, based on an abstract layer of reasoning over the game: the layer of algorithms. Algorithms determine player behavior during a match and also specify changes in this behavior with gained experience.
We name the abstract layer of reasoning as the algorithm selection metagame. At each choice point in the metagame, players select algorithms to dictate their behavior in the underlying game. If we consider a reasonably small set of algorithms and choice points, we can solve the metagame and discuss important game theory concepts, which is unfeasible on the underlying game’s original representation.
Among the contributions of this work, we propose a new model of incomplete information stochastic games, which corresponds to the most complex metagame variant: a sequential decision problem without knowledge of the algorithms and decision points of the opponent. Besides, we propose a new method to deal with this problem.
We instantiate simpler variants of the metagame (with a single choice point) upon StarCraft, a digital game regarded as one of the current greatest artificial intelligence challenges. We confirmed that the metagame allows the discussion of game theory concepts and we obtain playing strategies with theoretical guarantees, which was unfeasible on the game’s original representation.
Committee
Prof. Luiz Chaimowicz – Advisor (DCC – UFMG)
Prof. Ana Lúcia Cetertich Bazzan (INF – UFRGS)
Prof. Gisele Lobo Pappa (DCC – UFMG)
Prof. Levi Henrique Santana de Lelis (DPI – UFV)
Prof. Pedro Olmo Stancioli Vaz de Melo (DCC – UFMG)
Prof. Ana Lúcia Cetertich Bazzan (INF – UFRGS)
Prof. Gisele Lobo Pappa (DCC – UFMG)
Prof. Levi Henrique Santana de Lelis (DPI – UFV)
Prof. Pedro Olmo Stancioli Vaz de Melo (DCC – UFMG)
