El problema del laberinto en SuperBASIC

El problema imaginario de la rata en busca de comida dentro de un laberinto se ha utilizado frecuentemente para escenificar diferentes estrategias de “búsqueda”, un área muy estudiada en la Inteligencia Artificial.

Imaginemos que se sueltan tres ratas en un laberinto en cuyo interior hay, en algún lugar, una apetitosa comida. Cada rata utiliza una técnica de búsqueda diferente:
– La primera rata emplean un sistema de búsqueda aleatorio (“el recorrido del borracho”).
– La segunda rata ejecuta una búsqueda exhaustiva (“enumeración sistemática”)
– Y la tercera rata realiza una búsqueda heurística (“exploración guiada”).

¿Cuál de ellas sería la técnica más eficiente?

Pues, a todas luces parece que la tercera técnica es la más inteligente y la que requiere menos esfuerzo para llegar a la solución.

Hay que observar que todos los métodos heurísticos dependen de “alguna forma” de saber cuándo la búsqueda se está aproximando a su objetivo (en nuestro ejemplo sería el olfato de la rata). Sin este tipo de conocimiento, la búsqueda no tendría más remedio que ser sistemática para hallar un resultado de forma segura.

Para demostrar esto presentamos el clásico problema de la búsqueda en el laberinto escrito en SuperBASIC. Es muy frecuente ver este programa ejemplo en textos de Inteligencia Artificial, y en su momento se presentaron versiones para Spectrum, MSX, Commodore, … en revistas de la época (una de ellas es “Mi Computer” -de donde saqué esta idea-). Pues bien, ahora le toca el turno a nuestro querido QL y su SuperBASIC. La ventaja sobre otras plataformas de los 80 es que el Basic del QL es más “humano” a la hora de leer y comprender el código que cualquier otro Basic de los de “antes”.

Nuestro pequeño programa es experimental, y sólo pretende ilustrar una técnica de búsqueda empleando alguna heurística. Sobra decir que el BASIC en general no es un buen lenguaje para tratar este tipo de problemas, tal como lo pueda ser por ejemplo el C, Pascal o Lisp, pero aquí sólo tratamos de divertirnos con nuestros viejos ordenadores y de paso repasar o aprender algo más de programación (:-).

Bueno, comencemos …

El problema consiste en lo siguiente:

1) Construir un laberinto aleatorio donde colocamos un símbolo que representa a la rata “R” y otro símbolo que representa a la comida “C”.

Laberinto, posiciones iniciales: Rata y Comida

Laberinto, posiciones iniciales: Rata y Comida

2) El segundo paso, y el más interesante, es diseñar una estrategia que permita a la rata ir “aproximándose” a la comida sin necesidad de hacer una exploración exhaustiva. En la imagen 2 vemos el resultado de dicha exploración y cómo la rata va “olfateando” las distintas casillas hasta llegar a su objetivo.

Laberinto, rutina de exploración

Laberinto, rutina de exploración

3) Y finalmente, pintamos el recorrido más óptimo que ha encontrado la rata (no necesariamente el mejor).

Laberinto, resultado final

Laberinto, resultado final

He intentado que el código sea lo más autodescriptivo posible, por lo que sólo comentaré las partes más interesantes.

El laberinto está representado en una matriz de dos dimensiones, codificada así

210 DIM M(MaxAlto+1, MaxAncho+1)

El alto y ancho del laberinto lo podemos configurar mediante las variables MaxAlto y MaxAncho. En nuestro ejemplo le hemos dado valores para que ocupe prácticamente toda la pantalla en Modo 8 del QL.

Cada casilla de esa matriz contiene alguno de los valores para representar: nuestra “ratita”, la comida, las secciones de muro, y las casillas blancas donde la rata puede transitar. En el vector C$ colocamos los caracteres que representa cada una de esas posibilidades.

La estructura de datos más importante del programa son los siguientes vectores donde se va almacenando del “árbol” de búsqueda que va realizando la rata:

350 DIM Camino(LimArbol)
360 DIM Pasos(LimArbol)
370 DIM Nodos(LimArbol)
380 DIM Heu(LimArbol)

