Please use this identifier to cite or link to this item:
https://hdl.handle.net/10216/83517| Author(s): | João dos Santos Rodrigues Soares dos Reis |
| Title: | A GPU implementation of Counterfactual Regret Minimization |
| Issue Date: | 2015-07-06 |
| Abstract: | Notable milestones in the advancement of Artificial Intelligence have been achieved through solving games. Regret minimization is a technique that has seen a lot of use in the context of solving games in the past few years. In particular, Counterfactual Regret Minimization (CFR) is an algorithm that applies this technique and can be used to find equilibria in massive games. Therefore, one can use an algorithm like this to develop an agent with a very solid strategy for such games. One issue with this algorithm is the amount of execution time it requires, especially when applied to large extensive games. To address this issue, games are usually abstracted which can lead to worse solutions. This dissertation proposes an implementation of CFR that runs on the GPU, using CUDA, which is able to take advantage of the ability of GPUs to process many parallel streams of data. Using this approach, it is possible to reduce the execution time in some Poker variants, as our results demonstrate. This means that this approach has the potential to allow the computation of Nash Equilibria for games with a larger search space than before. |
| Description: | Marcos notáveis no avanço da Inteligência Artificial foram alcançados através da obtenção de soluções para jogos. A técnica da Minimização do Arrependimento tem sido muito usada no contexto da obtenção de soluções para jogos nos últimos anos. Em particular, Counterfactual Regret Minimization é um algoritmo que aplica esta técnica e pode ser usado para encontrar equilíbrios em jogos massivos. Portanto, pode-se usar um algoritmo deste género para desenvolver um agente com uma estratégia muito sólida para esses jogos. Um problema com este algoritmo é a quantidade de tempo de execução que exige, especialmente quando aplicada a jogos com enormes árvores de pesquisa. Para abordar este problema, os jogos são geralmente abstraídos o que pode levar a soluções piores. Esta dissertação propõe uma implementação do CFR que corre no GPU, usando CUDA, que é capaz de tirar partido da capacidade de GPUs para processar elevadas quantidades de dados de forma paralela. Usando esta abordagem, é possível reduzir o tempo de execução, como demonstram os resultados. Isto significa que este método tem o potencial de permitir o cálculo de Equilíbrios de Nash para jogos com um espaço de pesquisa maior do que antes. |
| Subject: | Engenharia electrotécnica, electrónica e informática Electrical engineering, Electronic engineering, Information engineering |
| Scientific areas: | Ciências da engenharia e tecnologias::Engenharia electrotécnica, electrónica e informática Engineering and technology::Electrical engineering, Electronic engineering, Information engineering |
| DOI: | 10.34626/3g14-3t32 |
| TID identifier: | 201307162 |
| URI: | https://hdl.handle.net/10216/83517 |
| Document Type: | Dissertação |
| Rights: | openAccess |
| License: | https://creativecommons.org/licenses/by-nc/4.0/ |
| Appears in Collections: | FEUP - Dissertação |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| 35409.pdf | A GPU implementation of Counterfactual Regret Minimization | 1.81 MB | Adobe PDF |  View/Open |
This item is licensed under a Creative Commons License
