Se conoce por el nombre de Tactical Collectible Card Games (TCCG) a aquellos juegos de cartas en los que generalmente se enfrentan dos jugadores, que suelen contar con una base de cartas en constante crecimiento y que permiten la creación de un repertorio propio o mazo, los cuales suelen contar con una temática y explotan una faceta concreta de los mismos. Dichos juegos cuentan con un alto componente estratégico, tanto antes de la partida (creación del mazo) como durante la misma, y requieren de la capacidad de previsión para adelantarse al oponente y a las cartas que pueden aparecer. Para ello suelen aplicarse componentes estadísticos para los valores de las cartas, ya que se posee una información parcial e incompleta, cuyo correcto manejo es clave.
Normalmente hay un componente de azar, ya que no se usan todas las cartas de un mazo en una partida, pero hay un fuerte peso de gestión de recursos y se requiere del jugador que sea capaz de
2020 Copyright for this paper by its authors. CEUR
ceur-ws.org manejar una reserva y unos pagos, en este caso la reserva con la que se pagan los costes de las cartas se llama maná. El objetivo del juego es derrotar a un oponente, que cuenta con unos puntos de vida, que se irán reduciendo a medida que va recibiendo ataques generados por medio de cartas que juega el rival. Entre dichas cartas existe la posibilidad de crear esbirros, que también podrán atacar al jugador o a sus propios esbirros. Las cartas se juegan sobre un tablero y cada una tiene un coste en maná para poder jugarse.
En este trabajo nos centramos en el TCCG llamado Magic: The Gathering [
El objetivo es diseñar y probar un agente autónomo capaz de jugar al juego de manera eficiente y
efectiva y para ello, nos basaremos en la creación de un motor de comportamiento que modele las
decisiones que tomaría un jugador experto durante una partida. Dicho conjunto de reglas será
posteriormente optimizado por medio de un Algoritmo Genético [
La principal razón de esto es la falta de entornos de simulación en los que probarlos y por esa razón, como paso previo, se ha implementado un simulador que permite jugar partidas de MTG tanto a jugadores humanos, como a agentes. Este también se considera una contribución del trabajo.
Magic: The Gathering [
Una partida estándar de MTG se ve como se muestra en la Figura 1, con ambos jugadores enfrentados, manteniendo las cartas de la mano en secreto y con el mazo siendo oculto a ambos jugadores. Se puede apreciar un grupo de cartas coloreadas, estas son las Tierras, las cuales se usan, habitualmente, para generar maná (para pagar el coste asociado a las cartas). La gestión del maná es un punto muy importante de la partida. Sólo se puede jugar una por turno a no ser que se utilicen cartas especiales que alteren dicha restricción, los cuales pueden ser genéricos o de un color concreto. Los costes de las cartas suelen venir dados por un número y varios símbolos, el número indica el maná a pagar de cualquier color y los símbolos indican el precio añadido que tiene de un color concreto. Una vez una carta de la mesa se activa se debe girar y no se volteará de nuevo hasta que vuelva a tocarle a ese jugador.
Las Criaturas son cartas que al ser jugadas entran a la mesa y permiten atacar y defender, su uso es similar al del maná, si es usada en un ataque, no podrás usarla en la defensa ya que será girada en el proceso. Las criaturas poseen unas estadísticas X/Y donde X representa el valor de ataque y la defensa viene dada por Y. Las criaturas recuperan toda su defensa al final de cada turno, propio y del oponente. En un supuesto de ataque, éste tiene oportunidad de defenderse, eligiendo qué criaturas quiere usar para enfrentarse a cada criatura atacante enemiga. Tras un ataque, las criaturas que hayan sido derrotadas son enviadas al cementerio, allí están las cartas disponibles para que ambos jugadores las vean, pese a que cada cementerio es personal.
Figura 1: Imagen conceptual de una partida de Magic: The Gathering.
En la Figura 2, se muestran los distintos apartados que conforman una carta, en este caso llamada Enormous Baloth. En concreto, en esta carta el tipo sería Bestia, que no tiene mucha repercusión debido a que no hay cartas en la simulación que requieran un tipo específico. También se incluyen las habilidades, pero al no haber ninguna, se incluye un fragmento de su historia o descripción para completar. Para pagar su coste habría que gastar seis manás de cualquier color y además otro verde, siete en total. Su ataque es de siete y habría que hacerle siete puntos de daño o más en un turno para eliminarle. Una criatura bastante cara, que no se puede jugar hasta el denominado Late Game debido a su coste.
La estructura de la partida se organiza en rondas, divididas en turnos, cada jugador cuenta con un turno que se compone de varias fases las cuales siguen la siguiente composición y orden: • Mantenimiento: donde las criaturas, encantamientos y el maná se voltean para poder volver a usarlos. El jugador, además, debe robar una carta para reabastecer su mano. • Principal: Momento en el que se pueden jugar las cartas y permite iniciar la estrategia a seguir. • Combate: dividido en varias sub-fases que permiten, elegir las criaturas que atacan, elegir las que defienden y a que criaturas se enfrentan, ordenar los defensores para elegir cuales se enfrentarán primero y finalmente actualizar cuanto daño ha sufrido cada jugador o criatura. Por último, se pueden usar cartas de Hechizos, las cuales tienen múltiples efectos y dependen del mazo elegido. Estos efectos suelen ser inmediatos y una vez jugadas se envían al cementerio, esto es de gran utilidad ya que se permite un máximo de 4 cartas iguales por mazo, lo que facilita calcular la probabilidad de que un oponente repita una acción con ellas.
Desde el comienzo del estudio de los Agentes Autónomos, los juegos de cartas han sido un gran aliado, como se ha mencionado, al igual que en el aprendizaje humano. Los juegos permiten un entorno controlado para plantear problemas o situaciones que evidencien un comportamiento o tendencia.
Esto ya se pudo estudiar en el 2003 en Opponent Modelling in Póker [
Se utilizaba para ello un algoritmo Monte Carlo Tree Search (MCTS), es decir, un árbol de decisiones en el que se simulan todas las opciones posibles de acciones en cada instante y se elige la mejor por medio de un algoritmo MINMAX. Pero el mayor problema de este sistema es que en el árbol de decisión deben contenerse todas las posibles opciones y en los casos de una baraja de cartas de un mínimo de 60, obtenemos 8,23 · 1081 posibilidades para la sucesión de cartas que podría obtener cada jugador. A su vez, deberíamos añadir la información incompleta que se maneja y por tanto convierte el problema en un cómputo imposible para el agente.
Para resolver dicha problemática se deben definir estados más acotados y situaciones generales que cuenten con acciones recomendadas. En este mismo artículo se puede encontrar el resultado del uso de MCTS en MTG, aconsejando al agente buscar opciones para derrotar a otro oponente autónomo que trabajaba con un MCTS centrado en evaluar opciones recomendadas por un jugador experto. El resultado concluyó en que un 95% de las jugadas que realizaba el agente con asistencia, eran mejores que las del que usaba MCTS sobre el espacio global de acciones.
Es imposible hablar de la aproximación de los agentes autónomos a los juegos, concretamente a los TCCG sin mencionar HearthStone. Este juego permite una gran variedad de sistemas para implementar un agente autónomo, ya que se trata de un sistema cerrado., en el que los recursos se adquieren de manera pasiva y los ataques son dirigidos al oponente o a una criatura concreta, añadiendo un sistema de Héroes, que representan al jugador y le otorgan habilidades y cartas únicas, pudiendo tomarse como una versión de los Colores o Clanes de MTG. Por tanto y debido a la gran variedad de ejemplos y a lo estandarizado que se encuentra en el campo, se pueden tomar dichos agentes como precursores e inspiración para este propio trabajo.
De esta manera se pueden diferenciar aquellos que gestionan una partida y los que generan mazos
para la misma. Los agentes que generan mazos para una partida [
Durante la fase inicial del trabajo se hizo una búsqueda de simuladores o juegos de código abierto
que implementasen la funcionalidad de MTG. Se localizaron algunas alternativas, pero no se pudo
encontrar un sistema que permitiese enfrentar dos jugadores autónomos. Por lo que se optó por la
implementación en Python de Hlynur David Hlynsson, llamada Open-MTG [
Por tanto, el esfuerzo inicial del proyecto se empleó en pulir el entorno de juego/trabajo (Framework), así como aumentar sus funcionalidades, para poder lanzar agentes autónomos y para extraer información detallada de las partidas, que permitiera evaluar el rendimiento de dichos agentes más allá de quién gana cada combate. Dicha información es muy relevante para el problema de la optimización de agentes.
El simulador finalmente desarrollado, OpenMTG.ai, permite, por tanto, jugar partidas de MTG con un gran mazo de cartas (una parte de las 19000 existentes) y las reglas fundamentales implementadas (algunas de las 2000 que tiene el juego), así como toda la lógica del juego. Permite además que jueguen jugadores humanos o autónomos, pudiendo enfrentar incluso dos agentes entre sí en tiempo de simulación, es decir, resolviendo partidas en fracciones de segundo. Junto a esto se obtienen datos de log, que describen gran parte de la actividad de los jugadores durante la partida, facilitando evaluar la calidad de un agente, por ejemplo.
Dicho simulador, implementado en Python, que se considera también una contribución de este trabajo, se puede encontrar en la URL: https://github.com/PabloGanivet/OpenMTG.ai. Se trata de un entorno que funciona en modo texto, dado que para este trabajo no era necesario un entorno visual.
El juego MTG requiere de planificación y de compromiso a una estrategia, ya que la mayoría de partidas se resuelven dependiendo de quién se centre más en su objetivo, ya sea eliminar las criaturas enemigas, reducir la vida del oponente a cero o agotar el mazo; por lo que cada decisión debe responder a un acercamiento constante al objetivo. Por ello, cada turno requiere de una organización y selección, cada elección elimina unos recursos y deben optimizarse al máximo.
En cuanto a los métodos de resolución de cada turno, durante el proceso de creación del agente se han elegido aquellas estrategias que sean más representativas de las humanas y que muestren distinto nivel de complejidad. Estas estrategias ayudan a recopilar información añadida sobre los mazos, ya que, durante el proceso, el ratio de victorias no ha sido equitativo en todo momento, lo que evidencia una desigualdad para un mazo en determinadas ocasiones. De este modo, se han considerado las estrategias: • Random: elección aleatoria de la jugada, simplemente respetando las reglas del juego. Se usará como rival un sparring. • Greedy: es una aproximación que toma las decisiones que proporcionan una mayor ganancia, o consumo, en un momento dado, sin pensar en una estrategia futura. En los ataques sigue atacando con todo lo que pueda y en las defensas intenta eliminar a la mayor cantidad de criaturas a su alcance. • Minimax: árbol de búsqueda. Se implementa un modelo de MCTS que, como ya se mencionó, puede implicar un coste computacional demasiado elevado y que no tiene por qué traducirse en la mejor jugada o una jugada superior a los demás. • Heurística: se utilizan una serie de reglas basadas en conocimiento experto para guiar las decisiones del agente. Estas reglas pueden ser listas de acciones, similares a la normativa del juego, por ejemplo: “Nunca hagas que un hechizo tuyo tenga como objetivo una carta de tu propiedad o a ti mismo”, o pueden ser mucho más generales como “Esperar a ver qué hechizos tiene un enemigo antes de jugar una carta importante”. En este caso, se vuelve a recaer en el problema de tener que vaticinar cada situación o problema, pero proporciona soluciones estándar.
Siempre debemos tener en cuenta que estas soluciones pueden no ser lo que deseamos, pues no se llega a pensar más allá de lo estándar y por ende no obtenemos soluciones distintas a las humanas, solo un compendio de las mismas, pero en un uso más depurado.
El agente hace un cálculo de una función de fitness, que indica los beneficios de jugar una carta en un momento dado de la partida. Ésta se calcula combinando una serie de parámetros según las expresiones que se muestran en la Tabla 1.
De modo que el agente elegirá la carta que maximice el valor de fitness de entre las posibles. Para añadir que la estrategia a seguir por el agente sea ofensiva/agresiva o defensiva, se incluyen factores ponderadores al cálculo del fitness antes mencionado, en concreto son los mostrados en la Tabla 2. Para calcular las variables de las que depende el cómputo de dichos factores, se realizan simulaciones de jugadas de cada posible carta en el entorno OpenMTG.ai. Además, en dicho cálculo se consideran las variables Agresividad (aggressive ratio) y Defensivo (defensive ratio), que decide previamente el jugador en base a la estrategia que quiera que siga el agente.
Expresiones utilizadas para la valoración de cada tipo de carta a jugar.
El agente es también capaz de manejar hechizos, si bien su uso es muy complejo, por lo que se han implementado reglas de alto nivel, basadas en el conocimiento de un experto para gestionarlo de manera somera, y dependiente también de los factores Agresividad y Defensivo antes mencionados.
Expresiones utilizadas para la ponderación de las estrategias a utilizar.
A la hora de aplicar la optimización evolutiva al motor de comportamiento de los agentes se han seguido dos enfoques para el Algoritmo Genético (AG): el primero (versión UNO) se basa en utilizar dos poblaciones, que realizan una co-evolución, ya que ambas poblaciones compiten entre sí para ir mejorando a los agentes. En la segunda propuesta (versión DOS), se sigue una línea de actuación más convencional, en la que cada mazo cuenta con una población y se entrena frente un agente estático con valores heurísticos para las reglas, denominado sparring. Como aclaración, consideraremos dos tipos de agentes/jugadores: Gold, el cual seguirá una estrategia ofensiva/agresiva, centrada en el daño y Silver, que será un agente defensivo, basado en el aguante y desgaste del rival. Cada uno contará con un mazo adaptado para dicha estrategia.
Cada individuo del AG será un vector que tendrá valores para las variables: costmin (coste de maná mínimo que debe tener el jugador para lanzar determinados hechizos importantes), powmin (fuerza/daño mínimo que debe tener asociado una criatura para atacarla), toughmin (resistencia/salud mínima que debe tener asociada una criatura para atacarla), aggressive ratio (factor que controla el nivel de ataque del jugador en su estrategia) y defensive ratio (factor que controla el nivel de defensa del jugador en su estrategia), peso_vida_oponente (importancia relativa de la salud del rival), peso_vida_criaturas_oponente (importancia relativa de la salud de las criaturas rivales), peso_vida_propia (importancia relativa de la salud del jugador), peso_vida_criaturas_propias (importancia relativa de la salud de las criaturas del jugador). Dichos valores tendrán gran importancia en el comportamiento y las decisiones a tomar por el agente, por lo que serán los que se optimizarán. Cabe aclarar que dichos valores se moverán entre umbrales, ya que, por ejemplo, no tiene sentido considerar niveles de fuerza/daño por encima del que puede hacer la criatura más poderosa del juego.
La función de fitness considerada sigue esta expresión para el jugador (para una serie de combates): = 100 · − + + , (1) Donde, Winrate se refiere al porcentaje de victorias obtenido respecto al total de partidas jugadas, Turnos son los turnos medios empleados para terminar las partidas por el jugador, VidaRestante es la media de la vida de nuestro jugador al terminar las partidas y DmgRealizado el daño medio conseguido en esas partidas.
El cruce se ha combinado con la mutación, de manera que, para cada dos padres seleccionados, se generan dos hijos cogiendo valores aleatorios de los genes de cada padre y posteriormente aplicando una variación aleatoria (pero controlada para estar dentro del rango válido de cada gen). En las pruebas se ha considerado una tasa de mutación del 20%. El AG ha trabajado con 40 individuos y 40 generaciones, de los que se seleccionan 20 como padres (los mejores) y se realiza un reemplazo ordenando la población anterior, junto con los nuevos hijos y eligiendo los 40 mejores.
Los resultados obtenidos se describen en tres experimentos diferentes. En primer lugar, en la Tabla 3, se muestran los resultados alcanzados por los agentes optimizados en la versión UNO del AG (en la que hay co-evolución).
En dichos resultados se puede ver la media de 1000 combates realizados por tres agentes Gold (agresivo) y tres Silver (defensivo) enfrentados entre sí, considerando que lo que se muestra es el cálculo de la función de la Ecuación 1. Como se puede ver, los resultados están equilibrados, siendo el segundo agente Gold un poco mejor que los demás, si bien el segundo Silver también consigue buenos resultados. Pero ninguno destaca sobre los demás de forma clara, puesto que su evolución ha sido conjunta.
Resultados de fitness obtenidos por los tres mejores agentes de la versión co-evolutiva del AG tras la última generación (solución ofensiva frente a defensiva). Se consideran enfrentamientos de cada individuo ofensivo frente a su análogo defensivo.
En el segundo experimento, se muestran los resultados de los agentes evolucionados siguiendo la versión DOS del AG (una sola población frente a un rival sparring común). La Tabla 4 muestra dichos resultados, en los que, ahora sí se puede ver que se consiguen valores mucho más altos que en la versión anterior, ya que el rival es fijo y el AG es capaz de adaptarse a sus estrategias de mejor manera que en una versión co-evolutiva en la que los rivales también se van adaptando.
Resultados de fitness obtenidos por los tres mejores agentes de la versión simple del AG tras la última generación, tanto de la evolución de Gold, como de Silver. Se consideran enfrentamientos de cada individuo frente al sparring.
Podemos observar que se han encontrado mejores soluciones para la versión ofensiva. La explicación más lógica es que se debe a la cantidad de turnos empleados, ya que, en este juego, los mazos defensivos juegan en lo que se denomina Late Game, ya que o bien requieren de mucho maná para jugar sus cartas o juegan al desgaste del oponente. Como la cantidad de turnos empleados se valora negativamente, esto puede reducir su fitness.
Por último, se ha realizado un experimento en el que se han enfrentado los mejores agentes de cada versión del evolutivo (según los resultados anteriores). De modo que se han realizado 1000 combates entre cada par de agentes, uno ofensivo (Gold) y uno defensivo (Silver) de cada AG. Los resultados se pueden ver en la Tabla 5.
Número de combates ganados (de 1000 enfrentamientos) por los mejores agentes ofensivos (Gold) y defensivos (Silver), obtenidos en cada una de las implementaciones del Algoritmo Genético: co-evolutiva (1) y simple (2).
Como se puede ver, la versión UNO es capaz de ganar o casi empatar a su sucesora, esto es un punto muy importante porque se suponen versiones más toscas, la principal teoría reside en su entrenamiento, ambos jugadores se entrenaron entre sí, por lo que pese a obtener peores resultados, esto se debe a que sus oponentes estaban más cualificados. Aún así, la especialización que consiguen los jugadores de la versión DOS, les permite optimizar mucho más los parámetros de los genes que determinan su comportamiento y consiguen de esta forma un mejor rendimiento (mayor número de combates ganados). También se puede observar que los mazos Silver son mejores en ambas versiones. Esto se puede deber a dos factores principales: el mazo defensivo es mejor; esto implica que hay una desigualdad a la hora de comprobar la efectividad de los mazos, o podemos pensar que el resultado óptimo de la estrategia defensiva se encuentra más cercano al punto inicial de los agentes. Es decir, el agente rival (sparring) en la versión DOS tiende a ser más agresivo, por lo que los agentes evolucionados se habrán adaptado para jugar mejor frente a dicho rival y, por tanto, contra agentes ofensivos. Esto también se refleja en la victoria de Gold2 frente a Gold1.
Este trabajo presenta una propuesta de agentes para jugar al famoso juego de estrategia con cartas Magic: The Gathering. Se implementó en primer lugar un simulador de combates completamente funcional, llamado OpenMTG.ai, a partir de un proyecto existente muy preliminar y posteriormente se diseñaron agentes capaces de jugar a dicho juego de manera autónoma (a partir de mazos predefinidos). Dichos agentes, cuyo comportamiento dependía de una serie de factores, se han optimizado por medio de Algoritmos Genéticos (AGs).
Se han implementado dos versiones de dichos AGs, una co-evolutiva, en la que se han ido evolucionando individuos con estrategias agresivas, frente a otros defensivos; y otra versión en la que todos los individuos se han enfrentado a un agente diseñado de forma heurística por un jugador experto.
Se ha comprobado el rendimiento de estos agentes entre sí y también frente a un rival común, consiguiéndose mejoras significativas frente a las versiones iniciales sin optimizar. Los resultados muestran que los agentes son capaces de evolucionar y mejorar y convertirse en jugadores competitivos. Estamos convencidos de que, aumentando la complejidad del entorno añadiendo muchas más cartas, podremos obtener agentes capaces de jugar de manera efectiva contra los mejores jugadores humanos.
Como trabajo futuro se planteará implementar versiones de los AGs más adaptadas al problema, que permitan conseguir una optimización mayor. Además, se probarán otros operadores genéticos, que puedan ofrecer mejor rendimiento. También se plantearán varios tipos de rivales, para que la evolución no esté condicionada por el nivel de agresividad que se haya definido y se consiga agentes capaces de enfrentar con éxito a oponentes ofensivo o defensivos, incluyendo pruebas contra jugadores humanos.
Este trabajo ha sido financiado en parte por el proyecto TED2021-131699B-I00, financiado por MCIN/AEI/10.13039/501100011033 y por la Unión Europea “NextGenerationEU”/PRTR, así como los proyectos PID2020-113462RB-I00 (ANIMALICOS) y PID2020-115570GB-C22 (DemocratAI:: UGR) del Ministerio español de Economía y Competitividad.