Recibido: viernes, 20 octubre 2006

---

---

Rompecabezas: definición matemática, resolución automática

 

Pedro Cabalar

Departamento de Computación

Universidade da Coruña

e-mail: Esta dirección de correo electrónico está protegida contra los robots de spam, necesita tener Javascript activado para poder verla

página web: http://www.dc.fi.udc.es/~cabalar

 

 

Introducción

 

No es exagerado afirmar que los juegos de tipo rompecabezas son un elemento más de la educación y el aprendizaje humanos. Desde los primeros puzzles de reconocimiento de formas y colores a los que se enfrentan los niños en las guarderías hasta la resolución de crucigramas o la colocación ordenada de dígitos en un Sudoku, da la impresión de que el ser humano no sólo disfruta jugando sino que demanda este tipo de desafíos para ejercitar su destreza en la resolución de problemas.

 

Aparte de constituir un elemento lúdico y pedagógico, el uso de rompecabezas tampoco ha sido del todo ajeno a la ciencia. Es bien sabido que en la gestación o el análisis de algunos de los pasatiempos más conocidos han intervenido en mayor o menor medida las Matemáticas. Pensemos, por ejemplo, en el cubo Rubik popularizado en los años 80 y que surgió de la resolución de un problema de diseño estructural por parte del arquitecto húngaro Erno Rubik, siendo su aplicación como rompecabezas encontrada más tarde de modo casi accidental. Otro ejemplo de reciente auge es el antes mencionado Sudoku, que no es más que una sofisticación^[1] de un ejercicio combinatorio propuesto por Euler [Euler1782].

 

Aunque la finalidad original de los puzzles está íntimamente ligada al ejercicio del cerebro humano, éstos también han llegado a convertirse en un campo de pruebas para la investigación en la ciencia de los ordenadores, más concretamente en el área conocida como Inteligencia Artificial (IA). Pero, ¿qué sentido puede tener la resolución automática de puzzles? Por supuesto, los objetivos en este caso son sustancialmente distintos, dadas las diferencias entre el funcionamiento del cerebro humano y el de un ordenador. Desde luego, no cabe esperar que con ello la computadora se “divierta” o adquiera más habilidad en la resolución de problemas mediante la insistencia práctica^[2]. Sin embargo, los juegos de tipo rompecabezas poseen una propiedad muy interesante, ya que suelen plantear problemas de representación o de razonamiento difíciles de resolver, pero siempre dentro de un escenario “sintético” y de tamaño limitado. Gracias a esta propiedad, es posible centrarse en un aspecto concreto a formalizar y olvidar momentáneamente otros factores complejos presentes en un problema real, pero muchas veces irrelevantes para la característica bajo estudio.

 

A lo largo de la historia de la IA, esta metodología basada en ejemplos “de juguete” ha sido criticada en numerosas ocasiones, al ser considerada poco realista bajo el enfoque de la investigación aplicada, en la que se buscan resultados prácticos a corto o medio plazo. Sin embargo, el uso como campo de experimentación IA no sólo de los rompecabezas sino de los juegos en general también ha contado con importantes defensores, entre ellos, varios de los fundadores o pioneros de dicha área. Por ejemplo, una analogía probablemente formulada por Herbert Simon para referirse al ajedrez y utilizada posteriormente por John McCarthy en numerosas ocasiones para otros escenarios, es la de comparar el papel que asumen estos ejemplos de juguete en la IA con el de la drosophila o mosca de la fruta en la investigación en Genética, por tratarse del “conejillo de Indias” más habitual en ese campo debido a su adecuada combinación entre complejidad genética y simplicidad fisiológica.

 

 

Ahora bien, ¿qué aspectos de la resolución de un puzzle por ordenador pueden resultar interesantes desde el punto de vista de la investigación en IA? La respuesta más inmediata tendría que ver con el propio proceso de razonamiento a llevar a cabo para resolver el puzzle. Los rompecabezas se han utilizado en numerosas ocasiones como dominios de prueba para el análisis de los distintos mecanismos de razonamiento IA y los algoritmos que se les asocian. Sin embargo, un segundo aspecto tanto o más importante es el modo en que describimos el problema para que el ordenador sea capaz de resolverlo. Aunque esta segunda finalidad pueda parecer menos obvia, se convierte en realidad en un factor crítico, si queremos que nuestro “experimento con la drosophila” tenga después una aplicabilidad más genérica.

 

