DDA4230: Assignment 2 119010319.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Introduction to Open AI Gym \n",
    "[OpenAI Gym](https://gym.openai.com/) aims to provide an easy-to-setup general-intelligence benchmark with a wide variety of different environments. The goal is to standardize how environments are defined in AI research publications so that published research becomes more easily reproducible. The project claims to provide the user with a simple interface. \n",
    "\n",
    "### Looking at Gym Environments\n",
    "\n",
    "The centerpiece of Gym is the environment, which defines the \"game\" in which your reinforcement algorithm will compete.  An environment does not need to be a game; however, it describes the following game-like features:\n",
    "* **action space**: What actions can we take on the environment, at each step/episode, to alter the environment.\n",
    "* **observation space**: What is the current state of the portion of the environment that we can observe. Usually, we can see the entire environment.\n",
    "\n",
    "Before we begin to look at Gym, it is essential to understand some of the terminology used by this library.\n",
    "\n",
    "* **Agent** - The machine learning program or model that controls the actions.\n",
    "Step - One round of issuing actions that affect the observation space.\n",
    "* **Episode** - A collection of steps that terminates when the agent fails to meet the environment's objective, or the episode reaches the maximum number of allowed steps.\n",
    "* **Render** - Gym can render one frame for display after each episode.\n",
    "* **Reward** - A positive reinforcement that can occur at the end of each episode, after the agent acts.\n",
    "* **Nondeterministic** - For some environments, randomness is a factor in deciding what effects actions have on reward and changes to the observation space.\n",
    "\n",
    "It is important to note that many of the gym environments specify that they are not nondeterministic even though they make use of random numbers to process actions. It is generally agreed upon (based on the gym GitHub issue tracker) that nondeterministic property means that a deterministic environment will still behave randomly even when given consistent seed value. The seed method of an environment can be used by the program to seed the random number generator for the environment.\n",
    "\n",
    "Altough Google Colab does not allow us to render each environment, you can take a look at the environment at [OpenAI Gym Environments](https://gym.openai.com/envs/#classic_control)\n",
    "\n",
    "The Gym library allows us to query some of these attributes from environments. We will begin by looking at the FrozenLake-v0 environment. The RL agent will control the movement of a character in a grid world. Some tiles of the grid are walkable, and others lead to the agent falling into the water. Additionally, the movement direction of the agent is uncertain and only partially depends on the chosen direction. The agent is rewarded for finding a walkable path to a goal tile."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Action Space: Discrete(4)\n",
      "Observation Space: Discrete(16)\n",
      "Max Episode Steps: 100\n",
      "Nondeterministic: False\n",
      "Reward Range: (0, 1)\n",
      "Reward Threshold: 0.7\n"
     ]
    }
   ],
   "source": [
    "import gym\n",
    "import time\n",
    "import numpy\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "def query_environment(name):\n",
    "  env = gym.make(name)\n",
    "  spec = gym.spec(name)\n",
    "  print(f\"Action Space: {env.action_space}\")\n",
    "  print(f\"Observation Space: {env.observation_space}\")\n",
    "  print(f\"Max Episode Steps: {spec.max_episode_steps}\")\n",
    "  print(f\"Nondeterministic: {spec.nondeterministic}\")\n",
    "  print(f\"Reward Range: {env.reward_range}\")\n",
    "  print(f\"Reward Threshold: {spec.reward_threshold}\")\n",
    "\n",
    "query_environment(\"FrozenLake-v1\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The agent moves through a $4 \\times 4$ gridworld, with states numbered as follows:\n",
    "```\n",
    "[[ 0  1  2  3]\n",
    " [ 4  5  6  7]\n",
    " [ 8  9 10 11]\n",
    " [12 13 14 15]]\n",
    "```\n",
    "Each state can be categorized into the following states\n",
    "```\n",
    "SFFF       (S: starting point, safe)\n",
    "FHFH       (F: frozen surface, safe)\n",
    "FFFH       (H: hole, fall to your doom)\n",
    "HFFG       (G: goal, where the frisbee is located)\n",
    "```\n",
    "The agent has 4 potential actions:\n",
    "```\n",
    "LEFT = 0\n",
    "DOWN = 1\n",
    "RIGHT = 2\n",
    "UP = 3\n",
    "```\n",
    "\n",
    "Thus, $\\mathcal{S}^+ = \\{0, 1, \\ldots, 15\\}$, and $\\mathcal{A} = \\{0, 1, 2, 3\\}$.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Value Iteration\n",
    "\n",
    "Now we are going to instance a Fronzen lake environment, and try to implement Value itertaions. \n",
    "\n",
    "**You need to implement the code at where is labeled ``TODO:''**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def valueIteration(env, gamma=1.0, iteration=10000, eps=1e-20):\n",
    "    value = numpy.zeros(env.nS)\n",
    "\n",
    "    # Start Iteration\n",
    "    for i in range(iteration):\n",
    "        previous_value = numpy.copy(value)\n",
    "        for state in range(env.nS):\n",
    "            Q = []\n",
    "            for action in range(env.nA):\n",
    "                outcomes  = []\n",
    "\n",
    "                # TODO: Loop through all outcomes of performing that action and calculate the Q values\n",
    "                for probability, nextstate, reward, done in env.P[state][action]:\n",
    "                    outcomes.append(probability * (reward + gamma * (value[nextstate])))\n",
    "\n",
    "                Q.append(sum(outcomes))\n",
    "\n",
    "            # TODO: Calculate the value function\n",
    "            value[state] = max(Q)\n",
    "\n",
    "        if(numpy.sum(numpy.fabs(previous_value - value)) <= eps):\n",
    "            return value\n",
    "\n",
    "    print(\"Iterated over %d Iterations and couldn't converge\"%(iteration))\n",
    "    return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculatePolicy(env, v, gamma=1.0):\n",
    "    policy = numpy.zeros(env.nS)\n",
    "    for state in range(env.nS):\n",
    "        Q = [] \n",
    "        for action in range(env.nA):\n",
    "\n",
    "            # Reset all outcomes of this particular action\n",
    "                outcomes  = []\n",
    "\n",
    "                # TODO: Loop through all outcomes of performing that action and calculate the Q values\n",
    "                for probability, nextstate, reward, done in env.P[state][action]:\n",
    "                    outcomes.append(probability * (reward + gamma * (v[nextstate])))\n",
    "\n",
    "                Q.append(sum(outcomes))\n",
    "\n",
    "        # TODO: extract policy \n",
    "        policy[state] = Q.index(max(Q))\n",
    "\n",
    "    # Step 9: Return policy\n",
    "    return policy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def evaluatePolicyOnce(env, policy, gamma=1.0, eps=1e-20):\n",
    "    totalreward = 0\n",
    "    step = 0\n",
    "    start = env.reset()\n",
    "\n",
    "    while True:\n",
    "        action = policy[start]\n",
    "\n",
    "        start, reward, done, _ = env.step(action)\n",
    "\n",
    "        # TODO: Calculate the total reward with the given discount factor\n",
    "        totalreward += reward * (gamma ** (step-1))\n",
    "        step += 1\n",
    "\n",
    "        if done:\n",
    "            break\n",
    "    return totalreward\n",
    "\n",
    "def evaluatePolicy(env, policy, gamma=1.0, iteration=100, render=False, eps=1e-20):\n",
    "    scores = [\n",
    "    evaluatePolicyOnce(env, policy, gamma, eps)\n",
    "        for _ in range(iteration)\n",
    "    ]\n",
    "\n",
    "    return numpy.mean(scores)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ValueIterator(env, gamma=1.0, improvementIterations=1000, evaluationIterations=100, eps=1e-20):\n",
    "    optimalValue = valueIteration(env, gamma, improvementIterations, eps)\n",
    "    policy = calculatePolicy(env, optimalValue, gamma)\n",
    "    score = evaluatePolicy(env, policy, gamma, evaluationIterations, eps)\n",
    "    print('Score obtained', score)\n",
    "    print('Best score = %0.2f.'%(numpy.max(score)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Score obtained 0.83\n",
      "Best score = 0.83.\n"
     ]
    }
   ],
   "source": [
    "gamma = 1.0\n",
    "game = 'FrozenLake-v1'\n",
    "improvementIterations = 10000\n",
    "evaluationIterations = 100\n",
    "eps = 1e-20\n",
    "numpy.random.seed(0)\n",
    "env = gym.make(game)\n",
    "env.seed(0)\n",
    "\n",
    "env = gym.make(game).env\n",
    "ValueIterator(env=env, gamma=gamma, evaluationIterations=evaluationIterations, improvementIterations=improvementIterations, eps=eps)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We also provide the following code to visualize your calculated value function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAVQAAAFkCAYAAAB/6MMYAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuNCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8QVMy6AAAACXBIWXMAAAsTAAALEwEAmpwYAAAyfElEQVR4nO3ceXxU1f3G8c/JJJNlEtZAIOwKxYUiyI4iChUKKq4VRXFptVoXUNS6/FwQtS5oUSsUi1UEF1BBq2yKVqmIqFBQFOsCQohJSAIJ2beZ8/tjwsCQSWQ5YX3evuZlc8659577ncmTc+/caqy1iIjIvos60BMQETlcKFBFRBxRoIqIOKJAFRFxRIEqIuKIAlVExBEFqhxQxpjxxpiXDvQ86oMxZqox5p4DPQ/ZfxSohyhjzMnGmGXGmG3GmK3GmE+MMb2q+64wxizdg321N8ZYY0z0XsyjnzGm2BiTFKFvlTHmhj3dpwvGmFONMQFjTNFOr3fq8Xg1am6tvdZa+0B9HVMOPnv8CyQHnjGmATAP+BPwGuAFBgDl+3su1tpPjTHpwPnA9J3m2AU4Dnh1f89pJxnW2tYH8PhyhNEK9dD0KwBr7avWWr+1ttRa+5619itjzLHAVKBf9aosH8AYc0b1irHAGLPJGDN+p/39p/rf+dXb9Kve5vfGmG+NMXnGmHeNMe1qmc+LwGW7tF0GzLfWbjHGPFV9zAJjzEpjzIBIO6leVabv0rbBGPOb6v8dZYy5wxizzhizxRjzmjGmye4WbTePMb56vzOMMYXGmG+MMT13GtvGGDPXGJNTPYdn6qj5dGPMgztte7Ux5sfqK4q3jTGpO/VZY8y1xpgfqus92Rhj9uTc5MBToB6avgf8xpgXjTHDjDGNt3dYa78FrgU+tdYmWmsbVXcVEwy5RsAZwJ+MMedU951S/e9G1dt8Wt13F3Ae0Az4mNpXmzOBAcaYthAMPmAUMKO6/wugG9AEeAV43RgTtxfnPQY4BxgIpAJ5wOS92M8vGQHMIlirt4FnAIwxHoJXBhuB9kArYFYdNQ8xxgwCHgYuBFpW72PWLsPOBHoBJ1SPG+r2tKS+KVAPQdbaAuBkwALTgJzqFU9KHdt8ZK1dY60NWGu/IhiOA+s4zDXAw9bab621VcBfgG6RVqnW2k3AEuDS6qbBQBwwv7r/JWvtFmttlbX2CSAW6LyHp719Tv9nrU231pYD44EL6rj3m2qMyd/pdeFuHmeptXaBtdZP8I/FCdXtvQkG+W3W2mJrbZm1dnfvVV8CPG+t/W/13O8kuKJtv9OYR6y1+dbaNOBDgn+E5BCiQD1EVQfdFdX3CLsQ/EV/srbxxpg+xpgPqy9VtxFcUSXXcYh2wFPbwwjYChiglTHmrp2+6JlaPX7ny/7RwCvW2srqY99SfetgW/W+Gv7Cseua05s7zelbwA/U9ockw1rbaKfXa7t5nKyd/ncJEFcd2m2AjdV/YPZUKsFVKQDW2iJgC8FVbm3HTdyL48gBpEA9DFhr/0fwC6Eu25siDHuF4OVrG2ttQ4L3/Ewd4zcB1+wSSPHW2mXW2r9UX9omWmuvrR4/l2DYnkbwNsEMgOr7pbcTvIRtXH05vG2nY++sGEjY/kP1JXazXeY0bJc5xVlrf66jPHt6jLpsAtrWsiL+pf9sWwbBPwjbj+sDmgJ7Mnc5yClQD0HGmGOqV32tq39uA1wMLK8eshlobYzx7rRZErDVWltmjOlN8B7ndjlAADhqp7apwJ3GmOOrj9HQGPO72uZkrS0G3gBeILiKW7HTcauqjxFtjLkXaFDLbr4nuBo8wxgTA9xN8PbAznN6aPttB2NMM2PM2bXNaS+PUZfPgUzgEWOMzxgTZ4w5qbovUs139gpwpTGmmzEmluAtlM+stRv2cP5yEFOgHpoKgT7AZ8aYYoJB+jVwS3X/v4FvgCxjTG5123XABGNMIXAvwcetALDWlgAPAZ9UX073tda+CTwKzDLGFFTvf9gvzOtFgquwGTu1vQssJBhkG4Eygiu9Gqy126rn+RzBlVsxsPM38k8RXGW/V30ey6vrsNt24xh1besHzgI6AmnV242s7o5U8523/QC4B5hDMJSPBi7ak7nLwc/oPzAtIuKGVqgiIo4oUEVEHFGgiog4okAVEXFEgSoi4kid/7WpJp5k2zq6/X6aiojIwS+9agNb/bkR/8M1dQZq6+j2vJ26oq4hIiJHlBEZPWvt0yW/iIgjClQREUcUqCIijihQRUQcUaCKiDiiQBURcUSBKiLiiAJVRMQRBaqIiCMKVBERRxSoIiKOKFBFRBxRoIqIOKJAFRFxRIEqIuKIAlVExBEFqoiIIwpUERFHFKgiIo4oUEVEHFGgiog4okAVEXFEgSoi4ogCVUTEEQWqiIgjClQREUcUqCIijihQRUQcUaCKiDiiQBURcUSBKiLiiAJVRMQRBaqIiCP1FqgzC6YwIL0DnTfEcVZGDz4v+7jO8UtK3+W8zH502ZjEiWnJXL35bNZXfh/qX1Q8l9FZQ+iR1owuG5M4J6MPi0veDtvH/OLXGZHRk64bG3HcRh/Df+7GnKIXw8Y8mTeeDhtM2KtXWouwMU/k3cPg9GM4bqOPE9Iac0nWYFaWLdvHiuwd1XHfqYZuqI6/rF4CdV7xbCZsHct1De9ifuoqToztz5Wbh/FzVVrE8Zsqf+KPm8+mV+wA5qWu4qWU9ymzpfx+8/DQmM/KltA/bhD/TJnPvNRVnJYwnGuzzw17UxtHNeWGhnfzZsvlLEz9it8lXcntuX/gw5IFYcc7Krozn7fODL0WtVoT3h/TmQlNJ7ModQ2vt1hK6+gOXLH5t+T4Nzus0i9THfedauiG6rh7jLW21s6usT3t26kr9nin52T04RhvVx5JnhZqOy29E8N8F/Dnxg/XGL+g+A1uzBnJ9+0q8BgPAJ+WfsiozYNY2SaHJp7kiMc5O6M3veIGcHeTJ2qdy5kZJ3JK/NDQcZ/MG8/Ckjd4t9XXu30+hYECuqY1ZHrKIgbGD93t7faV6rjvVEM3VMcdRmT05KvyFSZSn/MVaoWt4OuKlQyIHxLWfnL8kFqX2F29PYkmhtlFz+G3fooChcwpepGu3l61Fh6g2BbSMKpxxD5rLZ+UfsD6yu/oHXtKWF9a1Xr6bmrFgPQO3Jh9EWmV6+s8n1cL/0GSacBx3m61jnNNddx3qqEbquPui3a6NyDPn4sfP8melLD2Zp4UPvG/H3Gb1jHtmdliMddn/457t1xPgADHe7vzQsrCWo8zo2AyWVXpnJs4Oqy9ILCNfptaUWHLicLDhKaTOTVhWKi/W2wfJiZP5+iYY9jiz+aZ/Ac5P7M/77X6hsaepqFxH5TMY0zORZTaEpp7WjKjxWKa7XJO9Ul13HeqoRuq4+6rty+lDOErYout0bZdTlUWt+f+gfMSL+NfLb/g1RYf4TNJ3JB9IQEbqDF+YfEcHs67jUnNXqZ1dLuwvkSTxPzU1fyr5Rfc2vghHto6jk9KPwj1n5owjDN9F3Kstysnx/+Gf6bMwxKocaO7X9xpzE9dzZwWyxgY/1tuyL6Q7KrMvS3HXlMd951q6Ibq+Mucr1Abe5Lx4CHHnxXWnuvPrvEXbrsZhZNJiPJxZ5PHQm2Tmr1E//Q2rCxfRq+4k0PtC4vnMC53NE8kz+D0hBE19hVlomgf0xGA42K78WPlt0zZ9hdOih8c8di+qEQ6eY9nQ9UPYe0JUT7aR3WkfUxHusf15bT0Tswqeo4xje7ZvULsI9Vx36mGbqiOu8/5CtVrvHTx9mBp6eKw9qWli+kR1z/iNqW2BA+esLbtPwfY8ddsXvFr3Jx7KROTpzPcd8FuzccSoMKW19pfHihjXeX/aO5pWed+Ar+wH9dUx32nGrqhOu4+5ytUgKsajmNczmhOiO1Nz9iTeLlwKtn+DEYlXQvAY3l38mX557zcIrhsHxR/Bs8XTOKp/PsZ4RtFcaCQiXl3keppw6+9PQB4p2gW43JHc1eTx+kTewo5VcG/ljHGSyNPEwCeyX+IbrF9aBt9FBW2nA9LF/Bm0UzGN/lbaG4Pbb2VwQln0crTltxANs/kP0BpoJjzEi8Hgt/+PbvtMQYnnEVzT0u2+nOYWRi8t3OG78L6KFetVEfV8GCoIaiOu6teAvVM30jy/Ft4Jv9BcvyZ/MrbhedTFoTujWRXZbKxcl1ofP/4QTyV/ArPFjzGP7ZNJM7E0y22L9NTFpEQ5QPg5cKpVFHFhK03MWHrTaFt+8QOZFbLjwAosUXcs+VPZPrTiTPxHB1zDE8kz2BE4sWh8VlV6YzNuZg8fy5NPM3oHtuXuS2Xh+YWTTQ/VH7D69nPk+/fQiNPU7p6ezGr5X841tu1PspVK9Vx36mGbqiOu6denkMVETlc7dfnUEVEjlQKVBERRxSoIiKOKFBFRBxRoIqIOKJAFRFxRIEqIuKIAlVExBEFqoiIIwpUERFHFKgiIo4oUEVEHFGgiog4okAVEXFEgSoi4ogCVUTEEQWqiIgjClQREUcUqCIijihQRUQcUaCKiDiiQBURcUSBKiLiiAJVRMQRBaqIiCMKVBERRxSoIiKOKFBFRBxRoIqIOKJAFRFxRIEqIuKIAlVExBEFqoiIIwpUERFHFKgiIo5EH+gJHAk6/HSgZ3Dom3TzgZ7B4eHmSQd6BoeBnrV3aYUqIuKIAlVExBEFqoiIIwpUERFHFKgiIo4oUEVEHFGgiog4okAVEXFEgSoi4ogCVUTEEQWqiIgjClQREUcUqCIijihQRUQcUaCKiDiiQBURcUSBKiLiiAJVRMQRBaqIiCMKVBERRxSoIiKOKFBFRBxRoIqIOKJAFRFxRIEqIuKIAlVExBEFqoiIIwpUERFHFKgiIo4oUEVEHFGgiog4okAVEXFEgSoi4ogCVUTEEQWqiIgj9RaoMwumMCC9A503xHFWRg8+L/u4zvFLSt/lvMx+dNmYxIlpyVy9+WzWV34f6l9UPJfRWUPokdaMLhuTOCejD4tL3g7bx/zi1xmR0ZOuGxtx3EYfw3/uxpyiF8PGPJk3ng4bTNirV1qLsDFP5N3D4PRjOG6jjxPSGnNJ1mBWli3bx4ocQFOmQIcOEBcHPXrAx3W/F6xZAwMHQnw8tGoFEyaAtftnrvVg6ZdTeOD5Dtz2tzieeKUH636u/fy3btvAzU+aGq9vNywKjfnqx7n8fe4Q7n62GXdMTmLSq334el34Z9Hvr+Td5RN48IWjue1vcUx86YSwfexq8ed/4eYnDXM+vCGs/asf5zJ17lDufrYZNz9p+HHTR3tVg4PGYf5ZrJdAnVc8mwlbx3Jdw7uYn7qKE2P7c+XmYfxclRZx/KbKn/jj5rPpFTuAeamreCnlfcpsKb/fPDw05rOyJfSPG8Q/U+YzL3UVpyUM59rsc8OCunFUU25oeDdvtlzOwtSv+F3Sldye+wc+LFkQdryjojvzeevM0GtRqzXh/TGdmdB0MotS1/B6i6W0ju7AFZt/S45/s8Mq7SezZ8PYsXDXXbBqFfTvD8OGQVrk94KCAjj9dEhJgS++gKefhokT4a9/3b/zdmTVd7N5c8lYftPrLm69ZBXtW/bnH28NI6+glvOvds05i7j/6szQq1ObQaG+H9OX0KnNIK4+ez63XLKKYzsM5/l554YF9YJld7NszVTOPfVpbr9sLf1/fS0vvHMu6dmrahxrQ+Zyln89jdTkrjX6yiuLaZ/an7NPOTTrH+YI+CwaW0fad43tad9OXbHHOz0now/HeLvySPK0UNtp6Z0Y5ruAPzd+uMb4BcVvcGPOSL5vV4HHeAD4tPRDRm0exMo2OTTxJEc8ztkZvekVN4C7mzxR61zOzDiRU+KHho77ZN54Fpa8wbutvt7t8ykMFNA1rSHTUxYxMH7obm+3XYef9ngTd/r0ga5dYdqO94JOneCCC+Dhmu8Ff/873H47bN4cXBUAPPhgsD09HYzZP/PexaSb93K7V/uQ2qwrI3+z4/wfmt6JEzpewJkn1zz/rds28MALHbj54i9om9JzD47Tm6NaDeDsU4KfxfumpTKo5+0M7D42NOaFeecTEx3Ppb99KdRWWr6NJ145kZG/mca7yyfQMrkL55/2TI39F5Xmcs+zzbj+/A/p2ObU3Z7Xrm6etNeb7rvD5LNIz57YFSsiHtz5CrXCVvB1xUoGxA8Jaz85fkitl81dvT2JJobZRc/ht36KAoXMKXqRrt5etYYpQLEtpGFU44h91lo+Kf2A9ZXf0Tv2lLC+tKr19N3UigHpHbgx+yLSKtfXeT6vFv6DJNOA47zdah13UKqogJUrYUj4e8GQIbCsllsYn34KAwbs+AADDB0KGRmwYUO9TbU+VPkrSM9eSee24effue0QNmTWfQvnhXnncc+zzXlq9kms/uGNXzxWWUUh8bE7PotV/nJiPHFhY2Ki41n/89Kwttfe/yMndLwgbAV8WDpCPovOAzXPn4sfP8melLD2Zp4UcvxZEbdpHdOemS0WMynvPjpvjKVrWkO+q1zDP1Pm1XqcGQWTyapK59zE0WHtBYFtHL8xkV9t9PL7zWdwX5OnOTVhWKi/W2wfJiZP54WUhTzcdBo5/izOz+xPnn9L2H4+KJnH8RsTOWZjHM8XTGJGi8U02+WcDnq5ueD3By+ZdpaSAlmR3wuysiKP3953CCkuzSVg/SQlhJ9PUkIKBSWRz8XrTWTEgMe5fPhrXH3OAn7VdjAzFoxkxbcvRRwPsPTLyWwrSqfnsTs+i8e0G8qSVU+SvfU7AjbAdxsX89WPcykoyQyN+XTNNHK3/ciw/g/s45keAo6Qz2J0fe3YEL4ittgabdvlVGVxe+4fOC/xMkb4LqbIFjIp715uyL6QV1r8mygTnvsLi+fwcN5tPN1sFq2j24X1JZok5qeupiRQxCdlH/DQ1nG0jm7PSfGDAcLCFaB7bF8Gph/FnKIXuarhuFB7v7jTmJ+6mjx/LrOKpnFD9oXMbfkpzaNb7nVNDphdL42srftyKdL4SO2HCrP7n8XE+GRO63FL6Oe2KT0pLs3l3ysfo+exl9YY/+UPc3j749u4bNgsmjTY8Vk8d+BTzH7/ah6ZeRwGQ9NGR9P7uCv5fO0LAGRv/Y75y+7ixt99TLTH6+IsDw2H+WfReaA29iTjwVNjNZrrz66xat1uRuFkEqJ83NnksVDbpGYv0T+9DSvLl9Er7uRQ+8LiOYzLHc0TyTM4PWFEjX1FmSjax3QE4LjYbvxY+S1Ttv0lFKi78kUl0sl7PBuqfghrT4jy0T6qI+1jOtI9ri+npXdiVtFzjGl0z+4V4mCQnAweT82/5tnZNf/yb9eiReTxUPs2BylffDJRxkNhcfj5FJVk11i11qVtiz58/s0LNdq//GEOL787mlFDZ9Dl6PDPYmJCM/4w4i0qq8ooLttCQ18q85beQZMGHQDYkPkpxaW5PDazS2ibgPWz/uf/sOyrqTx6fTHR0bF7croHtyPks+j8kt9rvHTx9mBp6eKw9qWli+kR1z/iNqW2BA+esLbtPwcIhNrmFb/GzbmXMjF5OsN9F+zWfCwBKmx5rf3lgTLWVf6P5p66V56BX9jPQcnrDT6asjj8vWDx4uA3rJH06xd8lKWsLHx8aiq0b19vU60P0R4vrZv34Lu08PP/Pm0x7VvWcv4R/JyzmiRf+Odj1fev8fKiS7l4yHS6dar9sxgTHUejxFYEAlV89eMcfn302QD8+uhz+POla7j1ktWhV5uUnnTvfBG3XrIaz+G2aj1CPov1csl/VcNxjMsZzQmxvekZexIvF04l25/BqKRrAXgs706+LP+cl1t8AMCg+DN4vmAST+XfzwjfKIoDhUzMu4tUTxt+7e0BwDtFsxiXO5q7mjxOn9hTyKkK/uWKMV4aeZoA8Ez+Q3SL7UPb6KOosOV8WLqAN4tmMr7J30Jze2jrrQxOOItWnrbkBrJ5Jv8BSgPFnJd4ORD8Rv/ZbY8xOOEsmntastWfw8zC4P3aM3wX1ke56te4cTB6NPTuDSedBFOnBm/qXxt8L7jzTvj8c/gg+F4wahTcfz9ccQXcfTd8/z088gjcd99Be5lVl1NPHMfL746mXYvedEg9iU++msq24gz6dw2e/7yld5K2+XOuOz94/p+vfRFPVAytm3fHEMU3P73DJ19O5syTHw3t87/fzeLld0czYsDjHN3qFAqqV8AejxdfXPCzuDHzM7YV/0xqs25sK/qZd5ePJ2ADDOrxZwDi4xoRH9cobK7eaB8JcU1ombxj1VpctpX8gjRKy/MByN32I/GxjUjytaCBL/z56YPeEfBZrJdAPdM3kjz/Fp7Jf5Acfya/8nbh+ZQFofud2VWZbKxcFxrfP34QTyW/wrMFj/GPbROJM/F0i+3L9JRFJET5AHi5cCpVVDFh601M2HpTaNs+sQOZ1fIjAEpsEfds+ROZ/nTiTDxHxxzDE8kzGJF4cWh8VlU6Y3MuJs+fSxNPM7rH9mVuy+WhuUUTzQ+V3/B69vPk+7fQyNOUrt5ezGr5H4711nxO8KA3ciRs2RJ83CQzE7p0gQULoF31/b7MTFi3472gYcPgKuD666FnT2jcGG65JfjLcAjq3nkkxWVbeO+zBykoyaRl0y788ewFofudBcWZ5OavC9tm8ecPklewERPloVmjX3HR6c+H3T9d9tVUAoEq3lpyE28tuSnUfnSrgdzwu48AqPSXsWDZ3WzZtp7YmESO7TCcS4bOrBGiv+SbdW/z6uIrQz/Pfv9qAIb2uY/f9hu/R/s64I6Az2K9PIcq4Q7oc6iHib19DlXCHdDnUA8X+/M5VBGRI5UCVUTEEQWqiIgjClQREUcUqCIijihQRUQcUaCKiDiiQBURcUSBKiLiiAJVRMQRBaqIiCMKVBERRxSoIiKOKFBFRBxRoIqIOKJAFRFxRIEqIuKIAlVExBEFqoiIIwpUERFHFKgiIo4oUEVEHFGgiog4okAVEXFEgSoi4ogCVUTEEQWqiIgjClQREUcUqCIijihQRUQcUaCKiDiiQBURcUSBKiLiiAJVRMSR6AM9gSPBTx0O9AwOffmNDvQMRH6ZVqgiIo4oUEVEHFGgiog4okAVEXFEgSoi4ogCVUTEEQWqiIgjClQREUcUqCIijihQRUQcUaCKiDiiQBURcUSBKiLiiAJVRMQRBaqIiCMKVBERRxSoIiKOKFBFRBxRoIqIOKJAFRFxRIEqIuKIAlVExBEFqoiIIwpUERFHFKgiIo4oUEVEHFGgiog4okAVEXFEgSoi4ogCVUTEEQWqiIgjClQREUcUqCIijihQRUQcUaCKiDhSb4E6s2AKA9I70HlDHGdl9ODzso/rHL+k9F3Oy+xHl41JnJiWzNWbz2Z95feh/kXFcxmdNYQeac3osjGJczL6sLjk7bB9zC9+nREZPem6sRHHbfQx/OduzCl6MWzMk3nj6bDBhL16pbUIG/NE3j0MTj+G4zb6OCGtMZdkDWZl2bJ9rMjeUR333Wu5UzhjbQf6fBnHqO968N+i2ms4NXM83VebiK+tldmhcZWBCqZk3ssZazvQ+8tYhn3Tlldyno64z4V5r9J9tWHM+jPD2od/0z7icW5cf0ZozAf5c7lu3VBOW9OM7qsNKwo/2qdaHHBTpkCHDhAXBz16wMd1f55ZswYGDoT4eGjVCiZMAGv3z1z3QnR97HRe8WwmbB3LhKZT6BV7MjMLp3Dl5mG812otraLb1hi/qfIn/rj5bK5oMIa/Js+kJFDEw3l/5vebh/NR6x8B+KxsCf3jBnFL4wdpFNWEfxW/zLXZ5/Jqi4/oHTcAgMZRTbmh4d0cHXMM0SaGf5fO4/bcP9AkqhmnJQwPHe+o6M7MavFR6Oco4wmbz1ExnZnQdDJtojtQZkv5Z8Ekrtj8W/7d+geaeVLqoWKRqY777t282UxMH8udbabQzXcyr+VO4Yb1w5hzzFpaemvW8LLmt3JB8rVhbXdsuAhjDE1imu9o23gxmys3cU+bf9DW24ktVZspD5TW2F96+XqezLiN7r4BNfpe6vwFAesP/Zxbmcmo73tweqMLQ22lgWJO8PVneONLuSftsr2qwUFj9mwYOzYYqiefHPz3sGGwdi20rfleUFAAp58Op5wCX3wB330HV1wBPh/ccst+n/7uMLaOtO8a29O+nbpij3d6TkYfjvF25ZHkaaG209I7Mcx3AX9u/HCN8QuK3+DGnJF8364CT/Uv5aelHzJq8yBWtsmhiSc54nHOzuhNr7gB3N3kiVrncmbGiZwSPzR03CfzxrOw5A3ebfX1bp9PYaCArmkNmZ6yiIHxQ3d7u32lOu6Q32iPhoeM/r4PneK6cm/bHTUcsbYTv2l0AWNSa9ZwV1kVmzhjbXsebDeTYY1HAfBpwXv8ecPvePu4dTSOjlxTgEpbye9/OJnfJV/HisIPyffn8vRR82od/1zWQ7yYPZH3umQQH5UQ1pdXlcugr5sx7egP6Zl06i/OuzbdV+31pvuuTx/o2hWm7Xgv6NQJLrgAHo7wXvz973D77bB5c3CFCvDgg8H29HQwZv/Me1c9e2JXrIh4cOeX/BW2gq8rVjIgfkhY+8nxQ2q93Ovq7Uk0Mcwueg6/9VMUKGRO0Yt09faqNQQAim0hDaMaR+yz1vJJ6Qesr/yO3rGnhPWlVa2n76ZWDEjvwI3ZF5FWub7O83m18B8kmQYc5+1W6zjXVMd9Vxmo4NuSlfRrEF7Dfg2G8GXx7t16eGvLP0nyNGJww/NDbR9ue4vjEnrxUvZfGfpNa0as7cSj6WMo8ReFbTs58/9I9bZnRJPLf/E41lre2vpPzmhyaY0wPSxUVMDKlTAk/L1gyBBYVst78emnMGDAjjAFGDoUMjJgw4Z6m+q+cH7Jn+fPxY+f5F0u6Zp5UvjE/37EbVrHtGdmi8Vcn/077t1yPQECHO/tzgspC2s9zoyCyWRVpXNu4uiw9oLANvptakWFLScKDxOaTubUhGGh/m6xfZiYPJ2jY45hiz+bZ/If5PzM/rzX6hsae5qGxn1QMo8xORdRakto7mnJjBaL9+vlvuq477bXsEl0+PGaRKewpSpyDXcWsAH+tfV5zmxyGd6o2FD7zxXrWV28FG9ULI+3n0OhP59Hf76RnMoMHu/wBhBcxb6bN5vZnVfv1lyXFy7m54qfOLfJVbt/goeS3Fzw+yFll/c+JQXer+W9yMqC1q1rjt/e16GD+3nuo3q5hwpgCF8RW2yNtu1yqrK4PfcPnJd4GSN8F1NkC5mUdy83ZF/IKy3+TZQJX0gvLJ7Dw3m38XSzWbSObhfWl2iSmJ+6mpJAEZ+UfcBDW8fROro9J8UPBggLBYDusX0ZmH4Uc4pe5KqG40Lt/eJOY37qavL8ucwqmsYN2Rcyt+WnNI9uudc12Ruq476rWa/aa7izTwoWklW5qUbIBQhgMPyl3SskeRoCcAfPcN36oWyp3EyU8XBv2hU83O4VGkRHXvnvau6WaRyf0IvOCd12a/wha9fLdGvrvnSPND5S+0HCeaA29iTjwUOOPyusPdefXWO1td2MwskkRPm4s8ljobZJzV6if3obVpYvo1fcyaH2hcVzGJc7mieSZ3B6woga+4oyUbSP6QjAcbHd+LHyW6Zs+0soCHbli0qkk/d4NlT9ENaeEOWjfVRH2sd0pHtcX05L78SsoucY0+ie3SvEPlId9932Gm6pCq/h1qrsGqvWSOZs+Qcn+PpzdPzxYe3J0S1pHtMqFKYAHeKOBSCrMo1SfzG5VZlcu+43of4AAQB6ro7mjWO+oX1c5x3zqczmo4J/cWfryXt+koeK5GTweIIry51lZ9dctW7XokXk8VD7NgeY83uoXuOli7cHS0sXh7UvLV1Mj7j+EbcptSV4CP+GePvP2z+IAPOKX+Pm3EuZmDyd4b4Ldms+lgAVtrzW/vJAGesq/0dzT90rpsAv7Mc11XHfxUR5OTahB8sLw2u4vHAxJ/gi13C77MoMlhbM57wmV9fo6+Y7iZzKjLB7phvLg4+mtYxpx/EJvXi98xpmdV4deg1sMILuvgHM6ryaVt7wS9W3t07Ha2IZ2uiivT3Vg5/XG3xManH4e8HixdC/lveiX7/gY1VlZeHjU1Ohfft6m+q+qJfnUK9qOI45RdOZVfgcP1Z8y/1bxpLtz2BUUvBxlMfy7uSSrB0rnUHxZ/B1xX95Kv9+fqr8ga/L/8ttuVeS6mnDr709AHinaBY351zC7Y0foU/sKeRUZZFTlUW+f2toP8/kP8TS0vdJq1zPjxXfMm3bE7xZNJNzfJeGxjy09VaWly1hU+VPrCr/jOtyLqA0UMx5icEvDgoDBTyedzeryj/j56o01pSv5M+5vyerKp0zfDseZ9kfVMd9d2mzcby9dTpztzzH+rJveSx9LDmVGaFHo57OuJNrfqy56v7XlueJj/JxeuOacx3WeBQNo5tyX9qVrCv9htVFnzDx57H8puEFNIlpTrzHR8f4LmGvJE8jfJ4kOsZ3ISbKG9qXtZY3tz7H0EYX4fMk1TjWtqqtfFeymnWlwacp0ip+5LuS1eRWZtUYe9AbNw6mT4fnnoNvvw0+QpWRAddWP6Z2550weKf3YtQoSEgIPir19dcwdy488khwP0fKJT/Amb6R5Pm38Ez+g+T4M/mVtwvPpywI3afLrspkY+W60Pj+8YN4KvkVni14jH9sm0iciadbbF+mpywiIcoHwMuFU6miiglbb2LC1ptC2/aJHcislh8BUGKLuGfLn8j0pxNn4jk65hieSJ7BiMSLQ+OzqtIZm3Mxef5cmnia0T22L3NbLg/NLZpofqj8hteznyffv4VGnqZ09fZiVsv/cKy3a32Uq1aq474b2ngk2/xbeC7rQXKrMukY14W/HbWAVG9wnrmVmWwqXxe2zfZv3Ic1viTiN+4JnkSmHv0+j/58I5d+34uk6Mac1vAcxrR8ZI/nt6LoI9LKf+Chti9F7F+y7W3u23Rl6OcHNgVXzNek3Me1Lcfv8fEOqJEjYcuW4KNPmZnQpQssWADtqu/fZ2bCup3ei4YNgyvS66+Hnj2hcePg86fjxkXe/0GgXp5DFXFtb59DlXAH9DnUw8X+fA5VRORIpUAVEXFEgSoi4ogCVUTEEQWqiIgjClQREUcUqCIijihQRUQcUaCKiDiiQBURcUSBKiLiiAJVRMQRBaqIiCMKVBERRxSoIiKOKFBFRBxRoIqIOKJAFRFxRIEqIuKIAlVExBEFqoiIIwpUERFHFKgiIo4oUEVEHFGgiog4okAVEXFEgSoi4ogCVUTEEQWqiIgjClQREUcUqCIijihQRUQcUaCKiDiiQBURcUSBKiLiSHRdnWt+DR1W7K+pHL7yGh/oGRz62m840DMQ+WVaoYqIOKJAFRFxRIEqIuKIAlVExBEFqoiIIwpUERFHFKgiIo4oUEVEHFGgiog4okAVEXFEgSoi4ogCVUTEEQWqiIgjClQREUcUqCIijihQRUQcUaCKiDiiQBURcUSBKiLiiAJVRMQRBaqIiCMKVBERRxSoIiKOKFBFRBxRoIqIOKJAFRFxRIEqIuKIAlVExBEFqoiIIwpUERFHFKgiIo4oUEVEHFGgiog4okAVEXFEgSoi4sjBH6hTpkCHDhAXBz16wMcf1z1+zRoYOBDi46FVK5gwAazdP3OtB8+VT+GEgg60yI/j1MIeLKuq+/w/qHyXIYX9aJOfxNHbkhlVdDY/+r8PG/N6xSsMKOhGan4Cnbe14I/Fl7I5kBXqf7F8GsMKB9BhWxPa5TfirKLT+LRqadg+ppVP5qSCrrTNb0Db/AYMKezHu5Xzw8ZcV3wFjfNN2Ov0wr77WJE9N4UpdKADccTRgx58TN01fI3X6EY3EkigHe2YyMRaxy5lKdFE04UuYe3f8A0XcAFHcRQGw3jG19j2P/yHEYygFa0wGKYzvcaYIoq4kRtpTWviiacznZnEpN0674PSYf77fHAH6uzZMHYs3HUXrFoF/fvDsGGQlhZ5fEEBnH46pKTAF1/A00/DxInw17/u33k7MrdiNneWjmVc7F0sSVpFb09/LiwaxqZA5PPf6P+JS4rPpm/0AJYkreIt3/uUUcqFxcNDY5ZXfcK1JaO52Hs5nyZ9w0u+t/gusJY/llwSGrO06iPO9Y7kX74PeD/pMzpGdeaCoqGs8/8QGtMqqjXj4x/lo6T/8u+kFQyIHsSlxefwtf+rsDmdGv0b/tcgM/R6zbfAcZXqNpvZjGUsd3EXq1hFf/ozjGGkEbmGC1nIKEbxR/7I13zNFKYwiUk8wzM1xuaRx2VcxmAG1+groYT2tOdBHqQDHSIeq4giutCFp3iKeOIjjhnHOOYzn5nM5Fu+5f/4P+7gDmYycw+qcJA4En6frbW1vujRo/bO/fHq3dty1VXhbR07Wu64I/L4KVMsSUmWkpIdbQ88YElNtQQCB+w88hrt3auHp7e9zHtVWNtRUR3tTbF3RBw/PeF1G0WUzW1YFWp72/dvC9gfG+TYvEbWToibaFubtmHbPRP/vPXhq3UeWxsGbHOTYh+Nf7rO+TYyje1f46eGfr445nI7JPqMvT7/nV97W/ze9LZXcVVYW0c62ju4I+L4i7nYnsM5YW1P87RtTWsbIBDWfi7n2vGMt/dxnz2e42udw/Ecb+/jvjrn6cNnX+CFiNvey71hbadwir2e6/eqHntZRjevw+T3mR49bG1dB+8KtaICVq6EIUPC24cMgWXLIm/z6acwYEDw8mC7oUMhIwM2bKi3qdaHClvBav9KTosOP//ToofweVXk8+/u6UkMMcyoeA6/9VNoC3m14kVO9PSiaVQyAH2iT2KzzWRh5TtYa9kSyGVu5SxOjxkecZ8AFVRQZstoaBpH7PdbP3MqZlFsi+gd3T+sb3nVUjpta07Pgl8xtuRqcgLZe1KGfVJBBStZyRDCaziEISwjcg3LKSeOuLC2eOJJJ52NbAy1TWEKWWRxN3e7n/hOTuZk3uEdNrEJgGUsYzWr+S2/rdfjOneE/D4fvIGamwt+f3C5v7OUFMjKirxNVlbk8dv7DiFbbC5+/DSLCj+f5lEpZNvI59LW0565iYt5pOw+UrbF0m5bQ9YG1jDLNy80pnd0P55LeJVrii+h+TYvHQuaYbFMSXix1rk8WHY3iSaRYTEjwtq/8a+hdX4iKdtiGVdyLTN9b3K859eh/sExv+Xvvhm8lfgBD8Q/wcqqzxlRNIhyW743JdljuQRrmEJ4DVNIIYvINRzKUN7iLd7jPQIE+J7veYInAMgkE4A1rOF+7udlXsaDp17P4WmephvdaEtbYohhIAN5lEc5kzPr9bjOHSG/zwdvoG5nTPjP1tZs+6XxkdoPEYbweVtsjbbtNgeyGFPyB0Z6L+PfiV/wTuJHJJLElcUXErABAP7nX8sdpWO4Ne4ePkxayRu+RWwOZHFzyTUR9zm1/CleLH+WGb65NDANwvo6RXXmP0mrWZy4nN/H/onrSi5nrf/rUP/53osYHjOC4z2/ZljMWbyeuJAfA9/x3i5fXtW3Panh1VzNGMZwNmfjxUtf+nIRFwHgwUM55VzERTzO47XeG3Xpb/yNT/iEt3mblaxkEpO4lVtZxKJ6P3a9OMx/n6MP9ARqlZwMHk/Nv0TZ2TX/am3XokXk8VD7NgeppiYZDx6yA+HnkxPIppmJfC7PlU8mwfiYEP9YqO1Z30t0KWjDZ/5l9Is+mUllD3NidG/GxN0GQBdPVxKMj+FFA7g78BCto9qEtp1a/hQPld7Na4kL6RHdu8bxvMbLUZ6OAHSP7skq/xf8vXwSf0v4Z8T5tYxKJTWqNesCP0Tsdy2ZYA13XY1mk11j1bqdwfAoj/IX/kIWWTSjGR/wAQDtaU8mmaxlLVdW/wMQIIDFEk00C1hQ4xbD3iqllDu5k9d5nbM4C4CudGU1q3mcxw+ty/4j5Pf54F2her3BxyoWLw5vX7w4+O1gJP36BR/DKCsLH5+aCu3b19tU64PXeOnm6cFHVeHn/1HV4hr3KbcrpaTGJej2nwMEfnGMZcfjKJPL/sqDpf/HrMT59Is+ebfmHCBQ5+X8lkAumYGfaRHVcrf2t6+8eOlBDxYTXsPFLKY/tXyGqnnw0IpWePHyKq/Sj340pzmtaMUa1rB6p3+u5Vo60pHVrP7F/e6Jyup/Ir1f29/PQ8aR8vtc15dZB/xb/lmzLDExlmnTLGvXWsaMsfh8lg0bgv133GEZNGjH+Px8S0qKZeRIy5o1ljlzgt8SPv74AT2Pvf1m+58Js2wMMfap+Gl2edJae413jPXhs1822GDzGll7U+wd9pToQaHx//J9YA3G3hE33q5I+t5+lLjSDo4ealuZNja9YZHNa2Tt5PgXbDTR9vH4KXZV0jq7MHGp7e7paU/wnBjaz/1xj9kYYuzzCbPt/xpkhl4bGuaHxoyNvd3OT/yP/TLpJ7s06St7U+wd1mDsa74FNq+RtZsaFtobYm+x7yYus18m/WTf8X1oe3n62lTTyqY1LNhv3/LPIljDaUyza1lrxxCs4QY2WIu1d3CHHcSg0PgccuwUpti1rLWrWGXHMMbGEWc/47NajxHpW/5yyu0qVtlVrLJHc7S9hmvsKlbZH/ghNKaQwtCYeOLt/dxvV7HKbmRjaMxABtrjOd5+yId2PevtC7xg44izT/P0XtXjQP4eHC6/z3V9y1/ndgc8UK21TJ5sadfO4vVaTjzRsmTJjr7LLw/27Tz+q68sAwZYYmMtLVpYxo8/sI9Y2H17XGhi/GTbxrSzXrz2BM+Jdl7ikrDHktqYdmHjn0t41Xb1dLc+fLapSbZDo8+0nyZ9Ezbm0fin7TFRx9l44m2KaWHPj7nYft1gU6i/jWlngRqvi2MuDzt2a9PWevHaZNPMDowebN/wLQr1ZzQssYOih9hk08zGEGNbm7b24pjL7ZoGafv1sSmLtZOZbNsRrOGJnGiXsCTUdzmX23a0C/2cQ47tS1/rw2cTSLCDGWyXs7zO/UcK1J/4KWINBzIwNOZDPow45nIuD43JJNNewRU2lVQbR5ztTGc7kYk1HuHa3deB/D3gMPl9ritQjbW1/78OTM+elhUr6nOBfETIi/y0keyBRvkHegaHB3Pw/p+MDh09e2JXrIj4rdjBew9VROQQo0AVEXFEgSoi4ogCVUTEEQWqiIgjClQREUcUqCIijihQRUQcUaCKiDiiQBURcUSBKiLiiAJVRMQRBaqIiCMKVBERRxSoIiKOKFBFRBxRoIqIOKJAFRFxRIEqIuKIAlVExBEFqoiIIwpUERFHFKgiIo4oUEVEHFGgiog4okAVEXFEgSoi4ogCVUTEEQWqiIgjClQREUcUqCIijihQRUQcUaCKiDiiQBURcUSBKiLiiLHW1t5pTA6wcf9NR0TkoNfOWtssUkedgSoiIrtPl/wiIo4oUEVEHFGgiog4okAVEXFEgSoi4sj/A5948a2yo56lAAAAAElFTkSuQmCC",
      "text/plain": [
       "<Figure size 432x432 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def plot_values(V):\n",
    "    # reshape value function\n",
    "    V_sq = numpy.reshape(V, (4,4))\n",
    "\n",
    "    # plot the state-value function\n",
    "    fig = plt.figure(figsize=(6, 6))\n",
    "    ax = fig.add_subplot(111)\n",
    "    im = ax.imshow(V_sq, cmap='cool')\n",
    "    for (j,i),label in numpy.ndenumerate(V_sq):\n",
    "        ax.text(i, j, numpy.round(label, 5), ha='center', va='center', fontsize=14)\n",
    "    plt.tick_params(bottom=False, left=False, labelbottom=False, labelleft=False)\n",
    "    plt.title('State-Value Function')\n",
    "    plt.show()\n",
    "\n",
    "optimalValue = valueIteration(env, gamma, improvementIterations, eps)\n",
    "plot_values(optimalValue)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Policy Iteration\n",
    "\n",
    "With the Frozen Lake environment, we are also going to try out the policy iteration method. \n",
    "\n",
    "**Again, please implement the code labeled #TODO**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"Given a policy, extract its corresponding value function\"\"\"\n",
    "def get_value_function(env, policy, gamma, eps=1e-20):\n",
    "\n",
    "    value = numpy.zeros(env.nS)\n",
    "\n",
    "    while True:\n",
    "        previous_value = numpy.copy(value)\n",
    "        for state in range(policy.size):\n",
    "            outcomes  = []\n",
    "\n",
    "            # TODO: Extract the action from policy\n",
    "            action = policy[state]\n",
    "\n",
    "            for probability, next_state, reward, is_done in env.P[state][action]:\n",
    "                # TODO: Get all outcomes of that action\n",
    "                outcomes.append(probability * (reward + gamma * value[next_state]))\n",
    "\n",
    "            # TODO: Extract the value function\n",
    "            value[state] = sum(outcomes)\n",
    "\n",
    "        if numpy.sum(numpy.fabs(previous_value - value)) <= eps:\n",
    "            return value\n",
    "\n",
    "    return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def policyIteration(env, gamma=1.0, improvementIterations=1000, eps=1e-20):\n",
    "\n",
    "    # Declare a random policy\n",
    "    policy = numpy.random.choice(env.nA, size=(env.nS))\n",
    "\n",
    "    for i in range(improvementIterations):\n",
    "\n",
    "        # TODO: calculate the value function with the previous policy, \n",
    "        #  then use this value function to iterate for an improved pocliy \n",
    "        #  Hint: you've already implemented how to use a value function \n",
    "        #  to calculate a policy in calculatePolicy\n",
    "        newPolicy = numpy.zeros(env.nS)\n",
    "        value = get_value_function(env, policy, gamma, eps)\n",
    "        for state in range(env.nS):\n",
    "            Q = []\n",
    "            for action in range(env.nA):\n",
    "                outcomes = []\n",
    "                for probability, next_state, reward, _ in env.P[state][action]:\n",
    "                    outcomes.append(probability * (reward + gamma * value[next_state]))\n",
    "                Q.append(sum(outcomes))\n",
    "            newPolicy[state] = Q.index(max(Q))\n",
    "\n",
    "        # If converged\n",
    "        if(numpy.all(policy == newPolicy)):\n",
    "            return policy\n",
    "        policy = newPolicy\n",
    "\n",
    "    print(\"Iterated over %d Iterations and couldn't converge\"%(improvementIterations))\n",
    "    return policy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "gamma = 1.0\n",
    "improvementIterations = 10000\n",
    "evaluationIterations = 100\n",
    "eps = 1e-20\n",
    "numpy.random.seed(0)\n",
    "env = gym.make(game)\n",
    "env.seed(0)\n",
    "\n",
    "def PolicyIterator(env, gamma=1.0, improvementIterations=1000, eps=1e-20, evaluationIterations=100):\n",
    "    optimalPolicy = policyIteration(env=env, gamma=gamma, improvementIterations=improvementIterations, eps=eps)\n",
    "    startTime = time.time()\n",
    "    policy_score = evaluatePolicy(env, policy=optimalPolicy, gamma=gamma, iteration=evaluationIterations, render=False, eps=eps)\n",
    "    endTime = time.time()\n",
    "    print('Best score = %0.2f. Time taken = %4.4f seconds'%(numpy.max(policy_score), endTime - startTime))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can also visualize the value function with respect to the policy."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Best score = 0.82. Time taken = 0.0379 seconds\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAVQAAAFkCAYAAAB/6MMYAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuNCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8QVMy6AAAACXBIWXMAAAsTAAALEwEAmpwYAAAyfElEQVR4nO3ceXxU1f3G8c/JJJNlEtZAIOwKxYUiyI4iChUKKq4VRXFptVoXUNS6/FwQtS5oUSsUi1UEF1BBq2yKVqmIqFBQFOsCQohJSAIJ2beZ8/tjwsCQSWQ5YX3evuZlc8659577ncmTc+/caqy1iIjIvos60BMQETlcKFBFRBxRoIqIOKJAFRFxRIEqIuKIAlVExBEFqhxQxpjxxpiXDvQ86oMxZqox5p4DPQ/ZfxSohyhjzMnGmGXGmG3GmK3GmE+MMb2q+64wxizdg321N8ZYY0z0XsyjnzGm2BiTFKFvlTHmhj3dpwvGmFONMQFjTNFOr3fq8Xg1am6tvdZa+0B9HVMOPnv8CyQHnjGmATAP+BPwGuAFBgDl+3su1tpPjTHpwPnA9J3m2AU4Dnh1f89pJxnW2tYH8PhyhNEK9dD0KwBr7avWWr+1ttRa+5619itjzLHAVKBf9aosH8AYc0b1irHAGLPJGDN+p/39p/rf+dXb9Kve5vfGmG+NMXnGmHeNMe1qmc+LwGW7tF0GzLfWbjHGPFV9zAJjzEpjzIBIO6leVabv0rbBGPOb6v8dZYy5wxizzhizxRjzmjGmye4WbTePMb56vzOMMYXGmG+MMT13GtvGGDPXGJNTPYdn6qj5dGPMgztte7Ux5sfqK4q3jTGpO/VZY8y1xpgfqus92Rhj9uTc5MBToB6avgf8xpgXjTHDjDGNt3dYa78FrgU+tdYmWmsbVXcVEwy5RsAZwJ+MMedU951S/e9G1dt8Wt13F3Ae0Az4mNpXmzOBAcaYthAMPmAUMKO6/wugG9AEeAV43RgTtxfnPQY4BxgIpAJ5wOS92M8vGQHMIlirt4FnAIwxHoJXBhuB9kArYFYdNQ8xxgwCHgYuBFpW72PWLsPOBHoBJ1SPG+r2tKS+KVAPQdbaAuBkwALTgJzqFU9KHdt8ZK1dY60NWGu/IhiOA+s4zDXAw9bab621VcBfgG6RVqnW2k3AEuDS6qbBQBwwv7r/JWvtFmttlbX2CSAW6LyHp719Tv9nrU231pYD44EL6rj3m2qMyd/pdeFuHmeptXaBtdZP8I/FCdXtvQkG+W3W2mJrbZm1dnfvVV8CPG+t/W/13O8kuKJtv9OYR6y1+dbaNOBDgn+E5BCiQD1EVQfdFdX3CLsQ/EV/srbxxpg+xpgPqy9VtxFcUSXXcYh2wFPbwwjYChiglTHmrp2+6JlaPX7ny/7RwCvW2srqY99SfetgW/W+Gv7Cseua05s7zelbwA/U9ockw1rbaKfXa7t5nKyd/ncJEFcd2m2AjdV/YPZUKsFVKQDW2iJgC8FVbm3HTdyL48gBpEA9DFhr/0fwC6Eu25siDHuF4OVrG2ttQ4L3/Ewd4zcB1+wSSPHW2mXW2r9UX9omWmuvrR4/l2DYnkbwNsEMgOr7pbcTvIRtXH05vG2nY++sGEjY/kP1JXazXeY0bJc5xVlrf66jPHt6jLpsAtrWsiL+pf9sWwbBPwjbj+sDmgJ7Mnc5yClQD0HGmGOqV32tq39uA1wMLK8eshlobYzx7rRZErDVWltmjOlN8B7ndjlAADhqp7apwJ3GmOOrj9HQGPO72uZkrS0G3gBeILiKW7HTcauqjxFtjLkXaFDLbr4nuBo8wxgTA9xN8PbAznN6aPttB2NMM2PM2bXNaS+PUZfPgUzgEWOMzxgTZ4w5qbovUs139gpwpTGmmzEmluAtlM+stRv2cP5yEFOgHpoKgT7AZ8aYYoJB+jVwS3X/v4FvgCxjTG5123XABGNMIXAvwcetALDWlgAPAZ9UX073tda+CTwKzDLGFFTvf9gvzOtFgquwGTu1vQssJBhkG4Eygiu9Gqy126rn+RzBlVsxsPM38k8RXGW/V30ey6vrsNt24xh1besHzgI6AmnV242s7o5U8523/QC4B5hDMJSPBi7ak7nLwc/oPzAtIuKGVqgiIo4oUEVEHFGgiog4okAVEXFEgSoi4kid/7WpJp5k2zq6/X6aiojIwS+9agNb/bkR/8M1dQZq6+j2vJ26oq4hIiJHlBEZPWvt0yW/iIgjClQREUcUqCIijihQRUQcUaCKiDiiQBURcUSBKiLiiAJVRMQRBaqIiCMKVBERRxSoIiKOKFBFRBxRoIqIOKJAFRFxRIEqIuKIAlVExBEFqoiIIwpUERFHFKgiIo4oUEVEHFGgiog4okAVEXFEgSoi4ogCVUTEEQWqiIgjClQREUcUqCIijihQRUQcUaCKiDiiQBURcUSBKiLiiAJVRMQRBaqIiCP1FqgzC6YwIL0DnTfEcVZGDz4v+7jO8UtK3+W8zH502ZjEiWnJXL35bNZXfh/qX1Q8l9FZQ+iR1owuG5M4J6MPi0veDtvH/OLXGZHRk64bG3HcRh/Df+7GnKIXw8Y8mTeeDhtM2KtXWouwMU/k3cPg9GM4bqOPE9Iac0nWYFaWLdvHiuwd1XHfqYZuqI6/rF4CdV7xbCZsHct1De9ifuoqToztz5Wbh/FzVVrE8Zsqf+KPm8+mV+wA5qWu4qWU9ymzpfx+8/DQmM/KltA/bhD/TJnPvNRVnJYwnGuzzw17UxtHNeWGhnfzZsvlLEz9it8lXcntuX/gw5IFYcc7Krozn7fODL0WtVoT3h/TmQlNJ7ModQ2vt1hK6+gOXLH5t+T4Nzus0i9THfedauiG6rh7jLW21s6usT3t26kr9nin52T04RhvVx5JnhZqOy29E8N8F/Dnxg/XGL+g+A1uzBnJ9+0q8BgPAJ+WfsiozYNY2SaHJp7kiMc5O6M3veIGcHeTJ2qdy5kZJ3JK/NDQcZ/MG8/Ckjd4t9XXu30+hYECuqY1ZHrKIgbGD93t7faV6rjvVEM3VMcdRmT05KvyFSZSn/MVaoWt4OuKlQyIHxLWfnL8kFqX2F29PYkmhtlFz+G3fooChcwpepGu3l61Fh6g2BbSMKpxxD5rLZ+UfsD6yu/oHXtKWF9a1Xr6bmrFgPQO3Jh9EWmV6+s8n1cL/0GSacBx3m61jnNNddx3qqEbquPui3a6NyDPn4sfP8melLD2Zp4UPvG/H3Gb1jHtmdliMddn/457t1xPgADHe7vzQsrCWo8zo2AyWVXpnJs4Oqy9ILCNfptaUWHLicLDhKaTOTVhWKi/W2wfJiZP5+iYY9jiz+aZ/Ac5P7M/77X6hsaepqFxH5TMY0zORZTaEpp7WjKjxWKa7XJO9Ul13HeqoRuq4+6rty+lDOErYout0bZdTlUWt+f+gfMSL+NfLb/g1RYf4TNJ3JB9IQEbqDF+YfEcHs67jUnNXqZ1dLuwvkSTxPzU1fyr5Rfc2vghHto6jk9KPwj1n5owjDN9F3Kstysnx/+Gf6bMwxKocaO7X9xpzE9dzZwWyxgY/1tuyL6Q7KrMvS3HXlMd951q6Ibq+Mucr1Abe5Lx4CHHnxXWnuvPrvEXbrsZhZNJiPJxZ5PHQm2Tmr1E//Q2rCxfRq+4k0PtC4vnMC53NE8kz+D0hBE19hVlomgf0xGA42K78WPlt0zZ9hdOih8c8di+qEQ6eY9nQ9UPYe0JUT7aR3WkfUxHusf15bT0Tswqeo4xje7ZvULsI9Vx36mGbqiOu8/5CtVrvHTx9mBp6eKw9qWli+kR1z/iNqW2BA+esLbtPwfY8ddsXvFr3Jx7KROTpzPcd8FuzccSoMKW19pfHihjXeX/aO5pWed+Ar+wH9dUx32nGrqhOu4+5ytUgKsajmNczmhOiO1Nz9iTeLlwKtn+DEYlXQvAY3l38mX557zcIrhsHxR/Bs8XTOKp/PsZ4RtFcaCQiXl3keppw6+9PQB4p2gW43JHc1eTx+kTewo5VcG/ljHGSyNPEwCeyX+IbrF9aBt9FBW2nA9LF/Bm0UzGN/lbaG4Pbb2VwQln0crTltxANs/kP0BpoJjzEi8Hgt/+PbvtMQYnnEVzT0u2+nOYWRi8t3OG78L6KFetVEfV8GCoIaiOu6teAvVM30jy/Ft4Jv9BcvyZ/MrbhedTFoTujWRXZbKxcl1ofP/4QTyV/ArPFjzGP7ZNJM7E0y22L9NTFpEQ5QPg5cKpVFHFhK03MWHrTaFt+8QOZFbLjwAosUXcs+VPZPrTiTPxHB1zDE8kz2BE4sWh8VlV6YzNuZg8fy5NPM3oHtuXuS2Xh+YWTTQ/VH7D69nPk+/fQiNPU7p6ezGr5X841tu1PspVK9Vx36mGbqiOu6denkMVETlc7dfnUEVEjlQKVBERRxSoIiKOKFBFRBxRoIqIOKJAFRFxRIEqIuKIAlVExBEFqoiIIwpUERFHFKgiIo4oUEVEHFGgiog4okAVEXFEgSoi4ogCVUTEEQWqiIgjClQREUcUqCIijihQRUQcUaCKiDiiQBURcUSBKiLiiAJVRMQRBaqIiCMKVBERRxSoIiKOKFBFRBxRoIqIOKJAFRFxRIEqIuKIAlVExBEFqoiIIwpUERFHFKgiIo5EH+gJHAk6/HSgZ3Dom3TzgZ7B4eHmSQd6BoeBnrV3aYUqIuKIAlVExBEFqoiIIwpUERFHFKgiIo4oUEVEHFGgiog4okAVEXFEgSoi4ogCVUTEEQWqiIgjClQREUcUqCIijihQRUQcUaCKiDiiQBURcUSBKiLiiAJVRMQRBaqIiCMKVBERRxSoIiKOKFBFRBxRoIqIOKJAFRFxRIEqIuKIAlVExBEFqoiIIwpUERFHFKgiIo4oUEVEHFGgiog4okAVEXFEgSoi4ogCVUTEEQWqiIgj9RaoMwumMCC9A503xHFWRg8+L/u4zvFLSt/lvMx+dNmYxIlpyVy9+WzWV34f6l9UPJfRWUPokdaMLhuTOCejD4tL3g7bx/zi1xmR0ZOuGxtx3EYfw3/uxpyiF8PGPJk3ng4bTNirV1qLsDFP5N3D4PRjOG6jjxPSGnNJ1mBWli3bx4ocQFOmQIcOEBcHPXrAx3W/F6xZAwMHQnw8tGoFEyaAtftnrvVg6ZdTeOD5Dtz2tzieeKUH636u/fy3btvAzU+aGq9vNywKjfnqx7n8fe4Q7n62GXdMTmLSq334el34Z9Hvr+Td5RN48IWjue1vcUx86YSwfexq8ed/4eYnDXM+vCGs/asf5zJ17lDufrYZNz9p+HHTR3tVg4PGYf5ZrJdAnVc8mwlbx3Jdw7uYn7qKE2P7c+XmYfxclRZx/KbKn/jj5rPpFTuAeamreCnlfcpsKb/fPDw05rOyJfSPG8Q/U+YzL3UVpyUM59rsc8OCunFUU25oeDdvtlzOwtSv+F3Sldye+wc+LFkQdryjojvzeevM0GtRqzXh/TGdmdB0MotS1/B6i6W0ju7AFZt/S45/s8Mq7SezZ8PYsXDXXbBqFfTvD8OGQVrk94KCAjj9dEhJgS++gKefhokT4a9/3b/zdmTVd7N5c8lYftPrLm69ZBXtW/bnH28NI6+glvOvds05i7j/6szQq1ObQaG+H9OX0KnNIK4+ez63XLKKYzsM5/l554YF9YJld7NszVTOPfVpbr9sLf1/fS0vvHMu6dmrahxrQ+Zyln89jdTkrjX6yiuLaZ/an7NPOTTrH+YI+CwaW0fad43tad9OXbHHOz0now/HeLvySPK0UNtp6Z0Y5ruAPzd+uMb4BcVvcGPOSL5vV4HHeAD4tPRDRm0exMo2OTTxJEc8ztkZvekVN4C7mzxR61zOzDiRU+KHho77ZN54Fpa8wbutvt7t8ykMFNA1rSHTUxYxMH7obm+3XYef9ngTd/r0ga5dYdqO94JOneCCC+Dhmu8Ff/873H47bN4cXBUAPPhgsD09HYzZP/PexaSb93K7V/uQ2qwrI3+z4/wfmt6JEzpewJkn1zz/rds28MALHbj54i9om9JzD47Tm6NaDeDsU4KfxfumpTKo5+0M7D42NOaFeecTEx3Ppb99KdRWWr6NJ145kZG/mca7yyfQMrkL55/2TI39F5Xmcs+zzbj+/A/p2ObU3Z7Xrm6etNeb7rvD5LNIz57YFSsiHtz5CrXCVvB1xUoGxA8Jaz85fkitl81dvT2JJobZRc/ht36KAoXMKXqRrt5etYYpQLEtpGFU44h91lo+Kf2A9ZXf0Tv2lLC+tKr19N3UigHpHbgx+yLSKtfXeT6vFv6DJNOA47zdah13UKqogJUrYUj4e8GQIbCsllsYn34KAwbs+AADDB0KGRmwYUO9TbU+VPkrSM9eSee24effue0QNmTWfQvnhXnncc+zzXlq9kms/uGNXzxWWUUh8bE7PotV/nJiPHFhY2Ki41n/89Kwttfe/yMndLwgbAV8WDpCPovOAzXPn4sfP8melLD2Zp4UcvxZEbdpHdOemS0WMynvPjpvjKVrWkO+q1zDP1Pm1XqcGQWTyapK59zE0WHtBYFtHL8xkV9t9PL7zWdwX5OnOTVhWKi/W2wfJiZP54WUhTzcdBo5/izOz+xPnn9L2H4+KJnH8RsTOWZjHM8XTGJGi8U02+WcDnq5ueD3By+ZdpaSAlmR3wuysiKP3953CCkuzSVg/SQlhJ9PUkIKBSWRz8XrTWTEgMe5fPhrXH3OAn7VdjAzFoxkxbcvRRwPsPTLyWwrSqfnsTs+i8e0G8qSVU+SvfU7AjbAdxsX89WPcykoyQyN+XTNNHK3/ciw/g/s45keAo6Qz2J0fe3YEL4ittgabdvlVGVxe+4fOC/xMkb4LqbIFjIp715uyL6QV1r8mygTnvsLi+fwcN5tPN1sFq2j24X1JZok5qeupiRQxCdlH/DQ1nG0jm7PSfGDAcLCFaB7bF8Gph/FnKIXuarhuFB7v7jTmJ+6mjx/LrOKpnFD9oXMbfkpzaNb7nVNDphdL42srftyKdL4SO2HCrP7n8XE+GRO63FL6Oe2KT0pLs3l3ysfo+exl9YY/+UPc3j749u4bNgsmjTY8Vk8d+BTzH7/ah6ZeRwGQ9NGR9P7uCv5fO0LAGRv/Y75y+7ixt99TLTH6+IsDw2H+WfReaA29iTjwVNjNZrrz66xat1uRuFkEqJ83NnksVDbpGYv0T+9DSvLl9Er7uRQ+8LiOYzLHc0TyTM4PWFEjX1FmSjax3QE4LjYbvxY+S1Ttv0lFKi78kUl0sl7PBuqfghrT4jy0T6qI+1jOtI9ri+npXdiVtFzjGl0z+4V4mCQnAweT82/5tnZNf/yb9eiReTxUPs2BylffDJRxkNhcfj5FJVk11i11qVtiz58/s0LNdq//GEOL787mlFDZ9Dl6PDPYmJCM/4w4i0qq8ooLttCQ18q85beQZMGHQDYkPkpxaW5PDazS2ibgPWz/uf/sOyrqTx6fTHR0bF7croHtyPks+j8kt9rvHTx9mBp6eKw9qWli+kR1z/iNqW2BA+esLbtPwcIhNrmFb/GzbmXMjF5OsN9F+zWfCwBKmx5rf3lgTLWVf6P5p66V56BX9jPQcnrDT6asjj8vWDx4uA3rJH06xd8lKWsLHx8aiq0b19vU60P0R4vrZv34Lu08PP/Pm0x7VvWcv4R/JyzmiRf+Odj1fev8fKiS7l4yHS6dar9sxgTHUejxFYEAlV89eMcfn302QD8+uhz+POla7j1ktWhV5uUnnTvfBG3XrIaz+G2aj1CPov1csl/VcNxjMsZzQmxvekZexIvF04l25/BqKRrAXgs706+LP+cl1t8AMCg+DN4vmAST+XfzwjfKIoDhUzMu4tUTxt+7e0BwDtFsxiXO5q7mjxOn9hTyKkK/uWKMV4aeZoA8Ez+Q3SL7UPb6KOosOV8WLqAN4tmMr7J30Jze2jrrQxOOItWnrbkBrJ5Jv8BSgPFnJd4ORD8Rv/ZbY8xOOEsmntastWfw8zC4P3aM3wX1ke56te4cTB6NPTuDSedBFOnBm/qXxt8L7jzTvj8c/gg+F4wahTcfz9ccQXcfTd8/z088gjcd99Be5lVl1NPHMfL746mXYvedEg9iU++msq24gz6dw2e/7yld5K2+XOuOz94/p+vfRFPVAytm3fHEMU3P73DJ19O5syTHw3t87/fzeLld0czYsDjHN3qFAqqV8AejxdfXPCzuDHzM7YV/0xqs25sK/qZd5ePJ2ADDOrxZwDi4xoRH9cobK7eaB8JcU1ombxj1VpctpX8gjRKy/MByN32I/GxjUjytaCBL/z56YPeEfBZrJdAPdM3kjz/Fp7Jf5Acfya/8nbh+ZQFofud2VWZbKxcFxrfP34QTyW/wrMFj/GPbROJM/F0i+3L9JRFJET5AHi5cCpVVDFh601M2HpTaNs+sQOZ1fIjAEpsEfds+ROZ/nTiTDxHxxzDE8kzGJF4cWh8VlU6Y3MuJs+fSxNPM7rH9mVuy+WhuUUTzQ+V3/B69vPk+7fQyNOUrt5ezGr5H4711nxO8KA3ciRs2RJ83CQzE7p0gQULoF31/b7MTFi3472gYcPgKuD666FnT2jcGG65JfjLcAjq3nkkxWVbeO+zBykoyaRl0y788ewFofudBcWZ5OavC9tm8ecPklewERPloVmjX3HR6c+H3T9d9tVUAoEq3lpyE28tuSnUfnSrgdzwu48AqPSXsWDZ3WzZtp7YmESO7TCcS4bOrBGiv+SbdW/z6uIrQz/Pfv9qAIb2uY/f9hu/R/s64I6Az2K9PIcq4Q7oc6iHib19DlXCHdDnUA8X+/M5VBGRI5UCVUTEEQWqiIgjClQREUcUqCIijihQRUQcUaCKiDiiQBURcUSBKiLiiAJVRMQRBaqIiCMKVBERRxSoIiKOKFBFRBxRoIqIOKJAFRFxRIEqIuKIAlVExBEFqoiIIwpUERFHFKgiIo4oUEVEHFGgiog4okAVEXFEgSoi4ogCVUTEEQWqiIgjClQREUcUqCIijihQRUQcUaCKiDiiQBURcUSBKiLiiAJVRMSR6AM9gSPBTx0O9AwOffmNDvQMRH6ZVqgiIo4oUEVEHFGgiog4okAVEXFEgSoi4ogCVUTEEQWqiIgjClQREUcUqCIijihQRUQcUaCKiDiiQBURcUSBKiLiiAJVRMQRBaqIiCMKVBERRxSoIiKOKFBFRBxRoIqIOKJAFRFxRIEqIuKIAlVExBEFqoiIIwpUERFHFKgiIo4oUEVEHFGgiog4okAVEXFEgSoi4ogCVUTEEQWqiIgjClQREUcUqCIijihQRUQcUaCKiDhSb4E6s2AKA9I70HlDHGdl9ODzso/rHL+k9F3Oy+xHl41JnJiWzNWbz2Z95feh/kXFcxmdNYQeac3osjGJczL6sLjk7bB9zC9+nREZPem6sRHHbfQx/OduzCl6MWzMk3nj6bDBhL16pbUIG/NE3j0MTj+G4zb6OCGtMZdkDWZl2bJ9rMjeUR333Wu5UzhjbQf6fBnHqO968N+i2ms4NXM83VebiK+tldmhcZWBCqZk3ssZazvQ+8tYhn3Tlldyno64z4V5r9J9tWHM+jPD2od/0z7icW5cf0ZozAf5c7lu3VBOW9OM7qsNKwo/2qdaHHBTpkCHDhAXBz16wMd1f55ZswYGDoT4eGjVCiZMAGv3z1z3QnR97HRe8WwmbB3LhKZT6BV7MjMLp3Dl5mG812otraLb1hi/qfIn/rj5bK5oMIa/Js+kJFDEw3l/5vebh/NR6x8B+KxsCf3jBnFL4wdpFNWEfxW/zLXZ5/Jqi4/oHTcAgMZRTbmh4d0cHXMM0SaGf5fO4/bcP9AkqhmnJQwPHe+o6M7MavFR6Oco4wmbz1ExnZnQdDJtojtQZkv5Z8Ekrtj8W/7d+geaeVLqoWKRqY777t282UxMH8udbabQzXcyr+VO4Yb1w5hzzFpaemvW8LLmt3JB8rVhbXdsuAhjDE1imu9o23gxmys3cU+bf9DW24ktVZspD5TW2F96+XqezLiN7r4BNfpe6vwFAesP/Zxbmcmo73tweqMLQ22lgWJO8PVneONLuSftsr2qwUFj9mwYOzYYqiefHPz3sGGwdi20rfleUFAAp58Op5wCX3wB330HV1wBPh/ccst+n/7uMLaOtO8a29O+nbpij3d6TkYfjvF25ZHkaaG209I7Mcx3AX9u/HCN8QuK3+DGnJF8364CT/Uv5aelHzJq8yBWtsmhiSc54nHOzuhNr7gB3N3kiVrncmbGiZwSPzR03CfzxrOw5A3ebfX1bp9PYaCArmkNmZ6yiIHxQ3d7u32lOu6Q32iPhoeM/r4PneK6cm/bHTUcsbYTv2l0AWNSa9ZwV1kVmzhjbXsebDeTYY1HAfBpwXv8ecPvePu4dTSOjlxTgEpbye9/OJnfJV/HisIPyffn8vRR82od/1zWQ7yYPZH3umQQH5UQ1pdXlcugr5sx7egP6Zl06i/OuzbdV+31pvuuTx/o2hWm7Xgv6NQJLrgAHo7wXvz973D77bB5c3CFCvDgg8H29HQwZv/Me1c9e2JXrIh4cOeX/BW2gq8rVjIgfkhY+8nxQ2q93Ovq7Uk0Mcwueg6/9VMUKGRO0Yt09faqNQQAim0hDaMaR+yz1vJJ6Qesr/yO3rGnhPWlVa2n76ZWDEjvwI3ZF5FWub7O83m18B8kmQYc5+1W6zjXVMd9Vxmo4NuSlfRrEF7Dfg2G8GXx7t16eGvLP0nyNGJww/NDbR9ue4vjEnrxUvZfGfpNa0as7cSj6WMo8ReFbTs58/9I9bZnRJPLf/E41lre2vpPzmhyaY0wPSxUVMDKlTAk/L1gyBBYVst78emnMGDAjjAFGDoUMjJgw4Z6m+q+cH7Jn+fPxY+f5F0u6Zp5UvjE/37EbVrHtGdmi8Vcn/077t1yPQECHO/tzgspC2s9zoyCyWRVpXNu4uiw9oLANvptakWFLScKDxOaTubUhGGh/m6xfZiYPJ2jY45hiz+bZ/If5PzM/rzX6hsae5qGxn1QMo8xORdRakto7mnJjBaL9+vlvuq477bXsEl0+PGaRKewpSpyDXcWsAH+tfV5zmxyGd6o2FD7zxXrWV28FG9ULI+3n0OhP59Hf76RnMoMHu/wBhBcxb6bN5vZnVfv1lyXFy7m54qfOLfJVbt/goeS3Fzw+yFll/c+JQXer+W9yMqC1q1rjt/e16GD+3nuo3q5hwpgCF8RW2yNtu1yqrK4PfcPnJd4GSN8F1NkC5mUdy83ZF/IKy3+TZQJX0gvLJ7Dw3m38XSzWbSObhfWl2iSmJ+6mpJAEZ+UfcBDW8fROro9J8UPBggLBYDusX0ZmH4Uc4pe5KqG40Lt/eJOY37qavL8ucwqmsYN2Rcyt+WnNI9uudc12Ruq476rWa/aa7izTwoWklW5qUbIBQhgMPyl3SskeRoCcAfPcN36oWyp3EyU8XBv2hU83O4VGkRHXvnvau6WaRyf0IvOCd12a/wha9fLdGvrvnSPND5S+0HCeaA29iTjwUOOPyusPdefXWO1td2MwskkRPm4s8ljobZJzV6if3obVpYvo1fcyaH2hcVzGJc7mieSZ3B6woga+4oyUbSP6QjAcbHd+LHyW6Zs+0soCHbli0qkk/d4NlT9ENaeEOWjfVRH2sd0pHtcX05L78SsoucY0+ie3SvEPlId9932Gm6pCq/h1qrsGqvWSOZs+Qcn+PpzdPzxYe3J0S1pHtMqFKYAHeKOBSCrMo1SfzG5VZlcu+43of4AAQB6ro7mjWO+oX1c5x3zqczmo4J/cWfryXt+koeK5GTweIIry51lZ9dctW7XokXk8VD7NgeY83uoXuOli7cHS0sXh7UvLV1Mj7j+EbcptSV4CP+GePvP2z+IAPOKX+Pm3EuZmDyd4b4Ldms+lgAVtrzW/vJAGesq/0dzT90rpsAv7Mc11XHfxUR5OTahB8sLw2u4vHAxJ/gi13C77MoMlhbM57wmV9fo6+Y7iZzKjLB7phvLg4+mtYxpx/EJvXi98xpmdV4deg1sMILuvgHM6ryaVt7wS9W3t07Ha2IZ2uiivT3Vg5/XG3xManH4e8HixdC/lveiX7/gY1VlZeHjU1Ohfft6m+q+qJfnUK9qOI45RdOZVfgcP1Z8y/1bxpLtz2BUUvBxlMfy7uSSrB0rnUHxZ/B1xX95Kv9+fqr8ga/L/8ttuVeS6mnDr709AHinaBY351zC7Y0foU/sKeRUZZFTlUW+f2toP8/kP8TS0vdJq1zPjxXfMm3bE7xZNJNzfJeGxjy09VaWly1hU+VPrCr/jOtyLqA0UMx5icEvDgoDBTyedzeryj/j56o01pSv5M+5vyerKp0zfDseZ9kfVMd9d2mzcby9dTpztzzH+rJveSx9LDmVGaFHo57OuJNrfqy56v7XlueJj/JxeuOacx3WeBQNo5tyX9qVrCv9htVFnzDx57H8puEFNIlpTrzHR8f4LmGvJE8jfJ4kOsZ3ISbKG9qXtZY3tz7H0EYX4fMk1TjWtqqtfFeymnWlwacp0ip+5LuS1eRWZtUYe9AbNw6mT4fnnoNvvw0+QpWRAddWP6Z2550weKf3YtQoSEgIPir19dcwdy488khwP0fKJT/Amb6R5Pm38Ez+g+T4M/mVtwvPpywI3afLrspkY+W60Pj+8YN4KvkVni14jH9sm0iciadbbF+mpywiIcoHwMuFU6miiglbb2LC1ptC2/aJHcislh8BUGKLuGfLn8j0pxNn4jk65hieSJ7BiMSLQ+OzqtIZm3Mxef5cmnia0T22L3NbLg/NLZpofqj8hteznyffv4VGnqZ09fZiVsv/cKy3a32Uq1aq474b2ngk2/xbeC7rQXKrMukY14W/HbWAVG9wnrmVmWwqXxe2zfZv3Ic1viTiN+4JnkSmHv0+j/58I5d+34uk6Mac1vAcxrR8ZI/nt6LoI9LKf+Chti9F7F+y7W3u23Rl6OcHNgVXzNek3Me1Lcfv8fEOqJEjYcuW4KNPmZnQpQssWADtqu/fZ2bCup3ei4YNgyvS66+Hnj2hcePg86fjxkXe/0GgXp5DFXFtb59DlXAH9DnUw8X+fA5VRORIpUAVEXFEgSoi4ogCVUTEEQWqiIgjClQREUcUqCIijihQRUQcUaCKiDiiQBURcUSBKiLiiAJVRMQRBaqIiCMKVBERRxSoIiKOKFBFRBxRoIqIOKJAFRFxRIEqIuKIAlVExBEFqoiIIwpUERFHFKgiIo4oUEVEHFGgiog4okAVEXFEgSoi4ogCVUTEEQWqiIgjClQREUcUqCIijihQRUQcUaCKiDiiQBURcUSBKiLiSHRdnWt+DR1W7K+pHL7yGh/oGRz62m840DMQ+WVaoYqIOKJAFRFxRIEqIuKIAlVExBEFqoiIIwpUERFHFKgiIo4oUEVEHFGgiog4okAVEXFEgSoi4ogCVUTEEQWqiIgjClQREUcUqCIijihQRUQcUaCKiDiiQBURcUSBKiLiiAJVRMQRBaqIiCMKVBERRxSoIiKOKFBFRBxRoIqIOKJAFRFxRIEqIuKIAlVExBEFqoiIIwpUERFHFKgiIo4oUEVEHFGgiog4okAVEXFEgSoi4sjBH6hTpkCHDhAXBz16wMcf1z1+zRoYOBDi46FVK5gwAazdP3OtB8+VT+GEgg60yI/j1MIeLKuq+/w/qHyXIYX9aJOfxNHbkhlVdDY/+r8PG/N6xSsMKOhGan4Cnbe14I/Fl7I5kBXqf7F8GsMKB9BhWxPa5TfirKLT+LRqadg+ppVP5qSCrrTNb0Db/AYMKezHu5Xzw8ZcV3wFjfNN2Ov0wr77WJE9N4UpdKADccTRgx58TN01fI3X6EY3EkigHe2YyMRaxy5lKdFE04UuYe3f8A0XcAFHcRQGw3jG19j2P/yHEYygFa0wGKYzvcaYIoq4kRtpTWviiacznZnEpN0674PSYf77fHAH6uzZMHYs3HUXrFoF/fvDsGGQlhZ5fEEBnH46pKTAF1/A00/DxInw17/u33k7MrdiNneWjmVc7F0sSVpFb09/LiwaxqZA5PPf6P+JS4rPpm/0AJYkreIt3/uUUcqFxcNDY5ZXfcK1JaO52Hs5nyZ9w0u+t/gusJY/llwSGrO06iPO9Y7kX74PeD/pMzpGdeaCoqGs8/8QGtMqqjXj4x/lo6T/8u+kFQyIHsSlxefwtf+rsDmdGv0b/tcgM/R6zbfAcZXqNpvZjGUsd3EXq1hFf/ozjGGkEbmGC1nIKEbxR/7I13zNFKYwiUk8wzM1xuaRx2VcxmAG1+groYT2tOdBHqQDHSIeq4giutCFp3iKeOIjjhnHOOYzn5nM5Fu+5f/4P+7gDmYycw+qcJA4En6frbW1vujRo/bO/fHq3dty1VXhbR07Wu64I/L4KVMsSUmWkpIdbQ88YElNtQQCB+w88hrt3auHp7e9zHtVWNtRUR3tTbF3RBw/PeF1G0WUzW1YFWp72/dvC9gfG+TYvEbWToibaFubtmHbPRP/vPXhq3UeWxsGbHOTYh+Nf7rO+TYyje1f46eGfr445nI7JPqMvT7/nV97W/ze9LZXcVVYW0c62ju4I+L4i7nYnsM5YW1P87RtTWsbIBDWfi7n2vGMt/dxnz2e42udw/Ecb+/jvjrn6cNnX+CFiNvey71hbadwir2e6/eqHntZRjevw+T3mR49bG1dB+8KtaICVq6EIUPC24cMgWXLIm/z6acwYEDw8mC7oUMhIwM2bKi3qdaHClvBav9KTosOP//ToofweVXk8+/u6UkMMcyoeA6/9VNoC3m14kVO9PSiaVQyAH2iT2KzzWRh5TtYa9kSyGVu5SxOjxkecZ8AFVRQZstoaBpH7PdbP3MqZlFsi+gd3T+sb3nVUjpta07Pgl8xtuRqcgLZe1KGfVJBBStZyRDCaziEISwjcg3LKSeOuLC2eOJJJ52NbAy1TWEKWWRxN3e7n/hOTuZk3uEdNrEJgGUsYzWr+S2/rdfjOneE/D4fvIGamwt+f3C5v7OUFMjKirxNVlbk8dv7DiFbbC5+/DSLCj+f5lEpZNvI59LW0565iYt5pOw+UrbF0m5bQ9YG1jDLNy80pnd0P55LeJVrii+h+TYvHQuaYbFMSXix1rk8WHY3iSaRYTEjwtq/8a+hdX4iKdtiGVdyLTN9b3K859eh/sExv+Xvvhm8lfgBD8Q/wcqqzxlRNIhyW743JdljuQRrmEJ4DVNIIYvINRzKUN7iLd7jPQIE+J7veYInAMgkE4A1rOF+7udlXsaDp17P4WmephvdaEtbYohhIAN5lEc5kzPr9bjOHSG/zwdvoG5nTPjP1tZs+6XxkdoPEYbweVtsjbbtNgeyGFPyB0Z6L+PfiV/wTuJHJJLElcUXErABAP7nX8sdpWO4Ne4ePkxayRu+RWwOZHFzyTUR9zm1/CleLH+WGb65NDANwvo6RXXmP0mrWZy4nN/H/onrSi5nrf/rUP/53osYHjOC4z2/ZljMWbyeuJAfA9/x3i5fXtW3Panh1VzNGMZwNmfjxUtf+nIRFwHgwUM55VzERTzO47XeG3Xpb/yNT/iEt3mblaxkEpO4lVtZxKJ6P3a9OMx/n6MP9ARqlZwMHk/Nv0TZ2TX/am3XokXk8VD7NgeppiYZDx6yA+HnkxPIppmJfC7PlU8mwfiYEP9YqO1Z30t0KWjDZ/5l9Is+mUllD3NidG/GxN0GQBdPVxKMj+FFA7g78BCto9qEtp1a/hQPld7Na4kL6RHdu8bxvMbLUZ6OAHSP7skq/xf8vXwSf0v4Z8T5tYxKJTWqNesCP0Tsdy2ZYA13XY1mk11j1bqdwfAoj/IX/kIWWTSjGR/wAQDtaU8mmaxlLVdW/wMQIIDFEk00C1hQ4xbD3iqllDu5k9d5nbM4C4CudGU1q3mcxw+ty/4j5Pf54F2her3BxyoWLw5vX7w4+O1gJP36BR/DKCsLH5+aCu3b19tU64PXeOnm6cFHVeHn/1HV4hr3KbcrpaTGJej2nwMEfnGMZcfjKJPL/sqDpf/HrMT59Is+ebfmHCBQ5+X8lkAumYGfaRHVcrf2t6+8eOlBDxYTXsPFLKY/tXyGqnnw0IpWePHyKq/Sj340pzmtaMUa1rB6p3+u5Vo60pHVrP7F/e6Jyup/Ir1f29/PQ8aR8vtc15dZB/xb/lmzLDExlmnTLGvXWsaMsfh8lg0bgv133GEZNGjH+Px8S0qKZeRIy5o1ljlzgt8SPv74AT2Pvf1m+58Js2wMMfap+Gl2edJae413jPXhs1822GDzGll7U+wd9pToQaHx//J9YA3G3hE33q5I+t5+lLjSDo4ealuZNja9YZHNa2Tt5PgXbDTR9vH4KXZV0jq7MHGp7e7paU/wnBjaz/1xj9kYYuzzCbPt/xpkhl4bGuaHxoyNvd3OT/yP/TLpJ7s06St7U+wd1mDsa74FNq+RtZsaFtobYm+x7yYus18m/WTf8X1oe3n62lTTyqY1LNhv3/LPIljDaUyza1lrxxCs4QY2WIu1d3CHHcSg0PgccuwUpti1rLWrWGXHMMbGEWc/47NajxHpW/5yyu0qVtlVrLJHc7S9hmvsKlbZH/ghNKaQwtCYeOLt/dxvV7HKbmRjaMxABtrjOd5+yId2PevtC7xg44izT/P0XtXjQP4eHC6/z3V9y1/ndgc8UK21TJ5sadfO4vVaTjzRsmTJjr7LLw/27Tz+q68sAwZYYmMtLVpYxo8/sI9Y2H17XGhi/GTbxrSzXrz2BM+Jdl7ikrDHktqYdmHjn0t41Xb1dLc+fLapSbZDo8+0nyZ9Ezbm0fin7TFRx9l44m2KaWHPj7nYft1gU6i/jWlngRqvi2MuDzt2a9PWevHaZNPMDowebN/wLQr1ZzQssYOih9hk08zGEGNbm7b24pjL7ZoGafv1sSmLtZOZbNsRrOGJnGiXsCTUdzmX23a0C/2cQ47tS1/rw2cTSLCDGWyXs7zO/UcK1J/4KWINBzIwNOZDPow45nIuD43JJNNewRU2lVQbR5ztTGc7kYk1HuHa3deB/D3gMPl9ritQjbW1/78OTM+elhUr6nOBfETIi/y0keyBRvkHegaHB3Pw/p+MDh09e2JXrIj4rdjBew9VROQQo0AVEXFEgSoi4ogCVUTEEQWqiIgjClQREUcUqCIijihQRUQcUaCKiDiiQBURcUSBKiLiiAJVRMQRBaqIiCMKVBERRxSoIiKOKFBFRBxRoIqIOKJAFRFxRIEqIuKIAlVExBEFqoiIIwpUERFHFKgiIo4oUEVEHFGgiog4okAVEXFEgSoi4ogCVUTEEQWqiIgjClQREUcUqCIijihQRUQcUaCKiDiiQBURcUSBKiLiiLHW1t5pTA6wcf9NR0TkoNfOWtssUkedgSoiIrtPl/wiIo4oUEVEHFGgiog4okAVEXFEgSoi4sj/A5948a2yo56lAAAAAElFTkSuQmCC",
      "text/plain": [
       "<Figure size 432x432 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "PolicyIterator(env, gamma=1, improvementIterations=10000, eps=1e-20, evaluationIterations=100)\n",
    "\n",
    "optimalPolicy = policyIteration(env=env, gamma=gamma, improvementIterations=improvementIterations, eps=eps)\n",
    "PolicyValue = get_value_function(env=env, policy=optimalPolicy, gamma=gamma, eps=eps)\n",
    "\n",
    "plot_values(PolicyValue)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#Comparing the value and policy iteration methods.\n",
    "\n",
    "Lastly, please try to play around with the FrozenLake environment with different configurations (gamma, improvement/evaluation iterations, random seed)and with value and policy iteration. Please try your best to get a policy with score as high as possible (though your grades will not be affected by this score). Repeat each experiment with 5 different random seed, then report the highest score you've achieved across the 5 repeats with 1 standard deviation and write (a few sentence) to compare the two iteration methods."
   ]
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "61dd0e9fca73d993dce8fd26eb066813c398e8547ba5df7c5876aeaa35e9886b"
  },
  "kernelspec": {
   "display_name": "Python 3.8.8 ('base')",
   "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.8.8"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}