14 de octubre de 2016

Aprendizaje vivencial con juegos de estrategia

En la semana del 26 al 30 de septiembre de 2016 se llevó a cabo en el Tecnológico de Monterrey la segunda edición de un evento denominado “Semana i”. Una vez por año, durante una semana completa, se suspenden todas las clases de nivel licenciatura en la institución con el fin de que los estudiantes afronten y resuelvan un reto de tiempo completo:
El aprendizaje basado en retos se fundamenta en el aprendizaje vivencial, enfoque pedagógico que forma parte del Modelo Educativo Tec21 con el que se involucra activamente al estudiante en una situación o problemática real, relevante, y de vinculación con el entorno. Semana i implica la definición de un reto, su análisis y resolución y la implementación y evaluación de una solución. Así, se desarrollan o fortalecen las competencias profesionales y personales de los alumnos1.
En la Semana i 2016 más de 50 mil alumnos y 3 mil profesores participaron en 1,400 proyectos que se llevaron a cabo en 26 campus del Tecnológico de Monterrey. Cada alumno tuvo la opción de llevar a cabo su reto en su propio campus, en otro campus, en México o incluso en el extranjero.


Reto IA con juegos de estrategia

Para la Semana i 2016 el profesor Roberto Martínez Román, colega de mi departamento, y yo diseñamos durante varios meses un reto titulado “Introducción a la inteligencia artificial orientada al diseño y programación de juegos de estrategia”. La actividad estuvo dirigido a alumnos de segundo a quinto semestre de las carreras de Ingeniero en Sistemas Computacionales (ISC) e Ingeniero en Sistemas Digitales y Robótica (ISDR). El objetivo principal del reto consistía en que los estudiantes diseñaran y programaran en Python un jugador autónomo inteligente que fuera capaz de competir en un torneo de juegos de estrategia contra los programas elaborados por sus demás compañeros.


El reto procuró fortalecer las siguientes competencias disciplinares y transversales:
  • Uso de TI para la solución efectiva de problemas
  • Pensamiento lógico y algorítmico
  • Reflexión ética
Se inscribieron 57 alumnos en total (todos del Campus Estado de México), con los que se conformaron 20 equipos compuestos de 2 o 3 integrantes cada uno. Los estudiantes tuvieron la libertad de formar sus equipos y nombrarlos a su gusto.

Alumnos y profesores en el último día del reto

A continuación realizo un recuento de todas las actividades que conformaron nuestro reto durante la Semana i 2016.

Arrancando el reto

Desde unos días antes de comenzar el reto creamos un grupo de Facebook para servirnos como principal medio de comunicación entre instructores y alumnos. Ahí estuvimos publicando anuncios y fotos durante toda la Semana i (e incluso un poco después).

Grupo de Facebook

A las nueve de la mañana del lunes 26 de septiembre dio inicio nuestro reto. Comenzamos explicando lo que planeábamos hacer, presentando la página web del reto, y dando un espacio para la conformación de los equipos de trabajo. También aprovechamos para hacer una breve introducción a los conceptos de “inteligencia artificial” y “prueba de Turing”.

Alan M. Turing, padre de la inteligencia artificial

Concurso de programación

El mismo día lunes tuvimos un concurso de programación con la intención de que los alumnos tuvieran la oportunidad de recordar un poco cómo programar con Python. Cabe mencionar que todos nuestros estudiantes ya habían trabajado con Python anteriormente, al menos durante el curso Fundamentos de programación que llevan en primer semestre, sin embargo la mayoría tenía varios semestres de no utilizarlo.


Antes del concurso invertimos una hora en un taller de preparación. Para el taller y el concurso utilizamos la plataforma de programación competitiva omegaUp.com, la cual permite crear competencias en línea de manera bastante sencilla. En el taller se utilizó el problema titulado “El mayor de dos” para que los equipos se familiarizaran con los mecanismos necesarios para resolver y subir problemas de programación usando Python.

