Please use this identifier to cite or link to this item: http://hdl.handle.net/1843/38313
Type: Dissertação
Title: Drafting in collectible card games via reinforcement learning
Other Titles: Criando estratégias de draft em jogos de cartas colecionáveis via aprendizado por reforço
Authors: Ronaldo e Silva Vieira
First Advisor: Luiz Chaimowicz
First Co-advisor: Anderson Rocha Tavares
First Referee: Leandro Soriano Marcolino
Second Referee: Adriano Alonso Veloso
Abstract: Collectible card games (CCGs), such as Magic: the Gathering and Hearthstone, are played by tens of millions of players worldwide, and their vast state and action spaces, intricate rules and diverse cards make them challenging for humans and artificial intelligence (AI) agents alike. In them, players build a deck using cards that represent creatures, items or spells from a fantasy world and use it to battle other players. Therefore, to win, players must be proficient in two interdependent tasks: deck building and battling. The advent of strong and fast AI players would enable, for instance, thorough playtesting of new cards before they are made available to the public, which is a long-standing problem in the CCG industry. In this thesis, we present deep reinforcement learning approaches for deck-building in the arena mode – an understudied game mode present in most commercial collectible card games. In arena, players build decks immediately before battling by drafting one card at a time from randomly presented candidates. We formulate the problem in a game-agnostic manner and investigate three approaches that differ on how to consider the cards drafted so far in the next choices, using different game state representations and types of neural networks. We perform experiments on Legends of Code and Magic, a collectible card game designed for AI research. Considering the win rate of the decks when used by fixed battling AIs, the results show that our trained draft agents outperform the best draft agents of the game, and do so by building very different decks. Moreover, a participant of the Strategy Card Game AI competition improves from tenth to fourth place when using our best draft agent to build decks. We conclude with a discussion on the results, contributions and limitations of this work as well as directions for future research.
Abstract: Jogos de cartas colecionáveis (JCC), como Magic: the Gathering e Hearthstone, possuem atualmente dezenas de milhões de jogadores pelo mundo. Seus vastos espaços de estados, junto de suas complexas regras e grande quantidade de cartas diferentes fazem com que jogá-los seja uma tarefa desafiadora tanto para humanos quanto para agentes de inteligência artificial (IA). Neles, os jogadores constroem um baralho usando cartas que representam criaturas, itens ou mágicas de algum universo fictício e o usam para batalhar contra outros jogadores. Para vencer, portanto, um jogador precisa ser proficiente em duas tarefas interdependentes: contruir baralhos e batalhar. O advento de IAs que joguem JCCs de forma proficiente e rápida possibilitaria, por exemplo, o playtest extensivo de novos conjuntos de cartas antes destes serem disponibilizados para o público, o que é, há muito tempo, um problema em aberto na indústria de JCCs. Nesta dissertação, propomos abordagens de aprendizado por reforço profundo para a tarefa de construir baralhos no modo arena – um modo de jogo presente na maioria dos jogos de cartas colecionáveis comerciais. No arena, os jogadores constroem seus baralhos imediatamente antes de batalhar, escolhendo uma carta de cada vez dentre cartas aleatórias apresentadas (processo chamado de drafting). Nós formulamos o problema de forma genérica, aplicável a vários JCCs, e investigamos três abordagens que diferem em como considerar as cartas já escolhidas nas próximas escolhas, usando diferentes representações de estados e tipos de redes neurais. Realizamos experimentos no Legends of Code and Magic, um JCC desenvolvido especificamente para pesquisa em IA. Usando como métrica de desempenho a taxa de vitória dos baralhos ao serem usados por IAs em batalhas, os resultados mostram que nossos agentes de drafting alcançaram desempenho melhor que as melhores IAs disponíveis para o jogo, e o fizeram construindo baralhos muito diferentes dos construídos por elas. Além disso, uma IA participante da competição Strategy Card Game AI competition, realizada na conferência IEEE CoG 2019, subiu do décimo para o quarto lugar na classificação ao usar nosso melhor agente para construir seus baralhos. Concluímos com uma discussão sobre os resultados, contribuições, limitações e possíveis trabalhos futuros.
Subject: Computação – Teses.
Jogos digitais – Teses.
Jogos de cartas colecionáveis – Teses.
Aprendizado por reforço – Teses.
language: eng
metadata.dc.publisher.country: Brasil
Publisher: Universidade Federal de Minas Gerais
Publisher Initials: UFMG
metadata.dc.publisher.department: ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO
metadata.dc.publisher.program: Programa de Pós-Graduação em Ciência da Computação
Rights: Acesso Aberto
URI: http://hdl.handle.net/1843/38313
Issue Date: 13-Oct-2020
Appears in Collections:Dissertações de Mestrado

Files in This Item:
File Description SizeFormat 
dissertacao-ronaldo-final.pdf3.58 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.