Para entender mejor lo que se pretende, tomemos el clásico ejemplo conocido como N-puzzle, estudiado en IA en innumerables ocasiones. Se trata de una parrilla de nxn casillas completamente cubierta con N=n² –1 fichas cuadradas y un hueco del mismo tamaño. El tamaño original del juego era de N=15 fichas (una parrilla de 4x4), aunque el caso más utilizado en IA es la versión de 8-puzzle, esto es, una parrilla de 3x3, tal como se muestra en la Figura 1 (que el lector puede probar a manipular). En cada movimiento es posible desplazar una de las fichas adyacentes hacia el hueco. El objetivo del juego es permitir alcanzar alguna configuración meta a partir de una configuración inicial habitualmente arbitraria.

Figura 1. Un ejemplo de problema en el juego del 8-puzzle.

 

A la hora de resolver el puzzle, un jugador humano trabaja más por ensayo y error, aplicando conocimiento subyacente (de sentido común) y aprendiendo características del problema sobre la marcha. La resolución por ordenador, sin embargo, suele recurrir a contemplar cientos de miles de posibilidades en unos pocos segundos mediante el uso de los así llamados algoritmos de búsqueda. El problema del 8-puzzle ha sido una de las “drosophilas” más frecuentes para el análisis de estos algoritmos, dado que, a pesar del reducido número de posibles acciones y su aparente simplicidad, proporciona un espacio de búsqueda (conjunto de estados alcanzables a partir del estado inicial) lo suficientemente grande como para contrastar tanto teórica como empíricamente el efecto de distintas estrategias de búsqueda. Además, se trata de un escenario para el que se conocen importantes propiedades: por ejemplo, el tamaño del antes mencionado espacio de búsqueda (181.440 estados en el caso del 8-puzzle, más de 10 billones para el 15-puzzle) o la categoría de complejidad computacional a la que pertenece (es un problema NP-completo).

 

Eso sí, esta delimitación del escenario tiene sus riesgos. Un error en el que se puede caer con facilidad es el de intentar lograr mayor eficiencia para resolver un dominio dado (en nuestro caso, el 8-puzzle) a costa de centrarse en exceso en el problema concreto que deseamos resolver, perdiendo toda capacidad de extrapolar los resultados y desvirtuando en cierto modo la orientación científica original. Podemos aplicar aquí las palabras de John McCarthy [McC04] dedicadas al ajedrez:

 

Desafortunadamente, los aspectos competitivos y comerciales de lograr que los ordenadores jueguen al ajedrez se han impuesto al uso del ajedrez como dominio científico. Es como si los genetistas después de 1910 hubiesen organizado carreras de moscas de la fruta y hubiesen concentrado sus esfuerzos en criar moscas para ganar esas carreras.

 

Para entender mejor la raíz del problema, supongamos que hemos construido un probador específico para resolver problemas de 8-puzzle de forma muy eficiente. Si deseamos que nuestro experimento sea verdaderamente útil, deberemos ser capaces de aplicar las técnicas usadas en este programa a otros escenarios. Nótese que si no hemos tenido cierto cuidado de partida, este objetivo puede incluso resultar imposible, ya que es fácil que hayamos incrustado a todos los niveles el escenario en el programa que lo resuelve. Por supuesto, lo ideal sería justo lo contrario, esto es, que nuestro programa sirviese para resolver cualquier problema pero, como quizá cabe esperar, esta meta puede resultar demasiado pretenciosa^[3]. Un objetivo que parece más sensato es plantearse aplicar el programa a escenarios de corte similar al original (lo que se suele llamar una elaboración). Por ejemplo, podemos suponer ahora que en la parrilla de 3x3 tenemos dos huecos y, por tanto, podemos manejar un 7-puzzle (Figura 2). En su apariencia física, esta elaboración apenas ha variado respecto al puzzle original y, de hecho, resolver ahora el rompecabezas manualmente resulta mucho más sencillo (podríamos incluso mover simultáneamente una ficha con cada mano).

 

 

