07_tutorial_MazePolicyGradient.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Reinforcement Learning: Using Policy Gradient to solve a Maze\n",
    "\n",
    "This does not even use a neural network, but instead the policy is stored in an array (table-based policy gradient)."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Example code for the lecture series \"Machine Learning for Physicists\" by Florian Marquardt\n",
    "\n",
    "Lecture 7, Tutorial (this is discussed in session 7)\n",
    "\n",
    "See https://machine-learning-for-physicists.org and the current course website linked there!\n",
    "\n",
    "This notebook is distributed under the Attribution-ShareAlike 4.0 International (CC BY-SA 4.0) license:\n",
    "\n",
    "https://creativecommons.org/licenses/by-sa/4.0/"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This notebook shows how to:\n",
    "- use policy gradient reinforcement learning to solve a given (fixed) maze (policy gradient based on a table, i.e. state space is sufficiently small)\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A little robot is sent through a maze, to collect treasure chests. The maze and the distribution of treasure chests are fixed (i.e. in every trial the robot encounters the same maze). \n",
    "\n",
    "Will it be able to find the best strategy?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "import matplotlib\n",
    "matplotlib.rcParams['figure.dpi']=90 # highres display\n",
    "\n",
    "# for subplots within subplots:\n",
    "from matplotlib import gridspec\n",
    "\n",
    "from IPython.display import clear_output\n",
    "from time import sleep"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Maze generation algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Maze generation algorithm from wikipedia\n",
    "# the code was removed in January 2020, but you can still\n",
    "# access it under this link:\n",
    "# https://en.wikipedia.org/w/index.php?title=Maze_generation_algorithm&oldid=930153705\n",
    "\n",
    "def maze(width=81, height=51, complexity=.75, density=.75):\n",
    "    # Only odd shapes\n",
    "    shape = ((height // 2) * 2 + 1, (width // 2) * 2 + 1)\n",
    "    # Adjust complexity and density relative to maze size\n",
    "    complexity = int(complexity * (5 * (shape[0] + shape[1]))) # number of components\n",
    "    density    = int(density * ((shape[0] // 2) * (shape[1] // 2))) # size of components\n",
    "    # Build actual maze\n",
    "    Z = np.zeros(shape, dtype=bool)\n",
    "    # Fill borders\n",
    "    Z[0, :] = Z[-1, :] = 1\n",
    "    Z[:, 0] = Z[:, -1] = 1\n",
    "    # Make aisles\n",
    "    for i in range(density):\n",
    "        x, y = np.random.randint(0, shape[1] // 2) * 2, np.random.randint(0, shape[0] // 2) * 2 # pick a random position\n",
    "        Z[y, x] = 1\n",
    "        for j in range(complexity):\n",
    "            neighbours = []\n",
    "            if x > 1:             neighbours.append((y, x - 2))\n",
    "            if x < shape[1] - 2:  neighbours.append((y, x + 2))\n",
    "            if y > 1:             neighbours.append((y - 2, x))\n",
    "            if y < shape[0] - 2:  neighbours.append((y + 2, x))\n",
    "            if len(neighbours):\n",
    "                y_,x_ = neighbours[np.random.randint(0, len(neighbours) - 1)]\n",
    "                if Z[y_, x_] == 0:\n",
    "                    Z[y_, x_] = 1\n",
    "                    Z[y_ + (y - y_) // 2, x_ + (x - x_) // 2] = 1\n",
    "                    x, y = x_, y_\n",
    "    return Z\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ True,  True,  True,  True,  True],\n",
       "       [ True, False, False, False,  True],\n",
       "       [ True,  True,  True, False,  True],\n",
       "       [ True, False, False, False,  True],\n",
       "       [ True,  True,  True,  True,  True]])"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "maze(width=5,height=5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAF0CAYAAADYVHlQAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjcuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/bCgiHAAAACXBIWXMAAA3XAAAN1wFCKJt4AAAXxElEQVR4nO3df0xV9/3H8ddFkSj3woXEHyCWuc6qabTYmEWzbNrFzPWPZc6lsXGdcwkMg9yujfvDrDIvlSmatI2RNCYG15EsVfuH/WP74+vYYqa2wWYLuNSUUZOVGI12Uy9cKcItn+8fi7dzFbhXDtxz3jwfyUngnsvhfT/n9NWPh/u+n5BzzgkAYEpergsAAHiPcAcAgwh3ADCIcAcAgwh3ADCIcAcAgwh3ADCIcAcAg2bmuoD7QqFQrksAgMAYr//U03AfHh7Wyy+/rN/97ncKhUL60Y9+pDfeeEMzZ2b2az6//jUvywEAk2aUfTzuczy9LdPU1KTz58/r8uXL+vDDD3Xu3Dnt37/fy18BAMiAp+F+/Phx7dmzR2VlZSorK9Mrr7yi1tZWL38FACADnoX77du3dfXqVVVVVaUfq6qqUm9vrxKJxJeeH4/HFQqF0hsAwDuehXsymZQkRaPR9GP3v+7v7//S8+PxuJxz6Q0A4B3Pwj0cDkvSA7P0+19HIhGvfg0AIAOehXtJSYkqKirU2dmZfqyzs1OLFi1ScXGxV78GAJABT98K+dOf/lS//vWv9Y1vfEOStH//flVXV3t2/I3lVZ4dCwD86P+udXpyHE/DvaGhQf/+97+1fPlySdILL7ygX/7yl17+CgBABkJ+WWYvFAqN28TEzB2AdZnM3GeUfTzuG1H4bBkAMIhwBwCDCHcAMIhwBwCDCHcAMIhwBwCDCHcAMMg3KzF5KdMOr0zeN+9VtxgATGWvDjN3ADCIcAcAgwh3ADCIcAcAgwh3ADCIcAcAgwh3ADCIcAcAgwh3ADDIZIdqLrBKFAA/YeYOAAYR7gBgEOEOAAYR7gBgEOEOAAYR7gBgEOEOAAYR7gBgEE1MHmE5vtxhuUQEBcvsAQAmhHAHAIMIdwAwiHAHAIMIdwAwiHAHAIMIdwAwiHAHAIMIdwAwiA5Vj7DMng2cR1jBzB0ADPIs3Ldv365Zs2YpHA6nt/fff9+rwwMAsuDpzL2urk7JZDK9rV271svDAwAyxG0ZADDI03Bva2tTaWmpnnzySb322msaGRkZ9bnxeFyhUCi9AQC841m4v/jii+ru7tann36q1tZWHT58WIcPHx71+fF4XM659AYA8I5n4f70009r7ty5mjFjhtasWaPdu3fr5MmTXh0eAJCFSbvnnpfH7XwAyBXPmphOnTql7373u4pEIvrrX/+q5uZm7dy506vD+55fl3FjCTrvMV6Tw8tr1a/X/VQ2yXkW7i0tLfrZz36mVCqlhQsXqq6uTrt27fLq8ACALHgW7n/5y1+8OhQAYIK4MQ4ABhHuAGAQ4Q4ABhHuAGAQ4Q4ABhHuAGAQ4Q4ABrHM3jj8uuyal911QX+NU12/X8cLkyOo55uZOwAYRLgDgEGEOwAYRLgDgEGEOwAYRLgDgEGEOwAYRLgDgEGBamLKxbJY02FJtaAvNxbkhq7pcH0FXVCvL2buAGAQ4Q4ABhHuAGAQ4Q4ABhHuAGAQ4Q4ABhHuAGAQ4Q4ABhHuAGBQoDpU/bzclZ9rG49fa/drF2su+PUcBZn164uZOwAYRLgDgEGEOwAYRLgDgEGEOwAYRLgDgEGEOwAYRLgDgEGBamLKlB8bCiT/1hV0fm1GCXJdXKvBx8wdAAzKONxbWlq0evVqFRQUaNOmTQ/s6+vr09atW1VUVKT58+dr3759XtcJAMhCxrdlysvLtWfPHrW3t+vq1asP7IvFYrp165Z6e3t18+ZNbdiwQZWVldq2bZvnBQMAxpdxuG/evFmS1NnZ+UC4DwwM6MSJE7pw4YKi0aii0ahisZhaW1sJdwDIkQnfc+/u7tbQ0JCqqqrSj1VVVenSpUtj/lw8HlcoFEpvAADvTDjck8mkCgsLNXPmF/8IiEaj6u/vH/Pn4vG4nHPpDQDgnQmHezgc1sDAgFKpVPqxRCKhSCQy0UMDAB7RhMN96dKlys/PV1dXV/qxzs5OrVixYqKHBgA8oozDPZVKaXBwUKlUSiMjIxocHNTQ0JDmzJmjLVu2qKGhQYlEQj09PTpy5Iiqq6sns24AwBgyfrdMU1OTGhsb09/Pnj1b69at09mzZ9XS0qLa2lpVVFRo9uzZqq+vz+k7ZYLcGYgv+HXsqSt3Mn2Nfq1/KmUc7vF4XPF4/KH7ioqK9Pbbb3tVEwBggvj4AQAwiHAHAIMIdwAwiHAHAIMIdwAwiHAHAIMIdwAwiGX2plAu6mJJtf/wa/NLLuqaDkv2+fWansrri5k7ABhEuAOAQYQ7ABhEuAOAQYQ7ABhEuAOAQYQ7ABhEuAOAQYQ7ABhkskM1U1PdjejXLsNMsXSZ97wcU79eX369bvzatewVZu4AYBDhDgAGEe4AYBDhDgAGEe4AYBDhDgAGEe4AYBDhDgAGBaqJieW6/I/mqi/49drxa7OTl/z6GllmDwAwIYQ7ABhEuAOAQYQ7ABhEuAOAQYQ7ABhEuAOAQYQ7ABhEuAOAQYHqUM1FJ6Jfux+DbjqMa5BfY5Brz5Rfu1i9wswdAAzKONxbWlq0evVqFRQUaNOmTQ/sW79+vQoKChQOh9PbtWvXvK4VAJChjMO9vLxce/bsUU1NzUP3Hzx4UMlkMr2Vl5d7ViQAIDsZ33PfvHmzJKmzs1NXr16dtIIAABPn2T33pqYmlZaWatWqVWpraxv3+fF4XKFQKL0BALzjSbgfOHBAV65c0Y0bN9Tc3KxYLKbTp0+P+TPxeFzOufQGAPCOJ+G+du1aFRcXKz8/Xxs3blRtba1OnjzpxaEBAI9gUt4KmZfHOywBIJcy/oNqKpVKbyMjIxocHFReXp4GBgb03nvvpd8OefbsWR09elTHjh2bzLrH5MeGgmxk0lwxHZYcDPp59Gv9fr2+4K2Mw72pqUmNjY3p72fPnq1169bpnXfeUWNjo55//nlJ0le+8hW9/vrreu6557yvFgCQkYzDPR6PKx6PP3RfR0eHV/UAADzAzXEAMIhwBwCDCHcAMIhwBwCDCHcAMIhwBwCDCHcAMChQy+xlajosEZapII+FX2v3a125wFj4FzN3ADCIcAcAgwh3ADCIcAcAgwh3ADCIcAcAgwh3ADCIcAcAgwLVxDRdlv7ysjFkOoyZX5eN82tdUy3or9HL8ziVTV/M3AHAIMIdAAwi3AHAIMIdAAwi3AHAIMIdAAwi3AHAIMIdAAwi3AHAoEB1qLKk1xemw1j4tas0F/xaVyb8WnvQO2fHw8wdAAwi3AHAIMIdAAwi3AHAIMIdAAwi3AHAIMIdAAwi3AHAoEA1MWXKenNCNljqzXt+XFJNCv555Fr1FjN3ADAo43C/d++eampqtHjxYkUiES1btkzHjx9P7+/r69PWrVtVVFSk+fPna9++fZNSMABgfBnflkmlUiorK1N7e7u++tWvqqOjQ88++6wqKir0ne98R7FYTLdu3VJvb69u3rypDRs2qLKyUtu2bZvM+gEAD5HxzL2wsFCvvvqqHn/8cYVCIa1Zs0bPPPOMzp8/r4GBAZ04cUJNTU2KRqN64oknFIvF1NraOpm1AwBG8cj33AcHB3Xx4kWtXLlS3d3dGhoaUlVVVXp/VVWVLl26NOrPx+NxhUKh9AYA8M4jhbtzTtXV1VqyZIk2b96sZDKpwsJCzZz5xV2eaDSq/v7+UY8Rj8flnEtvAADvZP1WSOec6urq1N3drfb2duXl5SkcDmtgYECpVCod8IlEQpFIxPOCAQDjy2rm7pzTzp071dHRoTNnzqi4uFiStHTpUuXn56urqyv93M7OTq1YscLbagEAGckq3Ovr63XhwgX98Y9/VElJSfrxOXPmaMuWLWpoaFAikVBPT4+OHDmi6upqzwsGAIwv49syn3zyid58800VFBSosrIy/fgLL7ygo0ePqqWlRbW1taqoqNDs2bNVX1/v+7dB+nX5L79ivLyXizEN8nkMcu1TLeNwr6ysHPMPn0VFRXr77bc9KQoAMDF8/AAAGES4A4BBhDsAGES4A4BBhDsAGES4A4BBhDsAGGRymb1Meblkl1+XCPOy6cOvS5z59TVO9fWVKb9e9379byiomLkDgEGEOwAYRLgDgEGEOwAYRLgDgEGEOwAYRLgDgEGEOwAYRLgDgEEmO1T92s2XqaleSsyvS5f5tcPTS9PhNeYCY8HMHQBMItwBwCDCHQAMItwBwCDCHQAMItwBwCDCHQAMItwBwCCTTUxBX4rLr/VP9ZJqXgp6M1qQrwm/Cvo1MR5m7gBgEOEOAAYR7gBgEOEOAAYR7gBgEOEOAAYR7gBgEOEOAAYR7gBgkMkO1UyxnN304dduUb9eE37tiPWSX8feK8zcAcCgjMP93r17qqmp0eLFixWJRLRs2TIdP348vX/9+vUqKChQOBxOb9euXZuUogEAY8s43FOplMrKytTe3q6+vj699dZb2rVrl86cOZN+zsGDB5VMJtNbeXn5pBQNABhbxuFeWFioV199VY8//rhCoZDWrFmjZ555RufPn5/M+gAAj+CR77kPDg7q4sWLWrlyZfqxpqYmlZaWatWqVWpraxvz5+PxuEKhUHoDAHjnkcLdOafq6motWbJEmzdvliQdOHBAV65c0Y0bN9Tc3KxYLKbTp0+Peox4PC7nXHoDAHgn63B3zqmurk7d3d169913lZf3n0OsXbtWxcXFys/P18aNG1VbW6uTJ096XjAAYHxZvc/dOaedO3eqo6NDf/rTn1RcXDzqc++HPgBg6mUV7vX19bpw4YL+/Oc/q6SkJP34nTt39N5776XfDnn27FkdPXpUx44d87zgqTYdmjmmg1ws/+fXa8d684409Y1mflxeMuPp9SeffKI333xT3d3dqqysTL+XfceOHRoeHlZjY6MWLFigkpISvfzyy3r99df13HPPTWbtAIBRZDxzr6ysHPMPnx0dHZ4UBACYOG6MA4BBhDsAGES4A4BBhDsAGES4A4BBhDsAGES4A4BB03qZvUxMh24+ZMev14Rfl//z67H82kHsFWbuAGAQ4Q4ABhHuAGAQ4Q4ABhHuAGAQ4Q4ABhHuAGAQ4Q4ABk3rJibrTQxe8+tyY16eR79eE34dLy95eX2BmTsAmES4A4BBhDsAGES4A4BBhDsAGES4A4BBhDsAGES4A4BBhDsAGGSyQ9Wvy6D51XRYnm068Ot45aKrdKrHwo9jz8wdAAwi3AHAIMIdAAwi3AHAIMIdAAwi3AHAIMIdAAwi3AHAoJBzzuW6CEkKhUL6/PrXcl2GOSxdZgPn0QavzuOMso81XnQzcwcAg7IK91gspkWLFqmoqEgLFy7USy+9pKGhIUlSX1+ftm7dqqKiIs2fP1/79u2blIIBAOPLKtzr6ur00Ucfqa+vT11dXerq6tKhQ4ck/Sf4b926pd7eXp07d07Hjh1TW1vbpBQNABhbVh8ctnz58vTXzjnl5eWpp6dHAwMDOnHihC5cuKBoNKpoNKpYLKbW1lZt27bN86IBAGPL+p57c3OzwuGw5s2bp66uLsViMXV3d2toaEhVVVXp51VVVenSpUujHicejysUCqU3AIB3sg733bt3K5lM6vLly9qxY4cWLFigZDKpwsJCzZz5xT8EotGo+vv7Rz1OPB6Xcy69AQC888jvllm+fLmeeuopbd++XeFwWAMDA0qlUun9iURCkUjEkyIBANmZ0Fshh4eH1dPTo6VLlyo/P19dXV3pfZ2dnVqxYsWECwQAZC/jcE8mk/rNb36jO3fuyDmnv//972pqatLGjRs1Z84cbdmyRQ0NDUokEurp6dGRI0dUXV09mbUDAEaRcYfq3bt3tWnTJv3tb3/TvXv3NG/ePP3whz9UY2Oj5syZo76+PtXW1ur3v/+9Zs+erfr6ev3qV7/KvJAMOlT9uJQVAHjJqw7VQH38AOEOwDo+fgAAMCrCHQAMItwBwCDCHQAMItwBwCDCHQAMItwBwKCsPvI3KFhuDIAfTWWvDjN3ADCIcAcAgwh3ADCIcAcAgwh3ADCIcAcAgwh3ADCIcAcAgwh3ADDIZIcqKzYBmO6YuQOAQYQ7ABhEuAOAQYQ7ABhEuAOAQYQ7ABhEuAOAQYQ7ABgUcs65XBchSaFQSJ9f/1quywAA35tR9rHGi25m7gBgEOEOAAYR7gBgEOEOAAYR7gBgEOEOAAYR7gBgEOEOAAYR7gBgkK86VAEAmRkvun2zhur/FhoKhcYt3s+CXH+Qa5eCXX+Qa5eCXX+Qa38YbssAgEGEOwAY5Ntw37t3b65LmJAg1x/k2qVg1x/k2qVg1x/k2h/GN39QBQB4x7czdwDAoyPcAcAgwh0ADCLcAcAgwh0ADPJduA8PD6u+vl4lJSUqLS1VLBZTKpXKdVkZ2b59u2bNmqVwOJze3n///VyXNaqWlhatXr1aBQUF2rRp0wP7+vr6tHXrVhUVFWn+/Pnat29fboocxVi1r1+/XgUFBQ+ch2vXruWm0Ie4d++eampqtHjxYkUiES1btkzHjx9P7/f72I9Xv9/HPxaLadGiRSoqKtLChQv10ksvaWhoSJL/xz4bvgv3pqYmnT9/XpcvX9aHH36oc+fOaf/+/bkuK2N1dXVKJpPpbe3atbkuaVTl5eXas2ePampqvrQvFovp1q1b6u3t1blz53Ts2DG1tbXloMqHG6t2STp48OAD56G8vHyKKxxdKpVSWVmZ2tvb1dfXp7feeku7du3SmTNnJPl/7MerX/L3+NfV1emjjz5SX1+furq61NXVpUOHDkny/9hnxflMRUWFe+edd9Lfnzp1yj322GM5rChzP/nJT9zPf/7zXJeRtb1797rvf//76e/v3r3rZs2a5T744IP0Y4cOHXLf+ta3clDd2P63duecW7dunXvjjTdyUs+j+sEPfuAaGhoCNfb/7X79zgVr/G/evOm+/e1vu23btgV27Efjq5n77du3dfXqVVVVVaUfq6qqUm9vrxKJRO4Ky0JbW5tKS0v15JNP6rXXXtPIyEiuS8pad3e3hoaGvnQeLl26lLuistTU1KTS0lKtWrXK9zOvwcFBXbx4UStXrgzk2P93/ff5ffybm5sVDoc1b948dXV1KRaLBXLsx+KrcE8mk5KkaDSafuz+1/39/TmoKDsvvviiuru79emnn6q1tVWHDx/W4cOHc11W1pLJpAoLCzVz5hcfGhqNRgNxDiTpwIEDunLlim7cuKHm5mbFYjGdPn0612U9lHNO1dXVWrJkiTZv3hy4sf/f+qVgjP/u3buVTCZ1+fJl7dixQwsWLAjc2I/HV+EeDocl6YFZ+v2vI5FITmrKxtNPP625c+dqxowZWrNmjXbv3q2TJ0/muqyshcNhDQwMPPCH7EQiEYhzIElr165VcXGx8vPztXHjRtXW1vryPDjnVFdXp+7ubr377rvKy8sL1Ng/rH4pOOMvScuXL9dTTz2l7du3B2rsM+GrcC8pKVFFRYU6OzvTj3V2dmrRokUqLi7OXWGP6P7FHjRLly5Vfn6+urq60o91dnZqxYoVOazq0fnxPDjntHPnTnV0dOjMmTPp6zsoYz9a/Q/jx/H/b8PDw+rp6QnM2Gcslzf8H6ahocGtWrXKXb9+3V2/ft2tWrXKNTY25rqsjJw8edIlEgk3MjLiPvjgA1dZWekOHTqU67JGNTw87D777DP3yiuvuO9973vus88+c/fu3XPOOffjH//YPfvss+7OnTvuH//4h3vsscfcb3/72xxX/IXRar99+7b7wx/+4O7evetSqZRrb293xcXF7tSpU7ku+QF1dXVu5cqV7l//+teX9vl97J0bvX6/j39/f787fvy4u337thsZGXGXLl1yy5cvdzU1Nc65YIx9pnwX7kNDQ66urs5Fo1EXjUZdfX29Gx4eznVZGfnmN7/piouLXWFhoXviiSfcwYMH3eeff57rska1d+9eJ+mBbd26dc455xKJhHv++eddOBx2c+fO9d3/YEer/ebNm+7rX/+6i0QiLhKJuBUrVrjW1tZcl/uAf/7zn06SKygocIWFhemttrbWOef/sR+rfr+PfzKZdBs2bHClpaWusLDQLV682P3iF79wd+/edc75f+yzwUf+AoBB/r4ZBgB4JIQ7ABhEuAOAQYQ7ABhEuAOAQYQ7ABhEuAOAQYQ7ABhEuAOAQYQ7ABj0/6f8UsuuK7qtAAAAAElFTkSuQmCC",
      "text/plain": [
       "<Figure size 576x432 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.imshow(maze(width=35,height=35))\n",
    "plt.show()"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Do a little random walk inside the maze"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAF0CAYAAADYVHlQAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjcuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/bCgiHAAAACXBIWXMAAA3XAAAN1wFCKJt4AAASt0lEQVR4nO3da2xU9brH8d8o0thO7QwMYmuhGy2IF7AkJJI0IgToiS8MSKQYQkyILZrSNoIm3igMCH0hm2ACNRiV7HgJbnmDGBNuygtKpCg4aiBpaIQ29HBRW6YXOpYJ67w4x9khcmSU/3TRp99PspJ2Zlj/Z7D5slwzsxrwPM8TAMCUW/weAADgHnEHAIOIOwAYRNwBwCDiDgAGEXcAMIi4A4BBxB0ADBrm9wC/CwQCfo8AAIPG9T5/etPEXZL+8dY//R4BAG56p1946bqP4bQMABhE3AHAIOIOAAYRdwAwiLgDgEHEHQAMIu4AYBBxBwCDiDsAGJR23Lds2aKpU6cqKytL8+bNu+q+rq4uLVq0SHfccYdGjx6tN954w/WcAIC/IO3LDxQUFGjlypXav3+/zpw5c9V9NTU16ujoUFtbmy5cuKDZs2erqKhIzzzzjPOBAQDXl3bc58+fL0mKxWJXxf3SpUv65JNPdOjQIYVCIYVCIdXU1Oj9998n7gDgkxs+597c3Kz+/n6VlJSkbispKdEPP/xwo7sGAPxNNxz3np4e5eTkaNiw//xPQCgUUnd395/+uWg0qkAgkNoAAO7ccNyDwaAuXbqkZDKZui0ejys3N/dP/1w0GpXneakNAODODcf9vvvu02233abvv/8+dVssFtOkSZNudNcAgL8p7bgnk0klEgklk0lduXJFiURC/f39ys7O1sKFC1VXV6d4PK6TJ09q8+bNqqioyOTcAIA/kXbc161bp9tvv13r16/X559/rttvv11lZWWS/vc98Hl5eSosLFRpaameffZZ3ikDAD4KeDfJCe9AIMCv2QOANJx+4aXrvlbJ5QcAwCDiDgAGEXcAMIi4A4BBxB0ADCLuAGAQcQcAg4g7ABiU9vXcrSpeftjvEQAMYi2bpvk9wjVx5A4ABhF3ADCIuAOAQcQdAAwi7gBgEHEHAIOIOwAYRNwBwCDiDgAGEXcAMIi4A4BBxB0ADCLuAGAQcQcAg4g7ABhE3AHAIOIOAAYRdwAwiLgDgEHEHQAMIu4AYBBxBwCDiDsAGETcAcAg4g4ABhF3ADCIuAOAQcQdAAwi7gBgEHEHAIOG+T3AUNayaZrfIwAmFC8/7PcINx2O3AHAIOIOAAYRdwAwiLgDgEHEHQAMIu4AYBBxBwCDiDsAGETcAcAg4g4ABhF3ADDIadzb29s1b948jRw5UpFIROXl5fr5559dLgEASIPTuC9btkyS1NraqlOnTimRSKi2ttblEgCANDiN+08//aTy8nIFg0Hl5uZq4cKF+vHHH10uAQBIg9O4r1ixQjt27FA8HtfFixe1fft2PfHEE9d8bDQaVSAQSG0AAHecxr20tFQXLlxQOBzWiBEj1NnZqVdfffWaj41Go/I8L7UBANxxFvcrV65ozpw5Ki0tVU9Pj3p6elRaWqqysjJXSwAA0uQs7h0dHWptbVVtba2ys7OVnZ2tmpoaNTU16ZdffnG1DAAgDc7iHolEVFxcrIaGBiUSCSUSCTU0NKiwsFCRSMTVMgCANDg95/7ZZ5/p2LFjuvvuu5Wfn68jR45o165dLpcAAKTB6S/IfuCBB7Rnzx6XuwQA/A1cfgAADCLuAGAQcQcAg4g7ABhE3AHAIOIOAAYRdwAwiLgDgEFOP8SEwaF4+WG/R4BRLZum+T0C/g9H7gBgEHEHAIOIOwAYRNwBwCDiDgAGEXcAMIi4A4BBxB0ADCLuAGAQcQcAg4g7ABhE3AHAIOIOAAYRdwAwiLgDgEHEHQAMIu4AYBBxBwCDiDsAGETcAcAg4g4ABhF3ADCIuAOAQcQdAAwi7gBgEHEHAIOIOwAYRNwBwCDiDgAGDfN7AAwdLZum+T0CMGRw5A4ABhF3ADCIuAOAQcQdAAwi7gBgEHEHAIOIOwAYRNwBwCDiDgAGEXcAMIi4A4BBzuO+a9culZSUKCcnRwUFBdq6davrJQAA1+H0wmG7d+9WVVWVPvroIz366KPq6urS+fPnXS4BAEiD07jX1dVp1apVmjFjhiQpHA4rHA67XAIAkAZnp2V6e3t19OhRtbe3a8KECbrrrru0YMECnT171tUSAIA0OYt7Z2enPM/Tzp07tW/fPrW0tCgrK0uLFy++5uOj0agCgUBqAwC44yzuwWBQklRbW6uioiIFg0GtWbNGBw4cUG9v7x8eH41G5XleagMAuOMs7qFQSGPHjr3mfcQbAAaW07dCLl26VJs3b1Z7e7v6+vq0du1azZo1K3VUDwAYGE7fLfPKK6+oo6NDDz/8sCRp5syZ+vDDD10uAQBIg9O433rrrdq4caM2btzocrcAgL+Iyw8AgEHEHQAMIu4AYBBxBwCDiDsAGETcAcAg4g4ABhF3ADDI6YeY8NcULz/s9whDgp9/zy2bpvmyLj9b4MgdAAwi7gBgEHEHAIOIOwAYRNwBwCDiDgAGEXcAMIi4A4BBxB0ADCLuAGAQcQcAg4g7ABhE3AHAIOIOAAYRdwAwiLgDgEHEHQAMIu4AYBBxBwCDiDsAGETcAcAg4g4ABhF3ADCIuAOAQcQdAAwi7gBgEHEHAIOIOwAYRNwBwCDiDgAGDfN7gKGsZdM0v0eAUUPtZ6t4+WG/R7jpcOQOAAYRdwAwiLgDgEHEHQAMIu4AYBBxBwCDiDsAGETcAcAg4g4ABhF3ADCIuAOAQRmJe19fn4qLixUKhTKxewDAdWQk7qtWrVJRUVEmdg0ASIPzuB89elS7d+/Wyy+/7HrXAIA0OY17MplUZWWlGhoaNHz48D99bDQaVSAQSG0AAHecxn3Dhg2aMmWKpk+fft3HRqNReZ6X2gAA7jj7ZR0tLS3aunWrvvvuO1e7BAD8Tc7i3tjYqPPnz2vChAmSpMuXL6u7u1uRSERffPGFHnnkEVdLAQCuw1ncy8vLNXv27NT3X3/9tSoqKhSLxXTnnXe6WgYAkAZncc/OzlZ2dnbq+1GjRikQCKiwsNDVEgCANGXsE6ozZszQxYsXM7V7AMCf4PIDAGAQcQcAg4g7ABhE3AHAIOIOAAYRdwAwiLgDgEHEHQAMcvYJVQwexcsP+z3CkMHfNfzCkTsAGETcAcAg4g4ABhF3ADCIuAOAQcQdAAwi7gBgEHEHAIOIOwAYRNwBwCDiDgAGEXcAMIi4A4BBxB0ADCLuAGAQcQcAg4g7ABhE3AHAIOIOAAYRdwAwiLgDgEHEHQAMIu4AYBBxBwCDiDsAGETcAcAg4g4ABhF3ADCIuAOAQcP8HgADr2XTNL9HAJwqXn7Y7xFuOhy5A4BBxB0ADCLuAGAQcQcAg4g7ABhE3AHAIOIOAAYRdwAwiLgDgEHEHQAMIu4AYJCzuP/222+qrKzUuHHjlJubq4kTJ2rbtm2udg8A+AucXTgsmUwqPz9f+/fv1z333KOmpiY9/vjjKiwsVFlZmatlAABpcHbknpOTo7Vr1+ree+9VIBDQtGnTNHPmTDU2NrpaAgCQpoydc08kEjpy5IgmT56cqSUAAP+PjMTd8zxVVFRo/Pjxmj9//jUfE41GFQgEUhsAwB3ncfc8T1VVVWpubtbOnTt1yy3XXiIajcrzvNQGAHDH6W9i8jxPy5YtU1NTk7788kvl5eW53D0AIE1O415dXa1Dhw7pq6++UjgcdrlrAMBf4Oy0TGtrq95++201NzerqKhIwWBQwWBQzz//vKslAABpcnbkXlRUxLlzALhJcPkBADCIuAOAQcQdAAwi7gBgEHEHAIOIOwAYRNwBwCDiDgAGEXcAMMjptWUGoz3/HfNt7f8q8G1pAMZx5A4ABhF3ADCIuAOAQcQdAAwi7gBgEHEHAIOIOwAYRNwBwCDiDgAGEXcAMIi4A4BBxB0ADCLuAGAQcQcAg4g7ABhE3AHAIOIOAAYRdwAwiLgDgEHEHQAMIu4AYBBxBwCDiDsAGETcAcAg4g4ABhF3ADCIuAOAQcQdAAwi7gBg0DC/B/Dbvf9+3r/FN/m3NADbOHIHAIOIOwAYRNwBwCDiDgAGEXcAMIi4A4BBxB0ADCLuAGAQcQcAg4g7ABhE3AHAIKdxv3z5sqqrqxUOhzVixAjV1NQomUy6XAIAkAancV+3bp0aGxt14sQJHT9+XAcPHlR9fb3LJQAAaXAa923btmnlypXKz89Xfn6+Xn/9db3//vsulwAApMFZ3Ds7O3XmzBmVlJSkbispKVFbW5vi8fgfHh+NRhUIBFIbAMAdZ3Hv6emRJIVCodRtv3/d3d39h8dHo1F5npfaAADuOIt7MBiUpKuO0n//Ojc319UyAIA0OIt7OBxWYWGhYrFY6rZYLKYxY8YoLy/P1TIAgDQ4fUF1yZIlWr9+vc6dO6dz586pvr5eFRUVLpcAAKTB6e9Qraur06+//qr7779fkrR48WK99tprLpcAAKQh4N0kr2YGAgH9461/+j0GANz0Tr/w0nXfiMLlBwDAIOIOAAYRdwAwiLgDgEHEHQAMIu4AYBBxBwCDiDsAGHRTfYgJAJCe66Xb6eUHbsSN/BsTCASG1GWDh9rzlYbecx5qz1caes8508+X0zIAYBBxBwCDTMR99erVfo8woIba85WG3nMeas9XGnrPOdPP96Z5QRUA4I6JI3cAwNWIOwAYRNwBwCDiDgAGDeq4X758WdXV1QqHwxoxYoRqamqUTCb9HisjfvvtN1VWVmrcuHHKzc3VxIkTtW3bNr/HGhB9fX0qLi5WKBTye5QBsWvXLpWUlCgnJ0cFBQXaunWr3yNlVHt7u+bNm6eRI0cqEomovLxcP//8s99jObNlyxZNnTpVWVlZmjdv3lX3dXV1adGiRbrjjjs0evRovfHGG87WHdRxX7dunRobG3XixAkdP35cBw8eVH19vd9jZUQymVR+fr7279+vrq4u/etf/9KLL76ovXv3+j1axq1atUpFRUV+jzEgdu/eraqqKr311lvq6urS8ePHNWPGDL/Hyqhly5ZJklpbW3Xq1CklEgnV1tb6PJU7BQUFWrlypSorK/9wX01NjTo6OtTW1qaDBw/q3Xff1QcffOBmYW8QKyws9Hbs2JH6/tNPP/XGjh3r40QD68knn/Tq6ur8HiOjvv32W++hhx7y9uzZ4+Xl5fk9TsZNnTrVe+edd/weY0BNmjTJ+/jjj1Pff/TRR96DDz7o40SZsXr1am/u3Lmp73t7e73hw4d733zzTeq2N99805s+fbqT9QbtkXtnZ6fOnDmjkpKS1G0lJSVqa2tTPB73b7ABkkgkdOTIEU2ePNnvUTImmUyqsrJSDQ0NGj58uN/jZFxvb6+OHj2q9vZ2TZgwQXfddZcWLFigs2fP+j1aRq1YsUI7duxQPB7XxYsXtX37dj3xxBN+j5Vxzc3N6u/v/0PDfvjhByf7H7Rx7+npkaSrzsP+/nV3d7cPEw0cz/NUUVGh8ePHa/78+X6PkzEbNmzQlClTNH36dL9HGRCdnZ3yPE87d+7Uvn371NLSoqysLC1evNjv0TKqtLRUFy5cSL121tnZqVdffdXvsTKup6dHOTk5GjbsP9dvDIVCzvo1aOMeDAYl6aqj9N+/zs3N9WWmgeB5nqqqqtTc3KydO3fqllsG7X/CP9XS0qKtW7dqw4YNfo8yYH7/ma6trVVRUZGCwaDWrFmjAwcOqLe31+fpMuPKlSuaM2eOSktL1dPTo56eHpWWlqqsrMzv0TIuGAzq0qVLV70JJB6PO+vXoC1DOBxWYWGhYrFY6rZYLKYxY8YoLy/Pv8EyyPM8LVu2TE1NTdq7d6/Z5ylJjY2NOn/+vCZMmKBIJKK5c+eqq6tLkUhETU1Nfo+XEaFQSGPHjr3mfZ7Rq4R0dHSotbVVtbW1ys7OVnZ2tmpqatTU1KRffvnF7/Ey6r777tNtt92m77//PnVbLBbTpEmTnOx/0MZdkpYsWaL169fr3LlzOnfunOrr61VRUeH3WBlTXV2tQ4cOad++fQqHw36Pk1Hl5eVqaWlRLBZTLBbTe++9p9zcXMViMU2ZMsXv8TJm6dKl2rx5s9rb29XX16e1a9dq1qxZqaN6ayKRiIqLi9XQ0KBEIqFEIqGGhgYVFhYqEon4PZ4TyWRSiURCyWRSV65cUSKRUH9/v7Kzs7Vw4ULV1dUpHo/r5MmT2rx5s7uGOXlZ1if9/f1eVVWVFwqFvFAo5FVXV3uXL1/2e6yMOH36tCfJy8rK8nJyclLbc8895/doA+LAgQND4t0yyWTSW7FihTdy5Ehv5MiR3lNPPeWdPXvW77Ey6vjx415ZWZk3YsQILxQKeTNnzvSOHTvm91jOrF692pN01fbYY495nud58Xjce/rpp71gMOiNGjXKW7NmjbN1uSokABg0qE/LAACujbgDgEHEHQAMIu4AYBBxBwCDiDsAGETcAcAg4g4ABhF3ADCIuAOAQcQdAAz6Hzp3XW1lQLnUAAAAAElFTkSuQmCC",
      "text/plain": [
       "<Figure size 576x432 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# make a maze, convert array from True/False to integer:\n",
    "world=np.array(maze(width=11,height=11),dtype='int')\n",
    "\n",
    "# the four directions of motion [delta_jx,delta_jy]:\n",
    "directions=np.array([[0,1],[0,-1],[1,0],[-1,0]])\n",
    "\n",
    "# initial position\n",
    "jx,jy=1,1\n",
    "\n",
    "# take a random walk through the maze and animate this!\n",
    "nsteps=40\n",
    "for j in range(nsteps):\n",
    "    # make a random step\n",
    "    pick=np.random.randint(4)\n",
    "    jx_new,jy_new=np.array([jx,jy])+directions[pick]\n",
    "    if world[jx_new,jy_new]==0: # is empty, can move!\n",
    "        jx,jy=jx_new,jy_new\n",
    "        # show what's happening\n",
    "        picture=np.copy(world) # copy the array (!)\n",
    "        picture[jx,jy]=2\n",
    "        plt.imshow(picture,origin='lower')\n",
    "        plt.show()\n",
    "        sleep(0.01)\n",
    "        clear_output(wait=True)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Now: policy gradient"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\delta\\theta = \\eta R \\sum_{s,a} {\\partial \\over \\partial \\theta} \\ln \\pi_{\\theta}(s,a)$$\n",
    "\n",
    "Here $\\theta$ stands for the parameters controlling the policy probabilities $\\pi_{\\theta}(s,a)$, s is the state, a the action, and the sum runs over all state-action pairs that were encountered in the given trajectory, which led to an overall return (sum of rewards) R.\n",
    "\n",
    "Let's do a softmax-type parametrization:\n",
    "\n",
    "So: $$\\theta=(z_0,z_1,z_2,z_3)$$ and\n",
    "\n",
    "$$\\pi_{\\theta}(s,a=j) = {e^{z_j} \\over \\sum_k e^{z_k}} $$\n",
    "\n",
    "...where in reality the $z_j$ of course also depend on the state s, but for brevity we did not display that dependence here. They will all be stored in arrays, of the size of the maze!\n",
    "\n",
    "So, we get:\n",
    "\n",
    "$$ {\\partial \\over \\partial z_l} \\ln \\pi_{\\theta}(s,a=j) = \\delta_{l,j}-\\pi_{\\theta}(s,a=l) $$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0.1, 0.4, 0.8, 1. ])"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.cumsum([0.1,0.3,0.4,0.2]) # cumulative sum, will be useful!\n",
    "# this is useful for drawing integer random numbers according\n",
    "# to a given arbitrary probability distribution!\n",
    "# just draw a uniformly distributed number p between 0 and 1 and then\n",
    "# check successively whether p<(entry of cumsum); stop when\n",
    "# this is first fulfilled! The index of the entry where you\n",
    "# stopped will be randomly distributed according to the\n",
    "# distribution given in the original array."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The policy gradient algorithm\n",
    "\n",
    "In 124 lines of pure python code, including visualization and comments"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAhIAAAIKCAYAAAB2uKZJAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjcuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/bCgiHAAAACXBIWXMAAA3XAAAN1wFCKJt4AABdbUlEQVR4nO3deXxTZb4G8Odkb5q2aWlpC4WCbCICRVBEUHBfR0UHcdABvOIyQL161bmOilRBRq/XueOAo+MMjuOobO6O+zoKoihSUFAWBctWWihd0rTN9t4/knOyNEnTw2nS5fl+Pv1As5yctJA8+b2/930lIYQAERERkQq6VJ8AERERdV0MEkRERKQagwQRERGpxiBBREREqjFIEBERkWoMEkRERKQagwQRERGpxiBBREREqjFIJElZWRkkSVK+CgoKcMkll2DLli3tPtbq1avxzDPPaH+SnVx7n3dZWRlyc3Pb/TiSJGHZsmXtvh8RUU/EIJFEWVlZWL9+PdavX48//vGP2LFjB84991zU1NS06zgMEomZM2cO3n333Y47ISIigiHVJ9CTGAwGnHrqqQCAU089FQMGDMCECRPwzjvvYMaMGSk7r6amJqSlpaXs8bXmdruh0+lQVFSEoqKiVJ8OEVG3xopECo0ePRoAsHfv3rDL//a3v2HEiBEwm80oLi7G//zP/yjXzZ49Gy+99BL+/e9/K8MkZWVlAIABAwbgjjvuCDvWM888A0mS4HA4AACffPIJJEnCu+++i0svvRQ2mw3z589XLv/kk08wbdo02Gw2HHfccfjzn/8c9znMnj0bJ598cqvLH3/8cVitVjQ0NAAAli9fjhNOOAFpaWnIzc3F5MmTsXXr1oR/VvGe95QpU/DLX/4STz31FAYNGgSLxYIDBw60GtpobGzE/PnzMWzYMFitVgwcOBDz5s1DfX19wudBREThWJFIoYqKCgDAwIEDlcseeeQR3H333fjtb3+LKVOmYOPGjViwYAGsVivmz5+PBQsWoKKiArW1tcqbvJpP3ddffz2uu+463HrrrbBYLHC5XACAG264AbNmzcKNN96IFStWYN68eRg3bhxOOeWUqMeZPn06LrroIuzevTvseaxatQoXXXQRMjIy8Omnn+Lmm2/GAw88gAkTJqC+vh7r169HXV1dwufb1vNet24dfvzxRzz88MOwWq3IyspqdQyn0wmv14sHH3wQeXl52Lt3Lx588EFMmzaNQyBERCoxSCSZx+MBAPz888+YP38+SkpKcNlllwEA6uvrcf/99+Pee+/FwoULAQDnnnsunE4nFi9ejN/85jcYNGgQcnJy4PP5lGESNaZNm4ZFixYp33/yyScAgF/96le49957Afg/6b/xxht4+eWXYwaJc889F7169cKqVatw1113AQD279+PtWvXYvXq1QCADRs2YNSoUfjd736n3O/SSy9t1/m29bxra2tRXl6O/Pz8mMfIy8vDE088oXzv8XgwcOBATJo0CRUVFejfv3+7zomIiDi0kVRHjhyB0WiE0WjE4MGDsWnTJrz88sswm80AgPXr16OxsRHTpk2Dx+NRvs466ywcOnQI+/bt0+xcLr744qiXn3feecrfjUYjhgwZEvdxDQYDrrjiCqxatUq5bM2aNUhPT1ceo6SkBJs2bcJtt92GTz/9VKl+aGns2LFxQ4Tsn//8J8aMGQObzQaj0YhJkyYBAHbs2KH5ORER9QQMEkmUlZWFr776Cl988QX+8pe/wOVyYcaMGfD5fACAw4cPAwBGjBihBA6j0YgzzzwTQOteimMR603XbreHfW8ymdDc3Bz3WFdffTXKy8uVN+NVq1bh0ksvVRo4zznnHPz973/Hp59+iilTpiA3Nxfz5s1DY2PjsT+RgERCxCuvvIKZM2diwoQJWLNmDb744gu88sorANDmcyQioug4tJFEBoMB48aNAwCMHz8eaWlpmDlzJtasWYPp06cjJycHAPCvf/0r6hvjsGHD4h4/tNdBdvTo0ai3lSRJzVOIavLkycjPz8eqVaswc+ZMfPHFF2HDGAAwa9YszJo1C9XV1Xj55Zdx2223ISMjAw899JAm55DI81mzZg3Gjx8f1kD673//W5PHJyLqqRgkUujaa6/Fww8/jIcffhjTp0/HhAkTkJaWhgMHDsQcegBiVwmKiorw/fffh1323nvvaX7ekfR6PaZNm4ZVq1bBYrHAbrfjggsuiHrbvLw83HTTTXj55Zexbdu2dj1OItWReJqampRhJNnzzz+v+nhERMQgkVKSJOHuu+/GNddcgw8//BBnn302ysrK8J//+Z/4+eefccYZZ8Dn82HHjh34+OOPlTL88ccfj9deew2vvvoqioqK0KdPH/Tp0wdTp05FaWkplixZgpNPPhkvvfRSu6ZYHovp06dj2bJl+L//+z9cfvnlMJlMynULFy5ETU2NMqyxadMm/Pvf/w6rRgwePBiTJ0/G8uXLYz5GrOedqHPPPRfz5s3Dgw8+iPHjx+Ott97Chx9+qO4JExERAPZIpNz06dMxZMgQZa2I3/72t3jqqafw9ttv47LLLsOvfvUrPP/88zj99NOV+8ydOxfnnXce/uM//gMnn3wynnrqKQDAjTfeiFtvvRV/+tOfcNVVV8FsNiszMDraxIkT0a9fPxw8eBBXX3112HUnn3wytm3bhptvvhnnn38+nnjiCSUwyTweD7xeb9zHiPW8E3XTTTfh9ttvx2OPPYYrrrgCP//8M1544YV2HYOIiMJJQgiR6pMgIiKirokVCSIiIlKNQYKIiIhUY5AgIiIi1RgkiIiISDUGCSIiIlKNQYKIiIhU6zQLUmm5ZDMRJa7LzQDnawVRcrXxGtFpggTQBV/QiLo4BngiOlYc2iAiIiLVGCSIiIhINQYJIiIiUo1BgoiIiFRjkCAiIiLVGCSIiIhINQYJajdO0yUiIhmDBLXLvqNOnPzgh1j99d5UnwoREXUCDBLULt8fbMBhRwu+3lOT6lMhIqJOgEGC2sXp8gAA3F4ObxAREYMEtVOz2wsAcHl9KT4TIiLqDBgkqF2aXIEg4WGQICIiBglqJ2egIuFmRYKIiMAgQe3UzIoEERGFYJCgdnG6WJEgIqIgBglqlyal2ZKzNoiIiEGC2kkJEhzaICIiqAgSr7/+OkpKSpCeno4+ffrgySefBADU19djxowZyMzMRH5+PhYtWqT5yVLqNXFog7oZiV/86mZfyWZoz43feecdzJ07F8899xxOP/101NfX49ChQwCA0tJS1NTUoKKiAlVVVTjnnHNQXFyMmTNndsiJU2qwIkFERKHaFSQWLFiA++67D1OmTAEAZGdnIzs7G06nEytXrsS6detgt9tht9tRWlqK5cuXM0h0M2y2JCKiUAkPbTQ2NmLjxo3Yv38/hg4dioKCAkybNg0HDx7E9u3b4XK5UFJSoty+pKQEW7ZsiXm8srIySJKkfFHX0Mx1JIiIKETCQeLo0aMQQuDVV1/F+++/j127dsFsNuPaa6+Fw+FAeno6DIZggcNut6OhoSHm8crKyiCEUL6oa5ArEi0c2iAiIrQjSNhsNgDALbfcguLiYthsNtx///34+OOPodPp4HQ64fF4lNvX1dUhIyND+zOmlGKzJRERhUo4SNjtdvTv3z/qdSNHjoTRaMTmzZuVy8rLyzFy5MhjP0PqVJrZbElERCHaNf3zxhtvxNKlS7F//340NTXhgQcewNlnn43MzExMnz4dCxYsQF1dHXbu3ImlS5dizpw5HXXelCLy0IZPAF4fh6SIiHq6dgWJu+66C2effTZGjx6Nfv36wel04p///CcAYNmyZcjKykJRUREmTpyI66+/njM2uhkhhDL9E+DwBhERAZLoJJ2OkiSx6bKTa3J5Mfy+d5TvNy88D1lpxhSeER2rLvn/TuNZXpwzRt2N5v+j23iN4BLZlLDQagTAigQRETFIUDswSBARUSQGCUpYk8sT9j1nbhAREYMEJazJFR4cWJEgIiIGCUqYM6IiwdUtiYiIQYIS1rpHoot1+xMRkeYYJChhzWy2JCKiCAwSlDB5VUsZmy2JiIhBghIWObThYkWCiKjHY5CghMk7f8oLC7IiQUREhlSfAHUdcpDIMBtQ3+xhjwRRFFq3IGu9hHdnPz+gA5Z47uS6+jLtrEhQwpyBoY0sq39/DQYJIiJikKCEyRUJeaMuDm0QERGDBCVMnv6ZaQkECa4jQUTU4zFIUMKcrEgQEVEEBglKmDz9Uw4S7JEgIiIGCUpYZI+EmxUJIqIej0GCEiZXJDLloQ1WJIiIejwGCUqYXJFgkCAiIhmDBCUsskeCzZZERMQgQQlrcnmhkwCbWQ+AzZZERNSOIDF79myYTCbYbDbla/369cr1brcb8+fPR3Z2NnJyclBaWgqPx9MhJ02p4XR5YDUZYNIHgoSH60gQEfV07apIzJ07Fw6HQ/maMGGCct3ixYuxdu1abNu2DVu3bsVnn32GJUuWaH7ClDrNbh8sRj2Mev/K8OyRICIizYY2nn76adx7770oLCxEYWEh7rnnHixfvlyrw1OKebw+uLw+pJl0MBn8/2wYJIiIqF1B4tlnn0VOTg5GjBiBRx99FD6f/43k6NGj2LdvH0pKSpTblpSUoKKiAnV1dZqeMKWG3GhpNRpg1AeCBJstiYh6vISDxC233ILt27ejuroay5cvx2OPPYbHHnsMAOBwOAAAdrtdub3894aGhqjHKysrgyRJyhd1bnKQsJj0MAcqEmy2JCKihIPESSedhLy8POj1epx66qm46667sGrVKgCAzWYDgLDqg/z3jIyMqMcrKyuDEEL5os5NXkPCatQrFQkGCSIiUt0jodMF75qdnY2ioiKUl5crl5WXl6Nfv37Iyso6phOkzkGuSKSZ9DAaOLRBRER+CQeJ1atXo76+HkIIfP3113jooYdw5ZVXKtdfd911ePDBB1FZWYnKykosWbIEc+bM6ZCTpuSTd/5MM+lhknskuI04EVGPZ0j0hsuWLcONN94Ij8eDvn37Yu7cubj99tuV6xcsWIAjR45g+PDhAIBrr70Wd999t/ZnTCnRLAcJY0iQYEWCiKjHSzhIfPrpp3GvNxqNePzxx/H4448f80lR56MMbRj1yvTP0B6JZrcXv17+JS4f0xfXjC9OyTkSUffQ2dvvWYsNxyWyKSEtgeqD2aBTFqQKDRJ7jjTiqz1H8dqmAyk5PyIiSg0GCUqIx+fP4Aa9DnqdBEkKH9rwBPolDjtaUnJ+RESUGgwSlBBPoPpg0PnX/TDpdWEVCW8gaFQ3MEgQEfUkDBKUELkiodf5hzVMep0y3BF6fUOLR1lzgoiIuj8GCUqIXHGQ+yNMhugVCYDDG0REPQmDBCVEHtrQBxYiM+p1cIesI+HxBUNFFYc3iIh6DAYJSognoiJhNEjw+oRSifB4WZEgIuqJGCQoId4oPRJAcApo6NAGGy6JiHoOBglKiDyMYQgECXnjLrnh0sMgQUTUIzFIUEK8gR4IQyBARG4l7g3pkajm0AYRUY/BIEEJkSsS+oiKhBwkQisSh1mRICLqMRgkKCFyD0Tk0Ia8umVYjwQrEkREPQaDBCUkdIlsAK027gqdCsoeCSKinoNBghISukQ20LrZMqxHoqEFQnB/PCKinoBBghLiiRjaMBnkHUBF2PWAP1w4WjxJPkMiIkoFBglKiEeZtdH2OhIAhzeIiHoKBglKSHBBquAS2UCw2TJ0ZUuAQYKIqKdgkKCEyEHBqAtu2gUAroiKhHw5Z24QEfUMDBKUkMhtxCMrEu7A0EdBpgUAKxJERD0FgwQlpK3pn95AxaIgyx8kuHEXUc8gusAXdSwGCUqIskR2jE275KBRmMWKBBFRT8IgQQmJtUR25MqWBQwSREQ9iqog0dTUhMGDB8NutyuX1dfXY8aMGcjMzER+fj4WLVqk1TlSJyAHBWPE0IYrYh0Je5oJANDY4k32KRIRUQoY1NzpvvvuQ3FxMQ4fPqxcVlpaipqaGlRUVKCqqgrnnHMOiouLMXPmTM1OllJHHsIIViT8f7oiVrZMMwaGPEJWuiQiou6r3RWJjRs34p133sF///d/K5c5nU6sXLkSixcvht1ux9ChQ1FaWorly5drerKUOpGbdsXaayPNpAfQel0JIiLqntoVJDweD2644QY8/vjjMJlMyuXbt2+Hy+VCSUmJcllJSQm2bNkS81hlZWWQJEn5os4tOGsjotkyokfCYvQHCTlgEBFR99auIPHII49gzJgxOOOMM8IudzgcSE9Ph8EQHCmx2+1oaGiIeayysjIIIZQv6tyCm3ZFrGwZMWvDbNCHfU9ERN1bwj0Su3btwpNPPolNmza1us5ms8HpdMLj8Shhoq6uDhkZGdqdKaWUN7Ii0WplS/+flkCPhIcVCSKiHiHhisTatWtx6NAhDB06FLm5ubjssstQX1+P3Nxc1NfXw2g0YvPmzcrty8vLMXLkyA45aUq+yN0/W+21EVGRcLNHgoioR0g4SFx11VXYtWsXysvLUV5ejr/97W/IyMhAeXk5JkyYgOnTp2PBggWoq6vDzp07sXTpUsyZM6cjz52SyBOxjkRwG/HwHgmjXoJBJym7hRIRUfeW8NCG1WqF1WpVvs/Ly4MkSSgqKgIALFu2DDfddBOKioqQlpaG+fPnc+pnNyIHA2UdCX2g8uAJX0fCoNfBoJc4a4OIqIdQtY4EAEyZMgW1tbXK95mZmVixYoUW50SdUOtNuwLrSMjNlt7gEtpGnY6zNoiIeggukU0JkSsMSo9E5KZdIUHDoJfYI0FE1EMwSFBCvD4BvS645odRF33TLoNOgkGvU9UjsfNQAzZVHG33/Q47WvDWtweVMBPJ6fLgxY370OTyL9vt8vjw+uYDqG92t/uxErX1QB227Ktt9/2q6pvx9rcHlSnRNY0u/GvLAc6CIaJOi0GCEuLx+ZRhDQAwBpot5UpFaEXCqPNXJNq7PshNz23ENX/7Ei2e9u3T8ccPdmDu89/gL5/+GPX6e175Dnes2YwFr30HAHjo7R9wy4pNeGbdnnY9Tnvc8I+vMf0vX8DR4kn4Pi6PDzOf3oDfPP8Nvv7ZH6j++MEOzH9hEx7/OPpzIyJKNQYJSojHJ2AMCRLywlTBHgmhXG4INGTGqhBE09jiwU/VjXC6vDjicLXr3LYdqAcA/PGDnfix2hF23cc/VOGVTfsBAC9u3Ic/fbgTf/98NwBgV1X4bbXS7PbiQF0zmtxefPxDVcL3e+KTH/FDpX8Rt6/21AAANuz2/7ns453YXhl7gTciolRhkOim6pvd2HqgTrPjeb0irCIhL5EdWZEw6CVl0ar2rG4ZGgAOO/xbkB9xtGDHofhvnkII7AwEApfHhzvXbMY731UGvg7inle+BQDMGN8fAPCH93dALpTsPeqMedztlQ1xqwm7Dzcq5xnpUH2z8vd3vqtULgsNLrVOV9hz23GoAcs+3ql8X15Ri8YWj3Ibt1fgty/6n9vanYfh48qhRNRJMEh0U/e/vg2XLF2LA7VNmhzP7fMpUz+B4AqXyqZdvvBZG6HXJSL0Tba6wf8GfeuqclyydC0a4vQyVDe0oKHZg+MLMjCiTya+qajFzc9tDHx9gwN1zfjF6D5YMnUkLhpZAACYOLgXjHoJe2ui/2x+qKzHhY99it+/9X3Mx7zwsU9x/TNfRb3+YF0wSHz0QxWqGpox9fF1uOixz7DjUANaPF5Me3I9LvnTWiWMLP1oF9xegf86dygMOgmb9tZiy746+ARw3gn5GN3Pjs376nDzcxtx7fIvlSoLEVGqqZ7+SZ3b/lonhACqGlrQx552zMeTmy1lcqiINWsDaN8OoDujBImdhxxweXyorGtGhsUY937HF2TgtnOH4vkvK8IeN82kw42nDwIA/H7qKJxQmInpJ/fHtCc/x54jTjS5vMqOpbLPdx2BTwDfVNRGfcz3tlWi2e3D5n112H24EQNz08OurwwJEk1uL67925c4ELjsty9uwYRBvZTz/uFgAyYNMWNboHo0e+IAvLetEt/tr8db3x4EAIwbkI0LTyzEc1/8jOqGFry8aT/e2HIAV44tivMTJSJKDgaJbkouy8szFY6FEAJur1CmfgLBdSTkaZ7ReiTc7Zi5sfNQeJDweH2oloc4Gl0YEvN+/tL/kPwMFPdKx90XDY/5GFlWI+af5T9Svxwr9hxxYu9RJ4bmh+8JU763FoB/uEUOUEcbXbBZDDDqdcpwBQC8/d1BzJ0yOOz+ckXilAE52LCnBjsOOZCTbkIfuwXle2uV4wPAzqoGnDIwB3uOOJGfaUamxYgx/bLx3f56vLhxHwCgpF82+uVY8buLhsPj9eHj7VVYt+sw6prcyEqLHrCo+1iIhZoeT8L9mh6vI3T2gTvuVx2OQxvdlKPZHySa2zkDIhp5ON4QMrQRsyKhl5SmzPZUJEJ7JKodLTjscCnHPNoYu/lyV+B+g3vbEn4sACjK9q/SuremdZ/Epr3+GRMujw97a5w47GjBxIc/wn888xVqGl34/McjyuZkoaFCJvdI/Gp8P5gD622UXToCj04rUQLYGUPzAPgrKnuONMLrExjS2x9oSvrZAfirGXqdhJF9s5RjG/Q6nHdCAdxegQ+/P9Su50xE1BEYJLopuSLR4j72IOEJ6X+QyUFCbqgMvU17hzaa3V78fKRR+f6wowUH64L9C0fiBAm5ktHeINE/J3qQOOxoCeud2FXlwFe7a+B0efHZzsOY9/w38PoEpo4pwsDcdGzZV4d9EU2b8rkPyrPhwakj8dsLhuEXowoxrCAD/zttNOadOQgLf3GCcny5P0R+DmP625VjHV+Q0Wro5YJAr8fbUUIMEVGycWijm2qQKxLuY1/IKHLDLiBkiWxPeEXCoJOC1YoEhzZ2H26ETwDH5aXjp+pGVDe0hM18qIkSJHw+AZ1Owo/VDhj1EopzrK1uE0+/HH/fyN6j/jd9IQQkSUJ5oC/Cv/GYf0bIUWfw8df/dAQAcOGJBbBbjXjikx/xzneVmHP6ccpt5B6JgkwLRhXZwx73spK+APxLipsMOuyqcrQKQwNz05GVZkRdk1upToSaOCgXGRYD/r2jGo4WD2xm/jcmotRhRaIbcnl8aAm8wTdpUpEIbsglk6TwXT7dIWHD0M6hDfkT+YTjegHw90iEznyIDBJ//mQXTlnyIb7aU4PDDheOy7WFnVsi+gWGNipqnNh5qAEnLnwXT3zyo9K/cPbw3sq5yattnntCPgAgK82ICYN64cITo1cGDtY1w6CT0Mtmjvn4Br0Ox+Wmo6bRhQ17/OFEDhKSJCkBYkz/7Fb3NRl0OHd4PlweH97ccqBdz5uISGsMEt1QY8j6B80aBInQakOo0D01QpfQNujbN/1TnsEwok8WMiwGVDe0hM18iBzaWP/jERx2tOA3z20E0P5hDSB8aGPNxn1odHnx6Hvb8a/AG/O0sf0A+KeCfru/DhkWAx67ugSXjCrEHecPg1Gvw8i+WehrT8PGn48qFRR3oEk0P9MSVsGJRj7vL37yLzo1JOR5zDl9IM49IV8JL5HkdTEefmc7jsRYz4KIKBkYJLohR1iQ0GJoI9D/oA9/YzTqdXB7gnttRO4MmuiCVLuq5JkXNuRlmNHo8uLH6mDPRE1j+BulvPLl4cCfaoKE3WqEzWzAvqNNePu7g8r57jniRJpRj8nD8pBu0mPrgXo0u30o6WeH1WTAshkn4denFgPwVw4uCFQl3t3qr0pUN7RACKAgy9LmOcjn7fUJ5KSbwioYpw/Jw19njos5K2PcgBxcM74/ahpduP+Nbe1+/kREWmGQ6Ibk/ghAm4qEJ0ZFwqjXKX0QXp9PuV5ePjuRjaaEEPj+oD9IDM6zIS/wZhq6Kmfkktk1jS5IUvB8huS3P0hIkoSi7DQ4WjzYW9OE0UVZGFfsH0YYWZQFo14XFlCi9SoAUBa5ktd8OBjSH9EWeZYG4H/u7XXXhcejMMuC1zcfwLpdh9t9fyIiLTBIdEONrpAgocH0z2jNloC/8qCsIxFWkZCHNtquSKzYsBe7DzdiRJ9MZKebkJfhDxLyG7JOQlizoxACNY0u9Eo34d6Lh2NwbxtODfRWtFf/kAbNi0YW4uFfjsLQfBuuGucf1hgc8kYfOpMi1Jh+2cjPNGPD7hoccQSHZBKpSIQGoMEqwlCGxYibzvA3eW78uf27phIRaYHt3t2QI7QiocGCVHJDpTGiodGg08HrE/D5BLw+AYtRH7idFHa/WA7WNeH3b30PnQQsmToSAJAbUt7vlW6CJEmoaXQpsyocLR64vD7kpJswe+JAzJ44UPXz6hcSJC48sRD9e1nx3m2TlcvCKxKtmx4BQKeTcP6IAjy7/me8t+0QnIGfd2ECQWJAr3TodRK8PqGqIgEAvQOVj7qmjtsSnYgoHlYkuqEGFT0Suw834jfPbQybdikLXf46lMkQnObpCdnUK5F1JIQQuPeV79DQ4sENpx+H0YGhA7kiAfg/1fdKN8HtFcpzOtrof8PMtpoSel7xyBWJEX0y0b9X6+mjcvNjcS8rctJjP96FJxYCAP615QAqA2tIJFKRMBl0KA48rprhGQDIDCwdXs8gQUQpwiDRDYVVJBIc2vjH53vw9neVStNgKHfI8tehjCGBwROlRyLerI3XNx/Ahz9UYUAvK249Z6hyeViQyLQgO93/RlkT6JM4Emi87GU79iBx6nG9YNLrMGvCgKjXn1ScjV7pJlwyqjDucU4ZmIO+9jSs23UEb245qJx7Is4dno/eGWaM6mtvz6kr5GZMViSIKFU4tNENOVqCbyqJNltuCqyfEO32Mad/BgKDy+ODT6DVrI1YPRJHHC0oe30rAODhK0eFrdwYWZGodfqfy5FGFwYE1l0AELdCkKhhBRn4YdEF0MWYppmTbsLGBee2eRy9TsKiy0fgP575WtmcK5GKBAD87qLh+F2c/UHawiBBRKnGikQ3FFqRaEpgaKPF48X3B+oBRB8KkXsd9JHTPwNDG3LVQ6lIKMtnR3/sB/61DUedblwzvj/GRzRK5oX0SBRmWZTAIAeII0qQiL3YU3vEChHtddbx+bispA8AQJKA3hmJBYljlZnm/yxQH/I7JyJKpnYFidLSUvTr1w+ZmZno27cvbr31Vrhc/hf2+vp6zJgxA5mZmcjPz8eiRYs65ISpbQ3tXJBq64F6uALDENFuL0//NEbO2gh8L+8wqlQkdLErEpV1zXit/ADyMsy468LjW10fXpFIU4KEvHGXUpGwdr5dLxf+YgR6Z5gxLD9D6R/paBnskSCiFGvXq93cuXPxww8/oL6+Hps3b8bmzZvxP//zPwD8IaOmpgYVFRX47LPP8Ne//hXPPvtsh5w0xRdakUhk0y55fwkAytLaoYLTPyN7JPzfy8twy98rFYkoPRJyD8alo/sob4KhctJNkAJ5pSDTovRCHIkMEnGWn06VnHQT3r9tMtbcPCFpj6nXSciwGBgkiChl2hUkhg8fjvT0dAD+rnudToedO3fC6XRi5cqVWLx4Mex2O4YOHYrS0lIsX768Q06a4mvvypZyf4T/9tEqEq13/wSCszPk+0TO2nBHWdlSXrhJXsgpklGvQ05gRkZBlkWZnSGvbikvTtVLgx6JjpBlNUYNSB36mGlGNLR4lF4WIqJkanf99aGHHoLNZkPv3r2xefNmlJaWYvv27XC5XCgpKVFuV1JSgi1btsQ8TllZGSRJUr5IO6FBIpFNu8r3Bhczit4jIW/aFTH9U65IuMKDhjHGypaHHS34ak8N8jPNGBNjXQbAP93SYtShj92iBAa5IiEvTqVFs2V3wSmgRJRK7Q4Sd911FxwOB7Zt24abb74ZBQUFcDgcSE9Ph8EQnARit9vR0NAQ8zhlZWUQQihfpB1HO3okqhtasLemSRlOiDZd1OuNvWlX6GO0tY7Ee1sPwSeA80cUxG1yXDbjJLz0m9NgNRmQY4vebNlZKxKpIM/cqG9mkCCi5FPdETZ8+HCMHj0as2fPhs1mg9PphMcTfAOrq6tDRkZGnCNQR5F7JPQ6qc0gIW+bPaJPJgCgJc6sjcituiN7JOTpoMrunxGzNuTNseSNrmLpY0/DiD5ZANBq1oY8xGHXYEGq7oJTQIkolY6ptdztdmPnzp0YNmwYjEYjNm/erFxXXl6OkSNHHvMJUvs5WjyQJMCeZkRzlObJUN8f9E/7PHlADgD/VNBIsTbtkoc2IisS8qyN0IqE0+XB+h+PICfdhFMCj5UIuUdC7o2ocbiQYTEkbVZEVyBPAWWQIKJUSHhBKofDgTVr1mDq1KnIysrCd999h8WLF+P888+H1WrF9OnTsWDBAqxYsQJVVVVYunQpp4CmiKPZA5vZgDSTHkcaXfCGbKgVSd7gKz+wEmO8BakijxE5tCF/H23WxpZ9dfD4BE4ZkNOqshGPUa9DpsWAo04Xmt1eNLq8GBBlOeueTBnaaOJaEt3R/bhf0+NpPZDcFTrcOvvgeVf4GcaT8Cu6JEl44YUXMGjQIGRkZOCyyy7DxRdfjD/+8Y8AgGXLliErKwtFRUWYOHEirr/+esycObOjzpti8PkEHC4PMswGZROtaFUGmdvj/y9mM/szpdxsKYTArqoG+HwiuER2m0MbEStbhswikIdQSmLsohlPL5sZTpcXB2r9+1iw0TIchzaIKJUSrkikp6fj/fffj3l9ZmYmVqxYoclJkXpOtxdCAOlmA8xGeejBh1gtBfJ+GBkW/z8FOXR88H0Vbnj2azx0xUilETNyaMMYMWtDXmfCEGXWxqYK/8yQMYHNudqjV7oJuw83Ymtg9U2tVrXsLjIZJIgohTjQ3M3IjZY2iwEWg78iEa/hUg4S8hRCuSKxt8YJANhf2xRSkYgMEoGVLd2RS2SHr2wphMCmilrodRJGFmW1+zmNHeCfKvrixn0AgJz0zreqZSpx1gYRpRKDRDcjb9gl90gA8deSkJfGthj1MITM8pDv0+z2xt60K7LZUh8+tCHP9jhY14yqhhYMy8+A1dT+feIuCmzT/enOagCsSERiRYKIUolBoptxtPjf1DMsBpgTqkj4Q4LJIMFs0Cm3dQaaMJvdPmXWRqwlspsjKxLK0Ib/fpsCS3Cr6Y8AgFFFWehrT4O83AjXkAgnV5MYJIgoFRgkuhllaMNsgCWkRyIWV6AnwqTXw2LUK3ttOF3ByoTc62CMHNrQtbFEdiBIyCtnqumPAPyNvuePCK49wWbLcMFZGwwSRJR8DBLdTHBowxictZFARcJokJQgIYRQdvRsdntDKhLRtxFXNu0KVCKMEduIyxWJMf1jL4vdltC9OeTVLsmPQYKIUolBoptpCGm2TDO23SPhVqoNOmWWR4vHp1Qkmt0+ZYgi5qyNQMVD7pEwhCxI5fH68O3+OmRYDDguN1318zqpfzZ6B7YYz+GqlmG4IBURpRKDRDcj77ORkfDQhv86k14XNsvD6QpttpQ35YrskQgMbbgi15Hw387l9aGh2YMWjw/9c6xx99doi04n4fbzhuLMYXk4vpBLr4cyG/SwGHWob+aCVESUfO1voadOTe6RSDcbYGlOfPpnaEWi2e1Dk9uj3DfW7p+RC1K13rTLp1wnD7Mci+kn98f0k/sf83G6o6w0Iw47XBBCcDddIkoqViS6qD99uBO3rSpvtXOqXJGwWYIrW0bb0VOm9EjoJaUi0eIJqUh4QoJEREXCENFsGVmR8PiEcl2aBkGCYsu0GOH1CTS62t42nohISwwSXdTqr/filU37W5WzG8KGNgI9EnHeXJShDYMubCjE2dK6RyKy2dJkiKxIBJotA3+6vT5lWEU+NnUMNlwSUarw1b2LkisG8vbasrCVLUOaJ2MJHdpQKhhuL5yBoY0mV2iPRMSCVLrwdSSM+sihDaFUQ8ysSHQo7rdBRKnCINFFNQYqDzWNLVEvt5kTWyLbFdojYQgGA7mK0eLxKptvxVwi2xVjHQmfUBox5XOhjsHVLYkoVRgkuiCP16dUGY44wisSDSFBQl4iu61mS71Ogl4nhewWGj790+uN3iOhrGzpCa9YGEM27ZIrEmkm/lPrSBzaIKJU4at7F+QMCQaRQxtyRSI9wemfbq9QKguWkHUnmkL23HDLQxsxZm14I5bQDhvakHskWJHoUKxIEFGqMEh0EW9/exBvbD4AAEojJAAciRkk9Mqbd9wFqTw+JRDI0z/rmtzKvhZen0CLO3qPROSS2ZGzNtw+n1IN0WL6J8WWaeGiVESUGlxHoou46+Vv4fUJ/GJ0H2VDLQA4Gtls2eKFUS/BbNArDY7xhjZavD7lTUgOHq2P6X+8yFkb8u6fMqVHImRlSznEyMMs1DHkikQDF6UioiRjkOgCmlxe5ZOmxxvsXwCiD22km/2/1jQlSEQf2hBCwO1tXZGocUYPEsaI4GDSR/ZM+AOEXhdckEp+bLmRkzpGImuGEBF1BAaJLuCwIzgzo7HFqwxfAOFDG16fvwIg744ZnP4Z/c3F6xMQIhgQYlYkmmNVJMK/l3skJEmCUS/5Z21waCMp0pQN2mL3wxABQFdY91Tzc9R4xE8YtT1eV8ePiV1AVUMwSDS0uGNWJOQhj3Sz/02lrQWpQle1DL19TWP4/7pgRSJ6s6UstIfCoNP5Z5cwSCSFHBrjLT5GRNQRGCS6gOqQIOFo8aAxpEciNEg0Bpow5aGNtsrdoWtI+G/v//NojKENfYxNu2ShFQuDXgosSOV/DC6R3bE4tEFEqcIgkWK7qhpa9TlEqg4Z2nA0eyJmbYSHDMC/hgTQdo+EvKqlvNS1uY1my1jbiMtChzqMeh3cPp/yCZlLZHesRBYfIyLqCAm/ure0tOCGG27AwIEDkZGRgeOPPx5PP/20cn19fT1mzJiBzMxM5OfnY9GiRR1ywt1JndONS5auxX+tLo97u+qwoY3wikSzO/hmrUz9NPmDROhKldEoQaKNioQ3xsqWrXskQoc2AhUJDm0khbzgV7w1Q4iIOkLCzZYejweFhYX44IMPcNxxx+HLL7/EhRdeiKKiIpx33nkoLS1FTU0NKioqUFVVhXPOOQfFxcWYOXNmR55/l1bjdKHZ7cMXPx0Jmz0R6XBkRSJiHPxIYwuKTFYlYFgDPRI6nQSTQRczSMgbdgWHNvz3q42xFkGrTbta9UgEvzfqdf7dPz3ctCsZzAmsGUJE1BESfnVPT0/HAw88gEGDBkGSJJx66qk488wzsXbtWjidTqxcuRKLFy+G3W7H0KFDUVpaiuXLl3fkuXd58myKZrcP2ysbYt4uskcidB0JINgnIfdIyEMbAGAx6Noc2jAawisS8mJUsTbpksVttgxUKxzN7sCxWZHoSMry5gwSRJRkqj8mNjc3Y8OGDRg1ahS2b98Ol8uFkpIS5fqSkhJs2bJFi3PstkKn6m3aWxvzdmFBotmjBIZcm3+a5xElSASXx5almfRxKhL+xGAKvOmbI5axzg5MI5W1ObShDx/aAIILJDFIdKxElkMnIuoIqoKEEAJz5szBkCFDcMUVV8DhcCA9PR0GQ/ANzG63o6Eh9qfssrIySJKkfPVEodt7b6o4GvN2sSoSRdlWAEBNYOOuyGZLwP8G7vEJpfoQyh1j1oYsxxoRJCKbLXWxKxLyMeVzYpDoWJy1QUSp0u4gIYTA3LlzsX37drz66qvQ6XSw2WxwOp3weIIl97q6OmRkZMQ8TllZGYQQyldPFLpQVHmMioQQInzWRosHjYEeiX45gSARWZEIWY46Xjd/ZJCIrEjkRFYkIoKDLrBrqCxy+icQUpHgypYdyqjXwaCTuI4EESVdu17dhRCYN28evvzyS7z33nvIysoCAAwbNgxGoxGbN29WblteXo6RI0dqe7bdTOjQxk/Vjahztm5yrG/2KE2RgDz90//m3C87DUDI0IYrfB0JIH7J2xUx/TOyatA6SLSuHBn14YtQRf69IdAjwb02Op7FGHsYi4ioo7QrSMyfPx/r1q3D+++/j+zsbOVyq9WK6dOnY8GCBairq8POnTuxdOlSzJkzR/MT7k5cEcMN5ftqW91GnrGREQgH0SoSR+P0SFjibNzVetZG+D+H7PTgOrCS5K9ARAod3ghfR0JSzhfgNuLJYDHqlFkyRETJknCQ+Pnnn/HnP/8Z27dvR3FxMWw2G2w2G26++WYAwLJly5CVlYWioiJMnDgR119/Pad+tkEe2pB334zWJyH3RwzITQfgX0ci2CMRUZGIEySi7bchL5Edq9kytEcish9CudwQWoVoXZ3wCf800WghhLRlMerh8vjg8/XMoUIiSo2E15EoLi6O28uQmZmJFStWaHJSPYU8tHHKwBx88H2V0ichhMD8FZuQm27CuAE5AICBuen4dn8dHM1uZWVLpdkysLplsNkypEdC2YOh7WZLo16CTvK/+QPhQxuRa0jIDG30SADBXUWpY4U2XFpN3I+PiJKDrzYpJM/aGFVkxwffV2HP4UYA/qrDm1sOQpIAa6C6IFck5L029DoJhVkWAFGaLaMNbUStSISvIyFJEixGvbLgVej0z8ipnrLQtSRCeyRCF6viPhvJEdoPEzHhhoiow/CjYgrJww1ZaUZkW404WNcMIQQq65oB+BeGWv3VXgBAcY4VkhRc2dJq0sNi1CPdpG/dbBnyaTStHT0SQHjDZWhFIlqjJRBs1ARiVyQ49TM5uN8GEaUCg0QKyUMbZoMOBVlpaPH4UOt042AgSADB/of8TAtsJgMaAkFCDgs5NhMaAjM74jdbRhvaEMrjy0L/nm0NHdqI/k/FoGu9CBUAGMLCCf+ZJYM8M4bLZBNRMvEVPoXkoQ2zUacMUxysa0ZlXVOr2+ZmmGCzGNDQ4oHXJ5T9NHJtZgD+2R3BIBGsAMj9CdHeXFyBiogxSvXApNchwxIMJJFbhgcvjzFrQ8eKRLKZWZEgohRgkEgheWjDbNAjP9MfJA7VNysVicyQN/I8mzlsxUq5IiEHkMr6ZjhavDDqpbDZF/EXpPJXJELDgFyRSAsMnchiNVvGXEcixnAJdRwuk01EqcAgkUJKRcIQWZHwB4mrT+kPwP8mnm31VyRk1kAZuyDTPwW0sq4ZjS2esGENIFjujraZk8sbu0fCatKHrf0Qq0ci9L56Xet1JEKPSR2LG3cRUSpw1kYKBXsk9CiQKwt1Tais9weJS0f3wXtbK5GVZoROJ4VXJAJ/L8jyD20cqG1Ck9vbajVKeWnq6D0SgZUtY1QkQqdtGmJscW6IslGX/+8h4YTLYyeF3FjLHol22qvx8fppeziuCnLsynQLNT7i/Rofr2tjkEghZWijVY+EP0j0y7bijdJJyif90J4FudJQkOWvSPxY7Z86aouoSFjivLkEp3+2rh5YTXqYDTpIkn/2SEIVCT1nbaQShzaIKBUYJFIodGgj2+pfjroy0CORZtQjM80QtjNq6LROeWMuOYD8WO0AAKUJUxZviezgypatF7CyGv2PbTHo0eT2JriOROvdPwGuI5Es8X7XREQdhTXnFAoGiWCz5U/VjahrcqMwy9Jqe/XwHonA0Ebgfj9W+YNErIpE1E27lHUkWlcP5IqHHCxiTf+MvWlX6DH5zywZuJU4EaUCX+FTKDhrQ4cMixE2swH7a/1TP+VgESojrEdCH3Y7eb2JdFNkkIgz/TNiZUsgOMvDqgQJ/5+JDG3EXkeCFYlkUIaxuJU4ESURg0QKyRUBeXVIueESCA5ZhIpWkTAZdMi1BRssI2dtxOvkd3uiNFsag82WQHBYoq0gEbk7aOg6EmYGiaSQQ2MLdwAloiRikEih0B4JIDw8FEQLEubgtt5yj0TkbW2xeiTi7bURpXogVzbkEBC7R8J/eWTQMLBHIum4RDYRpQKDRAop0z+N4cMUQAIViZDKg7yWROTlQOheG7GXyA7rkQiEGmtEj4Qh1hLZermHIjxIhPdd8J9ZMrDZkohSga/wKRTaIwGEh4c2eyRCeiEKwyoSMXokooybyz0SoRtvmSObLQ3xhzbkYZHIoGHgEtlJl2aK3Q9DRNRRGCRSqMXjg04KvumG90iktbp9eEUi+tBG6JAHEH9owxWlR0IOIhkW/zCKHChiLZEtn3vk9dy0K/mCQxvskSCi5OE6EinU4vHBbNAr0zzb6pEIrUJYQz7lF4RUL1o1W8Z5c4nWI/GL0X1w1OnCZSV9/PcPhABjjJUt5RkfkZt6hX7PHonkMHNog4hSgEEihVrc3rBlqOVeB6NeQq+Ipa6B8JUtQwND3KGNQLk76qyNKNM/c9JNuPWcocH7G+JXJIyxKhK61sMl1LG4siURpQJrzinkr0gEfwVyIMjPtIRNpZSFhgRrjFkbkRUJk96/zHX0dSRaN1tGMic4/bNVj0RYAyeDRDKksSJBRCnAikSKeLw+eHwibMvv7HQTfnvBMBRlW6PeJz3Kpl1AZJAIf9OWl7mOukR2lB6JSGltTf80xJq1wR6JZOOsDSJKBQaJFJFnTJgjdsacO2VwzPuYDDqYDTq0eHxhFQmryYBMiwH1za23EQf8b+Rxd/+MsztnW0tky5WKVutIhHyfZmJFIhm4RDYRpQI/KrbDpzuqMX7JB9iyr/aYjxVcQ6J9vwK5T8IasRS2PMsjcolswP8G0+T2QojwDYldUZoto93Xf5sY0z8TqUhwaCMp2CNBRKmQ8LvYsmXLMG7cOJjNZlx++eVh19XX12PGjBnIzMxEfn4+Fi1apPV5dgrrfjyMQ/Ut+Of6n4/5WKEbdrXH1Sf3x69O6dfqjftXp/TDuSfko4+99bRReXgiculkeWgjVv8DEFqRiDX9M9AjoY/TI8Fmy6SQAxv32iCiZEp4aKNPnz6499578cEHH2Dfvn1h15WWlqKmpgYVFRWoqqrCOeecg+LiYsycOVPzE06lhmYPAOD97w/B7fXF/STflsjFqBJ1x/nDol4+e+JAzJ44MOp1ZmW/DV/Ym7rLKwLNmPGCRFvNlrGGNtgjkWw6nQSTQaf82yIiSoaEg8QVV1wBACgvLw8LEk6nEytXrsS6detgt9tht9tRWlqK5cuXd9sgUet048ufapBm0uPONZvR7PbCaNDhgctOxOSheQkdK3KfjY6klLw9XmQhuF+HPwzFDhH++8rNlrG2EY9esTAZWJFIBYshej8MEVFHOeZ3se3bt8PlcqGkpES5rKSkBFu2bIl7v7KyMkiSpHx1BQ3NbuXvL2/ah9tXl+Onw404UNeMn484cceazahzuuMcIUjukYjX6KiVWCVvt9cXtoZENKOL7CjItGBs/+yo1wenf0avSEhScsIS+cn9MEREyXLMszYcDgfS09NhMAQPZbfb0dDQEPd+ZWVlKCsrU77vCmFCrkgAwMvf7AcAnDO8N/46cxzufHELXty4D4vf3IZHpo1u81gurzy00fGf1uVZE5Hd/G6vr9UCVpGGFWTgi7vPjnm93AvReols//dmQ/yhE9JWmkkPb4M45qG3HkXjH5N0UNvjQev/Plr/s+iI/95an2P9/ZoeTtujdX3H/Ouy2WxwOp3weIJvsnV1dcjIyDjWQ3c6ckWipJ8dgH8TrUWXnwhJknDvxcORazNjzcZ9+HzX4TaPpczaSObQRkjJWwgBt1cc85uNsmlXqyWydYHH5rBGMnErcSJKtmN+Fxs2bBiMRiM2b96sXFZeXo6RI0ce66E7nYZmD3QScP2kgZAk4L5fnKBMu7RbTbj9PP/S0h98X9XmsZQeiSQ0IkZ7c4m286caMVe2DFQouM9GcnEKKBElW8JDGx6PR/ny+Xxobm6GTqeD1WrF9OnTsWDBAqxYsQJVVVVYunRpt5wC2tDsgc1swC9G98HZw3u3WsthQK90AEBtk6vNYwVnbXT8G608ayN07NydwPLYiTDEmLXBikRqcOMuIkq2hD+OLl68GGlpaXjwwQfxxhtvIC0tDeeddx4A/xoTWVlZKCoqwsSJE3H99dd3uxkbXp+Ao8WjbK8dGSIAwG71X1ebQMNlMmdtKOtIhAYJT9uLUSUi1qyN0B4JSh7ut0FEyZZwRSKyOTJUZmYmVqxYodU5dUqOQKNl6A6ckbKt/h07a50JVCTc6hakUiNauTvaFuJqFGRZIEn+jcZCZaUZkWbUoyi79QJZ1HE4tEFEyca9NhJUH2i0zLQYY96mfRWJwNBGMnokonxK1apHoq89DZ/cMSVs4zDAX7H54PbJsKfF/nmR9rjfBhElG+vOAH4+0ohXN+1vtRdFqIYEKhIWox4Wow61TZ1raEP+lNrk9uKIowWvbz4AVwI7fyaquFd61MpKX3ta1E3EqONwmWwiSjYGCQAPv/MDbl1Vjh8qY699IU/9jBckAMCeZkKt0wWfL3YoAdTvtaFGcNzchz9/8iNuWbEJH/3gn1lyrM2W1Lkoa4awR4KIkoRBAsD+o00AgL01zpi3kSsSmW2U6u1WI3wCaGjxxL2d3PiYjIpEaCd/ReA5bjtQD+DYeySoczEry6GzR4KIkqNLvov8UFmPyrpmzY532OFvjqysj33MhpYEKxJKn0R4w+XmvbWoCxnySOo6EiFB4rCjBQDw4+FGAGhziWzqWrggFRElW5d7F9m8txYX/2ktblmxSZPjCSFQ3eB/cz0YJ5wEeyTiVySCMzeCoWHjzzW47PF1eOjtH5TLkjm0YTHInfxe5bn+VO0AoE2PBHUe0RpriYg6Upd6F3F5fPjvl7bA6xPYFXgjPFb1TR5lBkO8Kkd9U/sqEkdDKhKvlx8A4A9BMrXbiKsRHDf3KUFCDkYMEt1LmjEYGomIkqFLvYs88cmPSkNkTaNLkxfLakcwPMQLEolWJOyBioQ8jOHzCbz9XSUA4MdqB7yBJsyk7v4Z+JRa7WhRKiEyo4HNlt2JJaSxlogoGbpMkNhxqAHLPt4Ji1GHAb2sAICq+pZjPm51Q7ByEK9Hoj6B6Z8AlHUTjjb6j7tp71FUBaoALR6f0tjZ4k3i9M/A8Em0ZlI2W3YvHNogomTrMu8i+RkWXF7SF3ecNwyjA7tvHqxrOubjVjuCYeRgXVPMtSQalAWp4gcJpUciUJF4+1t/NcIaGF7YWeWvqKRiZct9R1v/vDi00b30y7Hi4lGFGFbQ/XbfJaLOqcu8i2RZjXhk2mhcP2kgCgLLMcerICRK7hkA/OXguhiLSSU6tJEVsrqlEMFhjWvG9wcA7Kzy93akYmXLpiifUlmR6F7GFmfj8Rkn4bKSvqk+FSLqIbrcu4gkScpyzFpMAQ0NEkDscNKQwBLZQPh+G1sP1GN/bRPGFmdj0pA8AMAuJUgkc2XL8KpH6P4XDBJERHQsuuS7SGEgSMSbrpkoOUj0z7HGPWYiS2QDobM23Nh6oA4AcOpxORjc2wYgtCKR/KEN2Un9s5W/J6PZk4iIuq8u+S5SkOX/RK1FRUJeoGlkUVbcY9Y3u6HXSUqvQyzKglRNbuw85A8NQ/Mz0CfLgnSTHj9WOSCECK5smcShDdlJ/e3K37lENhERHYsuuaOS3CNxUMMeiZF9s/DmloNxKxI2swGSFP+N154WHNqQ17oY3NsGSZIwuLcNm/fVobK+Wdk0KxlDG0a9DgadBE9g6ukYViSIFILtJETHpEu+i+RlmKHXSTikxdCGowUGnYTjA13u0Y7p8frgdHnbHNYA/G/M6SY9ap3+ioQkAYPy/MMag+ThjUMOZWgjWbMmQqsSRdlpyM80A2CPBBERHZsu+S6i10nonWFGVUMzPF71C+94fQJHHC3ItZnRx+4fLolW5XC0JDZjQ2a3mlDX5Mb+2ib0y7Yqb+JDevvDys4qB1o8XpgNujYrHFqR+yT0OgnZVhP6Zft7QhgkiIjoWHTZd5GCLAt8InwdiPY66nTBJ/wVjuBMkNZrLSTaaCmT+yQAYEigChH6911VDWhx+5IyrCGTmzp7pZug00lKcyl7JIiI6Fh03SCReewzN+T+iLwMMzLMBqSb9FGbLesTXIxKFhokBocEiRF9MwEA63YdQYvHp2zvnQzyfht5Gf4hjdOH5iLDbMDxBZlJOwciIup+umSzJQClgnAsfRJykMi1mSBJEvKzLPipuhGNLR6km4M/mkQXo5LJ+20A4UGiMCsNo4uysHmff1poMisS8tCGHCSmjinCZaP7QqdjRYKIiNTrshUJLdaSCK1IhB7zpn9uxB1rNiurXMpBIuGKRFrI0EZ++FLFF5xYqPw9mTMm5P028mxm5TKGCCIiOlaavpO53W7Mnz8f2dnZyMnJQWlpKTwej5YPoVDWkjiGKaDyGhLym+uJff1rSazddRgvbtyHB9/cBiB0C/HEKhLZIRWJQXnpYdddeGKB8vdkLEYlkxs+5dBERESkBU2DxOLFi7F27Vps27YNW7duxWeffYYlS5Zo+RAKbSsS/mP99/nH473bzsCr8yYi12bG6q/34bOd1cry2O1ttizMsrQKHwNy0zG80N+XkMqhDSIiIi1o2iPx9NNP4//+7/9QWOgv399zzz244447cN9992n5MACCzZYb99TggTe2qTrGZzurAfh7JAB/qX9oYChi0WUj8Jvnv8F/v7hFmRra3h6J0P6IUBeeWIDvD9YnOUj4KxK5NgYJIiLSjmZB4ujRo9i3bx9KSkqUy0pKSlBRUYG6ujpkZWWF3b6srAz333+/6sfLz7Qgw2zAgbpmPL1ut+rj6CSguFd6q8svHFmIi0YW4K1vK3EgUPXoG7LZVTzycEbonhahLh5ViKUf7Uz4eFqQg9dxea2fKxERkVqSEEJocaC9e/eif//+qK6uRm5uLgCguroavXv3xt69e1FUVBT/RCQJ7T2VH6sdyn4WahVlpym9EZGaXF6s23UYHp+A3WrEKQNyEm5Q3HagHoN6p8fsg/ix2oFcmxlZaYlVOY6V0+XBrioHRhXZk/J41DWo+X+XcklaxI2IAtp4jdAsSBw9ehQ5OTnYtWsXBg0aBADYtWsXhgwZgtra2lYViVYn0hVf0Ii6uC75/45Bgii52niN0GyQPjs7G0VFRSgvL1cuKy8vR79+/doMEURERNQ1adrtd9111+HBBx9EZWUlKisrsWTJEsyZM0fLhyAiIqJORNNZGwsWLMCRI0cwfPhwAMC1116Lu+++W8uHICIiok5Esx6JY9Ulx2qJurgu+f+OPRJEyZWsHgkiIiLqeRgkiIiISDUGCSIiIlKtU20jLnHsk4ja0tV6Ooi6uU4TJBJt+OqSzWEx8Ll0TnwuRESJ49AGERERqcYgQURERKp1uSCxcOHCVJ+CZvhcOic+FyKixHWaBamIiIio6+lyFQkiIiLqPBgkiIiISDUGCSIiIlKNQYKIiIhUY5AgIiIi1bpMkHC73Zg/fz6ys7ORk5OD0tJSeDyeVJ9Wm1paWnDDDTdg4MCByMjIwPHHH4+nn35auX7KlCkwm82w2WzK14EDB1J4xrHNnj0bJpMp7FzXr1+vXN+Vfkehz8Fms8FoNGLUqFHK9W0911RatmwZxo0bB7PZjMsvvzzsuvr6esyYMQOZmZnIz8/HokWL2nU9EVF7dZkgsXjxYqxduxbbtm3D1q1b8dlnn2HJkiWpPq02eTweFBYW4oMPPkB9fT2eeeYZ3H777XjvvfeU2zz88MNwOBzKV58+fVJ4xvHNnTs37FwnTJigXNeVfkehz8HhcGD48OG4+uqrw24T77mmUp8+fXDvvffihhtuaHVdaWkpampqUFFRgc8++wx//etf8eyzzyZ8PRFRe3WZIPH000/j3nvvRWFhIQoLC3HPPfdg+fLlqT6tNqWnp+OBBx7AoEGDIEkSTj31VJx55plYu3Ztqk9Nc131d7RhwwZs27YNs2fPTvWpJOSKK67A5Zdfjtzc3LDLnU4nVq5cicWLF8Nut2Po0KEoLS1VfgdtXU9EpEaXCBJHjx7Fvn37UFJSolxWUlKCiooK1NXVpe7EVGhubsaGDRvCyuiLFy9GTk4OxowZ0+k/HT777LPIycnBiBEj8Oijj8Ln8wHo2r+j5cuX48ILL2xVCYr1XDur7du3w+VytfodbNmyJaHriYjU6DS7f8bjcDgAAHa7XblM/ntDQwOysrJScFbtJ4TAnDlzMGTIEFxxxRUAgN///vc44YQTYLVa8dFHH+Gqq65CRkYGpk6dmuKzbe2WW27BI488gpycHHz11Ve46qqroNPpcNttt3XZ31FjYyNWrlzZKsDFe66dlcPhQHp6OgyG4H9ru92OhoaGhK4nIlKjS1QkbDYbAIR9spX/npGRkZJzai8hBObOnYvt27fj1VdfhU7n/9FPmDABWVlZMBqNOP/883HTTTdh1apVKT7b6E466STk5eVBr9fj1FNPxV133aWca1f9Ha1ZswZWqxUXX3xx2OXxnmtnZbPZ4HQ6wxpc6+rqlJ9/W9cTEanRJYJEdnY2ioqKUF5erlxWXl6Ofv36ddpPuqGEEJg3bx6+/PJLvPfee3HPWQ4YXUHouXbV39Hf/vY3zJo1K+xTejRd4fcybNgwGI1GbN68WbmsvLwcI0eOTOh6IiI1Ov+rY8B1112HBx98EJWVlaisrMSSJUswZ86cVJ9WQubPn49169bh/fffR3Z2tnJ5bW0t3nrrLTidTni9Xnz44Yd48sknceWVV6bwbGNbvXo16uvrIYTA119/jYceeijsXLva72j79u34/PPPcf3117e6rq3nmkoejwfNzc3weDzw+Xxobm6Gy+WC1WrF9OnTsWDBAtTV1WHnzp1YunSp8jto63oiIlVEF+FyucTcuXOF3W4XdrtdzJ8/X7jd7lSfVpv27NkjAAiz2SzS09OVr5tuuklUVVWJU045RWRkZIiMjAwxcuRIsXz58lSfckynn366yMrKEunp6WLo0KHi4YcfFl6vV7m+q/2O7rzzTnHGGWdEva6t55pKCxcuFADCviZPniyEEKKurk5cffXVwmaziby8PHH//feH3bet64mI2ovbiBMREZFqXWZog4iIiDofBgkiIiJSjUGCiIiIVGOQICIiItUYJIiIiEg1BoluZMCAAbjjjjsSuu0f/vAHnHnmmR18Rl3P/Pnzo64rQdRV8HUgXFlZWasN7hIxe/ZsjBs3Lu5tXC4XysrKwhbiA4D9+/fDZrPhp59+avfjdkUMEj2Qw+HAQw89hLvuuivVp9Lp3HHHHXj++eexa9euVJ8KUYfqKa8Dc+bMwbvvvtshx3a5XLj//vtbBYm+ffti+vTpeOCBBzrkcTsbBolOrqmpSfNjrlixAmazGeedd57mx+7qBgwYgEmTJuGJJ55I9akQKfg60H5utxterxdFRUUYO3Zs0h//uuuuw4oVK3DkyJGkP3ayMUgkiVwme/XVV3H88cfDYrFg0qRJ2LZtW9jtJEnCH/7wB9x6663Iy8tT9kE4fPgwZs2ahV69esFqtWLKlCn4+uuvoz7WokWLUFBQAJvNhmuuuabVNt7/+Mc/cMUVV0CSJOUyufz35ZdfYty4cUhLS8OkSZOwe/duVFVV4fLLL4fNZsPw4cPx0UcfhR3P6/WirKwM/fv3h9lsxogRI/DCCy8o1z/zzDMwmUyora0Nu9/WrVshSRI++OAD5bLXXnsN48aNg8ViQUFBAX7729/C7XbH/dlGK+U+88wzkCRJ2ZX0k08+gSRJeO+993DJJZcgPT0d/fv3x5NPPtnqeFdeeSWef/75Tr9tOHU9fB3ouNeBKVOm4Je//CWeeuopDBo0CBaLBQcOHIg6tLFlyxacdtppsFgsGDFiBN566y2MGzcOs2fPbnXc999/H6NGjUJ6ejomTZqErVu3KtfJG95dd911kCQJkiRhz549AICJEyciJycHK1eujHve3UKql9bsKWbNmiVyc3PFwIEDxXPPPSdeeuklceKJJ4qioiLR1NSk3A6AKCgoEFdddZV4++23xZtvvimEEGLixIkiPz9fPP300+L1118Xp59+urDZbGLnzp3KfYuLi0WfPn3EGWecIV5//XXxl7/8RWRlZYlf/vKXym0cDocwGAxi5cqVYee3cOFCkZaWJkaNGiWee+458corr4h+/fqJiRMnirPOOks88sgj4t133xVnn322yMnJEY2Njcp97777bmEwGMSiRYvEO++8I2644QYBQLzwwgtCCCGOHj0qTCaTePrpp8Mec8GCBSI/P194PB4hhBCrVq0SOp1O/OY3vxHvvvuu+POf/yyysrLE7bffHvdnW1xc3Oo2f//73wUA0dDQIIQQ4uOPPxYARFFRkfjd734n3nnnHXHTTTcJAOKNN94Iu295ebkAIMrLy+M+LlF78XWg414HJk+eLAoKCkRJSYlYs2aNePPNN0VdXZ1YuHCh6NWrl3K7xsZG5XYvv/yyeOGFF8TQoUNFXl6emDVrVtjvKi8vT4wePVqsXLlSvPbaa2LIkCFixIgRwufzCSGE+OijjwQAce+994r169eL9evXi+bmZuUYl19+ubj88svjnnd3wCCRJLNmzRIAxLp165TL9uzZI/R6vXjiiSeUywCIMWPGhN337bffFgDEJ598olzmcDhEbm6uuPHGG5XLiouLRXZ2tvLmKYQQzz33nJAkSWzbtk0IIcS6desEAPHdd9+FPYa8f0PoYzz++OMCQNh+DFu3bhUAxFtvvSWEEOLIkSPCarWKsrKysONdeOGFYujQocr3l156qTj//PPDbjN06FAxb948IYQQPp9P9O/fX8yePTvsNsuXLxcWi0UcPnxYxNKeIHHDDTeE3e6cc84R48ePD7vM7XYLvV4vnnrqqZiPSaQGXwc67nVg8uTJwmKxiMrKylbPKTRILFu2TBiNRrFv3z7lsi+//FIAaBUk9Hq92LFjh3LZK6+8IgCI77//XgghRENDgwAg/v73v0c9p4ULF4o+ffrEPOfugkMbSdS7d2+cdtppyvfFxcUYO3YsNmzYEHa7iy66KOz7DRs2oHfv3pg8ebJyWXp6Oi655BKsXbs27LbnnnsubDab8v3UqVMhhMBXX30FAKisrASAqF3MJpMJp59+uvL94MGDAQBnnXVWq8v2798PAPjuu+/gdDoxbdq0sGNNnz4dO3bsQHV1tfL9hx9+qIwXlpeXY8eOHZg+fToAYMeOHaioqMBVV10Fj8ejfJ111llobm7Gd9991+p81Zg6dWrY91dccQU2btwIr9erXGYwGGC325WfFZGW+DrQca8DY8eORX5+ftzbfPXVVxg7diz69u2rXHbKKadEvd+AAQMwZMgQ5fsTTjgBALBv3764jyHLzc1FVVUVRDff0opBIol69+4d9bKDBw+GXRb5D/rgwYNR75ufn4+ampq4j2G1WmGz2ZTHaG5uBgCYzeZWx8vIyIBOF/wnYTKZAAB2u73VZfJx5ONGnrP8vXx+l156KYxGI1566SUAwKpVq1BUVIRJkyYB8I/9Av4XT6PRqHwNHDgQALB3795W56tG5M+nd+/e8Hg8yuPLzGaz8hyJtMTXgY57HWgrRAD+EJWXl9fq8miXhT5noPXzbovZbFbCUHdmSPUJ9CRVVVVRLxsxYkTYZaHNTwBQWFgY9b6HDh1CTk5O3MdwOp1wOBwoLCwEAOX2tbW1rf6TqCEft6qqCr169Qo7t9DHs9lsuPjii7Fq1SrceOONWL16NaZNm6Y8V/l2Tz31FMaMGdPqceQXkmgsFgtcLlfYZUePHo1628ifT1VVFQwGQ6tPZrW1ta1+tkRa4OtAx7wOAK1/ZtEUFBRg+/btrS6XqyZaqq2thc1mg9Fo1PzYnQkrEklUVVWFzz//XPm+oqIC33zzDU455ZS49xs/fjyqqqrw6aefKpc5nU68+eabSpKXvf/++8pMBQB45ZVXIEmSsrDKsGHDAAC7d+8+5ucDACeeeCKsVivWrFkTdvnq1asxdOjQsJR/9dVX49///jfeeOMN/PTTT7j66quV64YNG4a+fftiz549GDduXKuv0BenSEVFRfj+++/DLnvvvfei3vaVV15p9f3YsWOh1+uVy6qrq+F0OjF06NC2fwBE7cTXgY55HUjUySefjI0bNyrDMoB/2EgOPe3RVoViz549PeJ1hBWJJMrNzcW1116LxYsXIy0tDQsXLkTv3r2jTjkKdf755+O0007D9OnT8dBDD6FXr1743//9XzQ1NeHOO+8Mu21aWhouvvhi3HnnnTh48CDuvPNOTJ06VRnbGzhwIAoLC7Fx40ZNVrTLycnBrbfeisWLF8NgMGDcuHF4+eWX8dZbb2HFihVht73oootgtVpx0003YeDAgWEvnDqdDo8++ih+/etfo76+HhdeeCFMJhN++uknvPrqq3jxxRdhtVqjnsPUqVNRWlqKJUuW4OSTT8ZLL70UNkUr1Ntvv4177rkHkydPxssvv4z3338fr732Wthtvv76a0iSFDaOTaQVvg50zOtAoq677josXrwYl1xyCRYuXIimpiYsXLgQeXl5YUM6iTCZTBg4cCBWr16NE088ERaLBaNGjVICxtdff42JEyce0/l2CSlu9uwxZs2aJcaOHSteeuklMWTIEGEymcRpp50mvv3227DbARBLly5tdf+qqirx61//WtjtdmGxWMQZZ5whNmzYEHab4uJi8V//9V9i4cKFonfv3sJqtYqrr75aHD16NOx28+bNE2eddVbYZZGdzUIEZzq0dY4ej0fcd999oqioSBiNRjF8+HDx3HPPRf05XHPNNQKAuOuuu6Je/9Zbb4lJkyYJq9UqMjIyxOjRo8U999wj3G531NsLIYTL5RK33XabyM/PF3a7Xdxyyy3iL3/5S9RZG++884644IILRFpamujbt694/PHHWx3vlltuEVOmTIn5eERq8XXAryNeByZPniyuvPLKVpdHe07l5eViwoQJwmQyiaFDh4pXXnlFDBkyRPznf/6nchv5dxVq9+7draaMv/vuu2LkyJHCbDYLAGL37t1CCP/vSq/Xh82A6a4YJJIk2j/KVPnmm2+EXq8XBw8eTPWpJE2sF8NIHo9H9O3bV/zzn/9M0plRT8LXgc7pp59+EgaDodUaF8fiySefFIMHD1bWnOjO2CPRA40ZMwbnn38+li1blupT6XTWrFmDtLS0sHFbou6oJ78O/P73v8c//vEPfPLJJ3j22Wdx0UUXIS8vD1deeaUmxxdC4LHHHsM999yTUANoV8cg0UM9+uijUac79XRCCCxfvhwGA9uHqPvrqa8DkiTh/vvvxwUXXIDS0lIMGjQIH330ETIzMzU5fmVlJa655hr8+te/1uR4nZ0kRDdfKYOIiIg6DCsSREREpBqDBBEREanGIEFERESqdZqOsom//N9UnwJRj7LuxTtSfQqqnHYVXyuIkunz1fFfK1iRICIiItUYJIiIiEg1BgkiIiJSjUGCiIiIVGOQICIiItUYJIiIiEg1BgkiIiJSjUGCiIiIVGOQICIiItUYJIiIiEg1BgkiIiJSjUGCiIiIVGOQICIiItUYJIiIiEg1BgkiIiJSjUGCiIiIVGOQICIiItUYJIiIiEg1Q6pPoKuQvELj42l6OAi91seTtD0gUQ/hTtP285lO49ceQ5O2x9P6tYe6HlYkiIiISDUGCSIiIlKNQYKIiIhUY5AgIiIi1RgkiIiISDUGCSIiIlKNQYKIiIhUY5AgIiIi1RgkiIiISDUGCSIiIlKNQYKIiIhUY5AgIiIi1RgkiIiISDUGCSIiIlKNQYKIiIhUY5AgIiIi1RgkiIiISDUGCSIiIlKNQYKIiIhUM6T6BLoKoZc0PZ47XdvjGZqFpscjInWMTT5Nj2fQ+HieNH5+JG3xXxQRERGpxiBBREREqjFIEBERkWoMEkRERKQagwQRERGpxiBBREREqjFIEBERkWoMEkRERKQagwQRERGpxiBBREREqjFIEBERkWoMEkRERKQagwQRERGpxiBBREREqjFIEBERkWoMEkRERKQagwQRERGpxiBBREREqjFIEBERkWqGVJ9AT2Vs9Gl6PKGXND0eEXUOQuL/bercWJEgIiIi1RgkiIiISDUGCSIiIlKNQYKIiIhUY5AgIiIi1RgkiIiISDUGCSIiIlKNQYKIiIhUY5AgIiIi1RgkiIiISDUGCSIiIlKNQYKIiIhUY5AgIiIi1RgkiIiISDUGCSIiIlKNQYKIiIhUY5AgIiIi1RgkiIiISDUGCSIiIlLNkOoT6Kkkr7bHE3ptj0dEnYPXLKX6FIjiYkWCiIiIVGOQICIiItUYJIiIiEg1BgkiIiJSjUGCiIiIVGOQICIiItUYJIiIiEg1BgkiIiJSjUGCiIiIVGOQICIiItUYJIiIiEg1BgkiIiJSjUGCiIiIVGOQICIiItUYJIiIiEg1BgkiIiJSjUGCiIiIVGOQICIiItUYJIiIiEg1Q6pPoKc6OkzbH33Wbq+mx/OaJE2PBwB6l9D8mETdneTT+oDaHk7frPUJAh4rP+N2JfxtERERkWoMEkRERKQagwQRERGpxiBBREREqjFIEBERkWoMEkRERKQagwQRERGpxiBBREREqjFIEBERkWoMEkRERKQagwQRERGpxiBBREREqjFIEBERkWoMEkRERKQagwQRERGpxiBBREREqjFIEBERkWoMEkRERKQagwQRERGpxiBBREREqhlSfQIdxXLEpenxmnuZND1e9g6PpsfzGSVNj5f95UFNjwcA9WMKND9mZyb5hKbHEzptf8fk507T9vOUscmn6fHcVm1/74YWbf9djn/wK02PBwDrHhyv+TE7M63/b2v92tMWViSIiIhINQYJIiIiUo1BgoiIiFRjkCAiIiLVGCSIiIhINQYJIiIiUo1BgoiIiFRjkCAiIiLVGCSIiIhINQYJIiIiUo1BgoiIiFRjkCAiIiLVGCSIiIhINQYJIiIiUo1BgoiIiFRjkCAiIiLVGCSIiIhINQYJIiIiUo1BgoiIiFQzpPoEeip9i0/T47VkavurPHBhX02PBwCuLG2PV/T7zzU9nvOK8ZoeT+gkTY9HHcPQrO3/Ra2ZGrV+rdBrerw3XjxN0+MBQL99Dm0P+MUWTQ/X+EttXyv0Lm1/xz5Dcl97WJEgIiIi1RgkiIiISDUGCSIiIlKNQYKIiIhUY5AgIiIi1RgkiIiISDUGCSIiIlKNQYKIiIhUY5AgIiIi1RgkiIiISDUGCSIiIlKNQYKIiIhUY5AgIiIi1RgkiIiISDUGCSIiIlKNQYKIiIhUY5AgIiIi1RgkiIiISDUGCSIiIlLNkOoT6CjGzT9perzms47X9Hhum17T4xmbhMbH82p6PABApbaHe/dAuabHO33+eE2Pl/nNQU2PV39SoabHIz/7V9r+nurGaft78hkkTY9ndPo0PV7Odk0PBwBoLErT9Hjpmh5Nex6Ltp/pdR5t3w/afLykPhoRERF1KwwSREREpBqDBBEREanGIEFERESqMUgQERGRagwSREREpBqDBBEREanGIEFERESqMUgQERGRagwSREREpBqDBBEREanGIEFERESqMUgQERGRagwSREREpBqDBBEREanGIEFERESqMUgQERGRagwSREREpBqDBBEREalmSPUJdBQpLU3T42V88L2mx4Ner+nhREuLpsdzTRiu6fEAQN/s1fR4G1rcmh7PtqNO0+P9NLNI0+Plfqftz4/8RK22v/d3/rha0+N93pyh6fHOs2r7/+aGvRM1PR4AlGRUaHq8t9aN0PR4meVVmh7PVZSt6fGac42aHq8trEgQERGRagwSREREpBqDBBEREanGIEFERESqMUgQERGRagwSREREpBqDBBEREanGIEFERESqMUgQERGRagwSREREpBqDBBEREanGIEFERESqMUgQERGRagwSREREpBqDBBEREanGIEFERESqMUgQERGRagwSREREpBqDBBEREakmCSFEqk8CACb+8n9TfQpEPcq6F+9I9SmoctpVfK0gSqbPV8d/rWBFgoiIiFRjkCAiIiLVGCSIiIhINQYJIiIiUo1BgoiIiFRjkCAiIiLVGCSIiIhINQYJIiIiUo1BgoiIiFRjkCAiIiLVGCSIiIhINQYJIiIiUo1BgoiIiFRjkCAiIiLVGCSIiIhINQYJIiIiUo1BgoiIiFRjkCAiIiLVGCSIiIhINUkIIVJ9EkRERNQ1sSJBREREqjFIEBERkWoMEkRERKQagwQRERGpxiBBREREqjFIEBERkWoMEkRERKQagwQRERGp9v+MuqGhZyFiywAAAABJRU5ErkJggg==",
      "text/plain": [
       "<Figure size 630x630 with 4 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# full policy gradient RL for picking up 'treasure chests'\n",
    "# in an automatically generated maze; 2020 by F.M.\n",
    "\n",
    "M=11 # the size of the world: M x M\n",
    "eta=0.01 # the learning rate\n",
    "num_chests=10 # maximum number of treasure chests\n",
    "\n",
    "# make a maze, convert array from True/False to integer:\n",
    "world=np.array(maze(width=M,height=M),dtype='int')\n",
    "\n",
    "# the four directions of motion [delta_jx,delta_jy]:\n",
    "directions=np.array([[0,1],[0,-1],[1,0],[-1,0]])\n",
    "\n",
    "# the policy probabilities as an array policy[state,action]\n",
    "# here the state is represented by two coordinates jx,jy\n",
    "policy=np.full([M,M,4],0.25)\n",
    "# and also the underlying 'z'-values for the\n",
    "# softmax parametrization:\n",
    "policy_z=np.full([M,M,4],0.0)\n",
    "\n",
    "# steps inside one trajectory\n",
    "nsteps=80\n",
    "\n",
    "# total number of trials, i.e. trajectories\n",
    "ntrials=100\n",
    "skipsteps=5 # don't plot every trial\n",
    "\n",
    "# storing all the state/action pairs of the current trajectory\n",
    "states=np.zeros([nsteps,2], dtype='int')\n",
    "actions=np.zeros(nsteps, dtype='int')\n",
    "\n",
    "# a map of rewards (the 'boxes' are here!)\n",
    "reward=np.zeros([M,M])\n",
    "\n",
    "# storing all the returns, for all trials:\n",
    "Returns=np.zeros(ntrials)\n",
    "\n",
    "# try random selection of reward sites (treasure chests)\n",
    "for n in range(10): \n",
    "    jx_target,jy_target=np.random.randint(M,size=2)\n",
    "    if jx_target>4 or jy_target>4: # stay away from starting point!\n",
    "        if world[jx_target,jy_target]==0: # empty, keep it!\n",
    "            reward[jx_target,jy_target]+=1\n",
    "        \n",
    "# try many trajectories:\n",
    "for trial in range(ntrials):\n",
    "\n",
    "    # set return to zero for this trajectory:\n",
    "    R=0\n",
    "    # initial position:\n",
    "    jx,jy=1,1\n",
    "    \n",
    "    # go through all time steps\n",
    "    for t in range(nsteps):\n",
    "        # make a random step, according to the policy distribution\n",
    "        p=np.random.uniform()\n",
    "        cumulative_distribution=np.cumsum(policy[jx,jy,:])\n",
    "        for pick in range(4):\n",
    "            if p<cumulative_distribution[pick]:\n",
    "                break\n",
    "\n",
    "        # record the move\n",
    "        states[t,0]=jx\n",
    "        states[t,1]=jy\n",
    "        actions[t]=pick\n",
    "\n",
    "        # now make the move\n",
    "        jx_new,jy_new=np.array([jx,jy])+directions[pick]\n",
    "\n",
    "        # really make it if there is no wall:\n",
    "        if world[jx_new,jy_new]==0: # is empty, can move!\n",
    "            jx,jy=jx_new,jy_new\n",
    "        \n",
    "        # get a reward if on a treasure chest!\n",
    "        r=reward[jx,jy]\n",
    "        R+=r\n",
    "   \n",
    "    # store the return\n",
    "    Returns[trial]=R\n",
    "    \n",
    "    # use policy gradient update rule to adjust\n",
    "    # probabilities!\n",
    "    for t in range(nsteps): # go through the trajectory again\n",
    "        a=actions[t] # remember the action taken at step t\n",
    "        sx=states[t,0] # state/x-position at step\n",
    "        sy=states[t,1] # state/y-position\n",
    "        kronecker=np.zeros(4); kronecker[a]=1.0\n",
    "        policy_z[sx,sy,:]+=eta*R*(kronecker-policy[sx,sy,:])\n",
    "\n",
    "    # now calculate (again) the policy probab. from the z-values\n",
    "    policy=np.exp(policy_z)\n",
    "    policy/=np.sum(policy,axis=2)[:,:,None] # normalize\n",
    "    # these two steps together implement softmax on every\n",
    "    # site! efficient array syntax!\n",
    "    \n",
    "    # visualize!\n",
    "    if trial%skipsteps==0 or trial==ntrials-1:\n",
    "        # show what's happened in this trajectory\n",
    "        clear_output(wait=True)\n",
    "        fig,ax=plt.subplots(ncols=2,nrows=2,figsize=(7,7))\n",
    "        ax[0,0].plot(Returns) # all the returns, in all trials\n",
    "        ax[0,0].set_title(\"Return vs. trial\")\n",
    "        \n",
    "        picture=np.zeros([M,M,3]) # last index: red/green/blue\n",
    "        picture[:,:,0]=world # walls are red\n",
    "        for j in range(nsteps): # highlight trajectory\n",
    "            picture[states[j,0],states[j,1],1]=0.5*(1.0+(1.0*j)/nsteps)\n",
    "        # put a bright pixel at the positions visited\n",
    "        picture[:,:,2]+=0.5*reward # highlight the target sites!\n",
    "        picture[:,:,0]+=0.5*reward\n",
    "\n",
    "        # show picture (transpose is needed because\n",
    "        # otherwise the first coordinate jx is plotted upwards,\n",
    "        # not to the right)\n",
    "        ax[0,1].imshow(np.transpose(picture,[1,0,2]),origin='lower')\n",
    "        ax[0,1].axis('off')\n",
    "        \n",
    "        ax[1,0].imshow(np.transpose(policy[:,:,0]),origin='lower')\n",
    "        ax[1,0].axis('off')\n",
    "        ax[1,0].set_title(\"prob(move up)\")\n",
    "        ax[1,1].imshow(np.transpose(policy[:,:,2]),origin='lower')\n",
    "        ax[1,1].set_title(\"prob(move right)\")\n",
    "        ax[1,1].axis('off')\n",
    "        plt.show()"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Tutorial Exercise: Change the algorithm, such that the treasure chests are 'taken away' by the robot\n",
    "\n",
    "That is: the reward value at a given site should decrease every time the reward is received (but you need to re-initialize to the old reward map for every new trial!)\n",
    "\n",
    "Observe how the strategy looks like now!\n",
    "\n",
    "Attention: don't go to negative rewards! (unless you want to train the robot to avoid places after it picked up a chest there!)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Tutorial Exercise: Think about other rules of the game!\n",
    "\n",
    "The only constraint is that the best (or at least a good) strategy can be formulated based only on the position (e.g. wandering ghosts like in PacMan would be a problem for the robot)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Homework Exercise: Invent a game where the state needs to contain additional information (rather than just the position jx,jy)!\n",
    "\n",
    "...but in such a way that it can still be handled with a table."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.8.16"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}