juego de dos baldes Carlos von der Becke (1989, con actualizaciones posteriores). Ejemplo de Búsqueda en Espacio de Estados de Inteligencia Artificial y Teoría de los Juegos 1) ENUNCIADO Disponemos de un balde grande de volumen G (p.ej 9 L) y un balde chico de volumen C (p.ej. 8 L). Como objetivo final ("estado gol") deseamos tener GOL = G−C+Sumando (donde Sumando puede ser, p.ej,, 6 L, en cuyo caso particular el GOL es tener 9 − 8 + 6 = 7 L) en el balde chico. La definición de Sumando se despeja de la ecuación previa y es Sumando = GOL − (G− C) . Para lograrlo disponemos de canilla de agua y de un sumidero. Si existen solucione múltiples, preferimos aquí que sea la que minimice el esfuerzo de llegar al estado GOL. 2) TIPO DE PROBLEMA Se trata de un problema muy elemental, pues no existe competencia contra la cual jugar (es un solitario, no un juego de dos o más contrincantes): el objetivo es lograr un único estado GOL y los estados ya superados por el análisis no pueden volver a estar en la solución óptima Es un problema lineal donde cada estado sucesivo es el resultado de un estado previo multiplicado por un operador; el estado inicial siempre es el mismo, ambos baldes con 0 L, lo cual se escribirá 00. Como siempre el estado inicial es el mismo y también lo es el estado GOL, esto es, GOL = G − C + Sumando , se trata de un problema típico de trayectoria. (Existen otros problemas de trayectoria fija con incógnita a optimizar que es el punto de partida o de llegada).Hay una red de estados que recorrer entre el estado inicial y el estado GOL, que tiene ramales muertos. Como se ha dicho, en esa red no hay que reciclar para retomar nodos superados. La revisación de la red es una de las más sencillas, tipo búsqueda primero en amplitud o FIFO (first in, first out) pues ella se adecua a que, en caso de soluciones múltiples, aparezca como buena la más corta de lograr. 3). NIVELES DEL PROBLEMA El problema o juego de los dos baldes se puede encarar desde el punto de vista de la inteligencia artificial en dos etapas muy diferentes. La primera etapa no exige aprender. Es un nivel inferior de "inteligencia". A este nivel se lo puede 1

denominar método evolutivo darwiniano, basado en el principio de MUTACION (o variación) CIEGA Y SUPERVIVENCIA DE LA SOLUCION MAS APTA , que será la TRAYECTORIA deseada en el espacio de problema o red de estados. La segunda etapa o nivel es más interesante ya que exige aprender o deducir nuevas reglas aplicables, en base a casos acumulados durante las tentativas. Por ejemplo, se puede aprender o intuir que para llegar a cierto estado GOL es inevitable pasar por algún determinado estado INTERMEDIO. Al llegar a este estado podemos decir que el problema original se ha dividido en dos subproblemas más sencillos. Uno desde el estado INICIAL al INTERMEDIO y otro desde el estado INTERMEDIO al FINAL o gol. A esto se lo denomina método GPS, General Problem Solver. En la BASE DE CONOCIMIENTOS del sistema ingresa un CONOCIMIENTO de procedimientos, referido a cómo deducir algún estado INTERMEDIO por el cual es necesario pasar, para facilitar nuevas resoluciones. En el mismo nivel puede surgir (con la ayuda de un especial conocimiento de procedimientos) la forma de detectar por adelantado futuros estados TABU, esto es, puntos situados en caminos sin perspectivas para llegar al estado GOL Es similar a lo que se llama espíritu crítico basado en experiencias previas o Case−Based Reasoning, CBR, razonamiento basado en casos. Por ejemplo llenar los dos baldes con agua a ras genera un estado TABU, inapropiado para obtener el estadoGOL, ya que ese estado TABU estará siempre dominado por llenar uno sólo de ambos baldes. Con los dos baldes llenos lo único que está permitido hacer es vaciar uno de ellos como operación siguiente, con lo cual aparece un sólo balde lleno y el otro vacío. ¿Para qué perder tiempo en llenar ambos baldes, si es más corto llenar uno solo y operar con él? Este CONOCIMIENTO de procedimientos, o regla no introducida previamente, puede ingresar a la BASE DE CONOCIMIENTOS por APRENDIZAJE. Es un borrador de un SISTEMA EXPERTO para la resolución del juego de los dos baldes. Aunque estrictamente, se prefiere construir sistemas expertos cuando hay que combinar por lo menos cincuenta reglas, lo cual no es este caso simple. A pesar de la sencillez del primer nivel queda claro que reducir un problema a resolver a una red de ESTADOS y de OPERADORES (o sea de las decisiones para transformar un estado en otro) es de por sí muy valioso y muy adecuado a las posibilidades de las oomputadoras digitales, para las cuales es inmediato operar con VECTORES (los estados) y MATRICES (los operadores), mientras que para la inteligencia humana esta capacidad no se da habitualmente. Tambien queda claro que un borrador de SISTEMA EXPERTO para resolver el problema de los dos baldes ahorra esfuerzos y PODA la red, evitando operar con estados TABU o descubriendo etapas intermedias para aplicar el método GPS. En estos casos ya no rige la técnica de búsqueda primero en amplitud sin eliminación de repetidos o FIFO, anteriormente mencionada, sino que ingresamos a una TEORIA DE COLAS CON PRIVILEGIOS o búsqueda primero en amplitud con eliminación de repetidos. Algo de la teoría se ha de aplicar en este trabajo, aunque su principal propósito es el de ilustrar el primer nivel, sin AUTOAPRENDIZAJE de procedimientos mejorados a usar. Se quiere llegar a un diagrama de flujos (FLUJOGRAMA) y a un programa computacional que resuelva cualquier problema de dos baldes, con la única limitación, por ahora, de un valor tope de 9 L para C, la capacidad del balde chico y que tanto G como C sean números enteros. 4. DETALLES EN LA REVISACION DE LA RED Piénsese que los sucesivos estados entre Inicial (00) y GOL o meta (07) se razonan así. El último dígito corresponde a los litros de agua del balde chico; así 00 indica (entre otras cosas) que allí el balde chico está vacío mientras 07 indica que en el balde chico de ocho litros totales hay siete. Descartando de la explicación el último dígito, el resto de ellos implica el estado del balde grande. Si. como se ha elegido, G = 9, quizás se consiga pasar por estados donde tenga menos. Por ejemplo 8, 7 ó 0. (El programa resolutorio aplicado a diferentes parámetros, revela que puede tener, operando correctamente, tanto 9 2

como 8,7,6,5,4,3,2,1,0 L, lo cual no es para nada intuitivo). A es el estado del balde grande , B es el del chico