(LimArbol es una constante predeterminada para almacenar el recorrido de la rata por los distintos nodos de exploración).

Las posiciones de cada casilla se van almacenando en el vector “Nodos”, se representan las coordenadas X,Y de la matriz que representa el laberinto por medio de un valor entero. La fórmula es CoordenadaXY = (Fila * MaxAncho) + Columna.

El vector Camino, va almacenando el “Nodo-Padre” de la casilla representada en cada elemento del vector. En cualquier elemento podemos hacer un recorrido hasta el nodo raíz empleando los valores de este vector.

El vector Pasos, representan el nivel de profundidad en el árbol de búsqueda.

Y por último, el vector Heu almacena el coste calculado. En base a este valor se van decidiendo los mejores nodos a expandir a medida que se avanza en la búsqueda. La heurística depende de los valores de este vector.

La estrategia empleada para el cálculo de este valor heurístico se denomina algorítmo A* (A estrella), y consiste en combinar un cálculo ponderado entre el recorrido realizado y la distancia que falta para llegar al objetivo. Nuestra fórmula empleada es:

CosteEstimado (H) = Distancia que queda (Q) + Distancia cubierta (C)

Podemos darle pesos a los valores de Q y C, en nuestro ejemplo 1 y 2 respectivamente. El valor más bajo de (H) es la elección mejor.

Otro aspecto importante a tener en cuenta, es que a medida que avanzamos en la búsqueda tenemos que “descatalogar” aquellas posiciones por las cuales no podemos seguir avanzando. Esto lo hacemos colocando un valor negativo en el vector Heu.

No sé si estos breves comentarios ayudarán en la lectura é interpretación del código fuente. A continuación se muestra el programa completo.

Si lo ejecutamos varias veces podemos comprobar que, en la mayoría de los casos, el resultado es bastante bueno.

En definitiva, un problema divertido con un lenguaje divertido como es el SuperBASIC del QL. Que lo disfrutéis.

.

