Librería IA NetLogo: Parte I

BFS

Uso: Aplicar Breadth-First-Search para resolver problemas de búsqueda y planificación.

Los estados se representan por medio de la familia de tortugas AI:states, que deben contener (al menos) las siguientes propiedades:

• content : Almacena el contenido (valor) del estado
• explored? : Indica si el estado ha sido explorado/creado o no
• depth : Indica la profundidad del estado dentro respecto del estado inicial (útil para la representación).
• path : Lista de estados por los que la búsqueda ha pasado para llegar desde el estado inicial hasta el actual.

Las transiciones vienen representados por medio de la familia de links AI:transitions, que deben contener (el menos) las siguientes propiedades:

• rule : Almacena información variada acerca de la transición. Debe ser una lista con la representación humana de la regla en la cabeza [rep ... ].

Junto a la representación anterior, necesitamos definir las siguientes funciones:

• AI:children-states : Lo ejecutan los estados, y devuelve una lista con información sobre los posibles sucesores del estado que lo ejecuta: [[s1 r2] [s2 r2]...[sn rn]]. En este sentido, cada estado devuelto deber ser un par [s r], donde s es el contenido del nuevo estado obtenido, y r es la regla que permite pasar de uno a otro.

• AI:final-state? : Lo pueden ejecutar los estados y devuelve si debe ser considerado un estado final. Este procedimeinto recibe como entrada un parámetro que, por ejemplo, permita comparar el estado actual con el #final-state en caso de que dicho estado final sea un estado concreto. Si no fuera así, el parámetro pasado no tiene utilidad y la verificación de si es final o no solo se basará en propiedades internas del estado actual.

• AI:equal? : Un predicado (report) de igualdad que decide si los contenidos de dos estados son iguales. Muchas veces podrá ser =, pero si la estructura es más compleja (por ejemplo, un conjunto representado por listas) será necesario definirlo adecuadamente.

La función principal es el procedimiento BFS, que construye el grafo de estados que se obtiene a partir de un estado inicial dado (siguiendo los constructores en anchura definidos por el usuario) y comprueba si el estado objetivo ha sido alcanzado o no. BFS es un report que devolverá:

• False si no ha habido éxito en la búsqueda.
• El estado final alcanzado, si dicho estado es un estado final válido que resuelve el problema (en la propiedad path de este estado encontraremos el camino que lo conecta con el estado inicial, por si hiciera falta).

Los datos de entrada que espera este procedimiento son:

• #initial-state : Contenido del estado inicial.
• #final-state : Contenido del estado final que se busca. (ver final-state?).
• #debug? : True / False - Indica si se mostrará el contenido en los estados, y las reglas en las transiciones.
• #visible? : Muestra/Oculta estados y transiciones en el interfaz.

Adicionalmente, debido a que BFS devuelve el estado final completo, del que podemos obtener el path que ha permitido construirlo, la librería proporciona un report, extract-transitions-from-path, que al ser ejecutado por un estado devuelve, a partir de la información almacenada en el estado, la sucesión (lista) de transiciones que se han aplicado para llegar desde el estado inicial hasta él. Obsérvese que este procedimiento no necesita ningún dato de entrada, ya que lo ejecuta el propio estado y él puede acceder a toda su información de manera directa.

Ejemplo

Problema: Comenzando por un número inicial, y usando solo las operaciones específicas: multiplicar por 3, sumar 7, o restar 2, queremos encontrar la forma más corta de alcanzar un número objetivo prefijado. Solo se permite trabajar con números positivos.

Los estados solo necesitan como contenido un valor numérico.

Las reglas (operaciones, movimientos, jugadas) permitidas para este problema (expresadas como la lilbrería BFS espera) son:

[ ["*3" x*3] ["+7" x+7] ["-2" x-2] ]

que podemos definir con el siguiente reporte:

to-report applicable-transitions
  report (list
           (list "*3" ([ x -> x * 3 ]))
           (list "+7" ([ x -> x + 7 ]))
           (list "-2" ([ x -> x - 2 ])))
end

Podemos definir un predicado que determina cuándo un estado es válido (que sea positivo):

to-report valid? [x]
  report (x > 0)
end

Y entonces el reporte children-states, que ejecutado por un estado devuelve los estados alcanzables desde él, en forma de pares [ns r], donde ns es el contenido del nuevo estado y r es la regla que permite alcanzarlo. Damos un resultado lo más general posible:

to-report AI:children-states
  report filter [ s -> valid? (first s) ]
                (map [ t -> (list (run-result (last t) content) t) ]
                     applicable-transitions)
end

Los reportes que deciden cuándo un estado es final, y cuándo dos estados son iguales serían:

to-report AI:final-state? [params]
  report ( content = params)
