Un artilugio para experimentar… o algo así.

Buen camino a todos:

Veamos…

Tenía un punto que comentar con vosotros, pendiente de una de las entradas anteriores.

En esa entrada, Tiempo para leer: Virginie Mathivet,  compartía con vosotros la última lectura que había hecho durante las vacaciones, recomendando un libro que me parecía interesante por los motivos que en ese momento expresaba. Escribía justamente al final de la misma:

He pensado que aunque no podamos compartir el código, si que parece aceptable que  algunas ideas que aparecen desarrolladas y adaptadas a otros ejemplos se puedan compartir en alguna futura entrada. Se pueden buscar otros problemas que se puedan resolver aplicando ideas parecidas (resolución puzzle-n enésimo, etc…).

Y comentaba ésto por un lado, por respeto a la autora, (lo de no compartir desde el blog el código que había portado desde Java a Delphi para mi uso personal) algo que siempre fue una máxima del blog desde que nació, intentar ser lo mas respetuoso con todos. Pero por otro lado, al momento de escribir la entrada era consciente de que, sin entrar en temas en I.A., el mero hecho de crearte una estructura que te permitiera pensar sobre aquellos puntos, sí merecía esa atención.

Y por ello, centrarme en un juego corriente, el Puzzle, o 8-Puzzle, (o n-puzzle), que no tenía que ver «directamente» con el ejemplo de la búsqueda de una ruta y la elección de un camino en función de un algoritmo, pero sí permitía aplicar algunas ideas que había captado de la lectura. Por ello, la elección del titulo de la entrada, «Mesa o artilugio para experimentar…o algo así» que ponía el foco o énfasis más en esa estructura que en el propio juego. De no ser así pues habría elegido: «Resuelve este puzzle…» o similar. El título para mi siempre es importante y suelo pasar bastante mas tiempo del que quisiera, para decidirme en uno u otro.

La siguiente imagen muestra dos estados del juego. Estado Objetivo, es decir, el estado que resuelve «mi» puzzle y un estado aleatorio de inicio (el que tiene la casilla remarcada en el centro en azul, a la derecha).

Paralelismos…

Decía que siendo distinto -a la búsqueda de una ruta-, guardaba algunos paralelismos.

En ambos existía un tablero. Eso me permitía re interpretar el código que había escrito y aprovechar una gran parte de el.

¿Recordáis la imagen con la que abríamos esa entrada?

Existía ese tablero con X casillas. En el ejemplo concreto de 10×10. Se establecía una casilla de punto de partida y un punto de llegada u objetivo, y se estudiaba la forma de generar una ruta que alcanzará ambos puntos con algunas premisas. No todas las casillas eran factibles (no se podía pasar a través de ellas, como el agua o las que representaban a un árbol). Otras tenían un coste superior, lo cual permitía optimizar esa decisión para gestionar la mejor ruta. Se muestra en esa imagen con casillas que exhiben círculos con distintos colores.

En el puzzle, la imagen de la derecha, representa un punto de partida. La de la izquierda el estado final que debemos buscar. Esta decisión es un tanto arbitraria, respecto a que ese estado final sea así o sea cualquier otro, a nuestros efectos. Y la casilla en blanco, que yo represento internamente con el valor 0 (cero) haría las veces de un hueco libre, que puede ser ocupado por cualquier casilla contigua. En este caso, la «ruta» sería los movimientos necesarios para pasar de un estado cualesquiera a ese estado objetivo, conocido por quien resuelve el problema.

También existe la analogía de la estrategia. Podemos diseñar distintas estrategias para abordar el problema (ese u otros). En el libro de Virginie Mathivet, recorre y explica cinco de ellas para las rutas, algunas ciegas (no informadas), sin conocimiento previo del punto de llegada, menos inteligentes, como la búsqueda en Profundidad o la búsqueda en Anchura, y otras, con mediciones, que nos ayudan a acercarnos a la solución. Mientras leía aquellas paginas me acordaba de una anécdota, siendo un chaval. Me desperté a media noche, tras una pesadilla, y en la habitación oscura no acertaba a encontrar el interruptor de la luz. Desorientado, y un poco asustado, buscaba puntos de referencia, palpaba las paredes, y me desplazaba tratando de alcanzarlo con la mano. Los gritos, esa agitación, despertaron a mi hermano, que dormía apacible en una cama contigua. Abrió la luz de la mesita. Y ahí estaba yo, en una pared opuesta a la que tenía el maldito interruptor… De estar solo, seguro que hubiera acabado recorriendo toda la habitación hasta encontrarlo a base de manotazos acá o allá… La búsqueda en profundidad o en extensión representan un poco esa idea: intentas recorrer todo el espacio de una forma sistemática para asegurarte que al final tienes éxito. El otro extremo, cuando contamos con alguna información que nos oriente, sería similar a aquellos juegos donde nos van informando de qué cerca estamos de la solución. ¡Frío! ¡Frío!… (te mueves hacia otro lado) ¡Caliente!… Te quemas… (¡llegaste!)

