Programando Un jugador Estratégico

Para el diseño e implementación de nuestro nuestro proyecto de jugador de estrategias para el juego de orugas comenzamos con un paso muy simple, pero que ahora hemos descubierto fue muy importante. Desde el inicio sabíamos que (con la información perfecta o completa) tendríamos que buscar (para cada tiro) la mejor respuesta posible que podríamos dar, de la misma forma desde los primeros instantes supimos que en la mayoría de los estados del juego es imposible buscar la mejor movida ganadora en un tiempo razonable. Así se nos presentó el problema de juzgar el estado de un juego. Sin iniciar el desarrollo de ninguna pieza de código jugamos el juego en una pizarra por horas hasta que nos encontramos con una noción concreta de cómo juzgar qué tan bueno es un estado.

Después comenzamos con nuestra implementación, que se hizo compleja bastante rápido. Con la complejidad nuestra dificultad fue el refinamiento y debugging dado que con el tiempo nos damos cuenta de que nuestras implementaciones no representaban nuestra idea como tal ni seguían nuestro algoritmo planeado (aunque aún así venció).

La estrategia que nosotros utilizamos para jugar es más una técnica que estrategia ya que nosotros no pensamos en la estrategia como tal, o sea que no buscamos las esquinas o seguimos al otro jugador ni nada por el estilo. Implementamos el algoritmo Alpha-Beta Pruning que es una optimización de Mini-Max, un algoritmo muy básico de búsqueda adversarial. Lo que si creamos nosotros fue la función de evaluación de nodos o heurística. Está busca maximizar el control del nuestro mientras minimiza el del oponente.
Nos encontramos un millar de dificultades a la hora de implementar esto, primero habíamos tenido un error de signo al comparar algunos valores del algoritmo como tal, después nuestra función de evaluación tomaba demasiado tiempo ya que utilizaba búsqueda de tipo DFS, además en algunos estados calculaba erróneamente, en general no funcionaba, al menos durante todo el primer día. El segundo día logramos hacer que funcionara y les ganó a todas las demás soluciones por grandes márgenes, pero al querer optimizarlo nos dimos cuenta que la solución que usábamos en realidad no funcionaba para nada, no evaluaba bien los estados, no propagaba bien los valores de la búsqueda y perdía algunos estados. De nuevo empezamos de casi cero, hicimos nuestras propias implementaciones de las funciones que utilizábamos mucho de dagor, creamos una nueva representación de estado y en general cambiamos la mayor parte de la estructura sin cambiar la lógica, en ese momento nos dimos cuenta que no funcionaba y estuvimos como 8 horas reparando todos los bugs que encontramos hasta que la solución a la que llegamos le ganaba a la del día anterior por los mismos márgenes que la otra a los demás equipos.


Tomando en cuenta lo anterior estamos esperando un muy buen resultado mañana.