Librería IA NetLogo: Parte I

Índice

• Breadth First Search
  • Ejemplo
• A-star
  • Ejemplo
• Templado Simulado
  • Ejemplo
• Monte Carlo Tree Search
  • Ejemplo

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 o no
• depth : Indica la profundidad del estado dentro del grafo de estados respecto del estado inicial (útil para la representación).
• path : Camino (lista de estados) por los que la búsqueda ha pasado para llegar desde el estado inicial hasta el actual.

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

• rule : Almacena información variada acerca de la transición. Debe ser una lista con, al menos, 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 : La ejecutan los estados, y devuelve una lista con los posibles estados sucesores del estado que lo ejecuta: [[s1 r2] [s2 r2]...[sn rn]] y la regla que nos lleva a ellos. En este sentido, cada elemento 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? : La ejecutan los estados y devuelve un booleano indicando si es un estado final o no. Este procedimiento recibe como entrada un parámetro que, por ejemplo, permite comparar el estado actual con el valor del parámetro (para aquellos casos en que el estado final sea un estado concreto #final-state). Si no fuera así, y la verificación de si es final o no solo se basara en propiedades internas del estado actual, entonces este parámetro no tendrá ninguna utilidad y se le puede pasar cualquier valor.

• AI:equal? : Un predicado 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 de esta librería 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 final encontraremos el camino que lo conecta con el estado inicial, por si hiciera falta).

Este procedimiento usa los procedimientos auxiliares anteriores, y los datos de entrada que espera son:

• #initial-state : Contenido del estado inicial.
• #final-state : Contenido del estado final que se busca. (puede no ser importante, 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 (acciones, operaciones, movimientos, jugadas) permitidas para este problema (expresadas como la librerí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, es decir, las restricciones que debe cumplir un contenido para que sea considerado un estado correcto (en este caso, 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 procedimiento lo más general posible y que podrá ser reutilizado en muchos problemas similares si se definen adecuadamente valid? y applicable-transitions:

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? [param]
  report ( AI:equal? content param)
end

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

Finalmente, una llamada estándar al algoritmo BFS sería, por ejemplo:

let sol (BFS Initial Final True True)
let path [extract-transitions-from-path] of sol 

Ten en cuenta que la última instrucción solo funcionará si sol no es false.

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.

Las transiciones, AI:transitions, también son una ampliación de las de BFS, y deben contener (al 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 de 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 estimar 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 exitoso, en caso contrario.

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 que en BFS, las diferencias principales para modelar este problema para A-star serían:

Ahora es necesario que las reglas tengan un coste asociado (vamos a asignar, por ejemplo, mayor coste a la operación de multiplicación):

[ ["*3" 2 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" 2 ([ 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 energía 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 actual.

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 en 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 [a1 ... aN], que indica que hay reinas en las posiciones [ (1,a1) ... (N,aN) ] (realmente, por las características del lenguaje, usaremos los índices 0,...,N-1).

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 total de amenazas que hay en el tablero actual (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 a partir de una configuración de reinas al azar 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 proporcionada para ejecutar el algoritmo MCTS hace uso de las siguientes estructuras:

state: cualquier estructura que responda a la siguiente interfaz:

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

rules: cualquier estructura que permite ejecutar acciones sobre estados y que responda 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 dos estructuras, el algoritmo necesita internamente de 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 explícito de las, dirigimos al lector a la documentación completa de la librería, y pasamos a explicar la función más importante 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 deben estar en el rango $[0.0, 1.0]$.

Esta función ya está definida, la librería la ejecuta haciendo uso de los procedimientos particulares que el usuario ha definido anteriormente, pero sí es necesario conocer cómo se ejecuta porque es la que se usará en el desarrollo del juego para obtener el movimiento resultante.

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 ó 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

Y, finalmente, el procedimiento que valora el resultado de una jugada desde el punto de vista del jugador actual (en este caso, nos restringimos al uso de valores 1/0, pero en otros juegos podríamos considerar una valoración más compleja):

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

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