Si encuentras una forma de medir o interpretar esa distancia, acabarás alcanzando el destino mas rápidamente, o bien de forma «optimizada», en función del contexto del problema. Aunque no siempre esa medida, sea una condición necesaria y suficiente, pues podemos encontrar estados intermedios menos deseables respecto a la medida, pero necesarios para llegar a un estado superior. En el caso de las rutas, podrías tener ese punto del destino al alcance de una mano, y entre ambos un abismo que te obligue a alejarte para rodearlo. Si la distancia fuera la única condición posiblemente nunca acertarías a resolverlo. En el puzzle pasa algo similar. Cuando varias fichas están en posiciones invertidas, respecto a la solución, puedes necesitar movimientos extras para ordenarlas, lo cual, podría hacerte pensar en función de esa medida, que esos movimientos te alejan de la solución. En el puzzle, una de esas medidas que usamos es la distancia Manhatan, que calcula la suma de las distancias de cada casilla respecto a su posición objetivo (excluida la que representa el hueco).

La verdad es que el libro ayuda a comprender con detalle la elección de un heurismo u otro, que es una de las razones de que disfrutara su lectura y os lo recomendara.

Artilugios…

Dije, y si no lo digo ahora, que mis conocimientos en Inteligencia Artificial son básicos, sincera y humildemente básicos. De no ser así, a lo mejor no hubiera sentido esa curiosidad sana por el contenido del libro de V. Mathivet  🙂   Sí. Creo que sí que lo dije en aquella entrada…. Quizás también por esa razón necesitara crearme un artilugio para hacer las pruebas, donde añadir, borrar, explorar, curiosear, sin tener que estar reinventando la rueda en cada ejemplo que abordaba del libro. De hecho, de la lectura, y del mismo código, ya se adivinaba que la autora se crearía una estructura genérica lo suficientemente flexible para ser utilizada en mas de un problema. A fin de cuentas, cuando hablas de grafos, de nodos o de arcos, hablas de abstracciones que están representado multitud de problemas, desde la distancia entre varias ciudades, la mejor jugada en una partida de ajedrez, o la combinación de objetos que optimizan un contenedor.

En uno de los vídeos que incluía en la entrada, se aprecia por ejemplo como «limpio» el tablero, y añado manualmente nuevas condiciones de inicio. Se podían definir distintos pares inicio-final, o distinta selección de algoritmos para encontrar la solución deseada. Incluso, al incorporar, la ejecución del algoritmo heurístico en el contexto de un hilo, permitir que se ejecuten en concurrencia, nada impide disfrutar de una competición entre ellos, o que puedan colaborar, siempre y cuando, establezcas esas garantías de que el acceso al hilo principal sea sincronizado.

Por todo esto, me parecía a mi que centraba el foco en compartir ese entramado de clases, mas que la propia búsqueda y análisis de una solución, algo para lo que contamos con miles de páginas en la Red, analizando los pormenores de la resolución de problemas para el n-puzzle, o de las n-reinas, o cualesquiera de ellos, publicados por Universidades y profesionales del ámbito de la Inteligencia Artificial e Ingenierías. Una búsqueda en Google con los términos «8-puzzle problema» ya te devuelve 818.000 resultados. Lo que pueda aportar yo, sería irrelevante por lo que no paso el trabajo para añadir una coma mas. 🙂 (al menos a nivel de blog).

Y de hecho, y en las lineas posteriores que os mostrarán el código, sustituí la clase que implementaba la resolución del puzzle (apoyándome en A*) por una plantilla vacía, que no hace nada, y que os puede dar un espacio enorme para pensar (como a mi me lo ha dado), si alguien se decide a participar en el taller que abriré para dar continuidad a estas letras.

Este sería su código:

unit UClaseAlgoritmo8PuzzleBlank;

interface

uses UClaseGrafo;

type
  TAlgoritmo8puzzleBlank = class(TAlgoritmoThread)
  private
  protected
    procedure Run; override;
  public
  end;

implementation

uses System.Classes, System.SysUtils, Generics.Collections, UClaseRegistro,
UClasePuzzle;

procedure TAlgoritmo8puzzleBlank.Run;
begin
    { TODO : Añadir implementación algoritmo... }