La cuestión que deseamos plantear con esta variante es: ¿en qué grado nos permite nuestro programa original para 8-puzzle ser adaptado a este nuevo problema? Si hemos desarrollado el programa de forma cuidadosa, es posible que un pequeño ajuste en las estructuras de datos que maneja y quizá una reprogramación de dos o tres puntos del código sean suficientes. Sin embargo, una forma mucho más interesante y que ofrece mucha mayor flexibilidad sería que nuestro programa tomase, como información de entrada, una descripción del problema que se desea resolver, de modo que su variación suponga retocar esa descripción (enfoque declarativo) y no el método que usamos para resolverla (enfoque procedural).

 

Por supuesto, esto nos lleva a la difícil elección de un lenguaje adecuado en el que poder expresar la descripción del problema. Este es, de hecho, el objeto de estudio de un campo central dentro de la IA conocido como Representación del Conocimiento, en el que se establecen una serie de criterios que permitan valorar la forma más adecuada para “transmitirle” al ordenador qué problema deseamos que resuelva. Entre esos criterios, podemos citar como los más habituales: la sencillez, la capacidad para lograr descripciones compactas, la facilidad para asociar métodos de razonamiento eficientes, y lo que se denomina como tolerancia a la elaboración. Esto último fue definido por McCarthy [McC98] como la capacidad de aceptar cambios en una representación de hechos sobre una materia sin verse forzado a rehacerlo todo desde un principio.

 

Un lenguaje enormemente versátil que satisface algunos de los factores deseables que mencionábamos antes es el propio lenguaje humano (en nuestro caso, el español). Nótese cómo nos ha bastado arriba con un par de líneas de texto para definir la nueva variante del 7-puzzle. Sin embargo, la interpretación del lenguaje humano, plagado de ambigüedades y necesitado de constante aplicación de conocimiento de contexto, es un campo muchísimo más complejo que los propios puzzles que deseamos usar como drosophila. Una opción que resulta mucho más “fácil de manejar” computacionalmente hablando, son los lenguajes lógicos, ya que permiten descripciones precisas, poseen métodos de inferencia asociados bien conocidos y ofrecen un razonable grado de flexibilidad.

 

En el resto del artículo, con el objeto de ilustrar algunas de las ideas que acabamos de introducir, formalizaremos algunos rompecabezas más o menos conocidos utilizando un lenguaje de aspecto cercano a la lógica matemática y para el que existe un probador accesible en Internet que nos permite experimentar y jugar (de modo limitado) a proponer variantes para cada uno de estos juegos.

 

 

Un par de escenarios estáticos

 

El Functional Action Language (FAL) [Cab05, FAL06] está pensado para describir problemas de satisfacción de restricciones que pueden además conllevar razonamiento temporal en un sistema de transición de estados. En FAL, un problema se expresa en términos de un conjunto de funciones y un conjunto de reglas que establecen la relación entre los valores que deben tomar esas funciones. Cada solución al problema es una posible asignación de valores de función que concuerda con el conjunto de reglas que hemos proporcionado.

 

Desde el punto de vista sintáctico, FAL se asemeja a los lenguajes de programación lógica, mostrando un estilo similar al del lenguaje Prolog [Col92], uno de los más utilizados en IA. Por ejemplo, una regla Prolog perfectamente posible en FAL podría ser:

           

           

que podríamos leer como “Y es la madre de X si es uno de los progenitores de X y además es mujer”. Al igual que en Prolog, las variables se representan con la letra inicial en mayúsculas, como la X o la Y de arriba, mientras que el símbolo “:-” se entiende como la implicación hacia la izquierda ←, y la coma viene a representar la conjunción . La principal diferencia sintáctica de FAL respecto a Prolog es la posibilidad de referirse a valores de funciones^[4] en lugar de usar exclusivamente predicados (como los que hemos visto: madre, progenitor o mujer). Por ejemplo, dado que normalmente la madre de una persona es única, podríamos usar una función madre(X) en lugar de un predicado binario:

 

madre(X)=Y :- progenitor(X,Y), mujer(Y).

 

La ventaja más interesante del uso de funciones es su anidamiento, esto es, que pueden ser usadas como argumentos de otras funciones o predicados, como en la regla:

 

abuela(X,madre(Y)) :- progenitor(X,Y).

 

que indica que, como abuela de X, podemos tomar el valor de madre(Y) para cualquier Y progenitor de X.

 

