jueves, 20 de enero de 2011

Skynet se une al enjambre: cómo la Supermente Berkeley ganó la competencia de StarCraft AI (Inteligencia Artificial) del 2010 (Parte II)

...vienen de la primera parte.

"Se requiere más gas vespeno"
La primera cosa que nuestro agente tenía que hacer era reunir recursos y construir edificios y unidades. Esto es a la vez muy fácil y muy difícil. Hay estrategias de apertura muy populares, conocidas y bien estudiadas en la comunidad de StarCraft, estrategias que definen las secuencias en la producción de edificios y unidades. Como aperturas de ajedrez, que están diseñadas para equipar el jugador con una configuración de juego en particular, para la transición a estrategias en la mitad del juego. Hay aperturas para primeros ataques con unidades ligeras, hostigamiento aéreo, construcción de fuerzas pesadas para mediados o finales de juego, y así sucesivamente.
Estas aperturas están bien optimizadas, y es tentador elegir sólo una o varias y codificar las macros del agente como un conjunto de secuencias de comandos o estados finitos de máquinas. Así funcionan los AI incorporados de StarCraft y de muchos otros juegos: el conocimiento experto humano se codifica como una secuencia explícita de acciones, con transiciones predefinidas. Construir tanques a menos que el enemigo construya unidades de aire, a continuación, crear unidades anti-aéreas. Si el enemigo fabrica unidades invisibles, construir detectores, y así sucesivamente. La versión antigua de nuestro agente esencialmente utilizaba este enfoque, jugando como los terran y masificando tanques. Tal vez lo primero que aprendimos fue que este no era el mejor enfoque.
Aprender esta lección implicó un momento de vergüenza. Siempre había habido una especie de impulso Deep Blue-contra-Kasparov detrás de nuestro agente, y StarCraft es un reto, precisamente porque es un juego donde los seres humanos lo hacen bien y AI lo hace mal. Así que la única manera de probar y mejorar realmente el agente sería jugar contra jugadores humanos calificados. Orgullosos de que el agente pudiera derrotar a los IA integrados, jugamos un juego durante la clase en contra de John Blitzer, un post-doc en el grupo de Dan que jugó partidos en la Ciber Copa Internacional (iCCup).

Fue un desastre. 

Blitzer utilizó una táctica conocida como robo de gas, enviando una unidad de trabajo a la base de nuestro agente para construir una refinería sobre nuestro géiser de gas vespeno (uno de los recursos en el juego). Esto impidió que el agente recolectara gas hasta destruyera la refinería de Blitzer y construyera la propia. La medida fue totalmente inesperada, y nuestro agente, cuya estrategia de fabricar tanques era fuertemente dependiente del gas, estaba desconcertado por completo. Blitzer fue capaz entrar y demoler la base del agente, mientras el esperaba a construir tanques con un gas que no tenía. Habíamos pensado que Blitzer podría derrotar a los tanques de nuestro agente con una mejor táctica, pero nunca llegamos a ese punto en el juego. 

"Lo siento si el partido se fue un poco diferente de lo planeado", señaló Blitzer en un e-mail después analizar el juego. Fue un eufemismo. Pero también fue una lección muy valiosa: el agente debía de ser robusto frente a las interrupciones, o simplemente se quedaría atorado.
Una forma de lograr alguna robustez es para un programador humano la previsión de las posibilidades y la codificación de las respuestas. Es difícil evitar hacer algo así, pero para un sistema tan complejo como StarCraft, es imposible contabilizar todas las situaciones de antemano. Esta es también la razón por la que la IA resulta ser bastante fácil de superar: hay brechas en su lógica que, una vez encontradas, se puede explotar una y otra vez.
El vídeo abajo muestra un ejemplo de esto. Está protagonizado por Sparky el Drone Maravilla, nuestro scout de inicios de juego y mascota de facto del equipo . El encuentro con el "robo de gas" generó un saludable respeto por las tácticas poco ortodoxas de inicios del juego, y hemos incorporado algunas de estas en nuestro agente. 
En el video, Sparky ataca los trabajadores de la AI incorporada, que han sido programados para responder a un ataque contra atacando, pero que no estaban programados para saber cuándo parar. Sparky termina aquí con "el robo de gas", pero es fácil arrastrarlos en una alegre persecución indefinidamente, evitando que el AI incorporado recoleccione recursos y construya unidades. Las travesuras de Sparky son tan devastadores contra la IA incorporada, que tuvimos que desactivarla durante la prueba o nunca llegábamos a las últimas etapas del juego.