|A|B| Un ejemplo trivial es el de proponer como estado GOL 08, (o sea A = 0 y B = 8) pues basta con llenar el balde chico a ras para lograrlo. Otro ejemplo trivial es GOL = 01, pues llenando el balde grande a ras, estado (90), transfiriendo de grande a chico hasta el ras de éste, estado (18), y drenando el chico, estado (10), para volcar en él, el contenido del grande, se obtiene el estado GOL (01). Los otros casos de la lista previa son notoriamente más complejos Esto es, requieren una secuencia mayor de OPERADORES. 5. OPERADORES La forma matemática para el empleo de operadores o matrices cuadradas es la siguiente: Vector fila de entradas, premultiplicador Matriz cuadrada de operadores adimensionales, postmultiplicadora Vector fila de salidas o resultados de la multiplicación vectorial Las posibilidades permitidas, con un poco de manipuleo y experiencia, se reducen a sólo seis decisiones diferentes, cada una de las cuales tiene una típica forma de operar., a veces necesitada de ajustes especiales. Con dichos ajustes puede decir que hay seis algoritmos diferentes para transformar ESTADOS, Esos seis algoritmos son seis OPERADORES, o seis decisiones, a saber I) Vaciar el balde chico a cero, con un operador no estocástico, la matriz cuadrada de la segunda y tercera fila: A 1 0 A

B 0 0 0

II) Vaciar el balde grande a cero, operador no estocástico de la segunda y tercera fila: A 0 0 0

B 0 1 B

III) Transferir de chico a grande, operador estocástico que admite dos opciones: ð Si A + B < C, no hay posibilidad de llegar a ras del balde grande y entonces el operador es el de la seguna y tercera fila: A 1 1 A+B

B 0 0 0

3

ð En el otro caso, se puede llegar a ras en el balde grande y puede quedar remanente en el chico, caso donde el operador es el de la siguiente segunda y tercera fila: A 1 (G−A)/B G

B 0 (A+B−G)/B A+B−G

En una versión más elaborada se puede introducir una variable auxiliar que adopta diferente forma según cada una de las dos opciones. Con ella, el operador es único para ambos casos. IV) Transferir de grande a chico, con dos opciones: ð Si A + B < C no hay posibilidad de llenar a ras el balde chico y entonces el operador estocástico es A 0 0

B 1 0

1 A+B

ð En el otro caso, se puede llenar a ras el balde chico y puede quedar un remanente en el balde grande, con el siguiente operador: A (A+B−C)/A 0 A+B−C

B (C−B)/A 1 C

