Intelligent search in complex games with adversary. Design, application and evaluation

Abstract

[EN] Monte Carlo Tree Search (MCTS) is a heuristic method used in decision-making that aims to simulate all possible outcomes that result from choosing a given action, assigning a value to each of them and choosing the best one. In this work, it was decided to apply it to the popular game UNO, a card game with hidden information and a great degree of uncertainty and randomness involved. MCTS had already been implemented for games with these characteristics, such as Poker, Bridge or Hearts, among others. We implement a simulator of the game for its two-player version. The MCTS agent and several simulation strategies and other tweaks are then integrated, and agents are matched against each other and against a virtual player with the objective of comparing the different versions and interpret the obtained results.

[ES] El árbol de búsqueda Monte Carlo (MCTS) es un método heurístico usado en la toma de decisiones que trata de simular todos los posibles resultados que surgen de elegir una determinada acción, asignando un valor a cada una de ellas y eligiendo la mejor. En este trabajo, se ha decidido aplicar el método al popular juego UNO, un juego de cartas con información oculta y un alto grado de incertidumbre y aleatoriedad involucrados. MCTS ya había sido implementado para juegos de estas características, como el Poker, Bridge o Hearts, entre otros. Se ha implementado un simulador del juego para su versión de dos jugadores. El agente MCTS y varias estrategias de simulación han sido integradas en el mismo, y los agentes son enfrentados entre ellos y contra un jugador virtual con el objetivo de comparar las diferentes versiones e interpretar los resultados obtenidos.

[CA] La recerca Monte Carlo (MCTS) es un mètode heurístic emprat en la presa de decisions que tracta de simular tots els possibles resultats que sorgixen de triar una determinada acció, assignant un valor a cada una d’elles i triant la millor. En aquest treball, s’ha decidit aplicar el mètode al popular joc UNO, un joc de cartes amb informació oculta i un alt grau d’incertesa i aleatorietat involucrats. MCTS ja havia sigut implementat per a jocs d’aquestes característiques, com ara el Poker, Bridge o Hearts, entre altres. S’ha implementat un simulador del joc per a la versió de dos jugadors. L’agent MCTS i diverses estratègies de simulació hi han sigut integrades, i els agents són enfrontats entre ells i contra un jugador virtual amb l’objectiu de comparar les diferents versions i interpretar els resultats obtinguts.