PJ 2 - Búsqueda Multi Agente

Multi Agent Search

Pacman, ahora con fantasmas. Minimax, Expectimax, y Evaluación.

En este proyecto, van a diseñar agentes para la versión clásica de Pacman, incluyendo fantasmas. A lo largo del camino, van a implementar tanto minimax como expectimax search y diseñar funciones de evaluación.

Preparación

Por favor lean las siguientes instrucciones cuidadosamente antes de seguir con el proyecto.

Visiten este link. Aquí encontrarán todos los archivos necesarios para completar este proyecto.

Abran una terminal en el directorio que prefieran, y ejecuten el siguiente comando:

git clone https://www.github.com/ug-ai-foundations/2025-pj-02-multi-agent-search-<USUARIO>

Tutorial de Git y GitHub

Si no están familiarizados con Git y GitHub, por favor visiten el siguiente link para aprender los comandos básicos de Git y cómo subir su código a GitHub.

Instalación y Tutorial de Python

Por favor para tener completo el material para el proyecto por favor visitar el link de instalación de material.

Contenido del proyecto

El código de este proyecto consiste en varios archivos de Python, algunos de los cuales deberán leer y entender para completar la tarea, y algunos de los cuales pueden ignorar.

Archivos que van a editar

Archivo	Descripción
`multiAgents.py`	Donde residirán todos sus agentes de búsqueda multi-agente.

Archivos que quisas necesiten leer

Archivo	Descripción
`pacman.py`	El archivo principal que ejecuta los juegos de Pacman. Este archivo también describe un tipo GameState de Pacman, que usarán ampliamente en este proyecto.
`game.py`	La lógica detrás de cómo funciona el mundo de Pacman. Este archivo describe varios tipos de soporte como AgentState, Agent, Direction y Grid.
`util.py`	Estructuras de datos útiles para implementar algoritmos de búsqueda. No necesitan usar estas para este proyecto, pero pueden encontrar útiles otras funciones definidas aquí.

Archivos que pueden ignorar

Archivo	Descripción
`graphicsDisplay.py`	Gráficos para Pacman
`graphicsUtils.py`	Soporte para los gráficos de Pacman
`textDisplay.py`	Gráficos ASCII para Pacman
`ghostAgents.py`	Agentes para controlar fantasmas
`keyboardAgents.py`	Interfaces de teclado para controlar Pacman
`layout.py`	Código para leer archivos de diseño y almacenar su contenido
`autograder.py`	Autograder del proyecto
`testParser.py`	Analiza archivos de prueba y solución del calificador automático
`testClasses.py`	Clases de prueba generales para el calificador automático
`test_cases/`	Directorio que contiene los casos de prueba para cada pregunta
`multiagentTestClasses.py`	Clases de prueba automáticas específicas del Proyecto 2

¡Bienvenidos a Multi-Agent Pacman!

Después de clonar el repositorio, jueguen una partida de Pacman clásico ejecutando el siguiente comando:

python pacman.py

y utilicen las teclas de flecha para moverse. Ahora, ejecuten el agente proporcionado ReflexAgent en multiAgents.py.

python pacman.py -p ReflexAgent

Tengan en cuenta que juega bastante mal incluso en layouts simples:

python pacman.py -p ReflexAgent -l testClassic

Inspeccionen su código (en multiAgents.py) y asegúrense de entender lo que está haciendo.

Parte 1 (4 pts): Agente Reflexivo

Mejoren el Agente Reflexivo en multiAgents.py para que juegue de manera decente. El código del agente reflexivo proporcionado ofrece algunos ejemplos útiles de métodos que consultan el GameState para obtener información. Un agente reflexivo bueno deberá considerar tanto las ubicaciones de la comida como las de los fantasmas para desempeñarse bien. Su agente debe ser capaz de limpiar fácilmente y de manera confiable el layout testClassic:

python pacman.py -p ReflexAgent -l testClassic

Prueben su agente reflexivo en el layout predeterminado mediumClassic con uno o dos fantasmas (y la animación desactivada para acelerar la visualización):

python pacman.py --frameTime 0 -p ReflexAgent -k 1

