RL_GridWorld_QLearning.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "RL-GridWorld-QLearning.ipynb",
      "version": "0.3.2",
      "provenance": [],
      "collapsed_sections": [],
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/IALeMans/RL-meetup-Reinforcement_Learning/blob/master/RL_GridWorld_QLearning.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "metadata": {
        "id": "lcRtO5Mg-GKd",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# Jeu GRID WORLD\n",
        "\n",
        "Source https://cdancette.fr/2017/08/18/reinforcement-learning-part1/\n",
        "\n",
        "> ![Texte alternatif…](https://cdancette.fr/assets/qlearning2/capture.gif) \n",
        "\n",
        "Principe :\n",
        "\n",
        "![Texte alternatif…](https://cdancette.fr/assets/game.png)"
      ]
    },
    {
      "metadata": {
        "id": "zMF4Pww-6y1y",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "import random\n",
        "\n",
        "\n",
        "class Game:\n",
        "    ACTION_UP = 0\n",
        "    ACTION_LEFT = 1\n",
        "    ACTION_DOWN = 2\n",
        "    ACTION_RIGHT = 3\n",
        "\n",
        "    ACTIONS = [ACTION_DOWN, ACTION_LEFT, ACTION_RIGHT, ACTION_UP]\n",
        "\n",
        "    ACTION_NAMES = [\"UP\", \"LEFT\", \"DOWN\", \"RIGHT\"]\n",
        "\n",
        "    MOVEMENTS = {\n",
        "        ACTION_UP: (1, 0),\n",
        "        ACTION_RIGHT: (0, 1),\n",
        "        ACTION_LEFT: (0, -1),\n",
        "        ACTION_DOWN: (-1, 0)\n",
        "    }\n",
        "\n",
        "    num_actions = len(ACTIONS)\n",
        "\n",
        "    def __init__(self, n, m, wrong_action_p=0.1, alea=False):\n",
        "        self.n = n\n",
        "        self.m = m\n",
        "        self.wrong_action_p = wrong_action_p\n",
        "        self.alea = alea\n",
        "        self.generate_game()\n",
        "\n",
        "\n",
        "\n",
        "    def _position_to_id(self, x, y):\n",
        "        \"\"\"Donne l'identifiant de la position entre 0 et 15\"\"\"\n",
        "        return x + y * self.n\n",
        "\n",
        "    def _id_to_position(self, id):\n",
        "        \"\"\"Réciproque de la fonction précédente\"\"\"\n",
        "        return (id % self.n, id // self.n)\n",
        "\n",
        "    def generate_game(self):\n",
        "        cases = [(x, y) for x in range(self.n) for y in range(self.m)]\n",
        "        hole = random.choice(cases)\n",
        "        cases.remove(hole)\n",
        "        start = random.choice(cases)\n",
        "        cases.remove(start)\n",
        "        end = random.choice(cases)\n",
        "        cases.remove(end)\n",
        "        block = random.choice(cases)\n",
        "        cases.remove(block)\n",
        "\n",
        "        self.position = start\n",
        "        self.end = end\n",
        "        self.hole = hole\n",
        "        self.block = block\n",
        "        self.counter = 0\n",
        "        \n",
        "        if not self.alea:\n",
        "            self.start = start\n",
        "        return self._get_state()\n",
        "    \n",
        "    def reset(self):\n",
        "        if not self.alea:\n",
        "            self.position = self.start\n",
        "            self.counter = 0\n",
        "            return self._get_state()\n",
        "        else:\n",
        "            return self.generate_game()\n",
        "\n",
        "    def _get_grille(self, x, y):\n",
        "        grille = [\n",
        "            [0] * self.n for i in range(self.m)\n",
        "        ]\n",
        "        grille[x][y] = 1\n",
        "        return grille\n",
        "\n",
        "    def _get_state(self):\n",
        "        if self.alea:\n",
        "            return [self._get_grille(x, y) for (x, y) in\n",
        "                    [self.position, self.end, self.hole, self.block]]\n",
        "        return self._position_to_id(*self.position)\n",
        "\n",
        "    def move(self, action):\n",
        "        \"\"\"\n",
        "        takes an action parameter\n",
        "        :param action : the id of an action\n",
        "        :return ((state_id, end, hole, block), reward, is_final, actions)\n",
        "        \"\"\"\n",
        "        \n",
        "        self.counter += 1\n",
        "\n",
        "        if action not in self.ACTIONS:\n",
        "            raise Exception(\"Invalid action\")\n",
        "\n",
        "        # random actions sometimes (2 times over 10 default)\n",
        "        choice = random.random()\n",
        "        if choice < self.wrong_action_p:\n",
        "            action = (action + 1) % 4\n",
        "        elif choice < 2 * self.wrong_action_p:\n",
        "            action = (action - 1) % 4\n",
        "\n",
        "        d_x, d_y = self.MOVEMENTS[action]\n",
        "        x, y = self.position\n",
        "        new_x, new_y = x + d_x, y + d_y\n",
        "\n",
        "        if self.block == (new_x, new_y):\n",
        "            return self._get_state(), -1, False, self.ACTIONS\n",
        "        elif self.hole == (new_x, new_y):\n",
        "            self.position = new_x, new_y\n",
        "            return self._get_state(), -10, True, None\n",
        "        elif self.end == (new_x, new_y):\n",
        "            self.position = new_x, new_y\n",
        "            return self._get_state(), 10, True, self.ACTIONS\n",
        "        elif new_x >= self.n or new_y >= self.m or new_x < 0 or new_y < 0:\n",
        "            return self._get_state(), -1, False, self.ACTIONS\n",
        "        elif self.counter > 190:\n",
        "            self.position = new_x, new_y\n",
        "            return self._get_state(), -10, True, self.ACTIONS\n",
        "        else:\n",
        "            self.position = new_x, new_y\n",
        "            return self._get_state(), -1, False, self.ACTIONS\n",
        "\n",
        "    def print(self):\n",
        "        str = \"\"\n",
        "        for i in range(self.n - 1, -1, -1):\n",
        "            for j in range(self.m):\n",
        "                if (i, j) == self.position:\n",
        "                    str += \"x\"\n",
        "                elif (i, j) == self.block:\n",
        "                    str += \"¤\"\n",
        "                elif (i, j) == self.hole:\n",
        "                    str += \"o\"\n",
        "                elif (i, j) == self.end:\n",
        "                    str += \"@\"\n",
        "                else:\n",
        "                    str += \".\"\n",
        "            str += \"\\n\"\n",
        "        print(str)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "oAJEq_EfihOj",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# entrainement"
      ]
    },
    {
      "metadata": {
        "id": "mVBFwjJRFrEF",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "# q learning with table\n",
        "import numpy as np\n",
        "\n",
        "states_n = 16\n",
        "actions_n = 4\n",
        "Q = np.zeros([states_n, actions_n])"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "55L8Y17CFyIp",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "On définit le nombre d’états (16), et d’actions pour chaque état (4). Et on construit le tableau de valeur etat / action Q, rempli de 0."
      ]
    },
    {
      "metadata": {
        "id": "azBvHL3wF1R8",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "# Set learning parameters\n",
        "lr = .85\n",
        "y = .99\n",
        "num_episodes = 1000"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "WzbAjYBWF8LF",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "On définit les paramètres de l’apprentissage.\n",
        "\n",
        "**lr ** : learning rate, c’est la vitesse d’apprentissage. Plus il est élevé, plus les nouvelles informations seront importantes par rapport aux anciennes. À 0, l’agent n’apprend rien, et à 1, il ne retiendra pas les anciennes infos qu’il a apprises. C’est l’idéal si l’environnement est déterministe (ie 1 etat + 1 action = toujours le même état et la même récompense). Ici l’environnement n’est pas déterministe, car l’agent peut se tromper de direction. On le place donc à .85 (valeur trouvée par tatonnement).\n",
        "\n",
        "**y** : facteur d’actualisation (gamma), entre 0 et 1. : détermine l’importance des récompenses futures. Trop élevé (trop proche de 1), il y a risque de divergence.\n",
        "\n",
        "**num_episodes** : le nombre de parties que l’on va faire. 1000 est largement suffisant ici, comme on peut le voir dans les graphiques plus bas.\n"
      ]
    },
    {
      "metadata": {
        "id": "lnC4ivZFGG82",
        "colab_type": "code",
        "outputId": "a047089d-934a-48b1-c4b6-291bb7d68019",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 121
        }
      },
      "cell_type": "code",
      "source": [
        "cumul_reward_list = []\n",
        "actions_list = []\n",
        "states_list = []\n",
        "game = Game(4, 4, 0) # 0.1 chance to go left or right instead of asked direction\n",
        "for i in range(num_episodes):\n",
        "    actions = []\n",
        "    s = game.reset()\n",
        "    states = [s]\n",
        "    cumul_reward = 0\n",
        "    d = False\n",
        "    while True:\n",
        "        # on choisit une action aléatoire avec une certaine probabilité, qui décroit\n",
        "        # TODO : simplifier ça (pas clair)\n",
        "        Q2 = Q[s,:] + np.random.randn(1, actions_n)*(1. / (i +1))\n",
        "        a = np.argmax(Q2)\n",
        "        s1, reward, d, _ = game.move(a)\n",
        "        Q[s, a] = Q[s, a] + lr*(reward + y * np.max(Q[s1,:]) - Q[s, a]) # Fonction de mise à jour de la Q-table\n",
        "        cumul_reward += reward\n",
        "        s = s1\n",
        "        actions.append(a)\n",
        "        states.append(s)\n",
        "        if d == True:\n",
        "            break\n",
        "    states_list.append(states)\n",
        "    actions_list.append(actions)\n",
        "    cumul_reward_list.append(cumul_reward)\n",
        "\n",
        "print(\"Score over time: \" +  str(sum(cumul_reward_list[-100:])/100.0))\n",
        "\n",
        "game.reset()\n",
        "game.print()"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Score over time: 5.0\n",
            "..ox\n",
            "....\n",
            "..¤.\n",
            "@...\n",
            "\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {
        "id": "YoITssH1FOQe",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "## Explications lignes par lignes\n",
        "\n",
        "```\n",
        "    actions = []\n",
        "    s = game.reset()\n",
        "    states = [s]\n",
        "    cumul_reward = 0\n",
        "    d = False\n",
        "```\n",
        "Initialisation du jeu\n",
        "\n",
        "\n",
        "```\n",
        "    Q2 = Q[s,:] + np.random.randn(1, actions_n)*(1. / (i +1))\n",
        "    a = np.argmax(Q2)\n",
        "```\n",
        "\n",
        "Etape importante : ici, on choisit quelle action on va effectuer pour ce tour. On a une probabilité de faire une action aléatoire (i = 0 au début, donc l’action est forcément aléatoire). Puis cette probabilité décroit au cours du temps.\n",
        "\n",
        "\n",
        "\n",
        "```\n",
        "    Q[s, a] = Q[s, a] + lr*(reward + y * np.max(Q[s1,:]) - Q[s, a]) # Fonction de mise à jour de la Q-table\n",
        "```\n",
        "\n",
        "\n",
        "On applique la formule du Q-learning."
      ]
    },
    {
      "metadata": {
        "id": "MmdUUbUFGYxk",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "## la performance\n"
      ]
    },
    {
      "metadata": {
        "id": "F4qbsBu78R9W",
        "colab_type": "code",
        "outputId": "8790f6f9-94f7-49cd-9dd5-780c95244cd2",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 362
        }
      },
      "cell_type": "code",
      "source": [
        "import matplotlib.pyplot as plt\n",
        "plt.plot(cumul_reward_list[:100])\n",
        "plt.ylabel('Cumulative reward')\n",
        "plt.xlabel('Étape')\n",
        "plt.show()"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAfIAAAFZCAYAAABjSq39AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4yLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvOIA7rQAAIABJREFUeJzt3Xt4lPWd///XHJNAghCcoIJ44OTK\nIYXa/a0cFjxWEantd8O6FqyuVfFA7cWlHAICbhdRa12l1KUr2C9LQTS6VdrLVrZS/G5rBJEuRVpU\nPFTOBJIAScjM3DP3749kBkJmMsnMfd+TIc/HdXmV3Jl75pOP2Fc+7/tzcJmmaQoAAOQkd7YbAAAA\n0keQAwCQwwhyAAByGEEOAEAOI8gBAMhh3mw3IB1VVScsf89evbqppqbB8vftauhHa9CP1qAfrUE/\nWiPTfgwEihJeZ0TezOv1ZLsJZwX60Rr0ozXoR2vQj9awqx8JcgAAchhBDgBADiPIAQDIYQQ5AAA5\njCAHACCHEeQAAOQwghwAgBxGkAMAkMMIcgAAchhBDgBADiPIAQDIYTl5aEqu+d22vXrvz4f08K0j\n5fN2/HenwzUNWvLzbWoIGja0zlouSWa2G3EWoB+tQT9ag37suG55Xs2ZOkp9enWz/bMIcgfs/KJG\nn+w9pr1Vdbrk/B4dvn/rR1U6Vh/S+b27Kd/fuf+V+XxuhcPRbDcj59GP1qAfrUE/dlz3fK9j/3/d\nuVPhLGFEmv4D2HM4vSDf+Xm1JGnWbaN0Tne/pW2zWiBQZMsxs10N/WgN+tEa9GPnxjNyB0SiTUWp\nvYfrOnxvMBzRJ3tr1b+ksNOHOADAeQS5AyLNI/K9VR0P8k/21MqImLr8kmKrmwUAOAt0itL65s2b\n9dBDD2nQoEGSpMGDB+vRRx/NcqusYzSPyPccrpNpmnK5XO2+98PmsvpQghwAkECnCHJJ+tu//Vst\nXbo0282wRWxEXt9oqOZEUMU98tt975+/qJbP69bgfufY1TwAQA6jtO6ASOTUwo2OlNdr64LaW1Wv\nwRf2lM/rsaNpAIAc12lG5Lt379b06dN17NgxPfjggxozZkzS1/bq1U1eG4ItECiy/D0lyTytlF5d\nH2735+z4a60k6W+Hnm9b2+yQS23tzOhHa9CP1qAfrWFHP3aKIL/44ov14IMP6sYbb9SePXt0++23\na8OGDfL7E8/SrqlpsLwNdi6vCIYMuVySaUq7Pj/a7s9570/7JUkXl3TPmaUfLFOxBv1oDfrRGvSj\nNTLtx2S/BHSK0nqfPn00ceJEuVwu9e/fX+eee64OHTqU7WZZJhIx1asoTwV5Hu2tqm/XPaZp6s9f\nVKtHd7/6Bbrb3EIAQK7qFEG+fv16rVy5UpJUVVWlo0ePqk+fPllulXWMaFRej1v9AoU6eLRBYSOS\n8p59VfU6Vh/S0It7dWiWOwCga+kUpfWrr75aDz/8sN5++22Fw2EtWrQoaVk9F0Uipjx5LvUrKdQn\ne49p/5EGXXRe289JYsvOLr+YZWcAgOQ6RZAXFhZq+fLl2W6GbSLNI/ILA4WSmtaTpwryP3/B+nEA\nQGqdorR+totETHncLl1YcirI2xI2IvpoT636BrqrZ2GeE00EAOQogtwBRsSU1+NW3+ZJa6nWkn+0\np1ZhI6qhlNUBACkQ5DaLmqaipimvx6V8v1clPQviW7UmYpqmfvXuXyVJV1xW4mRTAQA5iCC3WWxX\nN4+7aeb5hSWFqjsZVm1dKOHrt396VB/vqdVXBp6rgX3ZlhUA0DaC3Gaxs8g9nqau7tf8nDxReT0a\nNfXapk/lckn/Z8IA5xoJAMhZBLnNYmeRx0bk/Zpnric6m/wPOw5o35F6jR1+vvqeyyYwAIDUCHKb\nxU4+8zaPyC8saQroPWeMyIPhiF7//efye926ZdylzjYSAJCzCHKbxUfknqYR+bk9C5Tn97Ragvbb\nrXtUcyKo6752oXoVseQMANA+nWJDmLNZ7Bm51930O5Pb5VK/QHd9ceCEtu46LJfLJdM09eZ7X6qw\nwKcb/7+LstlcAECOIchtFhuRez2n9ku/qE+RPt13XM+//mGL1956zSB1y+dfCQCg/UgNmxnx5Wen\nnmJMHnOJzu/dXdHoqbXk+XkejR52nuPtAwDkNoLcZpFobPnZqRF5j+5+XfPVftlqEgDgLMJkN5vF\nR+QejiIFAFiPILdZ5IzJbgAAWIl0sZkRZUQOALAPQW6zMzeEAQDASqSLzWKHpnjdjMgBANYjyG12\nqrROVwMArEe62CwSab38DAAAqxDkNjPOOI8cAAArEeQ2M6JMdgMA2Id0sVmEETkAwEYEuc1YfgYA\nsBPpYrP4eeSMyAEANiDIbWYwIgcA2Ih0sVmi88gBALAKQW6zROeRAwBgFdLFZonOIwcAwCoEuc3Y\nEAYAYCdvthsQ8/jjj2v79u1yuVwqLy/XiBEjst0kS7D8DABgp04R5Fu2bNFf//pXvfzyy/r0009V\nXl6ul19+OdvNsgTnkQMA7NQphomVlZW69tprJUkDBgzQsWPHVFdXl+VWWSM+ImeyGwDABp1iRH7k\nyBENHTo0/nVxcbGqqqpUWFiY8PW9enWT1+uxvB2BQJHl7+n1NXVxn5Ii9eqRb/n7d0Z29GNXRD9a\ng360Bv1oDVtyxvJ3tIBpmm1+v6amwfLPDASKVFV1wvL3rW8ISZJqaxtkBMOWv39nY1c/djX0ozXo\nR2vQj9bItB+T/RLQKeq9JSUlOnLkSPzrw4cPKxAIZLFF1omfR86sdQCADTpFkI8ZM0ZvvfWWJGnn\nzp0qKSlJWlbPNQY7uwEAbNQpSuujRo3S0KFDdeutt8rlcmnhwoXZbpJlTo3IO8XvTACAs0ynCHJJ\nevjhh7PdBFsYUVMul+SmtA4AsAHDRJtFIlE2gwEA2IaEsVkkYjLRDQBgG4LcZkbUZEQOALANCWOz\nSCTK9qwAANsQ5DYzIqa8lNYBADYhyG0WiUblobQOALAJCWMzg8luAAAbEeQ2izDZDQBgIxKmHf7f\n9v3668H0NrqPRKKMyAEAtiHIUzgZNPR/f71Lv3z3i7TuNyKMyAEA9iFhUgiGI5KkxpDR4Xujpqmo\naXJgCgDANgR5CmGj6dCTUPP/dkQk0nTyGaV1AIBdCPIUjObTy0LNI/OOiESbTz6jtA4AsAkJk0Js\nRB5OY0RuMCIHANiMIE8hXloPp1FajzYFOZPdAAB2IWFSOPWMPI3SeiRWWmdEDgCwB0GeQvwZeTql\n9diI3E03AwDsQcKkEH9Gnk5pvfmXAJafAQDsQpCnEG4O46hpxkfn7XVqshvdDACwBwmTwumz1Ts6\n4e3U8jNG5AAAexDkKYRPG4WHOzjhLT4iJ8gBADYhyFNoMSLv4IS3+DNySusAAJuQMCkYGQR5bNY6\nI3IAgF0I8hROL613dJvW2F7rbAgDALALCZPC6aX1jm7TGt8Qhi1aAQA2IchTaPmMvIOT3diiFQBg\nMxImhZal9TRH5DwjBwDYhCBPwchkRM7pZwAAmxHkKbRYR57mhjCU1gEAdvFmuwH/9V//peeee079\n+/eXJI0ePVr33Xdfllt1SibryBmRAwDslvUgl6SJEydq9uzZ2W5GQpmU1jmPHABgNxImhYxK6yw/\nAwDYrFOMyLds2aK77rpLhmFo9uzZuvzyy9t8fa9e3eT1eixvRyBQ1Pqi61QIe/3exK9JIq/AJ0nq\nXdy9Q/fluq70s9qJfrQG/WgN+tEadvSjo0FeUVGhioqKFtduuukmzZgxQxMmTNAf//hHzZ49W7/8\n5S/bfJ+amgbL2xYIFKmq6kSr6w0nw/E/1x4/mfA1yRw/3ihJqq9r7NB9uSxZP6Jj6Edr0I/WoB+t\nkWk/JvslwNEgLysrU1lZWdLvjxw5UtXV1YpEIvJ4rB9xp8PIYB0555EDAOyW9YR54YUX9Ktf/UqS\n9PHHH6u4uLjThLh05hatHZ3sxoYwAAB7Zf0Z+c0336xHHnlE69atk2EYWrx4cbab1EI4ElW+36PG\nUITlZwCATifrQX7eeedp9erV2W5GUmEjqu753qYg7/CGMCw/AwDYi4RJwYhEVZDXNPu8o6V1g73W\nAQA2I8hTCBtR5fnc8npcHS6tx88jZ7IbAMAmJEwboqYpI2LK63HL7/WkUVpnRA4AsFfSZ+Svv/56\nmzfecsstljems4ntzObzuuXzuTu+RWuEZ+QAAHslDfI//OEPkqSamhrt2rVLpaWlikQi+tOf/qSR\nI0d2iSCPLT3zed3ye90tlqK1h8EWrQAAmyUN8h/+8IeSpO9973v67W9/q/z8fElSXV2d5s+f70zr\nsqxlkHvU0Bjs0P1GfNY6QQ4AsEfKmu/+/fvjIS5JhYWF2r9/v62N6ixiQe71uOX3dXxEfurQFErr\nAAB7pFxHPmjQIN16660aOXKk3G63tm/frosuusiJtmVd+PRn5F6PQkZUpmnK5WrfCNuImnK5JDel\ndQCATVIG+eOPP653331XH3/8sUzT1N13361x48Y50basi5fWPU3PyGPX/L72bSEbaZ7xDgCAXdoV\n5PPmzdOYMWOcaE+n0nJE3hTIoQ4FeZSJbgAAW6UcLno8HlVWVioYDCoajcb/6QqM056R5zWHdyjc\n/iVokSgjcgCAvVKOyCsqKrRq1SqZphm/5nK59Je//MXWhnUGiUbkHZnwZkSibAYDALBVyiD/4IMP\nWl374osv7GhLp3Pm8jNJHdqmNRI15aW0DgCwUcogj0Qi+v3vf6+amhpJUigU0vLly7Vx40bbG5dt\nZy4/k9Sh3d2MSPufpwMAkI6UQf7II4/o2LFj+uijjzRq1Cht375dM2bMcKJtWWckmuzWgf3WjYip\ngjxG5AAA+6SciXXw4EGtXLlSl1xyiZYuXaq1a9dqx44dTrQt61qU1ptH1h05ypTJbgAAu7U7ZQzD\nUDAYVN++fbV7924729RpnL6OPJ0ROcvPAAB2S1la/7u/+zu98MILuvbaa/Wtb31Lffv27TLLz2Kz\n1r3eU8vPOjJrnRE5AMBuKYP8wQcflCS53W6NHDlSR48e7TKbwxhG62fkwXaW1k3TbA5yRuQAAPuk\nDPKrrrpKpaWlGjt2rMaOHatRo0Y50a5OIb6O/PQtWttZWo80n3xGaR0AYKeUQb5x40bt2LFDmzdv\n1qOPPqqamhp99atf1bx585xoX1aFjZaHpkjtX34WP4uc0joAwEYpg9zj8Wjo0KEyDEPRaFRbtmzR\ntm3bnGhb1hlG06ja53Erz9exyW6MyAEATkgZ5HfccYfcbreGDh2qK664QlOnTlVRUZETbcu6cKRp\n9H36iLy9k92MSFOQM9kNAGCnlCnzN3/zNwqHw9q1a5c++ugjffrpp4pE2r+WOpe13KK1Yzu7ReKl\ndUbkAAD7pByRz549W5J04sQJbdmyRcuXL+8y5fXTt2j1+U4dY9oeRnNp3etmRA4AsE/KIP/444/1\n/vvv6/3339cnn3yiAQMGxMP9bBcrj/u8bkWiHTvGlBE5AMAJKYP8Bz/4gcaMGaN//ud/1vDhw+Vy\ndZ1gim3H6vO6FW0+xrW9z8gjEUbkAAD7pUyZFStWqLCwUBs2bJDL5dL27dsVDAadaFvWhY2oXGqa\neX7qGXl7S+uMyAEA9ksZ5I899pj27NmjzZs3S5J27typOXPm2N6wziAcicrrdcvlcsnrccslKdzu\n0nrz8jOCHABgo5RB/tlnn2nu3LnKz8+XJN122206fPhw2h+4ZcsWXXnllfrd734Xv7Zr1y7deuut\nuvXWW7Vw4cK039tqYcOUr3n5mMvlks/nVrDdy8+aJ8pRWgcA2Chlyni9TY/RY8/GGxoa1NjYmNaH\nffnll/rZz37WapvXxYsXq7y8XOvWrVNdXZ3eeeedtN7fauFINL7HuiT5vZ72ryOPMiIHANgvZZDf\ncMMN+s53vqO9e/fqX//1X3XLLbfo5ptvTuvDAoGAli1b1mJDmVAopH379mnEiBGSmvZ2r6ysTOv9\nrWYYkRYbuvi87g7MWmdDGACA/VLOWp86dapGjBihLVu2yO/365lnntGwYcPS+rCCgoJW12pqatSj\nR4/4171791ZVVVWb79OrVzd5m3das1Ig0HLHuogpdc/3xq93y/eqodFo9bpEuh+qkySd0yO/Xa8/\nm3S1n9cu9KM16Edr0I/WsKMfUwb54sWLNW/evPiIub0qKipUUVHR4tqMGTM0bty4Nu8zm5d5taWm\npqFDbWmPQKBIVVUnWlwLhiIqKvDFr7tdLjWGjFava6uNjSfD7Xr92SJRP6Lj6Edr0I/WoB+tkWk/\nJvsloF2HplRWVmrUqFHy+Xzx6+4Uk7jKyspUVlaWsmHFxcWqra2Nf33o0CGVlJSkvM8JYePMZ+Tu\ndh+aYrAhDADAASmDvKKiQqtWrZJpmnK5XPH//ctf/mJJA3w+ny699FJt3bpVV1xxhTZs2KBp06ZZ\n8t6ZME1TRiTa6hl5JGoqEo3Kk+IXGU4/AwA4IWWQf/DBB5Z92KZNm7Ry5Up99tln2rlzp1avXq0X\nX3xR5eXlWrBggaLRqEpLSzV69GjLPjNdp2/PGuP3xbZpjaogr+0gjy8/Y7IbAMBGKYPcShMmTNCE\nCRNaXR84cKDWrl3rZFNSip985mlZWo99ryCv7fsZkQMAnMBwMYlwbETtPb203jwib8dRppxHDgBw\nAimThJFoRO47NSJPJX76GSNyAICNUgb5sWPH9OSTT+rhhx+WJG3cuFHV1dW2NyzbYiPyM3d2k9Su\nmevx88gZkQMAbJQyZebPn6/zzz9fe/fuldS0E1tXOI88/ozc23pE3p7SOiNyAIATUgZ5dXW1br/9\n9vga8htuuCHtvdZzSaLJbr4OHGUaYUQOAHBAu1ImHA7HD005cuSIGhqs31mtszESTHaLldbD7Smt\nsyEMAMABKZefffvb39Y//MM/qKqqStOnT9eOHTs0b948J9qWVZmX1ll+BgCwX8ogv/HGGzVq1Cj9\n8Y9/lN/v17/8y790mi1U7dRmaZ3JbgCATiJlkI8fP16TJk3S5MmTddlllznRpk6hrVnr4Y5MdqO0\nDgCwUcrh4iuvvKJAIKBHH31U3/jGN7Ry5UodOnTIibZlldFGaT3YrmfkzSPyFHuyAwCQiZQpc955\n5+nOO+9URUWFfvKTn2jv3r269tprnWhbVsVH5J40R+RRRuQAAPu1a6/1jz/+WG+99ZY2bNignj17\nasGCBXa3K+tiz8hbbtHageVnbNEKAHBAyiC/4YYbVFBQoEmTJmnFihXq06ePE+3KuoSHpnRgi1aD\nDWEAAA5IGeTLli3TwIEDnWhLp9L2Fq3tKa3HRuQEOQDAPkmD/Pvf/76effZZ3XXXXfHNYCTJNE25\nXC5t2rTJifZlTcJ15B0orZ8akVNaBwDYJ2mQz58/X5ISnhN+8uRJ+1rUScRmrZ/+jNvnix1j2r4t\nWl0uyU1pHQBgo6TDxXPPPVeStGDBAvXt27fFP13i0JSEpfXmZ+TtKK0bEZOJbgAA2yUdka9fv14/\n+clPtH//fk2YMCF+3TAM9e7d24m2ZVWi0nrHDk2JMtENAGC7pEE+efJk3XTTTZo3b55mzJgRv+52\nu7vEzPVEs9a9Hrc8ble791pnRA4AsFubSePxePTEE0+oZ8+ecrlccrlcCgaDmjJlilPty5pEp59J\nTaPy9p5+xmYwAAC7pVx+tmLFCi1fvlyhUEjdunVTMBjUzTff7ETbsirRiFxqek4ebOdkNy+ldQCA\nzVLWfn/zm9/o3XffVWlpqd577z09/fTTGjRokBNty6pEk90kye/ztGuL1qYROaV1AIC9UiZN9+7d\n5ff7FQ6HJUnXXHON3n77bdsblm3xLVrPKI/7vO52HWMaiZpMdgMA2C5laf2cc87R+vXrNXjwYM2d\nO1cDBgzQ4cOHnWhbVhmRqLwed4vNcKSm3d3CRrAd9zPZDQBgv5RB/uSTT+ro0aO67rrrtGrVKh08\neFDPPPOME23LqrARbVVWlySfz61QOBLf4S4Zlp8BAJyQNMj37NnT4usjR47opptusr1BnUWyIM/z\numWqacTt87YR5IzIAQAOSBrk3/nOd+RyuWSaZqvvuVyus/45ediIypdg+ZjvtDPJEwW91LQfPc/I\nAQBOSBrkGzdudLIdnY4RiSo/r3X3xI4yDRlRdUtyLyefAQCckvIZ+axZsxJef+qpp9L6wC1btuih\nhx7S448/rquuukqSNG3aNDU0NKhbt6ZonD17toYNG5bW+1slbERV1K31iLs9R5nGTz6jtA4AsFnK\nIL/yyivjfw6Hw9q8ebP69euX1od9+eWX+tnPfqZRo0a1+t6SJUs0ePDgtN7XDuFINOEzcJ8v9X7r\nsRE5pXUAgN1SBvk3v/nNFl9PmTJF9957b1ofFggEtGzZMs2bNy+t+51imqYMI9pqVzfptBPQ2ghy\nIxIrrTMiBwDYK2WQR6MtA+vAgQP64osv0vqwgoKCpN9bunSpampqNGDAAJWXlys/Pz/pa3v16iZv\nc4nbSoFAkaSmkDYldevmj1+L6dmj6Wco6J7X6nsxLl/Tee3dE9zfFXTFn9kO9KM16Edr0I/WsKMf\nUwb55Zdf3mL2elFRke6+++6Ub1xRUaGKiooW12bMmKFx48a1eu3tt9+uIUOGqH///lq4cKHWrFmj\nu+66K+l719Q0pPz8jgoEilRVdUKSdDJoNF2MmvFrMUa46XtVR+pU1SMv4Xsdrj3Z/NpIq/vPdqf3\nI9JHP1qDfrQG/WiNTPsx2S8BKYN8165daX1gWVmZysrK2vXa6667Lv7nq6++Wm+++WZan2mVZNuz\nSqeWn7W1TWskPtmNZ+QAAHulDPJDhw7prbfe0okTJ1qsKX/wwQctaYBpmrrzzju1dOlS9ejRQ5s3\nb876oSxGkgNTpNOfkSeftR6JPSN384wcAGCvlEF+9913a+jQoerTp0/GH7Zp0yatXLlSn332mXbu\n3KnVq1frxRdf1JQpU3THHXeooKBAffr00YwZMzL+rEzEjzBNtEWrtwOz1hmRAwBsljLIe/bsqSVL\nlljyYRMmTNCECRNaXZ84caImTpxoyWdY4dRZ5K0n1OX5OrKOnCAHANgrZZBfd911Wr9+vUaOHCnP\nacF2wQUX2NqwbIqdRe5NtI68XcvPmu+ntA4AsFnKIP/oo4/0y1/+Uj179oxfc7lc2rRpk53tyqq2\nSut+SusAgE4kZZBv375d77//vvx+vxPt6RRiI/JEG8L42lVaZ0MYAIAzUibNsGHDFAwGnWhLpxFf\nfpb2iLz5GTlbtAIAbNau5WdXX321BgwY0OIZ+Zo1a2xtWDYZRvIRud936hjTZCKMyAEADkkZ5NOn\nT3eiHZ1KuB3ryNvaEMZgRA4AcEjKII9Eko88z1YZryOPMNkNAOCMlEH+/PPPx/8cDoe1e/dujRo1\nqsXxpmebU1u0Ji+th9oorceXn1FaBwDYLGWQr169usXXR48e1Y9+9CPbGtQZtLVFa3wdeVt7rXMe\nOQDAIR0eMvbu3VufffaZHW3pNNoqrbtdLvm87hQjcia7AQCckXJE/sgjj8jlOjWyPHDggNxn+Y5l\n4TZmrUtNE97aPP2MyW4AAIekDPLRo0fH/+xyuVRYWKgxY8bY2qhsiz/jTjAil6Q8v0dBNoQBAHQC\nbQb5nj179M1vfjP+9cmTJ3Xo0CEVFBTY3rBsSj0i96i+MZz0/vh55IzIAQA2SzpkrKys1D/90z/p\nxIkT8Wt79uzRd7/7XX344YeONC5b2lpHLjWdgNZ2aZ0ROQDAGUmTZtmyZXrxxRdVVFQUvzZ48GD9\n+7//u5599llHGpctqUbkeT63QuGITNNM+H3WkQMAnJI0yE3T1ODBg1tdHzRo0Fm/93pby8+kprXk\nppJvCmNQWgcAOCRpkDc0NCS9qba21pbGdBZtLT+TmkrrUvIT0AxK6wAAhyRNmkGDBumll15qdf2F\nF15QaWmprY3KtlRBHtvdLdnM9fhkN0rrAACbJZ21PmvWLD3wwAN64403NGzYMEWjUW3btk2FhYX6\n6U9/6mQbHRcLck8bz8glKZhkwlt8+dlZvt4eAJB9SYM8EAjolVdeUWVlpT755BN5PB7deOON+trX\nvuZk+7LCiETl9bjkdiUeUftTlNbjG8IwIgcA2CzlhjBXXnnlWX1ASiJhI5q0rC6lfkbOeeQAAKeQ\nNAmEI9E2Q9gfL60nG5FzaAoAwBkEeQLtHZEnf0YeO8aUIAcA2IsgTyAciSbdDEZqR2k9PiKnewEA\n9iJpEjBSjMhTLT8zIlG5XJKb0joAwGYEeQJho+1n5HkpgjwYisRfAwCAnQjyM5im2VRab/MZedP3\nkh2c0hiOKN9PkAMA7EeQnyESNWWayXd1kyS/v+0ReWMoonx/ypV9AABkjCA/Q2xXtzZL695UQW4o\njxE5AMABjg4bDcPQvHnz9OWXXyoSiWjWrFm64oortGvXLi1atEiSNGTIED322GNONqtlG1OcfCad\nGpEnmrUejZoKhaMqIMgBAA5wdET+xhtvqKCgQC+99JIWL16sJ554QpK0ePFilZeXa926daqrq9M7\n77zjZLNaSHVgitT2OvLYKJ3SOgDACY6mzeTJkzVp0iRJUnFxsWpraxUKhbRv3z6NGDFCknTVVVep\nsrJS48ePd6RNwXBEL2/crXDUVDBoKBhqCuK21pH7vbHJbq1H5I3N91NaBwA4wdEg9/l88T+vWrVK\nkyZNUk1NjXr06BG/3rt3b1VVVbX5Pr16dZPXa01QHjxar3d3HFDIaDm6HnJJbwUCRQnviW34YsrV\n6jXBpm+pZ4/8pPef7brqz201+tEa9KM16Edr2NGPtgV5RUWFKioqWlybMWOGxo0bpzVr1mjnzp1a\nvny5qqurW7zGNM2U711T02BZOz2SnvveOBX2KNDRo3WSmjZyKSzwqarqRNL7fF636hqCrV6z/+Bx\nSZIZibZ5/9kqECjqkj+31ehHa9CP1qAfrZFpPyb7JcC2IC8rK1NZWVmr6xUVFdq4caOef/55+Xy+\neIk95tChQyopKbGrWQnl+T3qWZSncGOo3ff4ve6Ez8hjpXXWkQMAnODoZLc9e/Zo3bp1WrZsmfLy\n8iQ1ldsvvfRSbd26VZK0YcMcgiaUAAAQFElEQVQGjRs3zslmpSXP70n4jDwYYrIbAMA5jqZNRUWF\namtrdc8998SvrVy5UuXl5VqwYIGi0ahKS0s1evRoJ5uVljyfR3Unw62uN4YMSYzIAQDOcDTIZ86c\nqZkzZ7a6PnDgQK1du9bJpmTM7/UoGG5sdb0xTGkdAOAcdnZLU57PrVA4qugZk/Mag5TWAQDOIcjT\nFNvdLXzGsrVYaZ115AAAJxDkaUq233qQ0joAwEEEeZr8zdu0hkItg5zlZwAAJxHkaYqVzoOtSus8\nIwcAOIcgT1OeL/F+60FG5AAABxHkafLHnpG3Kq03T3bzEeQAAPsR5GmKldZDRssgPxmKyO9zy+12\nZaNZAIAuhiBPU7IzyYOhCM/HAQCOIcjTFDuTPFFpPZ+yOgDAIQR5mpKV1oPhCBPdAACOIcjT5Pe1\n3hDGNE01hiLs6gYAcAxBnqa8BKX1UDgq02QNOQDAOQR5mmJ7rYdOm+zGyWcAAKcR5GmKz1o/7Rk5\nB6YAAJxGkKcp0V7rp44wJcgBAM4gyNOUl2Cy26mTz3hGDgBwBkGepvhe66cdmhIrrTMiBwA4hSBP\nU6K91jnCFADgNII8TW63Sz6vu0VpnSAHADiNIM9Ans9zRmk90nydZ+QAAGcQ5BnI87nPKK03PyPP\nY0QOAHAGQZ4Bv8/TctZ6rLTOoSkAAIcQ5Bnw+zwtDk3hGTkAwGkEeQbyfB6FwlFFTVPS6UHOM3IA\ngDMI8gz4m9eSh5v3W2eLVgCA0wjyDJy53zqldQCA0wjyDOSdsd96MByR1+OW10O3AgCcQeJkwH/G\nfuuNoQijcQCAoxydlWUYhubNm6cvv/xSkUhEs2bN0hVXXKFp06apoaFB3bp1kyTNnj1bw4YNc7Jp\naYnttx487Rk5QQ4AcJKjQf7GG2+ooKBAL730kj755BPNnTtXr776qiRpyZIlGjx4sJPNyVi8tN48\nIg+GIupZlJfNJgEAuhhHg3zy5MmaNGmSJKm4uFi1tbVOfrzlTi+tm6ZJaR0A4DhHg9zn88X/vGrV\nqnioS9LSpUtVU1OjAQMGqLy8XPn5+Unfp1evbvJ6rQ/MQKCoQ6/v3avpUUBegV89e3VXJGqqR/e8\nDr/P2aar//xWoR+tQT9ag360hh39aFuQV1RUqKKiosW1GTNmaNy4cVqzZo127typ5cuXS5Juv/12\nDRkyRP3799fChQu1Zs0a3XXXXUnfu6amwfL2BgJFqqo60aF7QsGwJOnI0Xrt3d9UXXBLHX6fs0k6\n/YjW6Edr0I/WoB+tkWk/JvslwLYgLysrU1lZWavrFRUV2rhxo55//vn4CP26666Lf//qq6/Wm2++\naVezLJV3WmmdNeQAgGxwdPnZnj17tG7dOi1btkx5eU2TwkzT1B133KHjx49LkjZv3qxBgwY52ay0\n+U+b7BZke1YAQBY4mjoVFRWqra3VPffcE7+2cuVKTZkyRXfccYcKCgrUp08fzZgxw8lmpS3RiJzt\nWQEATnI0yGfOnKmZM2e2uj5x4kRNnDjRyaZY4tTys+ips8gJcgCAg9jZLQP++IYwjMgBANlBkGfg\n9A1hmOwGAMgGgjwDLZ+RN5XWC5jsBgBwEEGeAf9pe63HDk6htA4AcBJBngE/pXUAQJYR5Blwu1zy\ne91NpfUg68gBAM4jyDPk93magjzc9Iyc0joAwEkEeYbyfG5K6wCArCHIM9Q0Io/Gt2gtIMgBAA4i\nyDPk93niI3K3yyWvhy4FADiH1MlQns+jkBHVyaChfL9HLpcr200CAHQhBHmGYpvCnGgIMdENAOA4\ngjxDsU1hTjSEmegGAHAcQZ6h2IjcFGvIAQDOI8gzFAtyiaVnAADnEeQZIsgBANlEkGco9oxcIsgB\nAM4jyDN0+og8j2fkAACHEeQZ8lNaBwBkEUGeoRaldR9BDgBwFkGeISa7AQCyiSDPUIsgz+MZOQDA\nWQR5hk5/Rp5HaR0A4DCCPEOU1gEA2USQZyiPdeQAgCwiyDPUcvkZz8gBAM4iyDNEaR0AkE0EeYZa\n7uxGkAMAnEWQZ8jHM3IAQBY5+lD36NGjmj17toLBoMLhsObOnavS0lLt2rVLixYtkiQNGTJEjz32\nmJPNyojb5ZLf61bYiLZ4Xg4AgBMcHZGvX79e3/jGN7R69WrNnDlTzz33nCRp8eLFKi8v17p161RX\nV6d33nnHyWZlzO/zyO/3yO1yZbspAIAuxtER+Z133hn/84EDB9SnTx+FQiHt27dPI0aMkCRdddVV\nqqys1Pjx451sWkYK8jzyRXhKAQBwnuPrpaqqqjR9+nTV19dr1apVqqmpUY8ePeLf7927t6qqqtp8\nj169usnrtb6MHQgUpXXf9G+VKhKNpn3/2YZ+sAb9aA360Rr0ozXs6EfbgryiokIVFRUtrs2YMUPj\nxo3Ta6+9pnfeeUdz587VkiVLWrzGNM2U711T02BpW6Wmzq2qOpHWvZeUdJektO8/m2TSjziFfrQG\n/WgN+tEamfZjsl8CbAvysrIylZWVtbi2ZcsWHTt2TOecc47Gjx+vWbNmqbi4WLW1tfHXHDp0SCUl\nJXY1CwCAs4qjD3Y3bNigX/ziF5Kkjz76SOeff758Pp8uvfRSbd26Nf6acePGOdksAABylqPPyO+/\n/37NmTNH//3f/61QKBRfclZeXq4FCxYoGo2qtLRUo0ePdrJZAADkLEeDvLi4WP/xH//R6vrAgQO1\ndu1aJ5sCAMBZgTVTAADkMIIcAIAcRpADAJDDCHIAAHIYQQ4AQA4jyAEAyGEEOQAAOcxltmdzcwAA\n0CkxIgcAIIcR5AAA5DCCHACAHEaQAwCQwwhyAAByGEEOAEAOI8gBAMhhjp5H3hk9/vjj2r59u1wu\nl8rLyzVixIhsNymnPPXUU/rggw9kGIbuvfdeDR8+XLNmzVIkElEgENAPf/hD+f3+bDez02tsbNSk\nSZN0//3368orr6QP07B+/XqtWLFCXq9X3/ve9zRkyBD6sYPq6+s1e/ZsHTt2TOFwWA888IACgYAW\nLVokSRoyZIgee+yx7Dayk/v44491//3364477tDUqVN14MCBhH8P169fr1WrVsntdmvKlCkqKytL\n/0PNLmzz5s3mPffcY5qmae7evducMmVKlluUWyorK83vfve7pmmaZnV1tTl+/Hhzzpw55ptvvmma\npmn+6Ec/MtesWZPNJuaMZ555xvzWt75lvvbaa/RhGqqrq83rr7/ePHHihHno0CFz/vz59GMaVq9e\nbT799NOmaZrmwYMHza9//evm1KlTze3bt5umaZozZ840N23alM0mdmr19fXm1KlTzfnz55urV682\nTdNM+Pewvr7evP76683jx4+bJ0+eNG+66SazpqYm7c/t0qX1yspKXXvttZKkAQMG6NixY6qrq8ty\nq3LH1772NT333HOSpB49eujkyZPavHmzrrnmGknSVVddpcrKymw2MSd8+umn2r17tyZMmCBJ9GEa\nKisrdeWVV6qwsFAlJSX6wQ9+QD+moVevXqqtrZUkHT9+XD179tS+ffvilUr6sW1+v18vvPCCSkpK\n4tcS/T3cvn27hg8frqKiIuXn52vUqFHatm1b2p/bpYP8yJEj6tWrV/zr4uJiVVVVZbFFucXj8ahb\nt26SpFdffVV///d/r5MnT8bLl71796Y/2+HJJ5/UnDlz4l/Thx23d+9eNTY2avr06brttttUWVlJ\nP6bhpptu0v79+3Xddddp6tSpmjVrlnr06BH/Pv3YNq/Xq/z8/BbXEv09PHLkiIqLi+OvyTR7uvwz\n8tOZbDuflt/+9rd69dVX9eKLL+r666+PX6c/U3v99df1la98RRdeeGHC79OH7VdbW6tly5Zp//79\nuv3221v0Hf3YPm+88YYuuOACrVy5Urt27dIDDzygoqKi+Pfpx8wk679M+7VLB3lJSYmOHDkS//rw\n4cMKBAJZbFHu+Z//+R8tX75cK1asUFFRkbp166bGxkbl5+fr0KFDLUpMaG3Tpk3as2ePNm3apIMH\nD8rv99OHaejdu7dGjhwpr9er/v37q3v37vJ4PPRjB23btk1jx46VJF122WUKBoMyDCP+ffqx4xL9\n95woe77yla+k/RldurQ+ZswYvfXWW5KknTt3qqSkRIWFhVluVe44ceKEnnrqKf30pz9Vz549JUmj\nR4+O9+mGDRs0bty4bDax03v22Wf12muv6ZVXXlFZWZnuv/9++jANY8eO1XvvvadoNKqamho1NDTQ\nj2m46KKLtH37dknSvn371L17dw0YMEBbt26VRD+mI9Hfw9LSUu3YsUPHjx9XfX29tm3bpiuuuCLt\nz+jyx5g+/fTT2rp1q1wulxYuXKjLLrss203KGS+//LJ+/OMf65JLLolfe+KJJzR//nwFg0FdcMEF\nWrJkiXw+XxZbmTt+/OMfq2/fvho7dqxmz55NH3bQunXr9Oqrr0qS7rvvPg0fPpx+7KD6+nqVl5fr\n6NGjMgxDDz30kAKBgBYsWKBoNKrS0lLNnTs3283stD788EM9+eST2rdvn7xer/r06aOnn35ac+bM\nafX38De/+Y1Wrlwpl8ulqVOnavLkyWl/bpcPcgAAclmXLq0DAJDrCHIAAHIYQQ4AQA4jyAEAyGEE\nOQAAOYwgB6ADBw5o9erVamxszHZTAHQQQQ50cdFoVFu2bNEtt9zSap9oAJ0f68iBLmrv3r264YYb\nNHLkyBbXx48fr0GDBqm0tDS+Yx+AzqtL77UOdHXFxcVavXp1q+t33nmnFi1aRJADOYAgB9DC2rVr\ntXXrVj388MNasmSJPv/8c61YsUJ+v1+RSERPPfWU+vXrp2nTpunyyy/XJ598oqqqKt17772aNGmS\njh07poULF6q6ulp1dXW68847dfPNN2f7xwLOWjwjB9DCbbfdpkAgoKeffloDBw7U8ePH9W//9m9a\nvXq1xo8frzVr1sRfaxiGXnzxRS1btkyPP/64otGonn32WY0bN07/+Z//qZ///OdaunSpqqurs/gT\nAWc3RuRAF1ZdXa1p06a1uPbII4+0+Prcc8/V7NmzZZqmqqqqWjxTjx15edFFF8nlcuno0aPavHmz\nduzYoddff12S5PV6tXfvXhUXF9v80wBdE0EOdGHJnpHHhMNhff/739cvfvELXXzxxfr5z3+uDz/8\nMP79aDQa/7NpmnK5XPL7/Vq4cKGGDx9ua9sBNKG0DqAVl8slwzBUX18vt9utvn37KhgM6u2331Yo\nFIq/7r333pMkff7553K73SouLtZXv/pV/frXv5YkNTY2atGiRTIMIys/B9AVsPwM6KKSLT/r16+f\n/H6/3n33XT355JN644039L//+7+64IIL9O1vf1uzZs3So48+qrVr12rgwIE6ePCg9u7dqwcffFBf\n//rXVVNTo/nz56u6ulqhUEj/+I//qClTpmTppwTOfgQ5gLRMmzZN9913n0aPHp3tpgBdGqV1AABy\nGCNyAAByGCNyAAByGEEOAEAOI8gBAMhhBDkAADmMIAcAIIf9/yicyhgwQEXsAAAAAElFTkSuQmCC\n",
            "text/plain": [
              "<Figure size 576x396 with 1 Axes>"
            ]
          },
          "metadata": {
            "tags": []
          }
        }
      ]
    },
    {
      "metadata": {
        "id": "dfLEIlMB5rke",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# démo "
      ]
    },
    {
      "metadata": {
        "id": "4EFB-A2k5qwa",
        "colab_type": "code",
        "outputId": "e1ede741-f066-4e1f-d976-c343e797446e",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 583
        }
      },
      "cell_type": "code",
      "source": [
        "    actions = []\n",
        "    s = game.reset()\n",
        "    game.print()\n",
        "    states = [s]\n",
        "    cumul_reward = 0\n",
        "    d = False\n",
        "    while True:\n",
        "        # on choisit une action aléatoire avec une certaine probabilité, qui décroit\n",
        "        # TODO : simplifier ça (pas clair)\n",
        "        Q2 = Q[s,:] + np.random.randn(1, actions_n)*(1. / (i +1))\n",
        "        a = np.argmax(Q2)\n",
        "        s1, reward, d, _ = game.move(a)\n",
        "        Q[s, a] = Q[s, a] + lr*(reward + y * np.max(Q[s1,:]) - Q[s, a]) # Fonction de mise à jour de la Q-table\n",
        "        cumul_reward += reward\n",
        "        s = s1\n",
        "        actions.append(a)\n",
        "        states.append(s)\n",
        "        game.print()\n",
        "        if d == True:\n",
        "            break"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "..@.\n",
            "..¤.\n",
            "....\n",
            ".ox.\n",
            "\n",
            "..@.\n",
            "..¤.\n",
            "..x.\n",
            ".o..\n",
            "\n",
            "..@.\n",
            "..¤.\n",
            "...x\n",
            ".o..\n",
            "\n",
            "..@.\n",
            "..¤x\n",
            "....\n",
            ".o..\n",
            "\n",
            "..@x\n",
            "..¤.\n",
            "....\n",
            ".o..\n",
            "\n",
            "..x.\n",
            "..¤.\n",
            "....\n",
            ".o..\n",
            "\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}