V) Llenar a ras el balde chico (usando la canilla para aportar lo que le falte), que implica reemplazar el valor de B previo por el nuevo valor, C, lo que se puede lograr multiplicando a B por el operador (C/B) − el caso particular de la indeterminación cuando B = 0 se debe resolver por L'Hopital así: B (C/B) = C. A 1 0 A

B 0 C/B C

Notas: Una computadora da señal de error si B es cero, por lo cual se debe prever por adelantado ese caso. En la versión más elaborada se utiliza una matriz de tres por tres en lugar de dos por dos, para permitir el libre uso del sistema de canilla/sumidero, cuya presencia física se indica en el modelo matemático con un 1 en la intersección de la tercera fila con la tercera columna. Esa fila y columna adquieren el referido significado físico y ya no aparece (C/B). Otras maneras de encarar el tema son considerar, muy sencillamente, el aporte de agua de canilla como una suma y el desaporte o vaciado usando sumidero como una resta. Si se sigue este razonamiento, hay entonces la opción de reemplazar sumas y restas, por multiplicaciones matriciales, mediante el expediente de aumentar la dimensionalidad de la matriz. Si el programa anda sin errores, es porque hay un sentido físico en lo hecho. Es una tarea entretenida encontrarle significado físico a dicho aumento, que resulta que aparece.

4

VI) Llenar al ras el balde grande, que implica reemplazar A por G, caso simétrico y con iguales comentarios al recién analizado V). En uno y otro caso está claro que al ingresar agua desde fuera de los dos baldes. la matriz cuadrada para ese aporte deja de ser estocástica. A G/A 0 G

B 0 1 B

NOTA: Si A = 0 y para evitar el error de dividir por cero con G/A, reemplácese A por G. Los seis operadores se clasifican en tabla de doble entrada: BALDE CHICO GRANDE

VACIAR A CERO Operador I Operador II

TRANSFERIR DE UNO A OTRO Operador III, de chico a grande Operador IV, de grande a chico

LLENAR A RAS Operador V Operador VI

