; Programa: Package con agentes jugadores de Tron basado en ; búsquedas, juego también denominado "light cycle", ; ver http://en.wikipedia.org/wiki/Light_cycle ; ; Asignatura: Introducción a la Inteligencia Artificial ; ETSII - ULL ; Práctica: (sistemas de producción) ; Autor: aluXXXX (Nombre) ; Fecha: 20/05/2006 ; Comentarios: ; ; Este código supone un esqueleto de ejemplo de el ; fichero que ha de contener los agentes jugadores ; de tron que que el usuario defina y usen búsqueda en ; sistemas de producción. ; ; Para personalizar este fichero ha de renombrarse, ; sustituyendo "aluXXXX" por el lo que desee. Además ; en este código ha de reemplazarse dondequiera que ; apareza "aluXXXX" o "ALUXXXX" por lo mismo, ya que ; el nombre del fichero sin extensión y el nombre ; del package aquí incluido han de coincidir (no ; sensitivo a mayúsculas"). ; ; Para añadir más agentes habrán de generarse las ; funciones correspondientes para los agentes, exportarlas ; dentro de la sección ":export" de defpackage, e ; incluirlas como sublistas en el contenido de la ; constante (defconstant) agentes. Para más información ; consultar "tron-agentes-simples.lsp" y ; "tron-loader.lsp". ; ; Los agentes definidos utilizan el entorno de juego ; Tron, definido principalmente por los packages ; tron-base y tron-comm. ; ; Las funciones accesibles más importantes son: ; ; agente-aluXXXX-camino-ba: Agente tron que busca el camino al ; adversario mediante búsqueda en anchura ; ; agente-aluXXXX-camino-bp: Agente tron que busca el camino al ; adversario mediante búsqueda en profundidad ; ; agente-aluXXXX-camino-es: Agente tron que busca el camino al ; adversario mediante búsqueda en secalada sin podas ; ; agente-aluXXXX-camino-a: Agente tron que busca el camino al ; adversario mediante búsqueda en A* con heurística ; city block ; ; Ver la documentación existente para cada una de ellas. ; ; Para su utilización es aconsejable usar el cargador ; del entorno de juego tron: tron-loader.lsp. ; ; ; Dependencias: ; ; Hace uso del paquete que contiene la interface (tron-comm) ; con el control del juego (tron-base). ; ; Hace uso del paquete interfaz para la creación de sistemas ; de producción simples (shell). ; ; Hace uso del paquete marco genérico para la búsquedas en ; sistemas de producción simples (q_search). ; ; Hace uso del paquete marco genérico para la implementación ; del algoritmo A y A* con q_search (a_star). ; ; Hace uso de la función agente-espiral del paquete ; tron-agentes-simples. ; ; Modificaciones: ; ; - Ver 0.1 (30/05/2006): Primera versión. ; ; - Ver 0.2 (01/06/2006): Cambiado orden cláusulas cond ; del resultados de búsqueda para evitar problemas de ; tiempo agotado y lista frente vacía simulataneos. ; ; Por hacer: ; ; ; - Mejoras en funcionalidades ; -------------------------- ; - ¿Tratamiento de estados visitados? ; - Llegado al límite tiempo empleado mover enotonces ... ; - ¿Otras estrategias de búsqueda para hallar camino? ; - Cuando esta muy próximo al adversario mover según ... ; - ¿Otra forma de detectar contrario encerrado? ; - ¿Reutilizar base hechos de búsquedas anteriores? ; ; ; ; Definición del package ; ---------------------- (defpackage "AGENTES-ALUXXXX-CAMINO" (:use "LISP" "TRON-COMM" "SHELL" "Q_SEARCH" "A_STAR") (:documentation "Agentes jugadores de Tron basado en búsquedas.") (:export "AGENTES" "*VERSION-AGENTES-ALUXXXX-CAMINO*" "AGENTE-ALUXXXX-CAMINO-INI" "AGENTE-ALUXXXX-CAMINO-BA" "AGENTE-ALUXXXX-CAMINO-BP" "AGENTE-ALUXXXX-CAMINO-ES" "AGENTE-ALUXXXX-CAMINO-A-INI" "AGENTE-ALUXXXX-CAMINO-A")) (in-package "AGENTES-ALUXXXX-CAMINO") ; ; Constante versión ; ----------------- (defconstant *version-agentes-aluXXXX-camino* "0.2" "Versión del package agentes-aluXXXX-camino.") ; ; Constante con lista de agentes presentes en este package ; -------------------------------------------------------- (defconstant agentes '((agente-aluXXXX-camino-ba agente-aluXXXX-camino-ini) (agente-aluXXXX-camino-bp agente-aluXXXX-camino-ini) (agente-aluXXXX-camino-es agente-aluXXXX-camino-ini) (agente-aluXXXX-camino-a agente-aluXXXX-camino-ini)) "Agentes basado en búsquedas para jugar a TRON.") ; ; Definición de estructura de estados ; ----------------------------------- (defstruct estado (camino nil) ; Camino como lista de listas (x y) (lon-camino 0) ; Longitud del camino (f-heur 0) ; Valor de la función heurística (dir-ini nil) ; Dirección inicial del camino: [0, 1, 2 ó 3] (ult-dir nil) ; Última dirección elegida (no-cam-dir t)) ; Sí el último movimiento no fue un cambio de dirección ; ; Definición de varialbes globales ; -------------------------------- (defvar *sistema-agente-camino* nil "Reglas del agente-camino.") (defvar *f-heur* nil "Función heurística que evalua un estado en acción de regla.") (defvar pos-adv nil "Posición del adversario, mediante lista x y.") (defvar dist-objetivo 1 "Distancia objetivo a alcanzar respecto a adversario.") (defvar situacion-partida nil "Usada para asignar propiedades que indican para cada jugador la situación de la partida entre movimientos (normal, encerrado, ...).") ; ; Funciones de apoyo para elaboración de reglas ; --------------------------------------------- (defun pos-vacia-p (pos &optional dir) "Mira si está vacía la posición POS, o la resultante de moverse en la dirección DIR, si DIR no es NIL. Devuelve T en el caso de que esté vacía y NIL en caso contrario." (null (consulta-pos-tab pos dir))) (defconstant dir-inc (make-array '(4 2) :initial-contents '((1 -1) ; Norte (0 +1) ; Este (1 +1) ; Sur (0 -1))) ; Oeste "Array para transformar de dirección a campo dir-jug de tron") (defmacro dir2dim-inc (dir) `(aref dir-inc ,dir 0)) (defmacro dir2val-inc (dir) `(aref dir-inc ,dir 1)) (defun pos-inc-dir (pos dir) "Calcula la posición resultante de desplazarse en la direcciónb DIR respecto a POS." (let ((pos-inc (copy-list pos))) (setf (nth (dir2dim-inc dir) pos-inc) (+ (nth (dir2dim-inc dir) pos-inc) (dir2val-inc dir))) pos-inc)) (defun distancia-city (pos1 pos2) "Calculo de la distancia city-block entre POS1 y POS2." (+ (abs (- (first pos1) (first pos2))) (abs (- (second pos1) (second pos2))))) ; ; Funciones para generar sistema de producción ; -------------------------------------------- (defun estados-iniciales (id) "Genera lista de estados iniciales." (list (make-estado :camino (list (consulta-pos-jug id)) :ult-dir (consulta-est-jug id)))) (defun estado-objetivo-p (est) "Chequea si un estado EST es estado objetivo o NIL." ; Si se ha acabado el tiempo o no se ha encontrado solución (or (consulta-contador) (null est) ; O ya se ha alcalnzado distancia objetivo con adversario (>= dist-objetivo (distancia-city pos-adv (first (estado-camino est)))))) (defun precond-regla-dir (est dir) "Generador de precondiciones de reglas." (let ((pos-est (first (estado-camino est)))) (and (not (member (pos-inc-dir pos-est dir) (rest (estado-camino est)) :test #'equal)) (pos-vacia-p pos-est dir)))) (defun accion-regla-dir (est dir) "Generador de acciones de reglas." (let ((nue-est (make-estado :camino (cons (pos-inc-dir (first (estado-camino est)) dir) (estado-camino est)) :lon-camino (1+ (estado-lon-camino est)) :dir-ini (or (estado-dir-ini est) dir) :ult-dir dir :no-cam-dir (eq dir (estado-ult-dir est))))) (if *f-heur* (setf (estado-f-heur nue-est) (funcall *f-heur* nue-est))) nue-est)) ; ; Funciones de apoyo para agentes de búsqueda de camino ; ----------------------------------------------------- (defun print-camino (camino) "Imprime (indirectamente mediante tron-vis) el camino encontrado." (dolist (pos (reverse camino) t) (tron-vis:envio-punteo-pos pos))) (defun print-mensaje (msg) "Imprime (indirectamente mediante tron-vis) el mensaje MSG." (tron-vis:envio-mensaje msg)) ; ; Inicializador de agentes de búsqueda de camino ; ---------------------------------------------- (defun agente-aluXXXX-camino-ini (id &rest dummy) "Inicialización de agente que buscan camino al adversario." (declare (ignore dummy)) ; Resetea la situacion-partida de id (setf (get 'situacion-partida id) nil) ; Inserta las reglas (3 1 0 2) (limpia-reglas) (regla #'(lambda (est) (precond-regla-dir est 3)) #'(lambda (est) (accion-regla-dir est 3))) (regla #'(lambda (est) (precond-regla-dir est 1)) #'(lambda (est) (accion-regla-dir est 1))) (regla #'(lambda (est) (precond-regla-dir est 0)) #'(lambda (est) (accion-regla-dir est 0))) (regla #'(lambda (est) (precond-regla-dir est 2)) #'(lambda (est) (accion-regla-dir est 2))) ; Almacena las reglas, por si alguien más usa shell (setf *sistema-agente-camino* *sistema*) t) ; ; Agente búsqueda de camino en anchura ; ------------------------------------ (defun agente-aluXXXX-camino-ba (id) "Agente jugador Tron que buscan camino al adversario moviéndose en anchura, si se queda encerrado se mueve como agente-espiral." ; (eq situacion-partida t) => Encerrado (if (get 'situacion-partida id) ; Encerrado (tron-agentes-simples:agente-espiral id) ; Como agente-espiral ; No encerrado (buscar camino a adversario) (progn ; Almacena posición del adversario (setf pos-adv (consulta-pos-jug (- 3 id))) ; Carga sistema a utilizar (setf *sistema* *sistema-agente-camino* *f-heur* nil) ; Lanzamos búsqueda (let ((est-sol (generic-search (estados-iniciales id) #'estado-objetivo-p #'hijos :display-fn #'null :merge-fn #'(lambda (new-states) (nconc *search-queue* new-states)) :dequeue-fn #'(lambda () (pop *search-queue*))))) ; Preguntamos por condiciones de parada (cond ((null est-sol) ; No encuentra solución (encerrado) (print-mensaje "¡Ya estás encerrado :)! lanzo espiral") (setf (get 'situacion-partida id) t) ; Nueva situacion-partida (tron-agentes-simples:agente-espiral id)) ; Como agente-espiral ((consulta-contador) ; Agotado el tiempo de búsqueda (print-mensaje "Agotado el tiempo") (estado-dir-ini est-sol)) ; Muevo primero frente ((estado-dir-ini est-sol) ; Aún no estoy pegado (print-mensaje "Encontrado camino anchura") (print-camino (estado-camino est-sol)) ; Imprimo camino hallado (estado-dir-ini est-sol)) ; Muevo primero frente (t ; Ya pegado al adversario (print-mensaje "Estoy a tu cola, lanzo imitador") (tron-agentes-simples:agente-imitador id))))))) ; Como agente-imitador ; ; Agente búsqueda en profundidad ; ------------------------------ (defun agente-aluXXXX-camino-bp (id) "Agente jugador Tron que buscan camino al adversario moviéndose en profundidad, si se queda encerrado se mueve como agente-espiral." ; (eq situacion-partida t) => Encerrado (if (get 'situacion-partida id) ; Encerrado (tron-agentes-simples:agente-espiral id) ; Como agente-espiral ; No encerrado (buscar camino a adversario) (progn ; Almacena posición del adversario (setf pos-adv (consulta-pos-jug (- 3 id))) ; Carga sistema a utilizar (setf *sistema* *sistema-agente-camino* *f-heur* nil) ; Lanzamos búsqueda (let ((est-sol (generic-search (estados-iniciales id) #'estado-objetivo-p #'hijos :display-fn #'null :merge-fn #'(lambda (new-states) (nconc new-states *search-queue*)) :dequeue-fn #'(lambda () (pop *search-queue*))))) ; Preguntamos por condiciones de parada (cond ((null est-sol) ; No encuentra solución (encerrado) (print-mensaje "¡Ya estás encerrado :)! lanzo espiral") (setf (get 'situacion-partida id) t) ; Nueva situacion-partida (tron-agentes-simples:agente-espiral id)) ; Como agente-espiral ((consulta-contador) ; Agotado el tiempo de búsqueda (print-mensaje "Agotado el tiempo") (estado-dir-ini est-sol)) ; Muevo primero frente ((estado-dir-ini est-sol) ; Aún no estoy pegado (print-mensaje "Encontrado camino profundidad") (print-camino (estado-camino est-sol)) ; Imprimo camino hallado (estado-dir-ini est-sol)) ; Muevo primero frente (t ; Ya pegado al adversario (print-mensaje "Estoy a tu cola, lanzo imitador") (tron-agentes-simples:agente-imitador id))))))) ; Como agente-imitador ; ; Agente búsqueda en escalada sin podas ; ------------------------------------- (defvar *pen-dir* 1 "Penalización en cálculo de distancia si el estado sigue la misma dirección que el padre.") (defun h-dist-city (est &optional (pen-dir *pen-dir*)) "Heurística distancia city-block con adversario." (+ (distancia-city (first (estado-camino est)) pos-adv) ; Preferir cambios de dirección (if (estado-no-cam-dir est) pen-dir 0))) (defun agente-aluXXXX-camino-es (id) "Agente jugador Tron que buscan camino al adversario moviéndose en escalada según distancia city-block, si se queda encerrado se mueve como agente-espiral." ; (eq situacion-partida t) => Encerrado (if (get 'situacion-partida id) ; Encerrado (tron-agentes-simples:agente-espiral id) ; Como agente-espiral ; No encerrado (buscar camino a adversario) (progn ; Almacena posición del adversario (setf pos-adv (consulta-pos-jug (- 3 id))) ; Carga sistema a utilizar (setf *sistema* *sistema-agente-camino* *f-heur* #'h-dist-city *eval-fn* #'estado-f-heur) ; Lanzamos búsqueda (let ((est-sol (generic-search (estados-iniciales id) #'estado-objetivo-p #'hijos :display-fn #'null :merge-fn #'(lambda (new-states) (nconc (sort new-states #'< :key *eval-fn*) *search-queue*)) :dequeue-fn #'(lambda () (pop *search-queue*))))) ; Preguntamos por condiciones de parada (cond ((null est-sol) ; No encuentra solución (encerrado) (print-mensaje "¡Ya estás encerrado :)! lanzo espiral") (setf (get 'situacion-partida id) t) ; Nueva situacion-partida (tron-agentes-simples:agente-espiral id)) ; Como agente-espiral ((consulta-contador) ; Agotado el tiempo de búsqueda (print-mensaje "Agotado el tiempo") (estado-dir-ini est-sol)) ; Muevo primero frente ((estado-dir-ini est-sol) ; Aún no estoy pegado (print-mensaje "Encontrado camino escalada/sp") (print-camino (estado-camino est-sol)) ; Imprimo camino hallado (estado-dir-ini est-sol)) ; Muevo primero frente (t ; Ya pegado al adversario (print-mensaje "Estoy a tu cola, lanzo imitador") (tron-agentes-simples:agente-imitador id))))))) ; Como agente-imitador ; ; Funciones de apoyo para agentes de búsqueda A ; --------------------------------------------- (defun f-dist-city (est) "Función heurísticas subdividida con coste camino acumulado + distancia city block." (+ (estado-lon-camino est) (h-dist-city est))) (defun igual-estado (est1 est2) "Comprube si EST1 y EST2 son iguales." (equal (first (estado-camino est1)) (first (estado-camino est2)))) ; ; Agente búsqueda A* ; ------------------ (defun agente-aluXXXX-camino-a (id) "Agente jugador Tron que buscan camino al adversario moviéndose con A* según distancia city-block, si se queda encerrado se mueve como agente-espiral." ; (eq situacion-partida t) => Encerrado (if (get 'situacion-partida id) ; Encerrado (tron-agentes-simples:agente-espiral id) ; Como agente-espiral ; No encerrado (buscar camino a adversario) (progn ; Almacena posición del adversario (setf pos-adv (consulta-pos-jug (- 3 id))) ; Carga sistema a utilizar (setf *sistema* *sistema-agente-camino* *coste-acum-fn* #'estado-lon-camino *f-heur* #'f-dist-city *eval-fn* #'estado-f-heur *igual-est-fn* #'igual-estado) ; Lanzamos búsqueda (let ((est-sol (generic-search (estados-iniciales id) #'estado-objetivo-p #'hijos :display-fn #'null :merge-fn #'priority-a-merge-fn :dequeue-fn #'priority-a-dequeue-fn))) ; Preguntamos por condiciones de parada (cond ((null est-sol) ; No encuentra solución (encerrado) (print-mensaje "¡Ya estás encerrado :)! lanzo espiral") (setf (get 'situacion-partida id) t) ; Nueva situacion-partida (tron-agentes-simples:agente-espiral id)) ; Como agente-espiral ((consulta-contador) ; Agotado el tiempo de búsqueda (print-mensaje "Agotado el tiempo") (estado-dir-ini est-sol)) ; Muevo primero frente ((estado-dir-ini est-sol) ; Aún no estoy pegado (print-mensaje "Encontrado camino A*") (print-camino (estado-camino est-sol)) ; Imprimo camino hallado (estado-dir-ini est-sol)) ; Muevo primero frente (t ; Ya pegado al adversario (print-mensaje "Estoy a tu cola, lanzo imitador") (tron-agentes-simples:agente-imitador id))))))) ; Como agente-imitador