Busqueda informada y heuristica. Algoritmos A* Y IDA* aplicados al juego Puzzle-8

[pic 1]                                                                                            [pic 2]

[pic 3]

Informe 1: Busqueda Informada y heuristica

Algoritmos A* Y IDA* aplicados al juego Puzzle-8

Carlos Nuñez

06-09-19

Inteligencia Artificial

1.- Introducción

La inteligencia artificial desde su concepción ha sigo desarrollada para generar diseños de asistentes inteligentes que guíen a los humanos en tareas que consideran tediosas. Hoy en día existen hack de altísimo nivel operacional, optimizados tanto para gastar bajos niveles de recursos como para actuar en tiempo real. Muchos de estas guías o hack’s son para encontrar soluciones a desafíos que video jugadores no están dispuestos a superar. Sistemas guías de disparos para juegos como PUBG o Apex, le dan a los players la sensación de tener talento o aparentarlo frente a otros. Pero ¿este uso de las metodologías para encontrar soluciones optimas en recreativos, ha nacido hoy en día? ¿Es algo netamente contemporáneo? ¿El informático actual es flojo, o siempre lo fue?

Hoy en día la metodología que estudia la búsqueda de soluciones se encuentra claramente clasificada en algoritmos de búsqueda, como lo son los ciegos o no informados, y los informados. Y podemos ver como algoritmos con metodologías básicas, son ampliamente adaptables a distintas problemáticas. Una de ellas es encontrar la ruta de acciones que dan la solución a un juego tan básico, como el puzzle-8, quizás uno de los primeros hack’s para jugadores old-school.

El objetivo de abordar este problema es el análisis de los algoritmos de búsqueda informada, y la generación de heurísticas que generen soluciones optimas, y a su vez disminuyan la cantidad de recursos necesarios para entregar estas respuestas y que sea en cortos periodos de tiempo.

Se van a mostrar el análisis de los algoritmos A estrella y IDA estrella, junto al estudio de Heurísticas. Se desarrollarán funciones en el lenguaje Python que serán utilizadas para ejecutar pruebas de rendimiento en el juego Puzzle-8, las cuales serán graficadas y estudiadas para definir conclusiones respecto al funcionamiento de estas.

La línea de desarrollo de este informe es la siguiente. Se estudiará la teoría de los algoritmos ya mencionados, se presentarán los códigos desarrollados en Python, los resultados en ejecuciones reales del juego Puzzle-8 y por último se definirá cual fue el que tuvo mejores respuestas, peor respuestas y comentarios adicionales.

2.- Marco Teórico

La inteligencia artificial (IA) es una de las ramas de la Informática, con fuertes raíces en otras áreas como la lógica y las ciencias cognitivas. Un problema típico de esta área es la búsqueda de estados concretos entre un conjunto establecido o espacio de estados. Pero ¿de qué manera un sistema inteligente es capaz de discernir cuál estado es una buena elección? Es aquí donde entran los algoritmos de búsqueda, metodologías automatizadas para la resolución de problemas por medio de grafos de estados-acciones. Estos son fuertes al enfrentarse a problemas que cuentan con ramificaciones de múltiples rutas posibles.

Entre ellos se pueden reconocer dos categorías; los de búsqueda no informada o ciega, y los de búsqueda informada. A continuación, se definen:

• Búsqueda no informada: Son algoritmos que no cuentan con información adicional para guiar su búsqueda de un estado meta, solo cuentan con el conocimiento sobre los estados ya recorridos. Ejemplos de este son algoritmos como el BFS mejor en anchura, o el DFS mejor en profundidad.
• Búsqueda informada: Estos utilizan el conocimiento del dominio o del espacio de estados, junto a heurísticas que logran dar dirección a la búsqueda entre las mejores opciones. Se puede considerar que los algoritmos de búsqueda informada son construidos sobre los no informados, tal como lo son el algoritmo “A estrella” basado en el “Algoritmo de costo uniforme”, o también el “Algoritmo A estrella con profundidad iterada” mejora del “A estrella” utilizando la metodología del “Algoritmo ID”.

Una forma simple de ver cómo funcionan los algoritmos de búsquedas, son los rompecabezas o puzzles. El que se ha planteado para desarrollar (programar) en este informe, es el rompecabezas del 8 o Puzzle-8, versión pequeña del conocido rompecabezas del 15.

Para el Puzzle-8 se usa un cajón cuadrado con capacidad para 9 bloques cuadrados, pero en el solo hay situados 8, dejando un cuadrado sin rellenar. Cada bloque tiene un número. Un bloque adyacente al hueco puede deslizarse hacia él. El juego consiste en transformar la posición inicial en la posición final mediante el deslizamiento de los bloques. En particular, consideramos el estado inicial y final siguiente:

[pic 4]

Aunque pareciera que con 15 o 8 piezas la cantidad de estados posibles no es tan rica en información como lo podría ser la búsqueda de rutas en un mapa real, la verdad es que el espacio de estados de estos rompecabezas es bastante amplio. En el de 8 piezas se cuenta con 362880 (trescientos sesenta y dos mil ochocientos ochenta) posibles estados, y con el de 15 es de 20922789888000 (veinte billones novecientos veintidós mil setecientos ochenta y nueve millones ochocientos ochenta y ocho mil) posibles estados. Esto se puede inferir mejor al ver las posibles expansiones de un estado:

[pic 5]

Como la cantidad de datos con los que se trabaja es baja, el costo de realizar una iteración de movimiento, tanto en memoria como en tiempo es pequeño, pero se complejiza cuando se desea encontrar la ruta para resolver el puzzle (conjunto de iteraciones necesarias para resolver el paso de un estado inicial no meta, al estado meta). Es con esto que se puede probar y comparar el desempeño teórico de los algoritmos de búsquedas.

Para encontrar rutas óptimas y con el mínimo uso de recursos, es que se utilizan algoritmos con fortalezas en el trabajo con grafos pesados, como lo son el A estrella y el IDA estrella.

2.1.- Algoritmos de búsqueda informada

Un primer contacto con estos algoritmos es el siguiente: “Búsqueda primero el mejor” o “Best First”, es presentado por Judea Pearl como el caso particular del algoritmo general de “Búsqueda de árboles” o “Búsqueda de grafos”, en el cual se selecciona un nodo para la expansión basada en una función de evaluación  que se dedica a medir la distancia hacia el objetivo.[pic 6]

Otro algoritmo importante es el “Búsqueda voraz primero el mejor” que aplica una metodología greedy, la cual expande el nodo más cercano al objetivo. Evalúa los nodos utilizando solamente una función heurística:

[pic 7]

Al hablar de algoritmos de búsqueda se debe considerar la forma de medir la complejidad de los problemas y algoritmos. El algoritmo de búsqueda depende en gran medida de la complejidad del problema, la cual se expresa por medio de tres cantidades:

1. Factor de ramificación  o el número máximo de sucesores de cualquier nodo.[pic 8]
2. Profundidad del nodo objetivo .[pic 9]
3. Longitud máxima de cualquiera camino en el espacio de estados .[pic 10]

2.2.- Algoritmo A estrella o A* (Peter E. Hart, Nils J. Nilsson y Bertram Raphael, 1968)

Descripción

El algoritmo A estrella es la combinación de otros dos. Un algoritmo de búsqueda por el mejor nodo como lo es “Best First” que combina las características de los métodos en anchura y en profundidad, se caracteriza porque cada nodo genera todos sus posibles sucesores y entre ellos solo expande el que cumpla con tener el valor menor según la función heurística , la que estima el coste del estado de cada nodo al objetivo. Aunque logra disminuir el consumo de recursos, lamentablemente no es ni optimo ni completo.[pic 11]

Por otra parte, el “algoritmo de costo uniforme” o “UCS” minimiza el coste de la ruta hacia el nodo, es decir, expande para cada conjunto de sucesores aquel que tenga el camino con menor coste según la función , la que mide el costo de la ruta desde el nodo inicial al nodo actual . Este cumple con ser un algoritmo optimo y completo, pero puede ser ineficiente.[pic 12][pic 13]

Bajo estas dos metodologías nace el algoritmo A estrella. Sus diseñadores combinaron las dos funciones que controlan la selección de los estados en los algoritmos “Best First” y “UCS”, y generaron:

[pic 14]

: función que calcula el costo de la ruta desde el nodo inicial al nodo n.[pic 15]

: función heurística que calcula el costo estimado (cota inferior) desde n hasta el nodo objetivo.[pic 16]

Por la naturaleza de ambas funciones,  es el coste estimado de la solución de menor coste que atraviesa al nodo .[pic 17][pic 18]

Supuestos

Si se intenta encontrar la solución de menor coste, es razonable intentar primero el nodo con el menor valor de . Lo bueno de esta estrategia, es que es más que razonable, ya que se puede comprobar que es completa y optima, dado una simple restricción de la función . La restricción es escoger una función  que nunca sobreestime el coste para alcanzar el objetivo (léase la sección de heurísticas para comprender esto 2.4).[pic 19][pic 20][pic 21]

...