python pacman.py --frameTime 0 -p ReflexAgent -k 2

¿Cómo se comporta su agente? Probablemente morirá con frecuencia con 2 fantasmas en el tablero predeterminado, a menos que su función de evaluación sea realmente buena.

Recuerden que newFood tiene la función asList().

Como características, prueben usar el recíproco de valores importantes (como la distancia a la comida) en lugar de los valores mismos.

La función de evaluación que están escribiendo evalúa pares estado-acción; en partes posteriores del proyecto, estarán evaluando solo los estados.

Puede ser útil ver el contenido interno de varios objetos para depuración. Pueden hacerlo imprimiendo las representaciones en cadena de los objetos. Por ejemplo, pueden imprimir newGhostStates con print(newGhostStates).

Opciones: Los fantasmas predeterminados son aleatorios; también pueden jugar para divertirse con fantasmas direccionales un poco más inteligentes usando -g DirectionalGhost. Si la aleatoriedad les impide saber si su agente está mejorando, pueden usar -f para ejecutar con un seed aleatorio fijo (las mismas elecciones aleatorias en cada juego se realizarán). También pueden jugar múltiples juegos seguidos con -n. Desactiven los gráficos con -q para ejecutar muchos juegos rápidamente.

Calificación: Ejecutaremos su agente en el layout openClassic 10 veces. Recibirán 0 puntos si su agente se agota o nunca gana. Recibirán 1 punto si su agente gana al menos 5 veces, o 2 puntos si gana los 10 juegos. Recibirán 1 punto adicional si el puntaje promedio de su agente es mayor a 500, o 2 puntos si es mayor a 1000. Pueden probar su agente bajo estas condiciones con:

python autograder.py -q q1

Para ejecutarlo sin gráficos, utilicen:

python autograder.py -q q1 --no-graphics

Sin embargo, no pasen demasiado tiempo en esta pregunta, ya que lo más importante del proyecto está por venir.

Pregunta 2 (5 pts): Minimax

Ahora escribirán un agente de búsqueda adversarial en la clase proporcionada MinimaxAgent en el archivo multiAgents.py. Su agente minimax debe funcionar con cualquier número de fantasmas, por lo que deberán escribir un algoritmo que sea un poco más general que lo que han visto previamente en las clases. En particular, su árbol minimax tendrá múltiples capas mínimas (una para cada fantasma) para cada capa máxima.

Su código también debe expandir el árbol del juego hasta una profundidad arbitraria. Califiquen las hojas de su árbol minimax con la función de evaluación proporcionada self.evaluationFunction, que por defecto es scoreEvaluationFunction. MinimaxAgent extiende MultiAgentSearchAgent, lo que da acceso a self.depth y self.evaluationFunction. Asegúrense de que su código minimax haga referencia a estas dos variables donde sea apropiado, ya que estas variables se completan en respuesta a las opciones de la línea de comandos.

Importante: Un solo nivel de búsqueda se considera como un movimiento de Pacman y todas las respuestas de los fantasmas, por lo que una búsqueda de profundidad 2 implicará que Pacman y cada fantasma se muevan dos veces (ver diagrama a continuación).

Minimax

Calificación: Estaremos revisando su código para determinar si explora el número correcto de estados del juego. Esta es la única manera confiable de detectar algunos errores muy sutiles en las implementaciones de minimax. Como resultado, el autograder será muy estricto sobre cuántas veces llaman a GameState.generateSuccessor. Si lo llaman más o menos de lo necesario, el autograder se quejará. Para probar y depurar su código, ejecuta:

python autograder.py -q q2

Esto mostrará lo que hace su algoritmo en varios árboles pequeños, así como en un juego de Pacman. Para ejecutarlo sin gráficos, utilicen:

python autograder.py -q q2 --no-graphics

Pistas y Observaciones