Desde el punto de vista semántico, sin embargo, FAL se separa de los aspectos más procedurales de Prolog (en FAL no existe orden de evaluación de las reglas o predicados de control de tipo corte), apoyándose por el contrario en un paradigma de programación lógica más declarativo: la semántica de Modelos Estables [Gel88]. Esta semántica surgió como interpretación formal de la negación por defecto que se usa en los programas lógicos^[5]. Con el tiempo, la programación bajo modelos estables (también conocida bajo el nombre de Answer Set Programming) ha dado lugar a todo un estilo distinto de programación lógica, orientada sobre todo a la resolución de problemas de tipo combinatorio, y para la que existen hoy en día herramientas de cálculo muy eficientes. La principal diferencia de este paradigma respecto a Prolog reside en el hecho de que la respuesta que obtenemos de un programa viene dada en término de varios modelos (sus modelos estables), siendo cada modelo un conjunto de átomos sin variables.

 

Sin entrar en mayor detalle, el funcionamiento actual del intérprete de FAL consiste en sustituir las referencias a funciones por nuevas variables auxiliares y generar como salida un programa lógico sin funciones que luego es interpretado por herramientas de cálculo de modelos estables (principalmente, smodels [SM00] y DLV [DLV06]). Una característica esencial de estas herramientas, y que por tanto hereda el intérprete de FAL, es la necesidad de manejar dominios finitos. La semántica de FAL y el proceso de traducción están descritos en [Cab04, Cab05].

 

En este artículo vamos a proceder de un modo más informal, introduciendo las ideas fundamentales mediante ejemplos. Consideremos un nuevo puzzle también muy conocido: se trata de colocar ocho reinas en un tablero de ajedrez de modo que no se ataquen entre ellas. Para resolver el problema debemos pensar en cómo expresar formalmente la solución. Por ejemplo, podríamos usar como guía el propio tablero, con un predicado que indique, para cada celda en fila X y columna Y, si hemos colocado en ella una reina o no, esto es, has_queen(X,Y) es cierto o falso. El problema de esta opción es que, aparte de comprobar que no haya ataques, tendríamos también que comprobar adicionalmente que el tablero contiene ocho reinas.

 

Para evitar hacer esa cuenta, por el contrario, podemos usar como guía cada una de las reinas que deseamos colocar. Así, sería suficiente con establecer, para cada reina, una fila y una columna (que llamaramos qrow y qcol respectivamente) que indican la posición donde la hemos colocado, y comprobar después que no existen ataques entre ellas. Para comenzar, podríamos declarar las dos funciones:

 

La etiqueta static se usa para indicar que estas funciones no varían en el tiempo (esto ahora es irrelevante, ya que no estamos planteando un problema temporal). A continuación, deberemos también declarar qué valores componen los conjuntos queen, row y column. Esto se realiza declarando componentes de conjunto (instances) del siguiente modo:

 

Tan sólo nos resta ahora proporcionar las reglas que describen el problema. Para ello, utilizaremos dos nuevos tipos de reglas que, aunque en realidad son traducibles al formato de las que hemos visto arriba (1), facilitan enormemente la labor de programación. En primer lugar, aunque qrow ha sido declarada con un rango tipo row, esto no conlleva que se le asigne valor alguno (en principio, sin añadir más declaraciones, su valor quedaría indefinido). Para indicar que deseamos asignar arbitrariamente un valor de fila a qrow (y análogamente a qcol) utilizaremos reglas del estilo:

 

donde, como podemos ver, estamos especificando una variable Q de tipo queen, de modo que siempre que usemos Q en una regla se va a entender como local a la regla y cuantificada universalmente.

 

En su estado actual, el programa generaría todas las combinaciones resultantes de colocar cada reina en cada una de las 64 posiciones del tablero, permitiendo incluso más de una reina en la misma celda. Esto es, obtendríamos 64⁸ = 2⁴⁸, es decir, más de 2.800 billones de soluciones posibles. El segundo tipo de regla que utilizaremos son las restricciones propiamente dichas. Sintácticamente se caracterizan por comenzar directamente por el símbolo :- (lo que representa una implicación con consecuente falso), y nos van a permitir descartar aquellas combinaciones que no deseamos. En nuestro caso, queremos rechazar combinaciones con dos reinas (distintas) en la misma fila o la misma columna:

 

