Los juegos siempre han estado ligados al desarrollo de las técnicas de inteligencia artificial. Por un lado, poseen la característica de tener el conocimiento estructurado, las acciones finitas y o bien son deterministas o su incertidumbre es "medible". Esta relación se mantiene en la actualidad, basta revisar la prensa de los últimos años para contrastar los avances acaecidos en el diseño de jugadores automáticos basados en técnicas de inteligencia artificial y aprendizaje automático para juegos de mesa como el ajedrez o Go, pero también en el mundo de los vídeojuegos. Existen diversas "familias" de juegos. En este Trabajo Fin de Grado nos vamos a centrar en juegos de estrategia. Denrro de esta familia existen los de tiempo real (RTS) y los por turnos (TBS).
En concreto, el juego escogido: Lux Ai, se consideraría de tipo TBS, que son los más parecidos a sus primos lejanos, los juegos de estrategia de mesa. En ellos, cada jugador tendrá un turno para realizar sus movimientos. En el cual, el o los oponentes no podrán realizar ninguna otra acción. De esta forma se les da a los jugadores tiempo para pensar sus jugadas. Las reglas particulares de este juego se pueden encontrar en su página web: https://www.lux-ai.org/specs-2021 Como particularidad, aunque hay turnos, los dos jugadores los juegan simultáneamente.
Como se puede ver se trata de una implementación reciente, de este mismo 2021, y la semilla que motiva el planteamiento de este trabajo es que existe una competición en la plataforma Kaggle asociada a él cuyta dirección web es https://www.kaggle.com/c/lux-ai-2021 Creemos que esto proporcionará retro-alimentación en el trabajo, ya que no sólo se puede intentar subir nuestros agentes y medir su desempeño global contra contricantes especializados (que es posible que nos superen), sino que se podrá participar activamente de los foros y las discusiones.
Muy resumido, en el juego hay dos jugadores que compiten por conseguir el mayor número de ciudades posibles en el espacio/mapa. Cada jugador trata de obtener recursos (madera, carbón, uranio) , para obtener unidades, y estas son capaces de construir ciudades. Al final del juego ganará el jugador que más ciudades haya conseguido.
El principal propósito de este trabajo es desarrollar algoritmos basados en sistemas imteligentes capaces de jugar al Lux Ai, y estudiar su desempeño. El problema es complejo porque el número de acciones posibles a realizar en un turno son muchas, y además las unidades se interrelacionan, con lo cual hay que buscar un enfoque global o colaborativo. Por ejemplo, técnicas básicas como estrategias de búsqueda A* por sí solas no serían factibles por esta complejidad/dimensionalidad.
Pretendemos probar diferentes técnicas, comenzando con heurísticas básicas, como baseline. La principal línea de actuación sería la de crear agentes basados en reglas, con mayor y menor complejidad, pero no descartamos explorar otras técnicas de IA. Al ser un problema inherentemente multi-agente y con contrincante, vamos a intentar aplicar aprendizaje por refuerzo. El Q-Learning clásico tampoco sería posible, debido a la gran cantidad de estados alcanzables, por lo que se va a estudiar la posible aplicabillidad del MARL (Multi Agent Reinforcement Learning). Finalmente y visto que hay trabajos donde los algoritmos genéticos se han podido emplear para RTS, también se podría abarcar esta dirección, según los resultados obtenidos y los avances conseguidos.
En definitiva, se tratará de buscar qué tećnicas de sistemas inteligentes nos parecen más idóneas para el problema (teniendo en cuenta los conocimientos y recursos disponibles), diseñar los algoritmos (y variantes) resultantes, hacerlos jugar para compararlos entre sí, y poder medir su desempeño.
1. Documentación sobre el planteamiento del juego: conocimiento de las reglas, principales estrategias, sistemas de puntos, etc… (representación del conocimiento)
2. Estudio del código y desarrollo de algunos agentes sencillos que serán nuestro propio baseline.
3. Diseño de agentes basados en reglas. Experimentación para medir su desempeño.
4. Estudiar la aplicabilidad de aprendizaje por refuerzo. Intentar desarrollar agentes basados en MARL y/o en algoritmos evolutivos. Experimentación si se consigue algún agente de desempeño razonable.
5. Comparativa entre los agentes propios, analizando las diferentes familias y también las parametrizaciones o variantes.
6. Comparativa con otros que puedan existir en la plataforma, y subida de los agentes a Kaggle para comprobar su desempeño global.
7. Análisis general de los resultados.
8. Redactar la memoria.
COMPETENCIAS
Este TFG permite completar las competencias específicas [CM3], [CM5] ,[CM6] y [CM7] de la Intensificación de Computación, es decir, se trabajarán principalmente (en distinto grado) las siguientes competencias específicas de la tecnología de computación:
- [CM3] Capacidad para evaluar la complejidad computacional de un problema, conocer estrategias algorítmicas que puedan conducir a su resolución y recomendar, desarrollar e implementar aquella que garantice el mejor rendimiento de acuerdo con los requisitos establecidos.
- [CM5] Capacidad para conocer los fundamentos, paradigmas y técnicas propias de los sistemas inteligentes y analizar, diseñar y construir sistemas, servicios y aplicaciones informáticas que utilicen dichas técnicas en cualquier ámbito de aplicación.
- [CM6] Capacidad para adquirir, obtener, formalizar y representar el conocimiento humano en una forma computable para la resolución de problemas mediante un sistema informático en cualquier ámbito de aplicación, particularmente los relacionados con aspectos de computación, percepción y actuación en ambientes entornos inteligentes.
- [CM7] Capacidad para conocer y desarrollar técnicas de aprendizaje computacional y diseñar e implementar aplicaciones y sistemas que las utilicen, incluyendo las dedicadas a extracción automática de información y conocimiento a partir de grandes volúmenes de datos.