Implementen el algoritmo recursivamente usando una o más funciones auxiliares.
La implementación correcta de minimax llevará a Pacman a perder el juego en algunas pruebas. Esto no es un problema: es un comportamiento correcto y pasará las pruebas.
La función de evaluación para la prueba de Pacman en esta parte ya está escrita (self.evaluationFunction). No deben cambiar esta función, pero deben reconocer que ahora estamos evaluando estados en lugar de acciones, como lo hacíamos para el agente reflexivo. Los agentes de vista anticipada evalúan los estados futuros, mientras que los agentes reflexivos evalúan acciones desde el estado actual.
Los valores minimax del estado inicial en el diseño minimaxClassic son 9, 8, 7, -492 para las profundidades 1, 2, 3 y 4 respectivamente. Tengan en cuenta que su agente minimax ganará con frecuencia (665 de 1000 juegos para nosotros) a pesar de la predicción negativa del minimax de profundidad 4.

  python pacman.py -p MinimaxAgent -l minimaxClassic -a depth=4

Pacman siempre es el agente 0, y los agentes se mueven en orden de índice de agente creciente.
Todos los estados en minimax deben ser GameStates, ya sea pasados a getAction o generados mediante GameState.generateSuccessor. En este proyecto, no abstraerás a estados simplificados.
En tableros más grandes como openClassic y mediumClassic (el predeterminado), verán que Pacman es bueno para no morir, pero bastante malo para ganar. A menudo se moverá sin sentido, sin hacer avances. Incluso podría moverse alrededor de un punto sin comerlo porque no sabe dónde iría después de comer ese punto. No se preocupen si ven este comportamiento, la pregunta 5 resolverá todos estos problemas.
Cuando Pacman cree que su muerte es inevitable, intentará terminar el juego lo antes posible debido a la penalización constante por seguir vivo. A veces, esto es lo incorrecto de hacer con fantasmas aleatorios, pero los agentes minimax siempre asumen lo peor:

  python pacman.py -p MinimaxAgent -l trappedClassic -a depth=3

Asegúrense de entender por qué Pacman se apresura hacia el fantasma más cercano en este caso.

Pregunta 3 (5 pts): Alpha-Beta Pruning

Creen un nuevo agente que use poda alfa-beta para explorar de manera más eficiente el árbol minimax, en AlphaBetaAgent. Nuevamente, su algoritmo será ligeramente más general que el pseudocódigo de la clase, por lo que parte del desafío será extender la lógica de poda alfa-beta de manera apropiada a múltiples agentes minimizadores.

Deberán notar una mejora en la velocidad (tal vez la poda alfa-beta en profundidad 3 se ejecute tan rápido como minimax en profundidad 2). Idealmente, la profundidad 3 en smallClassic debería ejecutarse en solo unos segundos por movimiento o más rápido.

python pacman.py -p AlphaBetaAgent -a depth=3 -l smallClassic

Los valores minimax de AlphaBetaAgent deben ser idénticos a los de MinimaxAgent, aunque las acciones que seleccione pueden variar debido a un comportamiento diferente en la resolución de empates. Nuevamente, los valores minimax del estado inicial en el diseño minimaxClassic son 9, 8, 7 y -492 para las profundidades 1, 2, 3 y 4 respectivamente.

Calificación: Como verificamos su código para determinar si explora el número correcto de estados, es importante que realices la poda alfa-beta sin reordenar los hijos. En otras palabras, los estados sucesores deben ser siempre procesados en el orden devuelto por GameState.getLegalActions. Nuevamente, no debes llamar a GameState.generateSuccessor más de lo necesario.

No deben podar en igualdad para que coincida con el conjunto de estados explorados por nuestro autograder. (De hecho, alternativamente, pero incompatible con nuestro autograder, también se podría permitir la poda en igualdad e invocar alfa-beta una vez en cada hijo del nodo raíz, pero esto no coincidiría con el autograder).

El pseudocódigo a continuación representa el algoritmo que deben implementar para esta pregunta.

Alpha-Beta

Para probar y depurar su código, ejecuten:

python autograder.py -q q3

Esto mostrará lo que hace su algoritmo en varios árboles pequeños, así como en un juego de Pacman. Para ejecutarlo sin gráficos, utilicen:

python autograder.py -q q3 --no-graphics

La implementación correcta de la poda alfa-beta llevará a Pacman a perder algunas de las pruebas. Esto no es un problema: es un comportamiento correcto y pasará las pruebas.

