A GPU implementation of Counterfactual Regret Minimization

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.