Juegos, rutas y circuitos, resolucion de problemas con Inteligencia Artificial

Juegos, rutas y circuitos, resolucion de problemas con Inteligencia Artificial

La industria global de los videojuegos en línea no es cosa de juego, pues se estima que en 2019 obtuvo 33,600 millones de dólares en ingresos. Todos los días, miles y miles de personas en todo el mundo juegan durante horas complejos juegos de estrategia por equipos, ya sea en partidas amistosas, o en torneos que pagan grandes premios en efectivo. De hecho, la industria de los esports (deportes electrónicos) genera 1,200 millones de dólares al año en ingresos y reparte más de 120 millones en premios, por lo que hay muchos equipos y ligas profesionales.

Uno de los juegos que más premios reparte cada año (35 millones de dólares en 2019) es Dota 2. Este videojuego, perteneciente al género de arena de batalla en línea, reúne diariamente más de 40 millones de jugadores que, en equipos de 5 integrantes, se enfrentan en un mundo de fantasía por el control de sus fortalezas.  Los jugadores pueden elegir de entre casi 120 personajes, cada uno con habilidades especiales y únicas. Debido a que Dota 2 está orientado al juego en equipo, los jugadores deben coordinar y planificar sus acciones con sus compañeros para lograr la victoria.

El 13 de abril de 2019, un equipo controlado por un programa de Inteligencia Artificial (IA) derrotó en dos de tres partidas al equipo campeón mundial 2018 de Dota 2. Después el programa, llamado OpenAI Five, se enfrentó durante 4 días a todo equipo que quiso jugar con él, ganando 7,215 veces y perdiendo sólo 42 (Lee el artículo que describe el proyecto aquí).


performance-3110696_400jpg 

Imagen de dife88 en Pixabay

Aunque sistemas como OpenAI Five tienen una arquitectura compleja y utilizan herramientas muy avanzadas, el principio con que funcionan es el mismo de cualquier juego: dada la situación actual, busca las acciones que puede tomar y evalúa cuál es la que más le acerca a su objetivo. Las técnicas para hacer esta búsqueda caen en el campo de la IA llamado resolución de problemas, el cual estudia cómo encontrar la secuencia de acciones que lleva a un estado de cosas deseado. Además de dominar juegos, la resolución de problemas se utiliza para encontrar la mejor ruta para llegar a un lugar, acomodar millones de componentes y conexiones en un circuito integrado, planear la navegación de robots, o encontrar la secuencia para el ensamblado automático de un producto.

Para entender los principios y algoritmos de la resolución de problemas utilizaremos un problema clásico: encontrar la ruta entre dos puntos. En la figura de abajo tenemos siete ciudades (de la A a la G), unidas por los caminos representados por las flechas y separadas por la distancia mostrada. Para simplificar, cada camino tiene un solo sentido. El problema consiste en hallar el camino para ir de la ciudad A a la ciudad G.

Blog 22-problemajpg

El elemento central de la resolución de problemas es el estado de cosas en que estamos. En nuestro ejemplo, el estado se representa por la ciudad en que nos encontramos. En otros casos es representado por la posición de las piezas en el tablero, por el conjunto de componentes y conexiones en un circuito o, en el caso de Dota 2, por la ubicación de los 10 jugadores, el inventario de artículos que tienen, así como la localización de todas las estructuras, enemigos, árboles y todo tipo de objetos (OpenAI Five representa un estado con 16,000 valores).

Resolver un problema consiste en encontrar la secuencia de acciones posibles que, a partir del estado inicial, nos permitan transitar entre diversos estados hasta llegar al estado objetivo. Como veremos más adelante, si incorporamos un criterio para evaluar qué tan cerca estamos del objetivo, esta información nos sirve para decidir qué acción tomar en el estado actual.

Ahora bien, ¿Cómo navegar entre los estados posibles? A lo largo del tiempo se han inventado muchos algoritmos de búsqueda, todos muy ingeniosos y que, con el poder de las computadoras actuales, permiten tener sistemas como Dota 2 o los asistentes de navegación. A continuación, mostraremos algunos de los más conocidos, cada uno adecuado a diferentes circunstancias.

  • Búsqueda en anchura. Si representamos nuestro problema como un árbol, esta técnica recorre en orden cada nivel, como lo muestra la animación. Llega al objetivo sin evaluar si siguió la mejor ruta.
Blog 22 - bfsgif
  • Búsqueda en profundidad. Este algoritmo explora completa cada rama del árbol que abre. En algunos casos llega más rápido al objetivo, pero depende del orden de los nodos. Tampoco evalúa la mejor ruta.
Blog 22 - dfsgif
  • Búsqueda de costo uniforme. Es como una búsqueda en profundidad, pero recorre primero las ramas con el menor costo acumulado de recorrido. Llega al objetivo por la ruta de menor costo, aunque no de la manera más rápida.
Blog 22 - ucsgif
  • Búsqueda con algoritmo A*. Funciona igual que el costo uniforme, pero para decidir qué rama seguir explorando suma al costo acumulado una estimación de que tan cerca estamos del objetivo (En nuestro ejemplo la distancia en línea recta a la ciudad G.) Llega a la mejor ruta más rápido, por lo que es de los algoritmos que más se utiliza.

Blog 22 - Asteriscogif

El método de búsqueda es fundamental para evitar revisar estados que no nos acercan al objetivo, situación crítica en problemas con millones y millones de estados posibles, cuya exploración puede llevar mucho tiempo aún con las computadoras más poderosas. Por eso el desarrollo de métodos de búsqueda y criterios para evaluar la proximidad al objetivo es un área de investigación muy activa de la IA, que ha producido técnicas interesantes.  Entre ellas están los algoritmos genéticos, que generan nuevos estados (hijos) a partir de la combinación de dos anteriores (padres) con un pequeño cambio (mutación), o los que emulan el comportamiento colectivo de animales o insectos.

La resolución de problemas, al igual que otras áreas de la IA como el aprendizaje reforzado o las redes neuronales, permiten que sistemas como OpneAI Five puedan ganar a un ser humano en un videojuego. Esto se logra sin que la máquina tenga consciencia de sí misma, pero el efecto es el mismo. Entonces, cuando se dice que el juego es una señal de inteligencia, ¿basta que parezca que juega?


¿Qué opinas? Comparte tus comentarios abajo. ¿Te gustó este artículo? Lee otros artículos de nuestro blog IF Inteligencia Futura aquí.

Visita nuestras secciones