Pregunta 4 (5 pts): Expectimax

Minimax y alfa-beta son geniales, pero ambos suponen que juegan contra un adversario que toma decisiones óptimas. Como cualquier persona que haya ganado al tres en línea pueden decir, esto no siempre es el caso. En esta pregunta, implementarán el ExpectimaxAgent, que es útil para modelar el comportamiento probabilístico de agentes que pueden tomar decisiones subóptimas.

Como con la búsqueda y los problemas que aún no se han cubierto en esta clase, la belleza de estos algoritmos es su aplicabilidad general. Para agilizar su desarrollo, hemos proporcionado algunos casos de prueba basados en árboles genéricos. Pueden depurar su implementación en pequeños árboles del juego utilizando el comando:

python autograder.py -q q4

Se recomienda depurar en estos casos de prueba pequeños y manejables, ya que les ayudará a encontrar errores rápidamente.

Una vez que su algoritmo esté funcionando en árboles pequeños, podrán observar su éxito en Pacman. Los fantasmas aleatorios, por supuesto, no son agentes minimax óptimos, por lo que modelarlos con búsqueda minimax puede no ser apropiado. El ExpectimaxAgent ya no tomará el valor mínimo sobre todas las acciones de los fantasmas, sino la expectativa según el modelo de su agente sobre cómo actúan los fantasmas. Para simplificar su código, asuman que solo estarán jugando contra un adversario que elige entre sus acciones legales uniformemente al azar.

Para ver cómo se comporta el ExpectimaxAgent en Pacman, ejecuten:

python pacman.py -p ExpectimaxAgent -l minimaxClassic -a depth=3

Ahora deberían observar un enfoque más audaz en espacios reducidos con fantasmas. En particular, si Pacman percibe que podría quedar atrapado pero podría escapar para recoger algunos puntos de comida más, al menos lo intentará. Investiguen los resultados de estos dos escenarios:

python pacman.py -p AlphaBetaAgent -l trappedClassic -a depth=3 -q -n 10

python pacman.py -p ExpectimaxAgent -l trappedClassic -a depth=3 -q -n 10

Deberían encontrar que su ExpectimaxAgent gana alrededor de la mitad de las veces, mientras que su AlphaBetaAgent siempre pierde. Asegúrense de entender por qué el comportamiento aquí difiere del caso minimax.

La implementación correcta de expectimax llevará a Pacman a perder algunas de las pruebas. Esto no es un problema: es un comportamiento correcto y pasará las pruebas.

Pregunta 5 (6 pts): Función de Evaluación

Escriban una mejor función de evaluación para Pacman en la función proporcionada betterEvaluationFunction. La función de evaluación debería evaluar estados, en lugar de acciones, como lo hacía su función de evaluación de agente reflejo. Con una búsqueda de profundidad 2, su función de evaluación debería limpiar el diseño smallClassic con un fantasma aleatorio más de la mitad del tiempo y aún así funcionar a una velocidad razonable (para obtener el crédito completo, Pacman debería tener un promedio de alrededor de 1000 puntos cuando está ganando).

Calificación: el autograder ejecutará su agente en el diseño smallClassic 10 veces. Asignaremos puntos a su función de evaluación de la siguiente manera:

Si gana al menos una vez sin agotar el tiempo del autocalificador, recibirá 1 punto. Cualquier agente que no cumpla con estos criterios recibirá 0 puntos.
+1 por ganar al menos 5 veces, +2 por ganar las 10 veces
+1 por un puntaje promedio de al menos 500, +2 por un puntaje promedio de al menos 1000 (incluyendo puntajes en juegos perdidos)
+1 si tus juegos toman en promedio menos de 30 segundos en la máquina de autocalificación, cuando se ejecutan con —no-graphics.
Los puntos adicionales por puntaje promedio y tiempo de cálculo solo se otorgarán si ganas al menos 5 veces.
No copies ningún archivo del Proyecto 1, ya que no pasará el autocalificador en Gradescope.

Pueden probar su agente bajo estas condiciones con

python autograder.py -q q5