El concurso tuvo una duración de tres horas. Cada equipo, sin importar el número de integrantes, podía utilizar hasta dos computadoras: una para programar y enviar las soluciones, y la otra para revisar la documentación. Los siete problemas del concurso fueron los siguientes:
  1. Bit de paridad (100 puntos)
  2. Calculando divisores (100 puntos)
  3. Buscando el mayor (100 puntos)
  4. Tabla de factoriales (100 puntos)
  5. Multiplicación binaria (200 puntos)
  6. Perímetro de asteriscos (200 puntos)
  7. Conociendo la moda (200 puntos)
El juez en línea se encargó de evaluar las soluciones que enviaron los equipos y de llevar la cuenta de los problemas resueltos, el tiempo transcurrido de cada envío y las penalizaciones aplicadas por envíos de soluciones incorrectas.  Al terminar el concurso teníamos una tabla con todos los equipos rankeados del primer al último lugar.

El concurso de programación

El primer equipo en resolver todos los problemas del concurso tardó solo 40 minutos. Al finalizar el concurso, trece equipos habían resuelto correctamente los siete problemas.

Framework Dagor para juegos de estrategia

El martes por la mañana les presentamos a los alumnos el framework Dagor2. Yo me encargué de diseñar y programar este framework con el fin de utilizarlo como herramienta central para este reto. Muchas de las ideas de Dagor fueron tomadas del sitio Gamesman elaborado por el profesor Dan Garcia de la Universidad de California en Berkeley. El software y la documentación de Dagor están disponibles en la página del reto. Dagor es software libre y se distribuye bajo la licencia GPLv3.

Dagor sirve para programar diversos tipos de jugadores que compiten entre sí para ganar un juego combinacional. En teoría de juegos, un juego combinacional tiene las siguientes características:
  • Siempre hay dos jugadores que toman turnos para tirar de manera alternada.
  • No hay elementos aleatorios como dados o cartas barajadas.
  • Ambos jugadores tienen información perfecta (no hay información oculta).
  • El juego es finito — debe terminar eventualmente.
  • Usualmente el último jugador en tirar gana.
Dagor es un módulo de Python que implementa el patrón de diseño conocido como método de la plantilla (Template Method). De manera muy general, para escribir el código de un jugador inteligente se requiere escribir una clase que implemente dos métodos:
  • tira: Este método se invoca automáticamente por el controlador del juego cuando le toca al código de mi jugador realizar su tiro.
  • heuristica: Este método lo implementamos para poder evaluar diversas posiciones durante el juego y decidir cuál nos conviene más al momento de realizar nuestro tiro.
El código fuente de Dagor muestra cómo implementar diversas categorías de jugadores para diferentes juegos. Hay tres categorías de jugadores:
  • Jugadores aleatorios: Realizan tiros válidos pero siempre al azar, salvo que puedan producir en un momento dado un tiro ganador.
  • Jugadores interactivos: Permiten que un usuario humano interactúe con el juego a través de la consola y verifican que los tiros seleccionados sean válidos.
  • Jugadores estratégicos: Implementan una o varias estrategias que les permitan jugar de manera inteligente.
El código de los jugadores es modular e intercambiable. Esto significa, por ejemplo, que podemos tener un juego en donde un jugador aleatorio compita con un jugador estratégico. O podemos tener un juego con dos jugadores aleatorios, o cualquier otra combinación que deseemos. Juegos como estos, siempre y cuando no involucren usuarios humanos, se llevan a cabo muy rápido (en unos cuantos segundos), de tal forma que podemos darnos el lujo de tener encuentros compuestos de muchos juegos entre los mismos dos jugadores.

El taller de Dagor

El juego de Orugas

Concretamente, el reto de nuestros alumnos fue implementar un jugador estratégico inteligente con Dagor para el juego de Orugas. A continuación se encuentran las reglas de este juego.


Las reglas

Piezas y tablero: Este juego se juega en un tablero rectangular de n renglones por m columnas, donde 4 ≤ n ≤ 10, 4 ≤ m ≤ 10. Inicialmente cada jugador ocupa una localidad del tablero (la cabeza de la oruga), determinada de manera aleatoria.

