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:

...