end;

initialization
  ModuleInfoManager.RegisterModule('TAlgoritmo8puzzleBlank', 
                                   TAlgoritmo8puzzleBlank, 
                                   'Algoritmo de 8-Puzzle Vacío');

end.

No hace nada… La implementación se puede discutir. O incluso podéis inventar otro artilugio… No tenéis que comulgar con él. Por ello, mi idea era reservar esa discusión para el grupo que había abierto en la Community de Embarcadero, Taller de Delphi Básico. Es algo que ya compartía con vosotros en Días de verano y tiempo para pensar…, cuando comentaba:

Pero no tiro la toalla en ese sentido. Sigue siendo uno de los objetivos, al menos respecto a los talleres prácticos. A partir de Septiembre y hasta el mes de Diciembre, quiero centrarme en ese tema y os mantendré informados si veo la posibilidad de abrir algún taller práctico (-tengo alguno en mente-).

Unas pinceladas…

Siguiendo ese compromiso, el código lo subí a un repositorio público similar a Github, que es Bitbucket: 8-Puzzle. A partir de ahora, voy a intentar que todo lo que se publique en blog se pueda descargar en ese o cualquier otro sitio de las mismas características.

Para que pueda entenderse mejor, estas líneas me permiten hacer algunos incisos y comentarios, que de seguro ayudarán.

Primero: No he querido crear un componente o componentes que representaran el puzzle y que se pudiera recrear en tiempo de diseño. ¡Es que me daba realmente igual!. Buscaba algo sencillo y no complicarme. La creación de un componente ya la vimos en meses anteriores, cuando diseñábamos el reloj analógico para integrarlo en el fichador, o registro horario de empleados. Así pues, lo que vais a encontrar es un grupo de proyecto que contiene dos proyectos (el primero de ellos para hacer pruebas sobre Windows, en un formulario mas amplio, donde pudiera captar muchos detalles). Y un segundo proyecto, muy sencillo en el que verifiqué que aquello, funcionaba en un dispositivo Android.

Segundo: Se puede optimizar.  Tampoco era uno de los objetivos. Los ejemplos que encontré en la red a menudo usan Arrays de enteros para representar el tablero y el estado, y a mi, me dio por usar una lista genérica de objetos, donde la lista representa el grafo y los objetos que contiene los nodos. A partir de ahí, que tuviera una dimensión de 3×3, 4×4 o 5×5 tan solo dependía de la cantidad de nodos que contiene la lista. En el video se muestra que la funcionalidad del tablero no se ciñe al 8-puzzle de 3×3.

Tercero:  No es código final, sino punto de partida para reflexionar, y que yo comparto con vosotros sin mas pretensiones. Tampoco me preocupa demasiado si la imagen, que la añado para adornar un poco, sea cargada a «piñon» o exista alguna rutina que busque en un directorio de imágenes, donde exista un cuidado catálogo, etc… También se podían haber utilizado interfaces (la elección de TInterfacedObject como clase base iba por ese camino, de cara a no cerrar esa posibilidad (*).

(*) En el código original de la búsqueda de rutas, si las empleaba pero finalmente, de cara al puzzle, y con los cambios, quedaron fuera.

Cuarto: El código se reparte en algunas carpetas de forma que quede mas estructurado.

• Algoritmos: Aquí dejaba las unidades que iba probando, con distintas implementaciones y pruebas. La unidad que representa el log me ayudaba a comprobar que el algoritmo funcionaba correctamente
• Helper: Contiene el módulo que representa el helper de las clases que representan al tablero y la imagen. Ambas comparten ese código para que sea mas fácil sincronizarlas y que los movimientos de las casillas sean paralelos a los de la imagen troceada.
• Marco: Contiene todas las clases que representan el juego, propiamente.
• TestAndroid/TesWindows: La unidad principal conteniendo el formulario, para las dos pruebas que hice.

Quinto: La siguiente imagen, os muestra un diagrama de clases, que se puede obtener con el mismo entorno de desarrollo, que puede facilitar una compresión global de las relaciones entre si. En el repositorio he añadido un jpg con esta misma imagen. Dadle un vistazo. Cualquier aclaración la podemos abordar desde ese grupo creado.

También he incluido un pequeño vídeo que os muestra el test para Windows, ejecutándose.

Jugando con el puzzle…

 

Pistoletazo de salida…

Tan pronto como publique esta entrada, dejaré abierto el tema en el grupo de taller.

Para evitar el spam, es necesario solicitar la entrada al grupo y registrarse en la Community.

Y espero que os guste.

Sed felices.