{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Taller 1: Agentes que Planean y Búsquedas\n", "### [Introducción a los Sistemas Inteligentes 2019-1](https://fagonzalezo.github.io/iis-2019-1/)\n", "### Universidad Nacional de Colombia, Bogotá\n", "\n", "---\n", "\n", "**Fecha límite de entrega**: _Viernes 17 de Mayo_ antes de la medianoche\n", "\n", "\n", "Cerciórese de reiniciar y correr el notebook en su totalidad antes de enviarlo. Verifique que todas las salidas se muestran de manera correcta.\n", "\n", "Integrantes del grupo (máximo 3):\n", "\n", "* Nombre_1 ID_1\n", "* Nombre_2 ID_2\n", "* Nombre_3 ID_3\n", "\n", "**Instrucciones de envío:**\n", "\n", "Este notebook debe enviarse a través del siguiente [File Request](https://www.dropbox.com/request/9E2czZTEupEd5IjrgouO) antes de la medianoche de la fecha límite. El archivo debe nombrarse como isi-taller1-unalusername1-unalusername2-unalusername3.ipynb, donde unalusername es el nombre de usuario asignado por la universidad (incluya los nombres de usuario de todos los miembros del grupo).\n", "\n", "---" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "El objetivo de este taller es construir un agente que planea que sea capaz de jugar el juego de *Snake*:\n", "\n", "\"Snake\n", "\n", "El agente tendrá acceso a todo el estado del ambiente. Debe usar esta información para hacer un plan y después actuar de acuerdo a este. \n", "\n", "Para esto vamos a usar como base este [proyecto](https://github.com/YuriyGuts/snake-ai-reinforcement) desarrollado por [Yuriy Guts](https://github.com/YuriyGuts).\n", "\n", "En este caso vamos a utilizar la clase `Environment` tal como está definida en el paquete `snakeai.gameplay.environment`. El método `get_observation()` retorna una arreglo de `numpy` con la información de todo el campo de juego. \n", "\n", "## 1. Problema de búsqueda\n", "Se debe modelar el problema de encontrar un plan (secuencia de acciones) para la serpiente como un problema de búsqueda. En particular el problema de búsqueda debe recibir la configuración actual del tablero la cual corresponde al estado inicial, las acciones corresponden a las acciones que puede ejecutar la serpiente, los estados finales son aquellos en que la serpiente se come la fruta.\n", "\n", "El estado se debe representar como una tupla con el estado del tablero y el de la serpiente (una instancia de la clase `Snake` del paquete `snakeai.gameplay.entities`)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "import numpy as np\n", "from snakeai.gameplay.entities import SnakeAction, Snake\n", "\n", "class SnakeProblem(object):\n", " \"\"\"The abstract class for a formal problem. A new domain subclasses this,\n", " overriding `actions` and `results`, and perhaps other methods.\n", " The default heuristic is 0 and the default action cost is 1 for all states.\n", " When yiou create an instance of a subclass, specify `initial`, and `goal` states \n", " (or give an `is_goal` method) and perhaps other keyword args for the subclass.\"\"\"\n", "\n", " def __init__(self, initial=None, **kwds): \n", " self.__dict__.update(initial=initial, **kwds) \n", " \n", " def actions(self, state): \n", " raise NotImplementedError\n", " \n", " def result(self, state, action): \n", " raise NotImplementedError\n", " \n", " def is_goal(self, state): \n", " raise NotImplementedError\n", " \n", " def action_cost(self, s, a, s1): \n", " return 1\n", " \n", " def h(self, node): \n", " return 0\n", " \n", " def __str__(self):\n", " return '{}({!r}, {!r})'.format(\n", " type(self).__name__, self.initial, self.goal)\n", " \n", "initial = (\n", " np.array([[4, 4, 4, 4, 4, 4, 4, 4, 4, 4],\n", " [4, 0, 0, 0, 4, 0, 0, 0, 0, 4],\n", " [4, 0, 1, 4, 4, 4, 4, 4, 0, 4],\n", " [4, 0, 4, 4, 4, 0, 4, 0, 0, 4],\n", " [4, 0, 0, 0, 4, 2, 0, 0, 0, 4],\n", " [4, 0, 0, 0, 0, 3, 0, 4, 0, 4],\n", " [4, 0, 0, 4, 4, 3, 0, 4, 1, 4],\n", " [4, 0, 0, 0, 4, 3, 0, 4, 0, 4],\n", " [4, 0, 0, 4, 4, 3, 0, 0, 0, 4],\n", " [4, 4, 4, 4, 4, 4, 4, 4, 4, 4]]),\n", " Snake(Point(11, 5), length=5)\n", " )\n", "\n", "problem = SnakeProblem(initial=initial)\n", "problem.result(initial, SnakeAction.MAINTAIN_DIRECTION)" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([[4, 4, 4, 4, 4, 4, 4, 4, 4, 4],\n", " [4, 0, 0, 0, 4, 0, 0, 0, 0, 4],\n", " [4, 0, 1, 4, 4, 4, 4, 4, 0, 4],\n", " [4, 0, 4, 4, 4, 0, 4, 0, 0, 4],\n", " [4, 0, 0, 0, 4, 2, 0, 0, 0, 4],\n", " [4, 0, 0, 0, 0, 3, 0, 4, 0, 4],\n", " [4, 0, 0, 4, 4, 3, 0, 4, 1, 4],\n", " [4, 0, 0, 0, 4, 3, 0, 4, 0, 4],\n", " [4, 0, 0, 4, 4, 3, 0, 0, 0, 4],\n", " [4, 4, 4, 4, 4, 4, 4, 4, 4, 4]])" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from snakeai.gameplay.environment import Environment\n", "inicial = {\n", " \"field\": [\n", " \"##########\",\n", " \"#...#....#\",\n", " \"#.O#####.#\",\n", " \"#.###.#..#\",\n", " \"#...#S...#\",\n", " \"#....s.#.#\",\n", " \"#..##s.#.#\",\n", " \"#...#s.#.#\",\n", " \"#..##s...#\",\n", " \"##########\"\n", " ],\n", "\n", " \"initial_snake_length\": 3,\n", " \"max_step_limit\": 1000,\n", "\n", " \"rewards\": {\n", " \"timestep\": 0,\n", " \"ate_fruit\": 1,\n", " \"died\": -1\n", " }\n", "}\n", "env = Environment(config=inicial, verbose=0)\n", "env.new_episode()\n", "env.get_observation()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 2. Algoritmos de búsqueda no informada\n", "Escriba diferentes funciones para resolver el problema de búsqueda usando BFS e IDS. Pruebe el algoritmo con diferentes configuraciones del problema (diferentes tamaños del tablero, obstáculos, longitudes de la serpiente, etc.). Evalue y discuta los resultados. " ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def solveProblemBFS(problem):\n", " \"\"\"\n", " Recibe una instancia de SnakeProblem y retorna una lista con la secuencia de acciones que resuelve el problema.\n", " La solución debe ser óptima (mínimo número de pasos).\n", " \"\"\"\n", " solucion = []\n", " return solucion\n", "\n", "def solveProblemIDS(problem):\n", " \"\"\"\n", " Recibe una instancia de SnakeProblem y retorna una lista con la secuencia de acciones que resuelve el problema.\n", " La solución debe ser óptima (mínimo número de pasos).\n", " \"\"\"\n", " solucion = []\n", " return solucion" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 3. Algoritmos de búsqueda informada\n", "Escriba una función para resolver el problema de búsqueda usando A*. Prueba al menos dos funciones heurísticas diferentes. Las heurísticas deben ser admisibles. Pruebe el algoritmo con diferentes configuraciones del problema (diferentes tamaños del tablero, obstáculos, longitudes de la serpiente, etc.). Evalue y discuta los resultados. " ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def solveProblemAStar_h1(problem):\n", " \"\"\"\n", " Recibe una instancia de SnakeProblem y retorna una lista con la secuencia de acciones que resuelve el problema.\n", " La solución debe ser óptima (mínimo número de pasos).\n", " \"\"\"\n", " solucion = []\n", " return solucion\n", "\n", "def solveProblemAStar_h2(problem):\n", " \"\"\"\n", " Recibe una instancia de SnakeProblem y retorna una lista con la secuencia de acciones que resuelve el problema.\n", " La solución debe ser óptima (mínimo número de pasos).\n", " \"\"\"\n", " solucion = []\n", " return solucion" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 4. Agente que planea para jugar Snake \n", "Desarrolle un agente para jugar Snake que construya un plan cada vez que aparece una nueva fruta. El agente debe precalcular el plan y después ejecutarlo. Cuando termine de ejecutar las acciones del plan, debe volver a calcular un nuevo plan. " ] }, { "cell_type": "code", "execution_count": 26, "metadata": { "collapsed": true }, "outputs": [], "source": [ "from snakeai.agent import AgentBase\n", "\n", "class MasterMindPlanningAgent(AgentBase):\n", " \"\"\" Represents a Snake agent that takes a random action at every step. \"\"\"\n", "\n", " def __init__(self):\n", " pass\n", "\n", " def begin_episode(self):\n", " pass\n", "\n", " def act(self, observation, reward):\n", " raise NotImplementedError\n", " \n", " def plan(self, observation):\n", " raise NotImplementedError \n", "\n", " def end_episode(self):\n", " pass" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Utilice el siguiente código para ejecutar el agente. Evaluelo en diferentes tableros iniciales. Reporte las estadísticas y compare el desempeño con los agentes al azar y reactivos de la [Práctica 1](https://colab.research.google.com/drive/14bQITZS1wVLYJEKG4jNVsWbsBGryuOvY). Analice y discuta los resultados." ] }, { "cell_type": "code", "execution_count": 27, "metadata": { "collapsed": true }, "outputs": [], "source": [ "from snakeai.gameplay.entities import ALL_SNAKE_ACTIONS, Point\n", "import numpy as np\n", "import random\n", "\n", "class EnvironmentFull(Environment):\n", " \"\"\"\n", " Full observation environment. Same as base class environment, overloads \n", " `get_observation` so that it returns the Field array and the Snake.\n", " (From Environment doc): Represents the RL environment for the Snake game that implements the game logic,\n", " provides rewards for the agent and keeps track of game statistics.\n", " \"\"\"\n", " def __init__(self, config, verbose=0):\n", " super().__init__(config, verbose)\n", "\n", " def get_observation(self):\n", " \"\"\" Observe the state of the environment. \"\"\"\n", " return (np.copy(self.field._cells), self.snake)\n", " \n", " def show_field(self):\n", " return self.field.__str__()\n", " \n", "def play(env, agent, num_episodes=1, verbose=1):\n", " \"\"\"\n", " Play a set of episodes using the specified Snake agent.\n", " Use the non-interactive command-line interface and print the summary statistics afterwards.\n", " \n", " Args:\n", " env: an instance of Snake environment.\n", " agent: an instance of Snake agent.\n", " num_episodes (int): the number of episodes to run.\n", " \"\"\"\n", "\n", " fruit_stats = []\n", "\n", " print()\n", " print('Playing:')\n", "\n", " for episode in range(num_episodes):\n", " timestep = env.new_episode()\n", " agent.begin_episode()\n", " game_over = False\n", " step = 0\n", " while not game_over:\n", " if verbose > 0:\n", " print(\"------ Step \", step, \" ------\")\n", " print (env.show_field())\n", " print (\"Observation:\", env.get_observation())\n", " print (\"Head:\", env.snake.head)\n", " print (\"Direction:\", env.snake.direction)\n", " step += 1\n", " action = agent.act(timestep.observation, timestep.reward)\n", " env.choose_action(action)\n", " timestep = env.timestep()\n", " game_over = timestep.is_episode_end\n", "\n", " fruit_stats.append(env.stats.fruits_eaten)\n", "\n", " summary = '******* Episode {:3d} / {:3d} | Timesteps {:4d} | Fruits {:2d}'\n", " print(summary.format(episode + 1, num_episodes, env.stats.timesteps_survived, env.stats.fruits_eaten))\n", "\n", " print()\n", " print('Fruits eaten {:.1f} +/- stddev {:.1f}'.format(np.mean(fruit_stats), np.std(fruit_stats)))\n", " \n", "inicial = {\n", " \"field\": [\n", " \"#######\",\n", " \"#.....#\",\n", " \"#.....#\",\n", " \"#..S..#\",\n", " \"#.....#\",\n", " \"#.....#\",\n", " \"#######\"\n", " ],\n", "\n", " \"initial_snake_length\": 2,\n", " \"max_step_limit\": 1000,\n", "\n", " \"rewards\": {\n", " \"timestep\": -0.01,\n", " \"ate_fruit\": 1,\n", " \"died\": -1\n", " }\n", "}\n", "\n", "env = EnvironmentFull(config=inicial, verbose=0)\n", "agent = MasterMindPlanningAgent()\n", "play(env, agent, num_episodes= 10, verbose=0)" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.6.8" } }, "nbformat": 4, "nbformat_minor": 2 }