100 REMark =============================================================
110 REMark -- Laberinto                               (afx, julio 2009)
120 REMark =============================================================
130 :
140 :
150 REMark -------------------------------------------------------------
160 REMark -- Declaraci–n variables globales y constantes
170 REMark -------------------------------------------------------------
180 :
190 MaxAlto = 20: MaxAncho = 39  : REMark ancho y alto del laberinto
200 DIM M(MaxAlto+1, MaxAncho+1) : REMark matriz del laberinto
210 LimArbol = 512               : REMark l“mite del vectores para Œrbol
220 Peso1 = 1: Peso2 = 2         : REMark pesos para la heur“stica
230 Muro = 1: Rata = 2:          : REMark constantes
240 Comida = 3: Dn = 4:          : REMark   "
250 Blanco = 5                   : REMark   "
260 Xx = 999999                  : REMark   "
270 XNodo = 0                    : REMark Siguinte Nodo libre
280 DIM C$(5)                    : REMark Caracteres del laberinto
290 C$(Muro) = CHR$(255)
300 C$(Blanco) = " "
310 C$(Rata) = "R"
320 C$(Comida) = "C"
330 C$(Dn) = " "
340 DIM Camino(LimArbol)         : REMark vectores para manejo Œrbol
350 DIM Pasos(LimArbol)          : REMark        "
360 DIM Nodos(LimArbol)          : REMark        "
370 DIM Heu(LimArbol)            : REMark        "     (Heur“stica)
380 FilComida = 0                : REMark Posici–n de la comida
390 ColComida = 0
400 NodCon = 0                   : REMark N™mero de nodos examinados
410 SFil = 0                     : REMark Siguiente Fila
420 SCol = 0                     : REMark Siguiente Columna
430 S = 0                        : REMark Mejor nodo, “ndice vector Œrbol
440 a$ = ""                      : REMark Para captura teclas
450 :
460 REMark --------------------------------------------------------------
470 REMark -- Secuencia principal
480 REMark --------------------------------------------------------------
490 :
500 REMark --- Pasos previos
510 :
520 InicializaPantalla
530 MensajeInfo 1, "Generando laberinto ..."
540 FabricaLaberinto
550 DibujarLaberinto
560 :
570 NodCon = 0
580 InicializarArbol
590 :
600 Nodos(1) = 2 * MaxAncho + 2 : REMark primer nodo abierto en pos 2,2
610 Pasos(1) = 0                : REMark por ahora no hay pasos
620 Camino(1) = 0               : REMark no hay ning™n predecesor (camino)
630 Heu(1) = (FilComida-1) + (ColComida-1) : REMark coste para heur“stica
640 :
650 REMark --- Bucle principal
660 :
670 MensajeInfo 0,"Explorando camino ..."
680 :
690 REPeat BuclePrincipal
700   BuscarMejorNodo
710   NodCon = NodCon + 1
720   MonitorExploracion
730   GenerarSucesores
740   IF (SFil = FilComida AND SCol = ColComida) OR NodCon > LimArbol-2 THEN
750      EXIT BuclePrincipal
760   END IF
770 END REPeat BuclePrincipal
780 :
790 REMark --- Resultado final
800 :
810 IF SFil = FilComida AND SCol = ColComida THEN
820   MensajeInfo 0, "Fin exploraci–n."
830   MensajeInfo 1, "Pulsa una tecla para pintar camino..."
840   a$ = INKEY$(-1)
850   :
860   DibujarLaberinto
870   MostrarCamino
880   :
890   MensajeInfo 0, "Pulsa una tecla para salir."
900   MensajeInfo 1, ""
910   a$ = INKEY$(-1)
920 ELSE
930   MensajeInfo 0, "Resultado."
940   MensajeInfo 1, "No he encontrado camino –ptimo..."
950   a$ = INKEY$(-1)
960 END IF
970 :
980 STOP
990 :
1000 :
1010 REMark -------------------------------------------------------------
1020 REMark -- Procedimientos, Funciones, ...
1030 REMark -------------------------------------------------------------
1040 :
1050 :
1060 DEFine PROCedure FabricaLaberinto
1070   LOCal i, j, lim
1080   FOR i = 1 TO MaxAlto + 1
1090     FOR j = 1 TO MaxAncho + 1
1100       IF RND(100) < 55 THEN 
1110         M(i,j) = Muro 
1120       ELSE 
1130         M(i,j) = Blanco 
1140       END IF 
1150       IF i = 3 OR j = 3 THEN M(i,j) = Blanco 
1160       IF i = MaxAncho - 4 OR j = MaxAlto -4 THEN M(i,j) = Blanco 
1170       IF i = 1 OR j = 1 THEN M(i,j) = Muro 
1180       IF i > MaxAlto OR j > MaxAncho THEN M(i,j) = Muro
1190     END FOR j
1200   END FOR i
1210   lim = INT(MaxAlto/2)
1220   FilComida = lim + INT(RND(MaxAlto-1-lim))
1230   lim = INT(MaxAncho/2)
1240   ColComida = lim + INT(RND(MaxAncho-1-lim))
1250   M(FilComida,ColComida) = Comida
1260   M(2,2) = Rata
1270   PasaEscoba
1280 END DEFine
1290 :
1300 :
1310 DEFine PROCedure PasaEscoba
1320   LOCal tx,ty,ax,ay,sx,sy,sw
1330   tx=2: ty=2: ax=1: ay=1: sx=1: sy=1 :sw=1
1340   REPeat tunel
1350     sw=RND(1,2)
1360     SELect ON sw
1370     =1
1380       IF sx THEN
1390         IF tx=MaxAlto THEN ax=-1
1400         tx=tx+ax
1410       END IF
1420       IF tx=FilComida AND ax=-1 THEN
1430         sx=0: IF ty>ColComida THEN ay=-1
1440       END IF
1450     =2
1460       IF sy THEN
1470         IF ty=MaxAncho THEN ay=-1
1480         ty=ty+ay
1490       END IF
1500       IF ty=ColComida AND ay=-1 THEN
1510         sy=0: IF tx>FilComida THEN ax=-1
1520       END IF
1530     END SELect
1540     IF M(tx,ty) = Comida THEN EXIT tunel
1550     M(tx,ty) = Blanco
1560   END REPeat tunel
1570 END DEFine
1580 :
1590 :
1600 DEFine PROCedure DibujarLaberinto
1610   LOCal i,j
1620   CLS
1630   FOR i = 1 TO MaxAlto + 1
1640     FOR j = 1 TO MaxAncho + 1
1650       AT i,j: PRINT C$( M(i,j) )
1660     END FOR j
1670   END FOR i
1680   INK 1: AT 2,2: PRINT C$(M(2,2))
1690   INK 6: AT FilComida,ColComida
1700   PRINT C$(M(FilComida,ColComida))
1710   INK 7
1720 END DEFine
1730 :
1740 :
1750 DEFine PROCedure InicializarArbol
1760   LOCal i
1770   FOR i = 1 TO LimArbol
1780     Camino(i) = 0
1790     Pasos(i) = Xx
1800     Nodos(i) = 0
1810     Heu(i) = Xx
1820   END FOR i
1830   XNodo = 2
1840 END DEFine
1850 :
1860 :
1870 DEFine PROCedure BuscarMejorNodo
1880   LOCal i, BN
1890   MensajeInfo 1, "Buscando mejor nodo ..."
1900   BN = Xx
1910   S = 1
1920   FOR i = 1 TO LimArbol
1930     IF Heu(i) >= 0 AND Heu(i) < Xx THEN
1940       V = Pasos(i) * Peso1 + ABS(Heu(i)) * Peso2
1950       IF V < BN AND Heu(i) >= 0 THEN
1960          S = i: BN = V
1970       END IF
1980     END IF
1990   END FOR i
2000   REMark IF S = 1 THEN PRINT#0, "Explorando ..."
2010   SFil = INT(Nodos(S) / MaxAncho)
2020   SCol = Nodos(S) - (MaxAncho * SFil)
2030 END DEFine
2040 :
2050 :
2060 DEFine PROCedure GenerarSucesores
2070   LOCal f, c
2080   LOCal res%
2090   MensajeInfo 1, "Generando sucesores..."
2100   res% = 0
2110   IF Heu(S) = 0 THEN RETurn
2120   REMark -- norte
2130   f = SFil - 1 : c = SCol
2140   IF f > 1 THEN
2150     res% = AbrirNodo% (f, c)
2160   END IF
2170   REMark -- este
2180   f = SFil : c = SCol + 1
2190   IF c <= MaxAncho THEN
2200     res% = AbrirNodo% (f, c)
2210   END IF
2220   REMark -- sur
2230   f = SFil + 1: c = SCol
2240   IF f <= MaxAlto THEN 
2250     res% = AbrirNodo% (f, c) 
2260   END IF 
2270   REMark -- oeste 
2280   f = SFil : c = SCol - 1 
2290   IF c > 1 THEN
2300     res% = AbrirNodo% (f, c)
2310   END IF
2320   REMark -- Cerrar nodo
2330   Heu(S) = -Heu(S)
2340   IF (SFil <> 2 AND SCol <> 2) AND (SFil>0 AND SCol>0) THEN
2350     AT SFil,SCol: PRINT ".";
2360   END IF
2370   M(SFil,SCol) = Dn
2380 END DEFine
2390 :
2400 :
2410 DEFine FuNction AbrirNodo% (pF, pC)
2420   LOCal nx, xy
2430   IF M(pF,pC) = Dn THEN RETurn 0
2440   IF M(pF,pC) = Muro THEN RETurn 0
2450   REMark hallar posici–n libre
2460   nx = 0
2470   REPeat HallarPosicion
2480     IF Pasos(XNodo) <> Xx THEN
2490        nx = nx + 1: XNodo = XNodo + 1
2500     END IF
2510     IF XNodo > LimArbol THEN XNodo = 1
2520     IF nx > LimArbol THEN
2530       PRINT "No hay hueco en el arbol para expandir mŒs nodos"
2540       STOP
2550     END IF
2560     IF Pasos(XNodo) = Xx THEN
2570       EXIT HallarPosicion
2580     END IF
2590   END REPeat HallarPosicion
2600   REMark abrir el nodo
2610   xy = (pF * MaxAncho) + pC
2620   Nodos(XNodo) = xy
2630   Camino(XNodo) = S
2640   Pasos(XNodo) = Pasos(S) + 1
2650   Heu(XNodo) = ABS(pF - FilComida) + ABS(pC -ColComida)
2660   IF pF > 0 AND  pC > 0 THEN
2670     AT pF,pC:PRINT "+"
2680   END IF
2690   RETurn 1
2700 END DEFine
2710 :
2720 :
2730 DEFine PROCedure InicializaPantalla
2740   MODE 8
2750   WINDOW 512,232,0,0
2760   WINDOW#2, 512,232,0,0
2770   WINDOW#0, 512,24,0,232
2780   PAPER 0: INK 7:BORDER 1,2: BORDER#2,1,2
2790   CLS:CLS#0:CLS#2
2800 END DEFine
2810 :
2820 :
2830 DEFine PROCedure MostrarCamino
2840   LOCal nPasos, x, y
2850   nPasos = Pasos(S)
2860   AT 0,0:PRINT "Camino de: ";nPasos;" pasos."
2870   INK 2
2880   REPeat PintaCamino
2890     REMark activar nodo padre
2900     S = Camino(S)
2910     IF S = 0 THEN EXIT PintaCamino
2920     y = INT(Nodos(S)/MaxAncho)
2930     x = Nodos(S) - y * MaxAncho
2940     AT y,x:PRINT "*"
2950   END REPeat PintaCamino
2960   INK 1
2970   AT 2,2:PRINT C$(Rata)
2980   INK 7
2990 END DEFine
3000 :
3010 :
3020 DEFine PROCedure MonitorExploracion
3030   AT 0,0:PRINT  FILL$(" ",40)
3040   AT 0,0:PRINT "Casilla  F:";SFil;" C:";SCol;"   Nodo Arbol:"; S
3050 END DEFine
3060 :
3070 :
3080 DEFine PROCedure MensajeInfo (linea%, mensaje$)
3090   AT#0,linea%,0:PRINT#0, FILL$(" ",40)
3100   AT#0,linea%,0:PRINT#0, mensaje$
3110 END DEFine

