miércoles, 19 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 I)

En el 1999 detrás de casa de mi hermana vivía  un cuate que no mas se la pasaba pegado a una PC que había armado de trozos recogidos de aquí y de allá. Era bueno programando, pero era igual de bueno jugando y cada juego que salía y valía la pena tarde o temprano lo tenía en la PC (Duke Nukem, Quake, Heretic, Monkey Island, todos los conocí ahí).  Una tarde mi hermana me dijo "ven para que veas el juego que tiene René.." cruzamos la barda de atrás de la casa (nunca se tomaron la molestia de dar la vuelta por la esquina) y vi por primera vez el juego. Unos hombrecillos recogían minerales y gas y construían estructuras y unidades, para luego atacar otras dos razas que convivían con ellos en el mapa (unos bichos y otros que parecían lagartijas con armaduras). No me llamó mucho la atención, pero pasado un tiempo pude meterle las manos y poco a poco caí en el vicio. Era el año 1999 y casi acababa de salir StarCraft Brood War. Jugábamos en red en aquel entonces unos contra otros y cuando me quedaba solo jugaba contra la máquina (llegue a ganar contra tres máquinas en meleé). Creo que es el mejor juegos de ETR que se han hecho (y Blizzard ha hecho varios buenos). Este artículo lo encontré en la mañana (es de ars technica) y ni lo pensé dos veces (perdonen las deudas, eventualmente todas saldrán adelante). Es la historia de el desarrollo de un agente de IA que diseñaron en Berkeley (ahí mismo, de donde es FreeBSD) valiéndose de que publicaron una API para acceder al juego. Ojo, estamos hablando de la versión vieja, la del 98 y la historia es en tiempo pasado (sucedió en el 2010). El año pasado salió SC2 (es lo que hago después de postear) que es otra historia. Este es largo, va en varias partes así que go go go!!

Skynet se une al enjambre: cómo la Supermente Berkeley ganó la competencia de StarCraft AI (Inteligencia Artificial) del 2010
Estamos reunidos en una sala de conferencias en el campus de Berkeley, los detritus de una LAN party dispersos alrededor de nosotros. La mesa está cubierta con computadoras y pizza, y hay un juego de StarCraft proyectado en la pantalla. Oriol Vinyals, un estudiante de doctorado en ciencias de la computación, es el comandante del ejército Terran en una batalla de vida o muerte contra las fuerzas del enjambre Zerg.
Oriol es muy bueno, fue competidor del World Cyber Games, el número 1 en España, está en el top 16 en Europa. Pero su situación actual es precaria: sus Goliath están conteniendo los mutaliscos volantes de los Zerg, pero no pueden estar en todas partes al mismo tiempo. El jugador Zerg es astuto, retrocede ante una potencia de fuego superior, pero no se aleja, eligiendo objetivos oportunos y aplicando una presión constante.
Entonces Oriol comete un error. Mueve el Goliath ligeramente fuera de posición, sólo por unos segundos. Es suficiente. Los mutaliscos reaccionan al instante, introduciéndose a través de la brecha en sus defensas y dirigiéndose directamente a sus trabajadores vulnerables. Para cuando Oriol trae al Goliath de nuevo para eliminar a los mutaliscos, sus trabajadores son eliminados y la producción de recursos queda de rodillas. 
Oriol hace un ataque desesperado de última hora en la base zerg, tratando de destruirla antes de que los mutaliscos se refuercen, pero es demasiado tarde. Uno tras otro, sus Goliats son destrozados por las defensas Zerg. Con cada nueva ola de mutaliscos que sale de los criaderos zerg, no tiene más remedio que ceder a la Inteligencia Artificial que acaba de derrotarlo.



