Approximating Nash Equilibria for Uruguayan Truco: A Comparison of Monte Carlo and Machine Learning Approaches
Juan Pablo Filevich, Héctor Cancela · 2023
Uruguayan Truco is a positive-sum and imperfect information card game with 2, 4 and 6 player variants. Finding the Nash equilibria of such games is very hard, so we approximate them using Computational Game Theory and Deep Reinforcement Learning methods. We implement Counterfactual Regret Minimization (CFR) and some of its variants, and Deep Monte Carlo (DMC). We also propose two levels of manual abstraction to reduce the number of information sets, which are sets of indistinguishable game states. We evaluate our methods on T1K22, a dataset of 79,000 random hands of Uruguayan Truco, against two baseline agents and a human player. We find that CFR-based methods outperform DMC, especially External Sampling Monte Carlo CFR, which converges faster and achieves a higher win rate. It is remarkable that, after 2 weeks of training (totaling 4,032 core hours), starting from scratch and without using any human knowledge, the best agents defeated every baseline, with win rates significantly higher than 50%.