Problema de 8 puzzle Busqueda Informada en Lisp
Es un problema clásico en la rama de la Inteligencia Artificial, aunque el problema parece de cierta manera trivial en la forma de entender y de plasmar en un lenguaje de programación, es sin embargo de cierta compledidad en la hora de resolverlo computacionalmente, iniciaremos dando una breve descripción del problema, y posteriormente veremos las técnicas comunes que son usadas para resolver este juego. sin mas preámbulo iniciaremos con el problema.
Descripción
Tratamos de resolver un juego de puzzle con 9 casillas para el caso del 8-puzzle, en la cual 8 están llenas de algún elemento (Imagen, Numero, Letra, etc) y la novena casilla se encuentra vacía, esto sirve para hacer movimientos de manera horizontal o vertical, el objetivo es llegar de un estado inicial a un estado meta (Solución).
Estado Inicial, Estado Meta A y Estado Meta B respectivamente.
Debemos notar que al mover una ficha de posición generamos un nuevo estado la cual tenemos que analizar, así moviendo las fichas de lugar en diferentes formas llegaremos al estado meta -sin embargo no todo esto es cierto- existe un problema en el juego de puzzle llamado error de paridad (Muy similar al error de paridad de las comunicaciones electrónicas). Por lo tanto no siempre desde cualquier estado inicial, podemos llegar a un estado meta.
Error de paridad
Antes de entender el error de paridad necesitamos plantear el concepto de inversión que depende del Estado Meta a llegar, por lo cual tomaremos nuestro Estado inicial y Estado Meta B respectivamente:
Llamamos inversión a la violación del orden de la posición de acuerdo a su valor “per se”, en otras palabras un numero mayor se encuentra justamente detrás de un numero menor, en el estado ilustrado anteriormente tenemos:
2 se encuentra detrás del 1 8 se encuentra detrás del 3, 1, 6, 4, 7 y 5 3 se encuentra detrás del 1 6 detrás del 4 y 5 Y por ultimo 7 detrás del 5Esto nos da un total de inversiones de 11, un numero impar.
De otra forma tenemos el Estado Inicial y el Estado Meta A:
Usando la misma logica pasada tenemos que:
2 se encuentra detrás del 1 8 se encuentra detrás del 1 y 3 3 se encuentra detrás del 1 6 se encuentra detrás del 4 y 7Con un total de 6 inversiones un numero par.
Como podra ya suponerse, el error de paridad depende exclusivamente del total de inversiones, ya que si es un numero par tiene solución, de lo contrario es imposible llegar al Estado Meta.
Búsqueda
Dado que al cambiar una ficha de posición estamos generando un nuevo estado, podemos ver el problema del puzzle en forma de arbol, en la que cada nodo es un estado del puzzle generado por un padre (Excepto el nodo raíz, el cual es el estado inicial), y cada nodo hijo es un nuevo estado generado a partir del movimiento de las fichas, por ejemplo:
Existen principalmente dos tipos de búsqueda para resolver el problema del puzzle y claro entre otros.
- Búsqueda a Ciegas (No informada)
- Fuerza Bruta (Sin orden en particular)
- Ordenada (Estrategia de orden)
- Depth-first (Expandir en profundidad)
- Breath-first (Expandir en anchura)
- Iterative Deeping Search (Una combinación de las estrategias anteriores)
- Búsqueda Contextual (Informada)
- Selectiva (Estrategias de expansión)
- Best-first
- A*
- Selectiva (Estrategias de expansión)
Algoritmo Best-First
La búsqueda usada en este problema fue de manera contextual y con estrategia de expansión de Best-First.
Los métodos de búsqueda contextual no se ajustan a un orden fijo para expandir los estados, sino que, para tomar la decisión, incorporan una función de evaluación ƒ(x) la cual se compone de dos partes:
ƒ(x) = g(x) + h(x)
Función de Costo Estimado y función de aptitud
h(x) es una función que evalúa el estado x en cuanto a su parecido con el estado meta.
g(x) evalúa la dificultad, en terminos del espacio de estados representados, de llegar hasta el estado x, o bien, la dificultad restante hasta llegar a un estado meta, esta componente de la funcion es usada usualmente en el algoritmo A*.
En lugar de expandir siempre un profundidad (Depth-first), siempre en anchura (Breath-first), o una combinación (Iterative Deeping Search), este algoritmo expande, en cada ocasión, el estado mas “prometedor”.
La función de evaluación heurística determina cuál es el nodo a expandir.
Función de Aptitud
Existen dos funciones de aptitud tradicionalmente usadas para este problema en particular, ambas funciones de aptitud miden las diferencia entre el estado evaluado y el estado meta.
Estado Meta usado
- El numero de fichas colocadas de manera incorrecta, basada en el estado meta.
h(e) = Numero de fichas mal posicionadas
h(e) = 4
- La suma de la distancia Manhattan (Suma Vertical y Horizontal), de cada ficha a su posición del estado meta.
h(e) = ∑ i=1 to i=8 ( e(i), Estado Meta(i) )
h(e) =1 + 1 + 2 + 1 = 5
Pasos del Algoritmo Best-First
- Definir la lista de estados a examinar (Lista OPEN), conteniendo exclusivamente el estado inicial S.
- Si la lista OPEN está vacía, entonces NO HAY SOLUCIÓN y terminar.
- Extraer de la lista el siguiente estado (n) con mejor aptitud y moverlo a una lista de nodos ya examinados (CLOSED), dado que la lista debería estar siempre ordenada debemos seleccionar el primer estado.
- Expandir el estado n (En todas sus formas validas).
- Si algún sucesor de n es el estado meta, SOLUCIÓN y reconstruirla, de lo contrario.
Para cada estado recién generado:
- Evaluar su aptitud con h(e).
- En caso de que el estado no se encuentre en alguna de las dos listas, entonces añadirlo a OPEN.
- Ordenamos OPEN
- Regresar al Paso 2
Ejemplo simple
Tenemos Estado Inicial y el Estado Meta respectivamente.
Paso 1, Insertar el estado inicial a la lista de OPEN.
Lista OPEN
Lista CLOSED
Vacía
Paso 2, verificar si la lista OPEN no esta vacía.
Paso 3 extraer de la lista OPEN el estado con mejor aptitud, en este caso como OPEN solo tiene un elemento,lo movemos a CLOSED
Lista OPEN
Vacía
Lista CLOSED
Paso 4, expendemos el estado.
Lo que nos da:
Paso 5, ningún estado sucesor de (n) es el estado meta.
Paso 6, Usaremos la función aptitud de posiciones incorrectas, y tenemos sus siguiente aptitudes respectivamente: h1(e) = 3, h2(e) = 5, h3(e) = 4
Ninguno de los estados se encuentra en CLOSED ni en OPEN, por lo tanto metemos nuestros estados a la lista OPEN.
Lista OPEN
Ordenamos de acuerdo a su aptitud h1(e) = 3, h3(e) = 4, h2(e) = 5:
Lista OPEN
Lista CLOSED
Repetimos el Paso 2, verificamos si la lista OPEN esta vacía.
Paso 3 extraer de la lista OPEN el estado con mejor aptitud. y lo movemos a CLOSED
Lista OPEN
Lista CLOSED
Paso 4, expendemos el estado.
Lo que nos da:
Paso 5, ningún estado sucesor de (n) es el estado meta.
Paso 6, Usaremos la función aptitud de posiciones incorrectas, y tenemos sus siguiente aptitudes respectivamente: h4(e) = 3, h5(e) = 4, h6(e) = 4, h7(e) = 3
Ya que h6(e) se encuentra en CLOSED no se insertara en la lista OPEN, por lo tanto solo metemos h4, h5, h7, lo que en la lista nos queda h3, h2, h4, h5, h7
Lista OPEN
Ordenamos de acuerdo a su aptitud h7(e) = 3, h4(e) = 3, h5(e) = 4, h3(e) = 4, h2(e) = 5
Lista OPEN
Repetimos el Paso 2, verificamos si la lista OPEN esta vacía.
Paso 3 extraer de la lista OPEN el estado con mejor aptitud. y lo movemos a CLOSED
Lista OPEN
Lista CLOSED
Paso 4, expendemos el estado.
Lo que nos da:
Paso 5, ningún estado sucesor de (n) es el estado meta.
Paso 6, Usaremos la función aptitud de posiciones incorrectas, y tenemos sus siguiente aptitudes respectivamente: h8(e) = 2, h9(e) = 3, h10(e) = 4
Ya que h9(e) se encuentra en CLOSED no se insertara en la lista OPEN, por lo tanto solo metemos h8, h10, lo que en la lista nos queda h4, h5, h3, h2, h8, h10
Lista OPEN
Ordenamos de acuerdo a su aptitud h8(e) = 2, h4(e) = 3, h5(e) = 4, h3(e) = 4, h10(e) = 4, h2(e) = 5
Lista OPEN
Repetimos el Paso 2, verificamos si la lista OPEN esta vacía.
Paso 3 extraer de la lista OPEN el estado con mejor aptitud. y lo movemos a CLOSED
Lista OPEN
Lista CLOSED
Paso 4, expendemos el estado.
Lo que nos da:
Paso 5, ningún estado sucesor de (n) es el estado meta.
Paso 6, Usaremos la función aptitud de posiciones incorrectas, y tenemos sus siguiente aptitudes respectivamente: h11(e) = 1, h12(e) = 3
Ya que h12(e) se encuentra en CLOSED no se insertara en la lista OPEN, por lo tanto solo metemos h11 lo que en la lista nos queda h4, h5, h3, h2, h10. h11
Lista OPEN
Ordenamos de acuerdo a su aptitud h11(e) = 1, h4(e) = 3, h5(e) = 4, h3(e) = 4, h10(e) = 4, h2(e) = 5
Repetimos el Paso 2, verificamos si la lista OPEN esta vacía.
Paso 3 extraer de la lista OPEN el estado con mejor aptitud. y lo movemos a CLOSED
Lista OPEN
Lista CLOSED
Paso 4, expendemos el estado.
Lo que nos da:
Paso 5, Un estado sucesor de (n) es el estado meta.
Reconstruimos la solución:
Conclusión
Con un poco de observación notaremos que solo 5 movimientos son necesarios para llegar del estado inicial al estado meta, sin embargo este ejemplo aunque parece simple, tiene varios detalles que contemplar como: las listas de OPEN y CLOSED van creciendo a un ritmo acelerado, tendríamos que reservar espacio en memoria para las dos listas, generar nuevos estados, comparar estado anteriores, ordenar la lista de OPEN para cada inserción de un nuevo estado, y generar aptitudes por cada estado, lo que hace que requiera un gran recurso de tiempo máquina. Llegando en ciertos lenguajes de programación imposible de llegar a una solución -Aunque esta exista-.
Una cosa mas que notar, es sobre la función de aptitud, ya que por lo generar en este juego, la función de aptitud de Manhattan es increíblemente superior a la función de posiciones incorrectas.
El tamaño del espacio de búsqueda para el 8-puzzle es de 9!, esto es: 362,880 permutaciones, ahora supongamos que necesitamos resolver el 15-puzzle, el cual tiene 15!, lo que es equivalente a: 1,307,674,368,000 permutaciones!!!!
Programa
Después de ver la descripción del problema, el algoritmo de búsqueda y un ejemplo, podemos ya probar el siguiente programa que resuelve el 8-puzzle y 15.puzzle, desarrollado en Common Lisp. Debo mencionar que el programa usa principalmente matrices para la solución, Claro que puede hacerse mucho mas simple y compacto el programa, sin embargo lo hice de esta manera para que fuera un poco mas didáctico y mas transparente para aquellos acostumbrados a C, por decir un ejemplo.
Descargar: 8puzzle
Cualquier duda, comentario o critica es bien recibida.
Quizá te interese :
Trabajando en un manual para Ubuntu 10.04, me he estado enfocando en la instalación y configurac ...
Para este tutoríal instalaremos postgresql-8.3 y postgresql-8.3-postgis desde el Gestor de paque ...
ANTES QUE NADA, NO ME HAGO RESPONSABLE POR EL USO QUE LE PUEDAN DAR A ESTA INFORMACIÓN, LA PUBLI ...
Excelente aporte, muchas gracias.
Mejor explicado que en los tediosos libros de texto (Y)
¡Está genial tu artículo!
Una vez que empecé a leerlo no pude parar hasta terminarlo. También me hizo recordar que en el libo “El último teorema de Fermat” relatan una historia sobre el 15-puzzle: se trata de un gran premio reservardo para la persona que pudiera llegar a una configuración final (meta), la cual tenía un número de inversiones par y por la tanto era imposible de resolver.
Gran trabajo, ¿no tendrás algunos tips para evaluar estados en un juego de ajedrez?
[...] This post was mentioned on Twitter by Daniel Doctor. Daniel Doctor said: RT @tweetmeme Problema de 8 puzzle Busqueda Informada en Lisp http://bit.ly/bduGJz [...]
Muchas gracias por el comentario, bueno como sabras hay muchos problemas que tienen un incentivo para ser resueltos, y como estos casos imposibles de resolver, y claro, no olvidemos los problemas de Hilbert, incluso en nuestros días se encuentran abiertos y premian con un millon de dolares aproximadamente a quien les de fin.
Por otro lado en cuestión del problema del ajedrez, sabes muy bien que tan solo las multiples posibilidades de tiradas son mounstruosas, llegando a ser insultantes, sin embargo se puede aplicar un tipo de algoritmo llamado MinMax, la estrategia general, es maximizar la ganancia o minimizar la perdida en cada turno del jugador, extrapolandolo al juego sería mejores tiradas y menos perdidas de elementos por ejemplo.
Este tipo de problema cae en la clasificación de “planeación”, el cual es generar el arbol de búsqueda de manera total o parcial, puedes o mejor dicho deberías solo tener un campo de visión de hasta 6 jugadas por ejemplo, -Lo que es lo mismo 6 niveles del arbol- y así planear tu estrategia de juego. 6 solo es meramente de ejemplo, depende mucho de los recursos que tengas disponibles.
Asi que este algoritmo no solo se fija en las mejores posibilidades para el jugador, como es el caso del Best-First, si no tambien seleccionar la mejor jugada que perjudique a tu openente.
Saludos, y espero te sirva el comentario.
estoy usando corman common lisp, y al ejecutar el archivo encontre unos inconvenientes al momento de ejecutar (menudisplay) aqui esta lo que me sale:
(displaymenu);hago enter y escribo
((2 8 3) (1 6 4) (7 – 5));esta cadena
pero me sale lo siguiente:
;;; An error occurred in function READ-EXPRESSION:
;;; Error: End-of-file encountered reading from stream #
;;; Entering Corman Lisp debug loop.
;;; Use :C followed by an option to exit. Type :HELP for help.
;;; Restart options:
;;; 1 Enter a value of the correct type.
;;; 2 Abort to top level.
por favor quisiera que me indiquen si no ejecute bien el programa y en donde me equivoque.
Buen día Edwin, el archivo fue probado con clisp en un sistema linux, al igual que el allegro lisp (Windows y Linux), aún así para verificar probé con el archivo que esta en esta pagína y no marco ningún error, y al parecer el error se encuentra al tratar de leer el estado final alguna lectura del archivo incorrecta, en lo personal jamas he utilizado corman common lisp, asi que lo único que podría recomendarte sera probarlo en clisp o allegro lisp en cualquiera de sus versiones. o usar cygwin.
Espero puedas probarlo en otras versiones de common lisp y comentarme al respecto.
Saludos y Gracias.
Excelente muy buena explicacion… tu implementacion en lisp es bastante buena, pude realizar este mismo puzzle en c++, pero a la hora de llevarlo a java, utilizando una tabla hash para guardar los estados que ya he revisado y no repetirlos, la verdad me ha sido dificil esta implementacion para la busqueda en profundidad y en anchura… podrias ayudarme con este problema?, gracias.
Muchas gracias “miracle boy” por tu comentario, bueno la migración del programa de C++ a Java no es mi complicada ya que manejan conceptos similares, sin embargo recuerda que las tablas hash no son 100% seguras, ya que podrían generar valores repetidos (Y claro que existen muchas técnicas que minimizan el problema) y no siempre genera un hash valido, claro con pequeños volúmenes de datos la probabilidad es casi insignificante, sin embargo existe.
Ahora bien, recuerda que el recorrido del árbol ya sea por profundidad o a la ancho es por medio de estructuras de datos, para el primer caso se utiliza una PILA (L.I.F.O) y para el siguiente una COLA (F.I.F.O), claro que estas se van llenando con forme recorras el árbol y generes los hijos, lo que va a variar solamente es la forma en cómo los extraes que es el trabajo de las estructuras mencionadas.
Solo te comento esto a ciegas, no sé exactamente cuál sea tu problema, puedes comentarlo y con gusto te responderemos.
Saludos y Gracias de nuevo.
Hola! Me pareció excelente el artículo. Necesito un programa que pueda resolver un puzzle 8, dando el estado inicial, y el estado final buscado. Pero permitiendo que el espacio en blanco quede a donde yo lo quierom, o sea, en el estado final quiero que el espacio en blanco quede en el medio, o en cualquier posicion. Intenté usar el archivo lisp que dejaste, pero la verdad que soy usuario de windows y no se como ejecutarlo. Podrias ayudarme? te lo agradecería muchisimo. mi mail es: rocaenio@yahoo.com.ar
Hola que tal Carlitox muchas gracias por tu comentario, pues efectivamente el programa funciona como tú deseas, primero poniendo el estado inicial y con el espacio en blanco donde lo especifiques, por ejemplo:
((1 2 3) (4 5 6) (7 8 -))
Donde el “-” es el espacio en blanco y obviamente puedes colocarlo en cualquier posición, recuerda también colocar números no repetidos y secuenciales.
Para ejecutar el script te recomiendo usar alguna distribución GNU/Linux la cual ya tiene los paquetes de clisp instalados.
Ahora bien, para ejecutar el script, desde una terminal teclea lo siguiente:
[user@host]$ clisp –i 8puzzle.lisp
Una vez iniciado teclea el siguiente comando:
(DisplayMenu)
Y el programa iniciara, debes de notar que ciertas combinaciones del puzle generan enormes cantidades de estados, por lo que el programa podría tardar mucho tiempo (Incluso días) para llegar a una solución o encontrar que no tiene solución posible, recuerda la complejidad mencionada en el artículo.
Existen alternativas para ejecutar el script en entornos Windows, por ejemplo puedes usar Allegro o bien Cygwin , claro existen otras herramientas, pero en lo personal te recomiendo esas, no está por demás mencionar que en sistemas GNU/Linux es mejor.
Espero haberte ayudado, y cualquier duda estoy a tus órdenes, Saludos
Necesito la Heuristica en C++, si la tienen les agradeceria su ayuda.