La respuesta a las travesuras de Sparky requiere una cierta cantidad de comportamientos específicamente humanos, pero la solución a la gestión de recursos y a la planificación de las construcciones necesitaba de un enfoque más flexible. La estructura resultante de planificador de construcciones del agente se asemeja a la del planificador de recursos de un sistema operativo. Acciones diferentes, análogas a los procesos, la petición de recursos como minerales, gas, o unidades desde el planificador central de la Supermente, que a continuación, intenta responder a las solicitudes por orden de prioridad. Esta arquitectura nos dio una gran flexibilidad. 
David Hall es un estudiante de doctorado en el grupo de Dan, y uno de los líderes del equipo. El planificador de construcciones "básicamente agrupa todas las cosas que se podían hacer, y luego elige la mejor en cualquier momento", dice. En lugar de tener una secuencia fija de edificios y unidades para producir una tras otra, especificamos combinaciones deseadas de edificios y unidades y dejamos al planificador que intentara alcanzar los objetivos de la mejor manera posible.
Esto nos dio un procedimiento mucho más robusto que el simple hecho de tener un orden fijo de construcción. Cuando algún evento inesperado como la acción del enemigo retrasa ciertos procesos, el agente ya no se congela esperando el próximo movimiento. Cuando un oponente logra robar gas, el agente simplemente amplia su base a un géiser en otro lugar o cambia automáticamente a la creación de edificios y unidades en su plan que no requieren de gas hasta que la situación del gas se ha resuelto. 
En última instancia, las secuencias que produce el planificador se parecen mucho a las aperturas de expertos en la Internet, pero con la capacidad para apartarse de sus planes y buscar soluciones alternativas. Esta flexibilidad y robustez es esencial para ganar en StarCraft, tanto para los jugadores humanos como para IA. El tema de la sustitución de acciones específicamente humanas, con herramientas que permitan al agente razonar y tomar sus propias decisiones se ha repetido una y otra vez para nosotros, en todos los aspectos del juego.

"Sabed que yo soy la Mente Suprema, la voluntad eterna de la colmena ..."

Para el verano de 2010, la infraestructura básica para las unidades de producción estaba en su lugar, y era hora de encontrar la manera de usarla. El agente necesario para el control de sus tropas en combate, la selección de objetivos y las unidades móviles para obtener una ventaja táctica. El reto aquí era a la vez logístico, así como técnico: la fecha límite de la competencia era en septiembre y se nos acababa el tiempo. 
Tuvimos que limitarnos. David Burkett, otro de los estudiantes de doctorado de Dan y lider del equipo, dice: "Resulto que la construcción de nodos de control para las unidades es difícil, así que hay un enorme costo asociado a la construcción de más de un [tipo de] unidad. Así que empezamos preguntándonos: ¿qué un tipo de unidad [sería] la más eficaz en general "


Centramos nuestros esfuerzos en los mutaliscos Zerg: rápidas, criaturas voladoras parecidas a dragones que pueden atacar tanto a objetivos en tierra como en el aire. Su movilidad no tiene igual, y sospechábamos que serían particularmente susceptibles al control por ordenador. Los Mutaliscos son baratos para lo fuertes que son, pero es raro verlos en gran número en juegos humanos, porque es difícil para un ser humano controlarlos sin que se aglomeren y sean presa fácil para enemigos con ataques de área (los ataques que hacen daño a todas las unidades en un área en lugar de un solo objetivo). Una computadora no tendría tales limitaciones. 
Además, el diseño de una IA para dirigir el enjambre Zerg era atractivo, y el equipo siempre había querido nombrar el agente después de la Mente Suprema, la mente que controla la colmena de los Zerg en la historia de StarCraft. Dan formuló la única objeción posible: "Ustedes saben, desde la perspectiva de la financiación que probablemente será más fácil si nuestra AI controla fuerzas humanas en lugar de dirigir babosas hordas alienígenas ..."

En teoría, una computadora deber ser buena controlando múltiples unidades de manera simultánea, dado que no tiene la limitación de la velocidad humana. De hecho, hay un error muy común y es que debido a que StarCraft es en tiempo real, deba ser un juego de reflejos. Pero mientras que la velocidad es útil e importante, no es un sustituto para saber tomar decisiones correctas. Una gestión adecuada de las unidades requiere la toma de decisiones inteligentes. Tan solo mover los mutaliscos en la demanda del combate requiere alguna sofisticación. Los mutaliscos necesitan volar hacia sus objetivos, pero deben mantenerse alejados de otros enemigos, necesitan concentrar su potencia de fuego, pero dispersarse cuando se enfrentan a unidades enemigas con ataques de área. Para colmo, decenas de mutaliscos debe hacer esto de manera sincrónica.
Para manejar estos problemas y limitar la sobrecarga computacional, nuestro agente usa campos potenciales artificiales para el movimiento de las unidades. El controlador de campo potencial genera fuerzas virtuales que mantienen los mutaliscos alrededor, equilibrando las fuerzas de atracción sobre los objetivos con las fuerzas de repulsión sobre las amenazas. Sumando las fuerzas que actúan sobre un mutalisco nos da una dirección de vuelo, dando lugar a un esquema de control sencillo pero robusto. Nos ayuda el hecho de que las unidades aéreas como los mutaliscos no se atascan en los obstáculos o entre sí.
El control de campo potencial es muy poderoso. Por ejemplo, las maniobras de ataque y retirada se pueden crear mediante la simple eliminación de los potenciales de atracción a blancos después de lanzar un ataque; los potenciales de repulsión a las amenaza automáticamente mantienen a los mutaliscos bailando fuera de rango en espera recargas para atacar. Los potenciales de atracción reúnen al grupo para concentrar el fuego, pero si aparece una amenaza de ataque de área, aparece un potencial de repulsión que hace que el clúster se disperse de manera rápida. 
El siguiente video se muestra este comportamiento en un enfrentamiento con Arcontes Protoss, poderosas unidades anti-aéreas. Con los campos de potencial ", se obtienen ciertos comportamientos deseados que simplemente emergen", dice David Burkett.



Continuará ......