o la misma diagonal:

 

:- |qcol(Q)-qcol(Q2)|=|qrow(Q)-qrow(Q2)|, Q!=Q2.

 

El programa completo, más resumido, se muestra en la Figura 3. Podemos probar a obtener soluciones copiando ese mismo texto en el recuadro de la página del probador online de FAL [FAL06] y pulsando el botón “submit”.

 

 

La solución aparece tras cierto tiempo. En realidad, no es de extrañar la tardanza, dado que desde el punto de vista de la eficiencia, nuestra descripción del problema contempla demasiada información irrelevante. Por ejemplo, una misma distribución de reinas sobre el tablero da lugar a distintas soluciones dependiendo de la etiqueta que pongamos a cada reina. En otras palabras, si una reina ocupa la casilla (1,1) nos importa poco saber si es la reina 4 o la reina 7. Dado que esa información es irrelevante, podríamos identificar, por ejemplo, cada reina por su fila correspondiente, puesto que sólo una reina ocupará cada fila. Esto da lugar a la segunda versión del problema representada en la Figura 4 y que, en realidad, aparece como escenario predefinido en la página de FAL bajo el nombre “8-queens”.

 

 

Como se puede comprobar, esta segunda versión ofrece una descripción más compacta y, sobre todo, permite obtener la solución de forma más eficiente (el número de posibilidades a explorar en teoría se reduce ahora a 8⁸=2²⁴ es decir, tan sólo del orden de unos 17 millones) lo que se percibe de forma inmediata al ejecutar el probador online. Incluso es ahora factible solicitar todas las soluciones (marcando la casilla “get all solutions”) y obtener las 92 respuestas en apenas un par de segundos.

 

Las dos codificaciones que hemos empleado en este ejemplo ponen también de manifiesto que, aunque estamos usando un enfoque declarativo y ya no dependemos del método de resolución del problema, la representación que escojamos para describirlo puede también sufrir de mayor o menor dependencia respecto al dominio que estamos tratando, permitiendo una mayor o menor flexibilidad. Por ejemplo, aunque nuestra segunda codificación es evidentemente mucho más interesante desde el punto de vista de la eficiencia, también muestra un menor grado de flexibilidad, pues supone una identificación completa entre fila del tablero y el número de reina. Esto dejaría de ser válido, por tanto, si nos pidiesen colocar las 8 reinas en un tablero ligeramente mayor, pongamos de 10x10, mientras que la formulación inicial en la Figura 3 seguiría siendo aplicable: en realidad, sería suficiente con añadir al texto las líneas

  

 

El escenario de las 8 reinas constituye un rompecabezas de tipo estático, en el sentido de que no involucra una secuencia temporal de movimientos (o transiciones de estados). Otro escenario de aspecto similar es el antes mencionado Sudoku. Se trata de colocar en cada casilla de una matriz de 9x9 un dígito del 1 al 9, sin repetir ninguno en la misma fila o la misma columna. Además, la matriz se subdivide en nueve bloques de 3x3, dentro de los que tampoco podemos repetir dígitos. Habitualmente, se suministran algunas casillas con valor fijo y debemos rellenar el resto. La Figura 5 muestra un juego de Sudoku y permite ir completándolo y chequeando posibles errores.

 

Figura 5. Un escenario de Sudoku.

 

 

En este caso podemos usar una función array(X,Y) para indicar el contenido de cada casilla X, Y en una solución dada. La Figura 6 muestra la codificación del problema a partir de esa representación. Las dos últimas restricciones se encargan de eliminar repeticiones en el mismo bloque (el símbolo “/” indica división entera). Nótese que, como queremos que las posiciones (R,C) y (R2,C2) sean distintas, obtenemos una disyunción (R ≠ R2)  (C ≠ C2) que se traduce en dos reglas, una para cada caso.

 

 

El Sudoku es uno de los puzzles predefinidos en la página de FAL. Para ponerlo a prueba, tan sólo resta añadir las casillas que queramos fijar. Por ejemplo, presionando el botón “Mostrar hechos FAL” en la Figura 5 obtenemos la lista de hechos correspondiente al estado actual del puzzle, la cual podemos copiar directamente junto con el texto de la Figura 6 en la página de FAL.

 