Para tirar: Cada jugador controla una oruga que crece rápidamente a partir de su cabeza. Durante el turno de un jugador, éste debe seleccionar una localidad contigua vacía en la que pueda crecer la cabeza de su oruga. La oruga puede crecer hacia la localidad de arriba, abajo, izquierda o derecha, mas no en diagonal. Es posible crecer saliéndose de una orilla del tablero y llegar a su correspondiente localidad opuesta.

Para ganar: Un jugador gana cuando su oponente ya no tenga una localidad donde crecer.

En el tablero, el primer jugador usa el símbolo B (blanco) como cabeza y b para el resto del cuerpo. El segundo jugador usa el símbolo N (negro) como cabeza y n para el resto del cuerpo.

Ejemplo

El siguiente es un tablero de Orugas de 4 renglones por 5 columnas, donde las posiciones iniciales de B y N son determinadas de manera aleatoria:
   0   1   2   3   4 
0    |   |   |   |   
  ---+---+---+---+---
1    |   |   |   |   
  ---+---+---+---+---
2    |   |   | N |   
  ---+---+---+---+---
3    | B |   |   |   
B tira primero. Tiene la opción de moverse a la izquierda, a la derecha y hacia arriba. También puede moverse hacia abajo, pero como está en la orilla se iría al extremo opuesto del tablero (renglón 0, columna 1). El jugador decide moverse hacia arriba al renglón 2, columna 1:
   0   1   2   3   4 
0    |   |   |   |   
  ---+---+---+---+---
1    |   |   |   |   
  ---+---+---+---+---
2    | B |   | N |   
  ---+---+---+---+---
3    | b |   |   |   
Ahora es el turno de N y se mueve hacia abajo al renglón 3, columna 3:
   0   1   2   3   4 
0    |   |   |   |   
  ---+---+---+---+---
1    |   |   |   |   
  ---+---+---+---+---
2    | B |   | n |   
  ---+---+---+---+---
3    | b |   | N |   
El juego continúa de esta forma, alternando los turnos entre B y N. Finalmente, en el tiro número 11, el jugador B se mueve al renglón 0, columna 2:
   0   1   2   3   4 
0  b | b | B |   |   
  ---+---+---+---+---
1  b | N | n |   |   
  ---+---+---+---+---
2  b | b | n | n |   
  ---+---+---+---+---
3    | b | n | n |   
En este momento el jugador N está completamente bloqueado por lo que no puede moverse a ningún lado. Por tanto N pierde en este turno y B resulta el ganador de este juego.

Desarrollando el jugador estratégico

El tiempo con el que contaron los alumnos para diseñar e implementar su jugador estratégico fue relativamente corto: desde el martes por la tarde hasta el jueves por la mañana.

En esencia, los alumnos tuvieron que programar una manera de evaluar qué tan buenas o malas eran ciertas posiciones en el juego y seleccionar la que les daba una mejor ventaja en cada tiro. Podían considerar, por ejemplo, qué tantas opciones de movimiento quedaban disponibles para su jugador después de un tiro, o qué tanto podían alejarse del jugador contrario con el fin de evitar un posible bloqueo más adelante. Hubo un equipo que diseñó una estrategia para cuando eran los segundos en tirar, y ésta consistía en imitar como espejo los tiros del contrario bajo el supuesto de que perdería primero por bloquearse solo. 

El miércoles antes del medio día los instructores realizamos una revisión del avance de cada equipo con el fin de verificar que estuvieran trabajando adecuadamente y resolver cualquier duda que pudieran tener. Ese mismo día por la tarde tuvimos un pre-torneo voluntario. Los equipos que quisieron pudieron competir entre sí para tener una idea más clara de qué tan efectivo estaba siendo su código. Seis de los veinte equipos participaron en este pre-torneo.

A todos los estudiantes se les permitió observar el pre-torneo, sin importar si su equipo estaba participando o no. Sin embargo, no se permitió que los equipos vieran el código de los demás, solo que vieran los resultados de los encuentros. El pre-torneo también sirvió para que los instructores nos percatáramos de las dificultadas logísticas que podrían llegar a presentarse al día siguiente en el torneo real. Nos dimos cuenta de que era necesario automatizar el proceso del torneo lo más que pudiéramos, de otra forma resultaría demasiado tardado.