6) REVISACION DE LA RED Aunque para cada nodo de la red hay 6 sucesores (que se obtienen a partir del estado a expandir, aplicándoles de a uno por vez los seis operadores precedentes) vamos a recurrir a la teoría de las colas con privilegios eliminando del análisis todos los sucesores que resulten ser repetidos de situaciones previas. Pese a esa simplificación o PODA de la red, se la considera una búsqueda primero en amplitud con eliminación de repetidos. Esto implica señalar que la revisación será empezando por el estado inicial, siguiendo por todos los sucesores de primer nivel no repetidos hasta terminar con ellos, siguiendo entonces con los sucesores de los sucesores, no repetidos, hasta terminar con este segundo nivel; y así siguiendo, hasta hallar el estado GOL o bien fracasar (por ejemplo se fracasa si se pide una solución GOL = número par (excluyendo al cero) con baldes G = 9 y C = 6, salvo la solución trivial GOL = 6, obtenida de entrada. Se aclara que podría haber otras maneras de revisar la red, por ejemplo privilegiando el estudio de los sucesores no repetidos usando el operador VI hasta fracasar y luego hacerlo con los sucesores del operador V, etc. Esta estrategia se denomina búsqueda primero en profundidad o LIFO, "last in, first out", como sucede con los usuarios de un ascensor que no ceden sitio a las damas al salir en planta baja. 7, LISTA ABIERTA − Búsqueda primero en amplitud o FIFO Contiene los sucesores que han sido generados durante la expansión de estados, segun la estrategia elegida, Conviene eliminar de la lista todos los estados repetidos; esta eliminación puede extenderse a la totalidad de la lista abierta. Se eliminan tambien las soluciones nulas en algunos casos. Como es búsqueda primero en amplitud o FIFO, se elige la cabeza de la lista como candidato para verificar si no está ya presente en la lista cerrada. Superada esa restricción, se generan sus sucesores, esto es, se procede a expandirlo. Si la cabeza ya está en la lista cerrada, se considera al candidato siguiente en el orden. En caso de no estar todavía en lista cerrada, se procede a cortar, esto es, a decapitar la lista abierta, en su cabeza, perdiendo su turno los sucesores anotados hasta inclusive el estado que se va a expandir, que se va a denominar el estado preferido (PR). 5

8. LISTA CERRADA Contiene, ordenadamente, los estados que ya se han expandido o que en este momento empieza a expandirse en sus sucesores, caso del preferido (PR), que estará al final de la lista cerrada. No puede haber repetidos en la lista cerrada. Si en la lista abierta todos los estados anotados ya están anotados tambien en la cerrada, es síntoma de fracaso en la búsqueda. 9. MANIPULEO DE LISTAS, INICIALIZACION: Empezamos. El estado INICIAL es el único estado de la lista abierta. Pasa a la lista cerrada y deja vacía la lista abierta, que sin embargo recibe los seis sucesores del estado INICIAL (Pasos 10 a 57 del programa del apéndice) CUERPO: PLAN MAESTRO (60 y 460) − PASAJE DE LISTAS = Reconocimiento del estado privilegiado (PR) y corte de la cabeza inútil de la lista abierta; incorporación de PR a lista cerrada (60 a 116) OPERADORES (120) − Reconocimiento de eventual identidad entre estado PR y estado GOL − Cálculo del número de dígitos de la trayectoria que llevó al estado preferido (PR) . Cáculo de A, B., P(I) y R(I), siendo A − contenido en este estado del balde grande B − contenido en este estado del balde chico F(I) − resultado de multiplicar el estado por el operador (I) explicado en alguna subrrutina siguiente R(I) − idem + la trayectoria recorrida desde el principio basta este estado Subrrutina Operador I − caso del vaciado del balde chico (5500 − 5599) Operador II − caso del vaciado del grande (5600 −5699) Operador III, transferencia de chico a grande (5700 − 5799) Operador IV, transferencia de grande a chico (5800 −5899) Operador V, llenado a ras del balde chico (5900− 5999) Operador VI, llenado a ras del balde grande (6000− 6100) Las subrrutinas llaman a otra para fijar el trayecto actualizado. − INGRESO A ABIERTA − Incorporación de los seis estados recién calculados al final de la lista abierta (210 a 240) −MUERTE DE DUPLICADOS DE ABIERTA Y DE PREFERIDO− Empleo de una lista auxiliar. Contraste entre lista principal y lista auxiliar para hallar duplicados de abierta y de preferido. Rescate de todas los estados que no sean nulos con trayectoria no nula (210 a 410) − FRACASO − Reconocimiento de eventual carencia de nuevos estados que no sean duplicados de estados ubicados en lista cerrada − EXITO − Subrrutina, activada desde OPERADORES que imprime información final so bre la trayectoria exitosa y la lista cerrada (500 − 540) 10. FLUJOGRAMA para el manipuleo de listas en el juego de dos baldes Comienzo −−> Inicialización − Ingreso de datos 6

! (A) −−−−−−−−−−−−> Sumador ! Pasaje de listas − Selección estado preferido (PR) Corte de cabeza lista abierta Agregado a lista cerrada Operadores − Reconocimiento de buen éxito−−−−−−−−−−−−−−−−−−Exito −−−−−−−−−−− FIN Ejecución en orden de 6 subrrutinas = expansión de PR ^ Ingreso a abierta − agregado al final de sucesores de PR ! Muerte de duplicados − contraste entre lista abierta y cerrada ! FRACASO − Los estados de la lista abierta coinciden con cerrada −−−−−−−−−/ <−−−−−−−−−−−−−Retornar a (A) 11. REDUCCION DEL JUEGO A UNA DEMOSTRACIÓN DE TEOREMAS. . En Inteligencia Artificial hay una técnica denominada "Demostración de Teoremas". Tiene una base de reglas conteniendo los axiomas en los cuales se cree. Tiene una meta a satisfacer, que es si un dado Teorema es válido o nó a la luz de los axiomas. En caso de que sea válido, la técnica provee la trayectoria (cómo combinó los axiomas), para llegar a la prueba. Esto se puede aplicar al Juego de dos Baldes con la siguiente analogía: a) Base de reglas = conjunto de dos axiomas, a saber: • Se puede cargar agua hasta el ras del balde con una fuente y se puede eliminar agua de un balde hasta dejarlo vacío con un sumidero. • Se puede pasar agua de un balde donante a otro, no más allá de llegar al ras en el balde receptor b) Teorema = Estado GOL . c) Trayectoria = enumeración de las sucesivas aplicaciones de los dos "axiomas" del caso. 12. DISCUSION a) ¿Cómo se puede utilizar el principio de superposición de sistemas lineales para cambiar la búsqueda del estado final por una búsqueda de las matrices cuadradas combinadas que den origen a la correcta transformación de estado inicial en estado GOL? b) ¿Cómo se pueden programar incorporaciones a una base de conocimientos que permita construir algo análogo a un sistema experto para la resolución del juego de los dos baldes? o) ¿Cómo se puede efectuar un autoaprendizaje? El objetivo es el de reducir el trabajo de expansión de estados preferidos.

7

Este tema se trata asimismo en • signi.html • formu.html • búsqueda primero en amplitud • razonamiento basado en casos • una teoría unificada de la cognición • espacio de problema • reglas de producción del juego de dos baldes segun Arteaga y Armijos • programa en basic para juedo de dos baldes Actualizado19.may.2000

8