end

to-report AI:equal? [a b]
  report a = b
end

La llamada al algoritmo BFS sería, por ejemplo:

let path (BFS Initial Final True True)

A-star

Uso: Aplicar A-star para resolver problemas de búsqueda y planificación.

Los estados, AI:states, son similares a los de BFS (mirar más arriba).

Las transiciones, AI:transitions, son similares a las de BFS, que deben contener (el menos) las siguientes propiedades:

• rule : Almacena información varia acerca de la transición. Debe tener una estructura en forma de lista: [rep coste ...].
• cost-link : Almacena el coste de la transición.

Además, el algoritmo A* almacena toda la información la búsqueda en una familia adicional de agentes denominada AI:searchers, que tienen las siguientes propiedades:

• memory : Almacena el camino de nodos que ha recorrido A* desde el estado inicial hasta el nodo en el que se encuentra este buscador.
• cost : Almacena el coste real del camino recorrido desde el estado inicial.
• total-expected-cost : Almacena el coste total esperado desde el estado inicial hasta el objetivo.
• current-state: Almacena el estado (AI:state) en el que se encuentra este buscador.
• active? : Establece si este buscador está activo o no, es decir, si los estados vecinos al suyo han sido explorados o no.

Junto a la representación anterior, necesitamos definir las siguientes funciones:

• AI:children-states : Idéntica a la definida en BFS (pero con las características propias de las reglas de A-star).

• AI:final-state? : Idéntica a la definida en BFS.

• AI:heuristic : lo pueden ejecutar los buscadores. Recibe como entrada el objetivo buscado, y devuelve el valor de la heurística que se usará para medir la distancia entre el estado en el que se encuentra el buscador y el objetivo.

• AI:equal? : Idéntica a la definida en BFS.

La función principal de la librería A-star es el procedimiento A*, que devolverá:

• False si no ha habido éxito en la búsqueda.
• La memoria del buscador que ha alcanzado un estado final.

Los datos de entrada que espera este procedimiento son:

• #initial-state : Contenido del estado inicial.
• #final-state : Contenido del estado final que se busca. (Ver final-state?).
• #debug? : True / False - Indica si se mostrará el contenido en los estados, y las reglas en las transiciones.
• #visible? : Muestra/Oculta estados y transiciones en el interfaz.

Ejemplo

Trabajando en el mismo problema de ejemplo, las diferencias principales para modelar este problema para A-star serían:

Ahora es necesario que las reglas tengan un coste asociado:

[ ["*3" 1 x*3] ["+7" 1 x+7] ["-2" 1 x-2] ]

que podemos definir con el siguiente reporte:

to-report applicable-transitions
  report (list
           (list "*3" 1 ([ x -> x * 3 ]))
           (list "+7" 1 ([ x -> x + 7 ]))
           (list "-2" 1 ([ x -> x - 2 ])))
end

Y hemos de proporcionar una función heurística (no nos preocupamos en este ejemplo de si es admisible o no):