Una de las características peculiares de FAL que nos resta por comentar es la posibilidad de definir un valor por defecto para cualquier función declarada. Como ejemplo, consideremos el par funciones booleanas (o predicados):

 

 

El primer predicado no tiene valor por defecto, por lo que podemos declarar le_gusta(X,Y)=true o declarar le_gusta(X,Y)=false, pero en ausencia de información al respecto, no tendrá un valor definido, lo que comprobaríamos usando la expresión unknown (le_gusta(X,Y)). Por el contrario, el segundo predicado, progenitor, está siendo declarado como falso por defecto. Esta sutil diferencia puede convertirse en un factor crucial, ya que normalmente nos interesará evitar tener que describir la lista de personas que no son progenitores de una persona dada. Aunque la inclusión de un valor por defecto pueda parecer bastante trivial, hay que tener en cuenta que decidir si una función toma su valor por defecto o no dependerá del conjunto de reglas que manejamos y del valor por defecto de otras funciones. En general, esta característica de FAL hace que el lenguaje posea exactamente la misma capacidad expresiva [Cab04] que los programas lógicos bajo modelos estables.

 

 

Escenarios dinámicos

 

En el apartado anterior hemos visto un par de puzzles que hemos denominado estáticos en el sentido de que no conllevan una evolución temporal. En otras palabras, el propósito era describir la configuración de un único estado del sistema (por ejemplo el tablero de ajedrez) pero no una secuencia de transiciones de estados (por ejemplo, una sucesión de movimientos de piezas en el tablero). Un gran número de juegos rompecabezas entrarían por el contrario dentro de la categoría de escenarios dinámicos, en los cuales disponemos de una serie de posibles acciones que nos permiten movernos de un estado a otro. Claramente, este es el caso del antes mencionado 8-puzzle, en el cual la solución que buscamos vendrá dada en términos de una secuencia de acciones (lo que se suele llamar un plan) que permita llegar del estado inicial al estado final o meta. Este tipo de planteamientos son los estudiados en un área de la Inteligencia Artificial conocida como Planificación.

 

Una posibilidad para representar escenarios de planificación en FAL sería el replicar aquellas funciones que varíen en el tiempo usando, por ejemplo, un subíndice para indicar la situación temporal a la que hacemos referencia. Esta representación es perfectamente posible, siempre que fijemos de antemano la longitud n de las secuencias de transiciones a considerar (recordemos que el intérprete de FAL necesita dominios finitos). Aunque, en la práctica, el modo en que el intérprete de FAL trata a la postre estos escenarios es precisamente el que acabamos de describir, el lenguaje ofrece construcciones de más alto nivel que facilitan la descripción de dominios dinámicos. Para empezar, se definen en FAL nuevos tipos de funciones: los más importantes son los fluentes y las acciones. Los fluentes representan variables del sistema cuyo valor puede fluctuar en el tiempo. Sobre los fluentes se aplica además el llamado supuesto de inercia, según el cual el valor por defecto para un fluente en la situación i es el valor que ese fluente poseía en la situación anterior i–1. En otras palabras, en el resultado de una transición estamos suponiendo que un fluente mantendrá por defecto su valor anterior, si no existe más información al respecto. Las acciones también cambian de valor en el tiempo, pero no cumplen este principio de inercia. Además, cuando planteamos un problema de planificación, su aparición es totalmente libre (podrían ser vistas como eventos externos carentes de justificación).

 

Al igual que hicimos con los escenarios estáticos, quizá sea más sencillo considerar un ejemplo, retomando ahora el juego del 8-puzzle. Podemos comenzar definiendo una función que represente el tablero (board) sobre el que movemos cada ficha (tile):

 

Nótese que el supuesto de inercia para la función board es esencial desde el punto de vista de la tolerancia a la elaboración. Sin ese supuesto, en las reglas de más abajo que describen el cambio de posición de una ficha dada necesitaríamos también especificar qué ocurre con el resto de fichas no modificadas por el cambio (gracias a la inercia, esto no será necesario). También podemos ver que en board(X,Y) podemos tener una ficha o el valor empty (vacío), siendo este último el valor por defecto. En el caso de los fluentes, el valor por defecto se usa para especificar la situación inicial, dado que en ese caso no hay valor anterior del que la inercia pueda “echar mano”. En nuestro ejemplo, esto significa que no hace falta declarar las casillas del tablero que deseemos que queden vacías (en el 8-puzzle, tan sólo una).

 