El pre-torneo

Torneo de estrategias

El momento de la verdad por fin llegó. El jueves a las 11 de la mañana nos dimos cita en el salón de congresos del campus para llevar a cabo el torneo de estrategias. Los equipos debían habernos enviado por correo electrónico sus programas antes de la hora señalada. Cada programa se inspeccionó manualmente para verificar que fuera un módulo válido de Python y que no tuviera código malicioso o instrucciones prohibidas (acceso a Internet, manipulación de archivos, creación de procesos externos, etc.).

Se definió al inicio del torneo que cada encuentro consistiría de 100 juegos en un tablero de 7 renglones por 6 columnas, en donde cada tiro debería efectuarse en menos de 3 segundos. Durante el desarrollo del proyecto los alumnos desconocían el tamaño que tendría el tablero durante el torneo, solo sabían que los renglones y columnas estarían entre 4 y 10. El turno inicial de cada juego se iría alternando entre los dos jugadores, es decir, el primer jugador comenzaría 50 juegos del encuentro y el segundo jugador comenzaría los otros 50.

Inicialmente el programa de cada equipo se enfrentó al jugador aleatorio provisto por Dagor. A los equipos que ganaran al menos 60 de los 100 juegos de este encuentro se les brindarían 20 puntos extra sobre la calificación final del reto. De nuestros veinte equipos, solo dos no lograron cubrir este objetivo.

Cerca de la una de la tarde, y después de resolver varias dificultades técnicas, comenzamos el torneo de todos contra todos. En total hubo 190 encuentros (el número de combinaciones de 20 elementos tomando 2 a la vez) cada uno consistiendo de 100 juegos. Cada equipo recibió una cierta cantidad de puntos dependiendo del resultado de cada encuentro:
  • 3 puntos si ganó 51 juegos o más
  • 1 punto si ganó exactamente 50 juegos
  • 0 puntos si ganó 49 juegos o menos
El ranking de cada equipo en el torneo se determinó por el total de puntos obtenidos.

Se utilizaron múltiples scripts para automatizar todo el proceso del torneo, desde la ejecución de los encuentros hasta la contabilización de los resultados. La mitad (aproximadamente) de los encuentros se corrieron en la computadora portátil del profesor Roberto Martínez, y la otra mitad en mi computadora. Se utilizó una tercera computadora para ir proyectando a la audiencia los resultados conforme se iban obteniendo3.

Después de un poco más de dos horas, el torneo había terminado. El equipo que obtuvo el primer lugar investigó e implementó el algoritmo minimax con poda alfa-beta. Esto le permitió ser el vencedor en sus 19 encuentros, 7 de los cuales ganó 100 juegos a 0. El segundo lugar solo perdió un encuentro, y el tercer lugar perdió dos.

El torneo

Conferencia del Dr. Edgar Vallejo

El viernes estuvo mucho más relajado que los días anteriores. Ese día tuvimos el honor de contar con la presencia del Dr. Edgar Emmanuel Vallejo Clemente, profesor de nuestro departamento, quien nos presentó la conferencia titulada “Predicción de epidemias de Zika usando redes sociales y redes de contacto vectorial”. 

El profesor Edgar Vallejo en su conferencia

La plática fue sobre el proyecto que está siendo elaborado por el Dr. Vallejo y su alumno de doctorado Héctor Manuel Sánchez Castellanos. El objetivo es que a través de un modelo informático sea posible estimar el riesgo de infectarse con el virus del Zika. Este modelo permitirá que se haga una predicción temprana de brotes para que se tomen las medidas necesarias para el control de la enfermedad. El proyecto fue uno de los ganadores los Premios de Investigación en América Latina de Google 2016. El premio consistió en un apoyo económico para que los involucrados puedan llevar a cabo sus investigaciones.

Reflexión ética