Hay un aire palpable de celebración en la sala, incluso Oriol está sonriendo. Ha sido derrotado por la Supermente Berkeley, un agente de IA en el que nuestro equipo en la sala ha pasado los últimos meses trabajando. La Supermente es nuestra entrada en la Competencia AI de StarCraft de 2010, y después de decenas de partidos de prueba, finalmente ha derrotado a nuestros expertos humanos en StarCraft por primera vez
Tenemos nuestro momento de gloria, de afirmación del yo, como un John Henry invertido, pero no hay tiempo para saborearlo. Con tres días antes de la presentación final del código, nuestro equipo tiene un montón que pulir y depurar aún. El profesor Dan Klein, nuestro consejero de la facultad, en general, entrenador en jefe, y la fuerza impulsora, sonríe brevemente y vuelve a la pizarra. Se detiene frente a uno de los 20 escenarios de prueba que aún tenemos que ejecutar.

"Está bien", dice. "Podemos vencer a los Goliath. - ¿Qué sigue?

Esta es la historia de cómo nuestro equipo creó la Supermente Berkeley, y las tecnologías que utilizamos.

Construir un futuro mejor a través de la prisa de los Zerg.
StarCraft es uno de los juegos más populares de siempre, un gran éxito de una compañía conocida por sus lanzamientos. Exige una gran habilidad de sus jugadores, y es uno de los pilares de las ligas de juego profesional. En Corea, el juego es tan popular que los jugadores profesionales de Starcraft son celebridades con contratos de seis cifras y sus juegos son transmitidos en vivo por la televisión nacional. 
También es un campo muy difícil para la inteligencia artificial,  un agente IA exitoso de StarCraft debe tratar de resolver una serie de problemas difíciles. Dan, que también imparte la clase de introducción a IA, en Berkeley, dice: ".. literalmente, puedo caminar por la lista de conceptos que abarcamos y mostrarle donde se evidencia cada uno de ellos en el juego y en nuestro agente." 
StarCraft fue lanzado en 1998, una eternidad para los estándares de los videojuegos. Durante esos años Blizzard Entertainment, creador del juego, ha actualizado el juego continuamente de modo que es uno de los Juegos de estrategia en tiempo real más afinados y equilibrados de la historia. Cuenta con tres razas jugables: los terran parecidos a los humanos, con familiares tanques y naves espaciales, los Zerg alienígenas, con grandes enjambres de criaturas orgánicas, y los Protoss, alienígenas tecnológicamente avanzados que dependen de unidades poderosas, pero caras. Cada raza tiene unidades y filosofías de juego diferentes, sin embargo, ninguna raza o combinación de unidades obtiene una ventaja insuperable. La habilidad del jugador, el ingenio y la capacidad de reaccionar de forma inteligente a las acciones enemigas determinan la victoria.
Este refinamiento y complejidad hace de StarCraft un ambiente ideal para la realización de investigaciones de Inteligencia Artificial. En un juego de estrategia en tiempo real, se desarrollan los acontecimientos en tiempo real y las órdenes de los jugadores se llevan a cabo de inmediato. Tienes que recolectar recursos de manera que puedas producir unidades de combate y mandarlas a la batalla. El mapa está envuelto en una niebla de guerra, por lo que las unidades y edificios enemigos sólo son visibles cuando están cerca de unidades o edificios amigos. Un jugador de StarCraft ha de adquirir y distribuir los recursos para crear unidades, coordinar las unidades en combate, descubrir, razonar y reaccionar ante las acciones enemigas, y hacer todo esto en tiempo real. Todos estos son problemas difíciles para ser resueltos por una computadora. 
Dan a veces compara StarCraft con otros juegos que han impulsado la investigación de AI en el pasado. "El ajedrez es difícil porque tienes que predecir el futuro, y es difícil avanzar porque hay un montón de piezas. En el póquer hay incertidumbre ", dice. "En StarCraft, tiene todo esto sucediendo a la vez, y tienes muy poco tiempo para calcular una solución".
Excelentes jugadores humanos resuelven estos problemas a través de la práctica y la formación, la acumulación de un almacén extenso de habilidades y conocimientos de expertos. Es simplemente imposible integrar este conocimiento humano en un agente de inteligencia artificial, dado que el agente debe razonar activamente sobre el mundo del juego y las posibles acciones futuras. Crear una IA de StarCraft que pueda enfrentar seres humanos requiere llevar hasta el límite lo que es posible actualmente con los ordenadores, con beneficios potenciales en aplicaciones mucho más allá del juego.
La competencia IA de StarCraft fue creada para aprovechar y promover StarCraft en un entorno de investigación. los investigadores de IA han utilizado los juegos RTS (Real Time Strategy) en el pasado, pero sus esfuerzos se vieron obstaculizados por la tecnología disponible. Los juegos de código abierto eran defectuosos y no probados, y los juegos comerciales como StarCraft eran inaccesibles. 
Esto cambió a principios de 2009 con el lanzamiento de la API de Brood War (BWAPI), un conjunto de herramientas de código abierto desarrollado por un grupo de entusiastas que da acceso directo al juego. Ben Weber, un estudiante en el Estudio de Inteligencia expresiva de la UC Santa Cruz, había estado trabajando en investigaciones basadas en juegos de estrategia en tiempo real basado en el juego. Se dio cuenta de que StarCraft y BWAPI podrían tener un impacto inmediato en su trabajo y ser una herramienta valiosa para la comunidad de IA. Se dedicó a organizar un torneo de agentes de AI de StarCraft para competir unos contra otros con la esperanza de impulsar el progreso y aumentar el interés. 
El anuncio para el torneo se realizó en noviembre de 2009, y la palabra pronto se esparció en los sitios web de juegos y blogs: la Conferencia de Inteligencia Artificial y entretenimiento digital interactivo (AIIDE) de 2010 , que se celebrará en octubre de 2010 en la Universidad de Stanford, será sede de la primera competencia AI de StarCraft .