A continuación debemos escoger el conjunto de posibles acciones. En el caso del 8-puzzle, este conjunto es muy reducido: si pensamos en que un movimiento corresponde a desplazar el hueco en el tablero, existen como mucho cuatro posibilidades en cada transición. Podemos definir una acción:

 

 

que nos deja seleccionar una dirección en la que desplazar el hueco de entre las cuatro posibilidades: arriba (up), abajo (down), izquierda (left), o derecha (right). Aunque con la función board tenemos toda la información necesaria para representar un estado, a veces es conveniente introducir nuevas funciones redundantes que facilitan la descripción del escenario. En nuestro caso, para describir el efecto de la acción move_dir, por ejemplo, sería mucho más conveniente representar en todo momento la situación en la que se encuentra el hueco a desplazar:

 

 

de modo que hole(r) y hole(c) indican la fila (row) y columna (column) donde se encuentra el hueco. Una regla de transición en FAL se caracteriza por permitir dos copias de cada función. En nuestro ejemplo, board(X,Y) representaría la posición X,Y del tablero en el estado anterior a la transición, mientras que board'(X,Y) sería el contenido de esa misma posición en el estado resultante. De este modo, el movimiento de una ficha viene determinado por el siguiente conjunto de reglas:

 

donde la función inc determina el incremento de fila o columna que le corresponde a cada tipo de movimiento:

Para finalizar, nos restaría especificar los estados inicial y final usando respectivamente las etiquetas initially y goals y proporcionando una lista de hechos (del estilo, por ejemplo, board(1,1)=4) en cada caso. El escenario completo puede consultarse en la página del intérprete de FAL bajo el nombre 8puzzle. Nótese que, para su resolución, es necesario establecer la longitud de la secuencia de transiciones, ya sea determinando un valor fijo (en este caso, basta con seis) o que se intenten incrementalmente todos los valores por debajo de un límite.

 

La representación que hemos obtenido para el 8-puzzle tiene la ventaja de economizar el número de acciones a elegir en cada caso (en la peor situación, con el hueco en el centro, debemos elegir entre cuatro posibles transiciones), lo que, como se puede imaginar, resulta muy conveniente para encontrar un plan más eficientemente. Ahora bien, desde el punto de vista de la tolerancia a la elaboración, estamos haciendo algunas suposiciones que impiden adaptar el problema a otras variantes. Si consideramos ahora la posibilidad del 7-puzzle mencionada en la introducción (esto es, tener dos o incluso más huecos) es fácil comprobar que nuestra representación ya no es válida, pues dependemos de la posición del hueco hole(r), hole(c)partiendo de que este último es único. Para evitar este problema, deberíamos cambiar el tipo de acción a ejecutar. Una posibilidad sería la mostrada en la Figura 7, usando una acción move(X1,Y1,X2,Y2) que toma como argumentos la casilla origen X1,Y1 y la casilla destino X2,Y2. El número de acciones posibles a elegir aumenta ahora considerablemente, ya que podemos tomar cualquier par de posiciones (en el 8-puzzle tenemos, en principio, 9x9=81 posibilidades de elección en cada transición). Las dos primeras reglas se encargan de eliminar las acciones no deseadas, escogiendo sólo aquellas que suponen un movimiento entre casillas adyacentes y que además mueven hacia una casilla vacía.

 

 

Lo interesante del ejemplo es que no se hace ahora supuesto alguno sobre el número de casillas posiblemente vacías. De este modo, podemos usar exactamente la misma representación para el 8-puzzle o el 7-puzzle: la diferencia se establecerá únicamente en la descripción del estado inicial, donde indicaremos en qué posiciones hay fichas, dejando las demás vacías por defecto. Como ejemplo, podemos probar a añadir al código anterior los siguientes estados inicial y final:

 

 

y lanzar el probador de FAL (encontraremos una solución en ocho transiciones, que pueden reducirse a cinco si marcamos la casilla de acciones concurrentes, “Enable concurrent actions”).

 

 

Conclusiones

 

