Aproximación de equilibrios de Nash en juegos de información imperfecta y suma positiva mediante métodos de Monte Carlo y aprendizaje automático

Abstract

El objetivo de esta investigación fue el de aproximar un equilibrio de Nash en el Truco uruguayo: un juego de cartas de suma positiva e información imperfecta de 2, 4 y hasta 6 jugadores; siendo este un problema PPDA-completo. Se implementó una serie de agentes basados tanto en la Teoría de Juegos Computacional moderna como en el Aprendizaje por Refuerzo Profundo: desde Counterfactual Regret Minimization (CFR) y sus variantes más populares hasta Deep Monte Carlo (DMC). Se formuló y demostró un teorema el cual asegura que toda partida de Truco se compone de un máximo de 2n − 1 rondas como máximo, donde n es el puntaje de la partida y se empleó este resultado para introducir el dataset de evaluación T1K22. Este último se compone de 79.000 rondas aleatorias de Truco uruguayo y fue usado en tareas de evaluación en conjunto con las tres líneas bases propuestas: un caminante aleatorio, un agente determinista y el autor de este proyecto de grado. También se introdujo el índice-D: una métrica alternativa de evaluación, específica para el Truco uruguayo. Luego de 2 semanas de entrenamiento y partiendo desde cero, los agentes basados en métodos de Monte Carlo fueron capaces de alcanzar un win rate (WR) superior al 91 %, 70 % y 59 % para cada línea base. Finalmente, se implementó y evaluó un módulo de búsqueda insegura basado en simulaciones Monte Carlo concurrentes en base a las estrategias estáticas previamente obtenidas. Bajo esta técnica, los agentes que emplean búsqueda insegura fueron capaces de superar a los agentes más robustos obtenidos en la etapa anterior, pero ahora utilizando 99.4 % menos espacio en disco y memoria.

In this research we try to approximate Nash equilibria in Uruguayan Truco: a positive-sum and imperfect information card game for its 2, 4 and 6 player variants; being this a PPDA-complete problem. We adapt and evaluate several agents based on modern Computational Game Theory as well as modern Deep Reinforcement Learning (DRL): from Counterfactual Regret Minimization (CFR) and its main variants to Deep Monte Carlo (DMC). We formulate and prove a theorem which states that every game of Truco is set to finish in 2n − 1 hands at most, where n is the agreed maximum score and use this result to introduce T1K22 : a dataset containing 79,000 random hands of uruguayan Truco. We then use this dataset for evaluation tasks on three baselines: a random walker, a deterministic agent and the author himself. After 2 weeks of training, starting from scratch and without human knowledge, our Monte Carlo based agents defeated every baseline achieving a win rate (WR) of approximately 91 %, 70 % and 59 % respectively. We also introduce the D-Index: a Truco-specific gameplay metric for evaluation purposes. Finally, we develop and evaluate an unsafe search module based on concurrent Monte Carlo rollouts based upon the previous blueprints. Under this technique, some agents are able to outperform the best agents developed in the first part of this research but now using strategies 99.4 % smaller.