.

NOTA (post editado):
– He corregido un error en las llamadas a la función AbrirNodo%, las llamada tenía dos parámetros más de los necesarios. Curiosamente esto no provocaba ningún error ni fallo en el programa, (los últimos parámetros no se utilizaban). ¡Curiosidades del SuperBASIC!
– Segunda corrección, se ha incluido una rutina (PasaEscoba) aportada por Badaman que asegura al menos un camino entre la rata y la comida.

Anuncios
4 comentarios
  1. badaman dijo:

    Qué gusto da ver programar en SuperBASIC. Gracias Afx.

    Esas 3 ratas (borracha, sistemática y guiada) recuerdan mucho a los 3 fantasmas del comecocos, aunque aquí el objetivo está inmovil.

    Lo pruebo todo y te cuento mañana.

  2. La verdad es que el SuperBASIC es una gran mejora respecto al BASIC normal para estos menesteres. Me gustará ver ejemplos de vida artificial en este lenguaje, sería curioso ver como van de bien y cómo queda el código.

  3. afx dijo:

    He incluido una mejora desarrollada por Badaman, la rutina PasaEscoba. Esta rutina asegura que al menos exista un camino entre la rata y la comida cuando se genera el laberinto (en la primera versión se generaban con frecuencia laberintos sin caminos posibles).

    Además, aprovechando que ya hay un camino posible, he poblado un poco más la cantidad de “muro” que hay en el laberinto para hacerlo más difícil para la rata.

    (Badaman ¡gracias por la aportación!).

  4. desearía que envíen un formulario de como se hace un laberinto en c# con varios ejemplos… Muchas Gracias

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s