Como hemos visto, los puzzles constituyen herramientas muy interesantes para medir la capacidad de los lenguajes de representación del conocimiento usados en Inteligencia Artificial. En ese sentido, hemos comprobado cómo utilizando una notación matemática es posible adoptar un enfoque totalmente declarativo, en el que se describe la solución a obtener y no el método empleado para obtenerla. Esto permite adaptar fácilmente la representación de un juego frente a pequeñas variaciones en el planteamiento del mismo. También hemos comprobado cómo, incluso bajo este enfoque totalmente descriptivo, es habitual que cuando se busca una representación más eficiente (en el sentido de contemplar menos combinaciones) se obtenga una representación menos flexible (en el sentido de poder ser adaptada a nuevas variantes). En cualquier caso, lo verdaderamente importante es que el lenguaje que utilicemos nos permita elegir el tipo de representación que nos conviene dependiendo de nuestros objetivos.

 

 

Referencias

 

[Cab04]         P. Cabalar, D. Lorenzo: Logic Programs with Functions and Default Values. En Actas de la IX European Conference on Logics in Artificial Intelligence (JELIA'04), Lisboa, Portugal. Lecture Notes in Artificial Intelligence 3229, pp. 294?306.

[Cab05]         P. Cabalar: A Functional Action Language Front-end. Presentado en el III Workshop on Answer Set Programming (ASP–05), Bath, Reino Unido, 2005.

[Col92]           A. Colmerauer, P. Roussel: The birth of Prolog. En History of Programming Languages (T.J. Bergin, R.G. Gibson, eds.). ACM Press/Addison-Wesley, 1996.

[DLV06]          The DLV Project: a Disjunctive Datalog System (and more),
http://www.dbai.tuwien.ac.at/proj/dlv.

[Euler1782]    L. Euler: Recherches sur un nouvelle espéce de quarrés magiques. En Verhandelingen uitgegeven door het zeeuwsch Genootschap der Wetenschappen te Vlissingen 9 (Middelburg, 1782), 85-239.

[FAL06]          Functional Action Language (FAL) web page, http://www.dc.fi.udc.es/~cabalar/fal. Probador online: http://www.dc.fi.udc.es/~cabalar/fal/FALonline.html.

[Gel88]           M. Gelfond, V. Lifschitz: The Stable Models Semantics for Logic Programming. En Actas de la V International Conference on Logic Programming. The MIT Press, 1988, pp. 1070?1080.

[Han94]          M. Hanus: The Integration of Functions into Logic Programming: From Theory to Practice. Journal of Logic Programming 19–20 (1994), 583–628.

[McC98]        J. McCarthy: Elaboration Tolerance. En Actas del IV International Symposium on Logical Formalizations of Commonsense Reasoning. Londres, 1998. [Versión actualizada disponible en http://www-formal.stanford.edu/jmc/elaboration.html].

[McC04]         J. McCarthy: What is Artificial Intelligence?,
http://www-formal.stanford.edu/jmc/whatisai/node1.html [Última actualización: noviembre 2004].

[SM00]           Computing the Stable Models Semantics, http://www.tcs.hut.fi/Software/smodels.

 

---

 

^[1] Sudoku es el nombre japonés del juego Number Place, ideado por el estadounidense Howard Garnes y publicado por primera vez en el año 1979. La principal innovación de Number Place respecto al ejercicio propuesto por Euler consistió en requerir la aparición única de cada cifra no sólo en filas y columnas, sino también en cuadrados de tres por tres casillas.

^[2] En realidad, esto último tampoco sería descabellado, si pensamos en los procesos de entrenamiento habituales de la disciplina IA de Aprendizaje Automático.

^[3] Esta fue de hecho una de las metas planteadas como factibles en los primeros pasos de la IA, con orientaciones del estilo General Problem Solver [GPS] que pretendían resolver cualquier problema genérico. Más tarde, gracias al avance en el área de complejidad computacional y a los resultados relacionados con la no computabilidad de determinados problemas, se comprendió que este objetivo era inalcanzable.

^[4] La integración del uso de funciones en la programación lógica es un área que se conoce como Programación Lógica Funcional (ver [Han94] como recopilatorio).

^[5] La negación por defecto de un hecho, por ejemplo not p(X), se lee como “no existe evidencia sobre p(X)” en lugar de la interpretación clásica que se leería como “p(X) es falso”.