Juegos, rutas y circuitos, resolucion de problemas con Inteligencia Artificial
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.
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.
- 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.
- 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.
- 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.
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?