El mismo día viernes les proyectamos a los alumnos la película “Ex Machina (2015)”.  Esta reciente cinta británica es una excelente película de ciencia ficción que trata sobre un joven programador que es seleccionado para ser el juez en una prueba de Turing, en donde deberá evaluar las cualidades humanas presentes en la I.A. de un asombroso robot humanoide con forma femenina. El filme permite abrir una discusión y reflexión muy interesante sobre los conflictos morales que podríamos afrontar al interactuar con máquinas que se comportan con una inteligencia similar a la de los seres humanos.

Alicia Vikander, Domhnall Gleeson y Oscar Isaac
protagonizan “Ex Machina (2015)”, A24 Films.

Al finalizar la película, les pedimos a los alumnos que respondieran en equipo a las preguntas de discusión de RameyLady tomadas de su sitio web Just:Words.

Premiación

Como última actividad del día viernes, entregamos reconocimientos a los equipos que obtuvieron los primeros tres lugares tanto en el concurso de programación como en el torneo de estrategias. Y con esto clausuramos nuestro reto de la Semana i.

Los profesores responsables del reto, Ariel Ortiz y Roberto
Martínez, con el equipo nokygerand, ganador del
primer lugar tanto del concurso de programación como
del torneo de estrategias. El equipo está integrado
por Andrés de Lago Gómez y  Gerardo Galván Olvera,
ambos alumnos de tercer semestre de la carrera ISC.

Documentando la experiencia

Durante toda la semana cada equipo fue documentando en su propio blog las impresiones y experiencias de las actividades que se fueron realizando. A continuación se listan los blogs de todos los equipos:

Conclusión

Nuestra Semana i 2016 resultó, tanto para los alumnos como para los instructores, un evento bastante agotador pero con un saldo final positivo. Me sentí muy complacido con los resultados obtenidos. Los comentarios de la mayoría de los alumnos fueron en general muy favorables.

Este fue un comentario bastante alentador tomado del blog del equipo rebelcoder:
Este reto me resultó grato desde muchos aspectos y considero que también me llevo muchas experiencias y aprendizajes nuevos. Los principales aprendizajes que me llevo tienen que ver con el “diseño e implementación de una solución de software ante un problema”, ya que la mayoría de los proyectos en los cuales he estado normalmente sabíamos el proceso para llegar a la solución o conocíamos la solución y aplicábamos reingeniería. En cambio en este reto no conoces el proceso para llegar al final ni tampoco la solución final para el problema del juego de Orugas, generando que nosotros tuviéramos que idear muchos algoritmos, casos de prueba y comparar otras soluciones para ver cuál era la mejor.
Este reto de la Semana i enfocado en el desarrollo de una Inteligencia Artificial en un Juego de Estrategia me gustó mucho y la verdad me agradaron mucho todas las actividades que hicimos. Lo que más me emocionó fue el torneo en sí cuando nosotros veíamos los resultados de cada uno de los enfrentamientos entre nuestros códigos y al final cuando nos enteramos del lugar en que quedamos. Gracias profesor Ariel y profesor Roberto por haber realizado esta actividad para nosotros.
— Servio Reyes
Hubo algunos detalles que nos señalaron varios participantes en cuestión de posibles mejoras. Un tema recurrente fue el manejo de los tiempos, al parecer muchos equipos hubieran querido contar con más tiempo para implementar su jugador estratégico. Algunos también sugirieron que se le permitiera al equipo ganador exponer ante los demás la manera en que diseñaron su solución. Me parece que vale mucho la pena considerar estos comentarios para mejorar el reto para cuando se llegue a ofrecer nuevamente en un futuro.


1 Inicia la segunda edición de Semana i con más retos en movimiento.

2 La palabra Dagor significa “batalla” en el idioma sindarin (conocido también como élfico gris), creado por el escritor británico J. R. R. Tolkien, autor del “Señor de los anillos”.

3 Lo que se estuvo proyectando realmente eran los resultados de unos comandos de SQL que tecleaba en el momento para consultar la base de datos con los resultados. Por falta de tiempo no pude automatizar esta parte del proceso.