StarCraft 101
Cuando Dan y los estudiantes en su laboratorio oyeron hablar de la competencia, se entusiasmaron inmediatamente. "Tan pronto como oí las palabras," .. hay acceso a la API de StarCraft '", dijo," Yo sabía que iba a suceder una investigación interesante y que habría mucho espacio para toda clase de proyectos de investigación que estaban cerrados con llave. "
El primer reto fue definir el espacio del problema. ¿Cuáles eran las tareas más importantes que un jugador de StarCraft tendría que hacer, y cómo se traduce esto a un agente de IA
El equipo que se había fusionado en este punto incluía a Dan, algunos de sus estudiantes de doctorado, y varios otros estudiantes graduados de la IA y los laboratorios de investigación de robótica en Berkeley (incluyendo a su autor). Este grupo tenía importantes conocimientos de IA, pero carecía de las habilidades de StarCraft, mientras que la población de informática de grado en Berkeley, incluía muchos jugadores ávidos. 
Para ayudar a cerrar esta brecha, Dan creó una clase para la enseñanza de conceptos de IA a través del diseño y la construcción de nuestra entrada al torneo. La clase podría ser una oportunidad para compartir conocimientos y explorar cómo los desafíos del juego podría ser estructurados como problemas concretos que deben abordarse en forma algorítmica y de principios, . También sería una buena manera de presentar y enseñar los conceptos de IA.
La respuesta al anuncio de la clase fue inmediata y entusiasta, y la clase fue un gran éxito. Pasamos el semestre aprendiendo sobre StarCraft y la inteligencia artificial, la exploración de algoritmos y estructuras, y simplemente tratando tantas cosas diferentes como pudimos. Fue una experiencia valiosa y fundamental para la evolución de nuestro agente. "Es seguro decir que sin la clase no lo hubiéramos hecho tan bien", dijo Dan después.
Al término de la clase, habíamos formulado los requisitos del juego en tres áreas problemáticas principales. En primer lugar, un agente necesario para adquirir y administrar los recursos, y decidir qué construir y cuándo. Esto se conoce en términos de juego como macro-gestión, o "macro", y es en última instancia un problema de planificación y optimización. 
La siguiente tarea es la microgestión. Una vez que tiene un ejército, el agente deberá seleccionar objetivos y gestionar el movimiento de sus unidades, un reto que plantea un problema complejo, el control multi-agente. Por último, el agente necesita gestionar la información, descubrir al enemigo y ajustar una estrategia adecuada a las acciones enemigas, combinando los aspectos de la unidad de control y planificación de alto nivel. 
Continuará..... en la segunda parte