to-report AI:heuristic [#Goal]
  let d abs (([content] of current-state) - #Goal)
  report ifelse-value (d > 1) [log d 3][d]
end

La llamada al algoritmo A* sería, por ejemplo:

let path (A* Initial Final True True)

Templado Simulado (SimulatedAnnealing)

Uso: Aplicar Templado Simulado para resolver problemas de búsqueda.

Como solo se mantiene un estado que va modificándose aleatoriamente, no es necesario el uso de una familia de agentes para almacenarlo, pero se debe mantener un conjunto de valores globales que indiquen la evolución y configuración del proceso en cada iteración. Por ello, se hará uso de las siguientes variables globales:

• AI:SimAnnGlobalEnergy: Almacena la energia del estado actual.
• AI:SimAnnTemperature: Almacena la temperatura actual del sistema.
• AI:accept-equal-changes?: Indica si el algoritmo aceptará cambiar el estado actual en caso de igualdad de energía.

Para el correcto funcionamiento de esta librería en el modelo principal se deben definir las siguientes funciones:

• AI:get-new-state: recibe un estado y genera otro a partir de él (normalmente, al azar entre las transiciones posibles).
• AI:EnergyState: recibe un estado y devuelve la energía asociada a él.
• AI:SimAnnExternalUpdates: procedimiento adicional auxiliar que se ejecutará en cada ciclo del algoritmo principal, por ejemplo, para mostrar información durante la ejecución o actualizar los valores de agentes del mundo.

La función principal de la librería SimulatedAnnealing es el procedimiento AI:SimAnn, que espera los siguientes datos de entrada:

• #Initial-state: Estado inicial desde el que comienza la búsqueda.
• #tries-by-cycle: Número de estados que se construirán en cada ciclo del bucle principal (todos ellos con la misma temperatura).
• #mim-Temp: Temperatura mínima a la que parará la búsqueda (si no se ha encontrado energía nula antes).
• #cooling-rate: Ratio de enfriamiento de la temperatura en cada ciclo.
• #aec: True/False ... si aceptamos cambios con la misma energía o no.

Ejemplo

Vamos a resolver el famoso problema de las N reinas haciendo uso de Templado Simulado. Representaremos los estados por medio de listas [a0 ... aN], que indica que hay reinas en las posiciones [ (0,a0) ... (N,aN) ].

El reporte que genera un nuevo estado al azar a partir de un estado actual (moviendo al azar una de las reinas en su columna) sería:

to-report AI:get-new-state [#state]
  let i random N
  let ai random N
  report replace-item i #state ai
end

El predicado que nos dice que las reinas de las columnas i y j se amenazan sería:

to-report threat [i j #state]
  let eli item i #state
  let elj item j #state
  report ifelse-value (eli = elj or
                      (elj - eli) = (j - i) or
                      (elj - eli) = (i - j))
                      [1][0]
end

Definimos la función de energía como el número de amenazas en el tablero (contadas una sola vez):

to-report AI:EnergyState [#state]
  report sum map [i -> sum map [j -> threat i j #state] (range (i + 1) N)] (range N)
end

Con el fin de mostrar información en cada ciclo del algoritmo, definimos el procedimiento:

to AI:SimAnnExternalUpdates [params]
  show params
  plot AI:SimAnnGlobalEnergy
  display
end

Y la forma de ejecutar el algoritmo de Templado Simulado sería, por ejemplo:

let res AI:SimAnn (n-values N [random N]) 100 (10 ^ -6) 1 true

MCTS (Monte Carlo Tree Search)

Uso: Aplicar Monte Carlo Tree Search para resolver problemas de búsqueda con adversario.

La librería montada para ejecuar el algoritmo MCTS hace uso de las sigiuentes estructuras:

state: cualquier estructura que responde a la siguiente interfaz:

• MCTS:get-content state : lee el contenido de state (el dato real del juego)
• MCTS:get-playerJustMoved state : Jugador (1 o 2) que ha generado este estado
• MCTS:create-state content player : devuelve un state con esa información

rules: estructura que permite ejecutar acciones sobre estados que responde a la siguiente interfaz:

• MCTS:apply rule state : devuelve un nuevo estado, el resultado de aplicar rule a state
• MCTS:get-rules state : devuelve una lista de reglas aplicables a state
• MCTS:get-result state player : devuelve el resultado del juego en state según el punto de vista de player

Junto a estas estructuras, el algoritmo necesita algunas estructuras adicionales para la construcción del árbol de búsqueda por medio del algoritmo, pero como el usuario no ha de hacer ningún uso de estas estructuras para el uso efectivo de esta librería, dirigimos al lector a la documentación completa de la librería, y pasamos a explicar la función principal que proporciona esta librería, MCTS:UCT:

• MCTS:UCT root-state iter: ejecuta una búsqueda UCT durante iter iteraciones comenzando por el nodo root-state. Devuelve el mejor movimiento encontrado. Los resultados de las jugadas debe estar en el rango $[0.0, 1.0]$.

Ejemplo

Para el juego del Nim simple (solo un montón, 2 jugadores, y se pueden sacar de 1 a 3 piezas en cada turno), usaremos el estado [content player], donde content es el número de piezas que quedan en el montón, y player indica el jugador que acaba de hacer el último movimiento (1 o 2).

Los diversos procedimientos que debemos definir para poder usar la librería MCTS son:

Procedimientos para manipular estados:

to-report MCTS:get-content [s]
  report first s
end

to-report MCTS:get-playerJustMoved [s]
  report last s
end

to-report MCTS:create-state [c p]
  report (list c p)
end

Procedimiento para obtener las reglas aplicables a un estado:

to-report MCTS:get-rules [s]
  report (range 1 (min (list 4 (1 + MCTS:get-content s))))
end

Reporte que devuelve el estado resultante de aplicar una regla determinada sobre un estado:

to-report MCTS:apply [r s]
  let c MCTS:get-content s
  let p MCTS:get-playerJustMoved s
  report MCTS:create-state (c - r) (3 - p)
end

to-report MCTS:get-result [s p]
  let pl MCTS:get-playerJustMoved s
  ifelse pl = p [report 1] [report 0]
end

Y para obtener la respuesta ideal proporcionada por el algoritmo partiendo de un estado en el que ha jugado el jugador ply dejando n piezas en el montón, bastaría ejecutar:

let m MCTS:UCT (list n ply) Max_iterations