Bloques Deslizantes

Aunque en un videojuego lo habitual es que sea el jugador (humano) el que resuelva los puzles, a menudo es útil disponer de un sistema capaz de hacerlo automáticamente. Esto puede servir para ayudar al jugador a superarlo o para darle cierta información (como los pasos que faltan por dar). También puede ayudar al diseñador a realizar pruebas más rápida y eficazmente, verificando que es posible superar el puzle y que este no tiene excesiva dificultad, e incluso a generar nuevos puzles, ya que es una tarea muy relacionada con el hecho de resolverlos.

El puzle de bloques deslizantes, sliding puzzle o n-puzzle, es un clásico dentro de los llamados “problemas de juguete”, una serie de problemas de combinatoria utilizados a menudo para teorizar o explicar conceptos lógico-matemáticos en Inteligencia Artificial. La variante de 8 bloques los tiene distribuidos en un tablero de 3×3 casillas, dejando habitualmente la esquina inferior derecha libre.

Instaura una pequeña anarquía, altera el orden establecido y comenzará a reinar el caos… Soy un agente del caos ¿Y sabes qué tiene el caos? Que es justo.

Joker (El caballero oscuro, 2008)

La mecánica que ofrece este tipo de puzles consiste en deslizar piezas, generalmente planas, sobre ciertas rutas predefinidas, básicamente a una casilla vecina que esté libre en un tablero bidimensional). El objetivo es llegar a una cierta configuración final, partiendo de una configuración inicial diferente. A menudo estas piezas van numeradas o llevan impreso partes de un dibujo que el jugador podrá ver completo cuando haya resuelto el puzle.

Propuesta

La práctica consiste en desarrollar un prototipo de IA que permita resolver, tanto manual como automáticamente, el puzle deslizante de dimensiones N x N, es decir con (N x N) -1 piezas distribuidas, donde N > 1. Como se puede en la siguiente figura, el tablero con números será fácilmente manipulable; y la solución automática se alcanzará mediante pura “fuerza bruta”.

El punto de partida es la plantilla Universal 2D que ofrece Unity, un proyecto vacío preparado para proyectos bidimensionales que utilizan el Universal Render Pipeline (URP).

Las características principales del prototipo son:

A. Se trabajará sobre el punto de partida para mostrar el puzle en su configuración inicial, indicando de alguna forma que el puzle se encuentra ordenado. El usuario podrá mover las piezas manualmente, tantas veces como desee. Una pieza se puede mover si es vecina del espacio libre (o “hueco”).

B. Habrá un botón para reiniciar el puzle a su configuración inicial, y otro para desordenarlo aleatoriamente.

C. Habrá también botones suficientes para resolver automáticamente el puzle con al menos dos estrategias no informadas.

D. Se podrá ver la resolución paso a paso, no sólo la configuración final.

E. Tras la resolución automática, se mostrarán medidas del éxito conseguido, como el número de pasos de la solución o el tiempo empleado en ella.

Revisión

Tener el repositorio a disposición del profesor con todos los entregables, preparados en tiempo y forma por todos los miembros del grupo de manera equitativa, supone un 10% de la nota de la práctica. El profesor tendrá una lista con los datos de todos los grupos y los enlaces a las organizaciones en GitHub (por ejemplo IAV00-G02, la del grupo 2 del curso Inteligencia Artificial para Videojuegos 2000-2001) donde se encontrarán los repositorios de las prácticas (por ejemplo IAV00-G02-P0).

Revisión de la documentación

En esta primera fase de revisión hay un único entregable:

• Documento de producción según la estructura recomendada por el profesor en el README.md. Supone un 10% de la nota.

Revisión del resultado

En esta segunda fase de revisión los entregables son estos:

• Proyecto con todos los ficheros de código fuente y recursos de la implementación en Unity y C# (llamado por ejemplo IAV00_G02_P0). Se incluirán enlaces a documentos compartidos en abierto (o con el profesor) mediante Google Drive, desde donde descargar todo lo que por peso o problemas de licencia no pueda mantenerse alojado en GitHub vía Git LFS. Supone un 20% de la nota.
• Fichero con la versión ejecutable para Windows de 64bits (llamado por ejemplo IAV00-G02-P0 1.0.0.zip), publicada como lanzamiento (release) en el repositorio. Cada característica del prototipo (A, B, C, D y E) correctamente implementada supone un 10% de la nota, sumando un total de 50%.
• Documental con las pruebas del juego, añadiendo al documento de producción el enlace a un video oculto en YouTube (llamado por ejemplo IAV00-G02-P0) de menos de 5 minutos de duración, donde quedan documentadas y comentadas por voz y títulos de texto las pruebas realizadas. Lo habitual será realizar el montaje de varios planos en varios momentos de la partida, evitando las partes menos relevantes. El documental tiene tantas secciones como características a probar (esto es A, B, C, D y E). Supone un 10% de la nota.

Más información

Además de la bibliografía recomendada, se pueden investigar las siguientes referencias. En ningún caso se debe replicar código de terceros sin entenderlo bien y «hacerlo nuestro», y siempre asegurándonos de que funciona exactamente como se requiere en esta práctica.

• Sliding puzzle (Wikipedia)
• How Sliding Puzzles Work (How Stuff Works)

Se pueden realizar ampliaciones para ir más allá en el aprendizaje.

• Aumentar el número de estrategias (algoritmos) utilizados, para compararlos.
• Ofrecer más medidas del éxito, como número de nodos expandidos, nivel de profundidad alcanzado, memoria máxima utilizada durante la resolución, etc.
• Probar con alguna estrategia informada, pensando en alguna heurística válida.
• Usar otros algoritmos, otros tipos de búsqueda (informada) o un resolutor interactivo. 
• Generalizar el problema a puzles NxM.
• Generalizar el problema a puzles con piezas que ocupan más de una casilla.