Dynamic_Programming-zh.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 迷你项目：动态规划\n",
    "\n",
    "在此 notebook 中，你将自己编写很多经典动态规划算法的实现。\n",
    "\n",
    "虽然我们提供了一些起始代码，但是你可以删掉这些提示并从头编写代码。\n",
    "\n",
    "### 第 0 部分：探索 FrozenLakeEnv\n",
    "\n",
    "请使用以下代码单元格创建 [FrozenLake](https://github.com/openai/gym/blob/master/gym/envs/toy_text/frozen_lake.py) 环境的实例。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "from frozenlake import FrozenLakeEnv\n",
    "\n",
    "env = FrozenLakeEnv()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "智能体将会在 $4 \\times 4$ 网格世界中移动，状态编号如下所示："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[[ 0  1  2  3]\n",
    " [ 4  5  6  7]\n",
    " [ 8  9 10 11]\n",
    " [12 13 14 15]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "智能体可以执行 4 个潜在动作："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "LEFT = 0\n",
    "DOWN = 1\n",
    "RIGHT = 2\n",
    "UP = 3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "因此，$\\mathcal{S}^+ = \\{0, 1, \\ldots, 15\\}$ 以及 $\\mathcal{A} = \\{0, 1, 2, 3\\}$。请通过运行以下代码单元格验证这一点。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Discrete(16)\n",
      "Discrete(4)\n",
      "16\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "# print the state space and action space\n",
    "print(env.observation_space)\n",
    "print(env.action_space)\n",
    "\n",
    "# print the total number of states and actions\n",
    "print(env.nS)\n",
    "print(env.nA)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "动态规划假设智能体完全了解 MDP。我们已经修改了 `frozenlake.py` 文件以使智能体能够访问一步动态特性。 \n",
    "\n",
    "请执行以下代码单元格以返回特定状态和动作对应的一步动态特性。具体而言，当智能体在网格世界中以状态 1 向左移动时，`env.P[1][0]` 会返回每个潜在奖励的概率和下一个状态。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "每个条目的格式如下所示"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "prob, next_state, reward, done"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "其中：\n",
    "- `prob` 详细说明了相应的  (`next_state`, `reward`) 对的条件概率，以及\n",
    "- 如果 `next_state` 是终止状态，则 `done` 是 `True` ，否则是 `False`。\n",
    "\n",
    "因此，我们可以按照以下方式解析 `env.P[1][0]`：\n",
    "$$\n",
    "\\mathbb{P}(S_{t+1}=s',R_{t+1}=r|S_t=1,A_t=0) = \\begin{cases}\n",
    "               \\frac{1}{3} \\text{ if } s'=1, r=0\\\\\n",
    "               \\frac{1}{3} \\text{ if } s'=0, r=0\\\\\n",
    "               \\frac{1}{3} \\text{ if } s'=5, r=0\\\\\n",
    "               0 \\text{ else}\n",
    "            \\end{cases}\n",
    "$$\n",
    "\n",
    "你可以随意更改上述代码单元格，以探索在其他（状态、动作）对下环境的行为是怎样的。\n",
    "\n",
    "### 第 1 部分：迭代策略评估\n",
    "\n",
    "在此部分，你将自己编写迭代策略评估的实现。\n",
    "\n",
    "你的算法应该有四个**输入**参数：\n",
    "- `env`：这是 OpenAI Gym 环境的实例，其中 `env.P` 会返回一步动态特性。\n",
    "- `policy`：这是一个二维 numpy 数组，其中 `policy.shape[0]` 等于状态数量 (`env.nS`) ， `policy.shape[1]` 等于动作数量 (`env.nA`) 。`policy[s][a]`  返回智能体在状态 `s` 时根据该策略选择动作 `a` 的概率。\n",
    "- `gamma`：这是折扣率。它必须是在 0 到 1（含）之间的值，默认值为：`1`。\n",
    "- `theta`：这是一个非常小的正数，用于判断估算值是否足够地收敛于真值函数 (默认值为：`1e-8`）。\n",
    "\n",
    "该算法会返回以下**输出结果**：\n",
    "- `V`：这是一个一维numpy数组，其中 `V.shape[0]` 等于状态数量 (`env.nS`)。`V[s]` 包含状态 `s` 在输入策略下的估算值。\n",
    "\n",
    "请完成以下代码单元格中的函数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(0.3333333333333333, 1, 0.0, False),\n",
       " (0.3333333333333333, 0, 0.0, False),\n",
       " (0.3333333333333333, 5, 0.0, True)]"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "env.P[1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "def policy_evaluation(env, policy, gamma=1, theta=1e-8):\n",
    "    V = np.zeros(env.nS)\n",
    "    while True:\n",
    "        delta = 0\n",
    "    \n",
    "        ## TODO: complete the function\n",
    "        for s in range(env.nS):\n",
    "            Vs = 0\n",
    "            for a, action_prob in enumerate(policy[s]):\n",
    "                for prob, next_state, reward, done in env.P[s][a]:\n",
    "                    Vs += action_prob * prob * (reward + gamma * V[next_state])\n",
    "            delta = max(delta, np.abs(V[s]-Vs))\n",
    "            V[s] = Vs\n",
    "        if delta < theta:\n",
    "            break\n",
    "    \n",
    "    return V"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "16"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "env.nS"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们将评估等概率随机策略  $\\pi$，其中对于所有 $s\\in\\mathcal{S}$ 和 $a\\in\\mathcal{A}(s)$ ，$\\pi(a|s) = \\frac{1}{|\\mathcal{A}(s)|}$。  \n",
    "\n",
    "请使用以下代码单元格在变量 `random_policy`中指定该策略。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "random_policy = np.ones([env.nS, env.nA]) / env.nA"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 0.25,  0.25,  0.25,  0.25],\n",
       "       [ 0.25,  0.25,  0.25,  0.25],\n",
       "       [ 0.25,  0.25,  0.25,  0.25],\n",
       "       [ 0.25,  0.25,  0.25,  0.25],\n",
       "       [ 0.25,  0.25,  0.25,  0.25],\n",
       "       [ 0.25,  0.25,  0.25,  0.25],\n",
       "       [ 0.25,  0.25,  0.25,  0.25],\n",
       "       [ 0.25,  0.25,  0.25,  0.25],\n",
       "       [ 0.25,  0.25,  0.25,  0.25],\n",
       "       [ 0.25,  0.25,  0.25,  0.25],\n",
       "       [ 0.25,  0.25,  0.25,  0.25],\n",
       "       [ 0.25,  0.25,  0.25,  0.25],\n",
       "       [ 0.25,  0.25,  0.25,  0.25],\n",
       "       [ 0.25,  0.25,  0.25,  0.25],\n",
       "       [ 0.25,  0.25,  0.25,  0.25],\n",
       "       [ 0.25,  0.25,  0.25,  0.25]])"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "random_policy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "运行下个代码单元格以评估等概率随机策略并可视化输出结果。状态值函数已调整形状，以匹配网格世界的形状。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAVsAAAFoCAYAAAD5IVjuAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4wLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvpW3flQAAIABJREFUeJzt3Hd8FNX+xvHP2ZZKCBBI6ARBARGR0EGxgqh47dhQbFeuV0WxYteLevVnRxFFL9jlKparYkEp0gUEQVFsWFACJLT0ze6e3x8TEpZsQoJkAH3evvaFmTlzzpnvzD472Rkw1lpERKRuefb0BERE/goUtiIiLlDYioi4QGErIuICha2IiAsUtiIiLlDYyl7FGPOTMeboPT2PumCMOccY89GenofsGQrbfZwxpr8xZp4xZosxZqMxZq4xpkfZuuHGmDm16KuNMcYaY3y7OJfRxphPYyxPM8YEjTGdd6Xf3cEYM6lsDvnbvYbW4XiVammtfclaO7CuxpS9m8J2H2aMSQHeBcYCDYHmwJ1AyR6a0gtAX2NM5g7LzwRWWGu/3ANz2t791trk7V6T9/B85C9EYbtv2x/AWvuKtTZsrS2y1n5krV1ujOkIjAf6lF3FbQYwxhxvjFlqjNlqjPnVGHPHdv1tuyrdXLZNn7JtLjTGfG2M2WSM+dAY0zrWZKy1a4DpwLAdVp0HPFfW137GmOnGmFxjTI4x5iVjTGqs/squRsds9/Phxpg12/3czBgzxRizwRiz2hhzZY0rFz2ONca0izXutjGNMdcYY9YbY9YaYy7Yrm2CMeZBY8zPZb9dzDHGJBCjljv+pmGM6WuMWVS23SJjTN/t1s00xvyr7DeVPGPMR8aYtF3ZP9k7KGz3bd8CYWPMc8aYwcaYBttWWGu/BkYA88uu4rYFWgFO+KUCxwP/MMacVLbusLI/U8u2mV+27ibgFKAxMBt4pZo5Pcd2YWuMOQDout02BrgXaAZ0BFoCd9R2x40xHuAd4AucK/qjgKuMMYNq21cNZAD1y8a5CHhiu1o/AGQBfXF+u7geiBCjljvMvyHwHvAY0Ah4CHjPGNNou2ZnAxcATYAAcO3u3zVxi8J2H2at3Qr0BywwAdhgjPmfMSa9mm1mWmtXWGsj1trlOCE4oJphLgXutdZ+ba0NAfcAXau6ugXeBNK3u0o7D3jfWruhbPzvrbXTrLUlZcse2sn4VekBNLbW3mWtDVprf8SpwZnVbHOtMWZz2SunFmOVAndZa0uttVOBfOCAssC/EBhprf2t7LeLedbamnyNczzwnbX2BWttyFr7CvANMGS7NhOttd9aa4uA/+J8aMk+SmG7jysLweHW2hZAZ5wrxkeqam+M6WWMmVH2q/cWnKvf6n49bQ08ui2kgI04V6fNjTE3bXezaXzZfAqB14DzjDEGOIeyrxDKxm9ijHnVGPObMWYr8OJOxq9uXs22C8/NOFfgVX7QAA9Ya1PLXrUZM7fsg2abQiAZZ97xwA+1nTzOcfp5h2U/41w9b5MdY0zZRyls/0Sstd8Ak3BCF5wr3h29DPwPaGmtrY/zva6ppv2vwKXbhVSqtTah7Arunu1uNo3YbpvngDOAY4B6ODfxtrm3bJwu1toU4Nztxt9RAZC43c8ZO8xr9Q7zqmetPa6KvqpTWM041ckBioH9Yqzb2T+n9zvOB8b2WgG/1XBs2ccobPdhxpgOZTduWpT93BI4C1hQ1mQd0MIYE9hus3rARmttsTGmJ873gttswPm+se12y8YDo40xB5aNUd8Yc/pOpjYb2Aw8DbxqrQ3uMH4+zo2j5sB11fSzDDjOGNPQGJMBXLXdus+ArcaYG8puUnmNMZ1N2WNvtbQMOLusj2Op4dca1toI8B/gobKbdd6yG2FxxK7l9qYC+xtjzjbG+IzzGFonoj+Y5E9EYbtvywN6AQuNMQU4IfslcE3Z+unAV0D2dt9RXgbcZYzJA27D+S4QKP8K4G5gbtmv5r2ttW8C9wGvlv3a/yUwuLpJWecfSX4e58rt+R1W3wl0A7bg3CB6o5quXsC5AfYT8BFQ/qiWtTaM8/1mV2A1zlXmMzg3smprZFlfm3G+9nirFtteC6wAFuF8xXIf4IlVy+03stbmAifgHKtcnBtrJ1hra/NdsuxDjP7xcBGRuqcrWxERFyhsRURcoLAVEXGBwlZExAUKWxERF9Tqn9IzaWnWtG5TR1MRqTmjh2h2C1vVXyeRGrM//4TNydlpJWsXtq3bEDd38a7PSgCI6PeJPywQ3Hkb2blgYOdtpHqlfbrXqJ3e9iIiLlDYioi4QGErIuICha2IiAsUtiIiLlDYioi4QGErIuICha2IiAsUtiIiLlDYioi4QGErIuICha2IiAsUtiIiLlDYioi4QGErIuICha2IiAsUtiIiLlDYioi4QGErIuICha2IiAsUtiIiLlDYioi4QGErIuICha2IiAsUtiIiLlDYioi4QGErIuICha2IiAsUtiIiLlDYioi4QGErIuICha2IiAsUtiIiLnAtbENPjaOkQybFqfGU9M0iMmd2te0js2dR0jfLad+xLaEJ46PXz/mU4GknUty2OcUJhtALkyr1UXrnrZQc3IHiRkkUN21AcPBRRObPi+7nxx8InnEyxS0bU9wkheA5Z2DXrYs5J1tcTEnPgylOMESWLK5dAXaD8PhxBPfPJJgST2nvGtTw01mU9s4imBJP8IC2hJ/eoYazP6X0lBMJZjYnGGcIPz+pch9vvUHp8YMINm9MMM4QmTUz9liLPqN08DEEGyYTbFSP0gF9sTk5ANhIxBmnXStnLq2bEhp+Lva333apDn9U6YRxFHTOJD8tnsJDswjPrb6O4TmzKDw0i/y0eAoOakvps9F1DD5wL4UDepDfLIX8No0pOn0I4ZVfRrWx1lJyzx0UtG9GfuMECgcfTvjrr6LHWfY5RSceQ36LVPJbNaL4ir9j8/Oj2uTXM5VeO87HDXviXLTWEvrXHQTbNCNYP4HSYw4nsvKrSu3Aea+Wdj/YOWd3eK9GFi+i9NijCaY3INgkldJBRxFZ9FntCrALXAnb8GuTCV07Eu/1NxFYsBRPr74ETxqM/eWXmO0jP60meNJxeHr1JbBgKd7rRhMadQXhN6eUt7H5+ZhOnfE/8CgkJMTsx7P/AfgeeYLA4hUEPpmDaZNJ8G/HloepLSig9ISBYC2BqZ8QmD4XgkGCpw7BRiKV+gvdeC2meYs/XpBdEH5tMuFrRuK94Sb8C5dievcldGLVNbSrVxP623GY3n3xL1yK9/rRhK++gsh2NSQ/H3NgZ3wPVl1DW1CAp09fvPc/VOXcIp8tJHT8QDwDDsc3ewH++UvwXn0t+P3lbTyHH4nvpf/iX7EK36tTsKt/JHTGybtUiz+idMpkSq4fSeCam0icsxRvr74UnTqYyK9Vn4tFpx6Ht1dfEucsJTBqNCXXXkHo7Yo6hufMxH/xZSR8PI+E96aDz0fxkKOxGzdWjPvw/ZSOfZC4B8aSMGsRnsZNKD7xGGxenjPO2t8pOvFoTJu2JE5fSMKbHxD5+iuKRwyvNKe4sRNI/H5t+ct39vm7tUY7s6fOxciD9xN55EF8D4/FN28RpnETQsdV1DBqjjdcCzHeqzY/n9CQYzHNmuGfOQ//rPmYpk0JnTAoZj+7lbW2xi/TLcvGF9lav0z3ntZ7wcXRy/ZrZ73X3hizvXfU9dbs1y562fCLrOnZO2Z7kpKs7+mJO51H3LotFrD+/31g44us9b/zocUYG/f7xoo22Zstxlj/e9OitvX/9y1rOnaygaUrLWADcxbtUi3ii6wNlNT+ZXr0tJ4LL45axn7trOe6G2O291xzvWW/dtHLLrjIml69Y7YnKcl6J0yscnz/bxssYH0fzag8t959rOeGm2q1P77X33aOxZaiXapHct6uvTzde1rf+RdHLTP7tbP+UTfGbO+/yjkXt1/mO+8i6+nRu8oxktbmWTweGz/5f87PWyPWpGfYwG1jKtqsL7QkJ9u4R8fb5Dxr4x59ytKwkU3aHCpvk7BguQVs4rLvypcBNv6F13Z5/3d87Svnor84YsnIsN47x1Qs2+zU0Pv4+Ohz6zXnvepf5rxXffMWVaybt8g57775saKfb36s1K5W9eiWZWuSn3V+ZWuDQezSJXiOGhi13HP0QCIL5sXcJrJwPp6jd2w/CPv5Ymxp6S7PI/zs05CSgqdLV2dhSQkYA/HxFQ3j48HjITJvTsW2a9ZQeuU/8E98qcpP3bpkg0Hs50ti1GQgtooa2lg1PGYQdsmu1zDmOOvXYxfMx2Q0pfSI/gRbplN65KFEpn9S9TYbNxJ59SVMz16Y7Wtfx2wwSGTpEnw7nIu+IwcSXhi7juHP5uM7cof2Rw8isrTqOtr8PIhEMKkNnJ9/Wo1dl413u35MQgLevocRLjt+NliC8fsxXm9Fm3jnXAvPn8P2Sq4fSX7rNAoH9KD02fExfwurK3vsXFy9GrKzMUdH19D0PyxqXLtmDaEr/4H3udjvVbP/AdC4MeFJz2JLSrAlJYT/MwFatcJ0OrBmc9lFdf81Qk4OhMOY9PSoxaZJOqzLjr3Numxn/fbt09MhFHL6q4Xw1HcpTkumJDWe0NiHCbw7rXwunp69ITmZ0OjrsAUF2IICQjdeC+EwZK8FwIbDBC84B9/Ia/Ac3LVWY+82ZTUkRk1sduwa2uzsSjWnya7VsDp29Y8AhP91O57zL8T3zgeYfocSOmEQkeVfRLUN3XQDwQZJlDZthP31F3xvvrvb5lGjueaWnYuNK5+Ltopz0cY6Fxs7dbS5sesYvH4kni5d8fTqU97HtnEqjbveWecdcCQ2N4fgg/92Am3TJkpuv9HZvuxcBAjcchfxkyaT8M7H+E49k5KbrqH0gXtqWoI/bg+di1XWcLtxbThMaPg5eKt5r5p69fBPm0nktcmUpiZSmppI5LXJ+N+bhqnjCykXn0Yw0T9a61xVVtk8RvtYy3fCM+AIAguXEZgxD+/AYwmeewZ2rXPymsaN8b/0GpGP3qekcT1K0utjt2zGHNINyq4wwvffg/H78Y4cVatx60SsmrhQw2qVXVV5Lr4U7/AL8XQ9BN+/7sH06Elkh5sg3lHX4V+4FN97H4HX69wk2zYnN/3ROlJ1HUtuHEV4/hziX5wSdZW6s3G9HQ8k7qnnKB33CAVNEilol4GndaYTLtv1E7jhVrx9++Pt0pXAldcQuPF2go/+X3V7Wzf21LlYzbiR++4Bnx/PVVW/V21REaG/X4indx98sxfgmzkX0/UQSk/7G7agoHZzqSVfnfYOkJYGXm+lKwe7YX2lT8dy6RmV269fDz4fNGpUq+FNUhJmv3awXzs8vXoT6dye8KRn8I2+FQDv0QPxrvzBuXPu82FSUyluk4FpnQlAeMYn2LmzKannj+o3OKA3ntOGEpj0Uq3ms0vKarjjbwJ2/frKVwxlTEZG5SuNDbtWw+qYjKbOnx07RS/v0BG7w00nk5YGaWmY/ffHdOhI6X4tsXPnYPofutvmU+1cG5Wdi+srn4s7XjGVbxPrXCyro2kYXceSG68m9PqrJLw3A09m26g+oOzqrEXL6HG3u8r2n3E2/jPOJrJ+HSYxCYyh9PGH8LTJrHKfvD16wdatRNavw1PV+2l32kPn4vY1NC23q+F240ZmfIKdM5vSpOj3aujQ3nhOH4rvuZeIvPoy9scfnJAt+xAzz79MaXoDIm+/iffsc2s0n11R51e2JhDAHJJFZPq0qOWRT6bh6d039qR69SEy/ePo9tOnYbp1x/j9MbepsUgEW1JSeZ5paZjUVMIzp8P69XhOOBEA/9MTCXz2hXN1vHAZ/remOssnvoR/zH1/bC41ZAIBTLcsIh9XrqGpooYmVg0/nobJ2g013F6bNtCsGfbbVVGL7XffYlq1rnq7bd8zxjgWdcUEAngOySK0w7kYmj4Nb6/YdfT27ENoxseV2nsOia5jyfUjCf33ZRLenY7ngA7R47bJxKRnEN5uXFtcTHj+bLwxjp+nSTomOZnQlMkQH4/3iGOq3Kfw8mUQH4+pn1plm91pj52LmZmQkYH9JLqGdu7s8nF9T0/Et/gLfIuWOa+3nfeq97mX8N5d9l4tLHSuhD3bRZ/H4yyr6+++3Xgawf/8qxa/3/rGTbCBpSut97IrLUlJNu6bn2x8kbWes4dZz9nDKu7Wf/2jJTHRev850gaWrrS+cRMsfr/1v/x6xVMDG/JsYMFSG1iw1JKQYH233mkDC5bauFU/lz954L3hZhuYtcDGrfrZBuYutt7zLrAEAjbw2Rfl/fie+o8NzJhnA199b/3/ecHSsKH1Xjmq6icJvlm9R55G8L7o1ND75ATrX7bSev7p1ND/7U/O3d1zhlnPOcOi77AmJlrP5SOtf9lK633SqaHv1dcr2uTmWd9nS63vM6eG3tvutL7Pllr/dz9XtFmb67T5aIYFrPfJCU6bn9dWzO3/HrakpFjfy/+1/q++s9677rb4fNa3aJlzB3jWPOt95HHrW7TM+r/9yfo++MSaPn0trdu4/jRC3CSnjnFjJ9jERSut/x9OHRO/+sl50uCsYdZ31rDy9okrnDr6LxtpExettHFjnTrGv/h6xRMLl1xmqVfPxr/7iU38fm35K2ltXsVd/zv/7bR5cYpNWLjC+k4dak1GU5v0+9aKNg+MtQmzl9jEz1fZwIOPWxISbOD+R8vXx0/+n4177GmbsHCFTfzie2cuKSnW/48rXX0aYU+di967nRr6Jk+xvs9XWM/pQy1Nm1p/ztaY8/SvWl3pKQP/F19b4uKs55IR1r9spfUt/dJ6zj7XqeMPv9bp0wiuhG18kbW+R56wtGptCQSsOaSbDUybVfEY2KEDrDl0QHQgfTTTmq6HOO1bt7G+x56MDvAPnTf/ji/Puec7YZtbYD1DTrJkNLUEApaMptZzwok2MGtB9CNl19xgSU+3+P3WtGtvff9+0MYVRva6sA2UWOt99AlL64oa+j6eVXHADxtgzWEDoh+BmVZRQ1q3sd6xT0av/6iKGg47v2LMCRNjt7nl9ui53X2fpWVLS2KiNd17WN/UaRXjfLbUmgGHWxo2LJ+L55IRu3xy/5GwTc6zNu6hJ6wpOxc9XbvZhPdnVTwa1n+A9fQfENU+4f2Z1nNwxbkY98iTUetj1Qew/tG3VzzqtTVi/aNvtyY9w3mz9zvMJixcEf1I2VnDLA2cGnk6d7FxTz8ftT7+jfetp0tXS3KyE16dOtvAfY/YpE2lrobtnjoX/cUR67nldkuGU0Nz6GHW9/mKKucYK2wDJdb63vvImr79LPXrW1JTrRlwuPXNnLvLtahp2Jra3KDwZHW3cXPd/5tTfzYR/SXpPywQ3NMz+HMIBvb0DPZ9pX26E1myeKd3+vS2FxFxgcJWRMQFClsRERcobEVEXKCwFRFxgcJWRMQFClsRERcobEVEXKCwFRFxgcJWRMQFClsRERcobEVEXKCwFRFxgcJWRMQFClsRERcobEVEXKCwFRFxgcJWRMQFClsRERcobEVEXKCwFRFxgcJWRMQFClsRERcobEVEXKCwFRFxgcJWRMQFClsRERcobEVEXKCwFRFxgcJWRMQFClsRERcobEVEXKCwFRFxgcJWRMQFClsRERf4atXagrF1NJO/kGBgT89g39dg056ewZ9DfvKensGfgKlZM13Zioi4QGErIuICha2IiAsUtiIiLlDYioi4QGErIuICha2IiAsUtiIiLlDYioi4QGErIuICha2IiAsUtiIiLlDYioi4QGErIuICha2IiAsUtiIiLlDYioi4QGErIuICha2IiAsUtiIiLlDYioi4QGErIuICha2IiAsUtiIiLlDYioi4QGErIuICha2IiAsUtiIiLlDYioi4QGErIuICha2IiAsUtiIiLlDYioi4QGErIuICha2IiAtcC9vQU+Mo7phJUYN4ivtmEZ47u9r24dmzKO6b5bTv1JbQhPHR6+d8SslpJ1K0X3OKEg2hFybF7Cfy3beUnHkKRU1TKWqUSHGfbkS++RoAu3EjwVFXUNy1A0UNEyhu35Lglf/A5uZG9VHcoQ1FiSbqVXrrjbtejD1t3DjIzIT4eMjKgtnVHwtmzXLaxcdD27Ywfnz17fdyhRPHsaFHJutax5M7MIvggur3PzhvFrkDs1jXOp6cnm0pfK7q/S949B7WZRi2jr48arm1lvz/u4MNBzdjXZsENp58OKFvvqoYY+5M1mWYmK/i/71W3m5D9zaV1ueN0bm4L3AlbEOvT6b0upH4rruJuPlL8fTuS/CkwUR+/SVm+8hPqwmefBye3n2Jm78U37WjKb3mCsJvTalolJ+Pp1NnAg88CgkJVfZTclQ/PG0yiZs6nbjFX+K/fQwkJwNg1/6O/f03/GPuJ27RCvz/eZHI3E8JDj+rUl++0bcR/+Pa8pfvhlv+eGH2hMmTYeRIuOkmWLoU+vaFwYPhl9jHgtWr4bjjnHZLl8Lo0XDFFTBlSuz2e7nityaTd+tIkkbeRKNpS/F378vmswcTXhN7/8M/r2bTOcfh796XRtOWknjlaPJuvoLidyvvf3DJAgpfnICvU5dK6wofv5/C8Q9S7+6xNHp/EZ60JmwaegyR/DwA/D36krZ8bdQr8crRmKRkAkcNjuoradRtUe2Srta5uC8w1toaN/Z0627j5y6u9SDFh/XC07kLgXETKpYd1B7vyafhv+veSu1Lb7mB8NtvEL/iu/JlwX9cTOTrr4ifOb9S+6LGyfgfehzfsOFRy4PDzwZjCEx8qcZzDX8wleCpJxC/djMmJcWZa4c2eEdcjv+qa2vcT3WKYn82uKNXL+jSBSZUHAvat4fTToN7Kx8LbrgB3ngDvqs4Flx8MXz1FcyvfCzckr5u17bLHdwLf6cupDxYsf85fdoTd8Jp1Lu58v7n/esGSqa+Qdr8iv3fMupiwqu+ouF7Ffsf2bqFjcd0I+XBCeQ/eBe+Dp1JufdxwLmqzTm4GQkXXk7yVTc7y4qK2NC5Ccm3P0DieZfGnGtOvwMI9BlAygNPly/b0L0NiRdeTtJlu+dcXJe+W7rZNX+Sc5Hu3bGLF5udNavzK1sbDGKXLsF79MDogY8aSGTBvJjbRBbOx3NUdHvvMYOwny/GlpbWbNxIhPDUdzAdOlFy4rEUtWpMcf8ehF6fXP12eVshLg4SE6OWhx55gKIWjSju1ZXS++7GBoM1msdeJRiEJUtgYHRtGTgQ5sU+FsyfX7n9oEGweDHU8FjsLWwwSGj5EgIDovcnMGAgpYti73/pkvmV2scdPojSL6LPxa3X/p24E04j0P/ISn2Ef1lNZH02cdv1YxIS8Pc+rMpxg3NnEv7hWxLO/XuldYVPPsD6jo3IPaor+Y/oXNxXzsW6/xohJwfCYWgS/RFqmqRj12XH3MSuy8bs0J4m6RAKOf3VxPr1kJ9P6P/uwXP0QOLemYb3jLMoveAcwlPfjT3u5s2E7roV7wWXYHy+8uXey64k8NwrxL0/A9+Iywk9/jClIy+r2Tz2JtuORfoOtU1Ph+zYx4Ls7Njta3Ms9hKRjc7+expH74+ncTqRDbH3P7I+O2Z7QiGnP6DwxQmEf/qe5Bv+VWUf5dvVcNyiF5/Gd+DB+Lt2j1qeePGV1H/yFRpMmUHChZdT+PTDbL1R5+K+cC76dt5kNzE7XGVbW3nZztrHWl6VSAQA7wl/w3/lKAA8B3fFfr6Y0FNP4D3uhOjuCwoInjYE06w5/rvvj1q3bXsAz0FdICWF0mFDsWPuwzRqVLP57E3cPhZ7m924/6HvV5F/z000fHs2JhDYLeNGNm2keOob1LvjoUrrkkZUnIv+Tl3wJKew5dKh1LvlPjwNdS7uzer+yjYtDbxe2OEq1m5YX/nqtYxJz6h81bthPfh8UNNwS0sDnw/ToVN03wd0xO5wM8Tm5xM8ybkJEZjyLiY+vtquPT16Odv98H3N5rK32HYsdrxyWL++8hXDNhkZsdvX5ljsJTwNnf3fdqW5TSRnPZ602PvvaZIRsz0+H54GjShdPB+7MYfcwzuzrrmPdc19lM6fRdGkcaxr7sOWlOBpkuFsV8Nxi/77HHg8xJ96zk73yd/NORfDP+lc3NvVediaQABzSBbhT6ZFLY9Mn4and9/Yk+rVh8iMj6OWhT+ZhunWHeP313hcT1YP7Heropbb77/FtGxd8XNeHsG/HQvhMIE3p2LKnlSojv1imfM/TZvWaC57jUDAeWxmWvSxYNo05w5vLH36wMcfV27fvTvU8FjsLUwggK9LFsFPo/c/+Ok0/D1i778/qw/B2R9Xbn+wcy7GDT6JRjNW0OjjZeUv38HdiT/pTBp9vAwCAbytMvE0yYga1xYXU7pwdsxxi156hvghZ+BJqb/TfSr9yjkXPU10Lu7tXPkawXflKEovGkaoe088ffoRemY8du3veC8eAUDw4vMACDzzPADei0cQGv84weuuwnfRpUTmzyX84iQCz71S3qfNz6+4soxEsL/+QuSLZdCwIZ6WrZxxr76e4LAzCPU9FM/hRxKZNYPwa68SmPyW00deHiVDBkLeVmdZQQG2oMDps2FDTCBAeOF87GcL8Bx2BNSvT2TJIkqvvxrP8SeWj7NPGTUKhg2Dnj2hXz/nOcXff4cRzrHgPOdY8LxzLBgxAh5/HK66Ci69FObOhUmT4JVXYna/t0u6dBRbrhiG75CeBHr0o/D58USyfyfxPGf/t1zu7H/9x539TzxvBIX/eZy8W68iYdilBBfNpWjyJOo/6ey/p34qnvqpUWOYxCRMakN8HTuXL0u85CoKHr0bb7sO+NruT/4jYzBJycSfcnbUtsGFcwh/uzLqCYTydYvnU7pkAYF+R+CpV5/SZYvIu/1q4gadiLeFzsW9nrW2xi9zSJZNKLS79PI//IQ1rVpbAgFrunazgY9mla/zHDrAeg4dENU+8OFMaw4+xGnfuo31P/pk9PoPZlig0st77vnR4z410Zp27S3x8dZ0Psj6J7280z4AG/hghk0otDZu7hJrevSy1K/v9LH/AdZ30+02Pqdgl2tRq6LXxeuJJyytnWNBt26WWbMq1g0Y4Ly2bz9zpuUQ51jQpo3lySf3+D6kZ+/6q976sTbNAAAePUlEQVS9T1hPC2f/fV262QZvzipf5+8zwPr7DIhq3+CNmdZ3kLP/npZtbL37nqy2f3+fATbhgn9GLWuyNmKTrrndeppkWOLirL/3YbbRjBWVto0//Tzrbd8xZr8NP1pi/d16WZPinIvedgfYpGtut01+LNjlWuzp4/hnOBfJyrI1aebKc7YSbY8+Z/snsavP2Uq0Pfqc7Z/F3vKcrYiIKGxFRFyhsBURcYHCVkTEBQpbEREXKGxFRFygsBURcYHCVkTEBQpbEREXKGxFRFygsBURcYHCVkTEBQpbEREXKGxFRFygsBURcYHCVkTEBQpbEREXKGxFRFygsBURcYHCVkTEBQpbEREXKGxFRFygsBURcYHCVkTEBQpbEREXKGxFRFygsBURcYHCVkTEBQpbEREXKGxFRFygsBURcYHCVkTEBQpbEREXKGxFRFzgq01jbwSSCupqKn8dnVbu6Rns+1r9vKdn8Ofw5il7egZ/HbqyFRFxgcJWRMQFClsRERcobEVEXKCwFRFxgcJWRMQFClsRERcobEVEXKCwFRFxgcJWRMQFClsRERcobEVEXKCwFRFxgcJWRMQFClsRERcobEVEXKCwFRFxgcJWRMQFClsRERcobEVEXKCwFRFxgcJWRMQFClsRERcobEVEXKCwFRFxgcJWRMQFClsRERcobEVEXKCwFRFxgcJWRMQFClsRERcobEVEXKCwFRFxgcJWRMQFClsRERe4FrZF/xnHxqxMclrEs+moLErnz662fencWWw6KoucFvFs7N6Woknjo/t79gk2DehCbmYKuZkpbB7ch+BH71XZX96ov5PT2FD4xANRyyPrssm7bBi5nTLIaZ3EpsMPpvj1l6LaFD50N5uP60dO6yRyGpta7vnus/61caw4MZPP+8bz9blZ5C2tvoZ5S2bx9blZfN43nhV/a8uG16NraMNhfnvy1vI+V5yYyW/jbsGGQuVtwoX5/HL/FSw/rgWf90vgy1MOYN1LD0f1s+GNp1l16REsOzyVJd0NJb//FD2PxTNZ0t3EfG36+LU/VpRd8OMH4/jwH5m8fWY8M67LImdl1XUs3rSWRQ+fzbQrOvDm6V6WjB1ebd+/zn6FN081zLvnhKjlq964lxnX9+Cdc1N474LGzL9nCFt/+TKqjbWWryffwfsXN+PtsxKYfdvhbP3lq6g2H45ow5unmqjXly/cWLsC7E3GjYPMTIiPh6wsmF39Oc2sWU67+Hho2xbGj6++/V7ElbAteXMyBTePJPGqm0idvhR/j75sOXMw4TW/xGwf/nk1W84+Dn+PvqROX0riyNEUjL6CknemVEy8WQuSbr2P1E8+J/Xjxfj7H8nW808i9NXyyuP/73VCSxfhyWhWaV3e5ecR/vZrUl54mwazVhB3xnnkXzaM0nmflrexwRICJ5xCwt+v2g3V2DUbP5rMrw+MJOOCm+j40lKSuvTl+ysHE8yOXcOS31bz/cjjSOrSl44vLSVj+Gh++b8r2PRJRQ2zn7uPDa89QctrH+PA17+h5TWPsuG1J8iedG95mzUPj2LL3PfIvOsFDnzta5peeDO/PX4jue+9UN4mUlxISu+BNP37HTHnknRwX7p8sDbqlXHBaDyJyaT0Hbx7ClRDa+ZOZvl/RrL/KTdxxANLaXhAX+bdPZjCDVWci6UlBFLS2P/kG2nYvle1fRdk/8iXz19Ho46HVlqX8+VM2h57GQPumUf/O6ZjvD7m3Hk0wbyN5W2+e+t+vv/fg3S5aCxH3LeIuJQmzL3rGEqL8qL66nD6bQx+Zm35q8Npt+xCJfYCkyfDyJFw002wdCn07QuDB8MvsY8Fq1fDccc57ZYuhdGj4YorYMqU2O33Mq6EbdH4h4g7czjxwy7Bt39Hkv89Fk96U4onPhmzffFz4/GkNyP532Px7d+R+GGXEDf0fIrGVVyVxg3+G4GjB+Nt2w7vfvuTdPPdmOR6lC6eH9VX+NefKbh5JPWeehn8/kpjlX42j/gL/4k/qxfeNm1JvOwaPM1bUrr0s/I2STfeReJl1+A76JDdVJHaW/fSQ6QNGU7jky8hIbMjra4fiz+tKRtej13DDVPG42/cjFbXjyUhsyONT76ERiecz7oXK2pYsHwe9Q8dQuphQ4hr1obUASdS/7ATKfhyYXmb/C/m0ei4YdTrfgRxzdrQ6ITzSDqod1Sb9LOvoukFo0nu2j/mXDz+AP60jKjXpk+m0HDQWXgTk3dThWrm+3ceotURw8k85hJSWnTk4IvHEp/alNUfxq5jUpM2HHzRY7Q+cjj+5IZV9hsJlbLokbPodPbdJKW3rbS+320f0vrIC0hp1Zn6rQ+i+5UvULJ1A7nfzAWcq9rv332E/U++keZ9TiWlVWeyrniOUFEea2a/HNWXL6Ee8Q0yyl++BHdruNs89BAMHw6XXAIdO8LYsdC0KTwZ+1gwfjw0a+a069jR2e788+GBB2K338vUedjaYJDQF0sIHD4wanng8IGULpoXc5vSRfMrtz9iEKFli7GlpZXHCIcpefNVbEE+/h59K5aHQuRdehYJo27Bt3/HmGP5e/Wn5O3/EtmYi41EKHn/bSK5GwgcdnRtd7XOREqDFH6zhJTe0TVJ6T2Q/OWxa1iwYn6l9vX7DKJg5WJsyKlhctf+5C2eQfFP3wBQ9ONK8hZPJ6XfceXbJHftz+ZP3yGY/SvghG/hqmWk9D12l/cnb/FMSn75lrST/77LfeyKSGmQzT8sIf3g6Lo06TqQ3FWx61hTK1++mcTGbWh9xPk1ah8qzoNIBH9yAwAK162mZHM2TbpWzM0bl0CjTodVmtt3/3uAd89vxPRrurLq9buJlAb/0Nz3iGAQliyBgdHHgoEDYV4Vx2L+/MrtBw2CxYshRi7sbXx1PUBkYw6Ew3gap0ct9zRJx376cext1mfjGRAddp7G6RAKYXNzMBlNAQitXMHmwX2gpBiTlEzKpDfxdTqofJvC+27HNGhEwgX/qHJ+9Z79L3mXnMnGA9LA54NAHPWeegXfQV13dZd3u9Bmp4a+htE19DVMp3Rh7BqW5mZTr+fRldoTDhHanIM/rSnp599AuCCPr07vBB4vhENkXHgzTU6/rHybltc9xi/3jGDFCa3A65wura4bS+qh0d9J1saGN58mYf+DSerUfZf72BUleTnYSJi4+tF1jK+fzobNsetYE+uWfcSauZM58sFlNd5m+bMjqZ/ZlUb79wGgeHM2QKW5xaWmU5z7W/nPbY+7ktTMQwjUa8Sm7z/jqxdvpGD9arpd9swuz3+PyHHOadKj95f0dPi4imORnQ1HH125fSjk9Ne0ad3MdTep87AtZ3a4sWRt5WU7a7/Dcm+7A2gwYxmRrZsJvjOFvCvOp/5bM/F17Ezp3FmUvDqJ1BnVvwEK77kFuzGHlCkf42mYRvD9t8j/53l4//cpvs4H12YP614ta2iqqiHO8k0fTSZ36vNkjnmZhP0OpHDVMn59cCRxzTJJO+kiADZMHkv+F3PZ76H/EWjamvzPP2XNo9cSaNaG+rtwdRvaspHNM96gxdUP1Xrb3WaHulgs22pSWyVbc/j88eF0v+plAmVXqTuzfOIocr+Zw2Fj5mC83mrntuMxbn/iqPL/r9+mC76EFBY9NJQDh91HXL1Gu7QPe1Qd5MLeqs7D1tMwDbxeIuuzo5ZHNqzH7HC1W75Nkwwi63Zon7MefD5Mw4oTygQCzne2gL9rd0LLFlE0/mHqPfoswbkziKxby8bO233ahcMU3nUDxU89QsPlawiv/oHiZ8aSOmNZebD6Oh9M6YLZFD0zlnqP7B1XC75Up4ah3OiahDatx98odg39jTIojdEerw9fqlPDNY9dR/q519Jw0JkAJLQ7iODan8medC9pJ11EpLiI3x4fTdt/v0bqYUMASGzfhcJvl7HuxQd2KWxz330OjIdGg8+p9bZ/VFy9NIzHS8nm6LqUbFlPXGrsOu7M1l++pHjTWubeWXHFZW0EgLdO93HUI19Rr/kB5euWT7yaNXNe5dA7Z5CUUfHdbnxqhjOXzdkkprWs8dy23bQrWPv9vhW2ac45TXb0sWD9+spXu9tkZMRu7/NBo71/3+v8O1sTCOA7OIvgrGlRy4OzpkV9v7o9f48+lO7wFUNw1jR8XbtjYtzkKheJQLAEgIQLLiN11nJSZywrf3kympEw4mpS3vgEAFtU6Gy349WFx+v0tZfw+AMkdshi68LoGm5dOI3kLrFrmHRQH7bu8BXD1oXTSOrUHeNzahgpLsR4dth3r7c8LGyo1Pl+d4f6mD9Qn5y3n6HhMWfgTa6/S9v/ER5/gNT9slj/RXQd138xjUYHxK7jzjRo14OjHl7BkQ8uK3817X4ijToeypEPLiOpSWZ52+XPjmTN7Jfpf+d06rXoENVPYnomcakZUXMLB4vJ/Xp2tXPb/JPzm1t8g737V+hKAgHnEa5p0ceCadOcpw1i6dOn8lcM06ZB9+4xb37vbVz5GiFhxCjy/jkM/yE98fXqR/Gk8USyfyd++AgA8v55HgD1nngegPjzR1D07OPk33wV8edfSmjhXEpenUS9p14p77PgrhsJHHM8nuYtsfl5lEx5mdK5M0l52XnW1tO4CZ7GTaIn4vdjmmTga+dcaXjbd8CT2Y786y8j6c4H8DRoRMn7b1E6axr1Xni7fLPwml+wmzYS/vUnAEIrnBPcm9kOk+zOneD0c0bx023DSDqwJ0kH9yNnynhKN/xO2qlODVff5tQw8y6nho1PHcGG/z7Orw9eRdopl1LwxVxy35lE5t0VNUw9dAjZz/2buOaZxLc9kMJVS1n/0kM0PN7py5ucQnK3Afw29ka8CckEmrYm7/NZ5E59nhZX3F/eT2lONqW52ZT88i0AxT+uJJy3mUBGK3z1K+7g5y+bQ/GPK2l909N1W6xqtBsyisWPDaNB+5407NCPnz4cT/Gm38kc6NRx8WPOvne/8vnybTavdo53qHArxnjYvHoZHl+AlJad8MUnkdKqc9QY/qRUIpFQ1PJlE/7Jr7NeoPcNbxFIakDxJucKzRefjC8hGWMM7U64ilVT7ia5eQfqNdufb14fgy8+mRaHng1A7qr5bPp2AWmdj8CfWJ9N3y9ixaSryehxIomNW9Vd0erKqFEwbBj07An9+jlPG/z+O4xwjgXnOceC58uOxYgR8PjjcNVVcOmlMHcuTJoEr7wSs/u9jSthG3fyUCKbcil8eAyRdWvxduhM/Vem4m3ZGqDS87be1pnUf3kq+bdeTfGkJ/FkNCPpnseIG3JqeZvI+mzyLjuXyPpsTEp9fJ26kPLq+wSOHFTjeRm/n/qvTKXgXzey9dwh2IJ8vJntSH5sInGDhpS3K/z3bZRMfq78581HOo+Apbw1g0C/w3elJLXWcOBQQltyWfvsGEpz1pKwX2faPTqVuKZODXd83jaueSbtHp3Krw9dzYbXn8TfuBktr32MBkdV1LDldWP5ffyt/PLvyyjdtB5/WlPSTr6EphffVt6m7T2v8tsTo1l96zmEtm4kkNGaZiP+ReOhl5e32TBlPGsn3Fn+8/dXHQ9A69snkjZkeEW7NycQn9mR5K79dmttaqNFv6EE83JZ9foYijetJaVVZ/reNJXEJk4di3IqP+M549roR/6yF79DYuPWDBr/U43HXf3BOADm3HFU1PIOZ9xOx6F3AND+pOsJB4v4YsI/KS3YRIP2veh320f4E+oB4PXHsWbuZL75752EQyUkprWmzdGX0P6k62s8j73K0KGQmwtjxsDatdC5M0ydCq2dY1HpedvMTGf91Vc7j4c1awaPPQannlq5772QseU3TXbO37W7Tf14cR1O56+h9c97egb7vlaq4W7x5il7egZ/At27Yxcv3ukdOv3bCCIiLlDYioi4QGErIuICha2IiAsUtiIiLlDYioi4QGErIuICha2IiAsUtiIiLlDYioi4QGErIuICha2IiAsUtiIiLlDYioi4QGErIuICha2IiAsUtiIiLlDYioi4QGErIuICha2IiAsUtiIiLlDYioi4QGErIuICha2IiAsUtiIiLlDYioi4QGErIuICha2IiAsUtiIiLlDYioi4QGErIuICha2IiAsUtiIiLlDYioi4QGErIuICX20ah3yQk1ZXU/nrOOWNPT2Dfd9Tl+7pGfw5GLunZ/DXoStbEREXKGxFRFygsBURcYHCVkTEBQpbEREXKGxFRFygsBURcYHCVkTEBQpbEREXKGxFRFygsBURcYHCVkTEBQpbEREXKGxFRFygsBURcYHCVkTEBQpbEREXKGxFRFygsBURcYHCVkTEBQpbEREXKGxFRFygsBURcYHCVkTEBQpbEREXKGxFRFygsBURcYHCVkTEBQpbEREXKGxFRFygsBURcYHCVkTEBQpbEREXKGxFRFygsBURccG+FbbjxkFmJsTHQ1YWzJ5dfftZs5x28fHQti2MH+/OPOvIVzPH8cpNmTz7z3jeuDuLtd9Vvf+FW9byyTNnM/m2DkwY4WXmpOGV2rzz4OE8famp9HrtjgPL26yaNylmm1BpcXmbSCTMordvLZ/bKzdlsuitW4iEQ876cCkLp9zA63d14T9XJPHCdU355Jmzyd/4y+4rTi2MYxyZZBJPPFlkMZudnEdl5jAHHz460zlq+Wu8Rne6k0oqSSTRla48x3NRbfLI4yquojWtSSCBvvRlEYvK15dSyg3cQBe6kEQSTWnK2ZzNL0TX6Ad+4GROpjGNSSGFMziDdazbxUrsBf5C72nfnp5AjU2eDCNHOgenf3/nz8GDYeVKaNWqcvvVq+G44+DCC+HFF2HOHLjsMmjcGE491f35/0E/LJrMvMkj6X/2ODLa9WflzHG8P3YwZ9yxkuSGlfc/XFpCfHIaXY+9kW9mPx2zz2NGvEEkFKzYJlTC63cdRNusM6La+QKJnDnmh+hl/vjy///ig/tYOfMJDh/+HA2bH0Tub8uZOel8vP44uh1/K6FgITm/fs4hg2+mUcuuBIu2sOD1a5j62LGcdutyPF73TsPJTGYkIxnHOPrTn3GMYzCDWclKWhHjPCqziU2cx3kcxVH8xm9R6xrRiFu4hQ50wI+fd3mXi7iIxjTmOI4D4GIuZjnLeY7naEELXuRFjuZoVrKS5jSnkEI+53Nu5ma60pUtbOEaruFYjmU5y/Hho4ACBjKQgziIT/gEg+FWbmUIQ1jAAjz72LXTX+09bay1NW/cvbtl8eI6nE41evWCLl1gwoSKZe3bw2mnwb33Vm5/ww3wxhvw3XcVyy6+GL76CubPr/v5VuPvsbOvWm/e24tGLbpw2LCK/X/11va07XYaPU+Osf/b+eDxE4hPTuPw4ZOqbffdwpeYOfE8zrrnJ5IbtgScK9u5r17OhY/lV9t/XFIjjrig4mpuxsTzKSnI5djL3425zabfV/LanQdy2m3Ladj8oGrnFctTl9Z6EwB60YsudGECFXVsT3tO4zTupeo6nsIpHMzBWCyv8zpf8mW143SjG4MYxL3cSxFF1KMeU5jC3/hbeZssshjMYMYwJmYfK1nJgRzIcpZzEAfxER9xLMeSSy4NaADAFrbQgAZ8xEcczdG1KQUApuZv/93vz/Ke7t4du3ix2VmzfeOjMBiEJUtg4MDo5QMHwrx5sbeZP79y+0GDYPFiKC2tm3nWkXAoSM4vS2jRKXp/WnQcyLofqtj/XfDNnAm07Dy4PGjLxw8W8fLo1rx0Qws+ePwEcn5ZGrU+o11/fl81g83Z3wBOkP6+ajotOx9X5VjB4q0ABBIb7Lb570yQIEtYwkCi6ziQgcyj6jqOYxzZZHMLt+x0DIvlEz5hFas4jMMACBEiTJh44qPaJpDAHOZU2ddWnBptC9YSSjCYqH7iiceDp9p+9kp/wff0vhG2OTkQDkN6evTy9HTIzo69TXZ27PahkNPfPqQ4PwcbCZNQL3p/ElLSKdxaxf7X0uZ137L221l06H9J1PLU9AMYcP5/GHjZ2xx58St4/fG8fX8/tqyruLo4eNANtO89jP/e0YkJ//Dz2p0Hsn/v8znw8MtijhUOBVnw+jW06jKE5AYtdsv8ayKHHMKESSe6jumkk03sOq5gBXdyJy/xEl68Vfa9hS0kk0yAAMdzPI/xGIMZDEA96tGHPoxhDL/xG2HCvMiLzGc+a1kbs78gQa7hGoYwhBY4NepNb5JJ5jquo6Dsv2u5ljDhKvvZa/0F39P7RthuY3a4Ure28rKdtY+1fF8Rc392z758M3sCifWb0uqg46OWp+/Xh/37nE9ay640bX8oR10ymZTG+/HljLHlbX5YPJnvFjzPkRe9zKm3fM7hFzzPylnj+GbOs5XGiYRDzPjPuQQLN3P4+RN3y9xry+xQM4uttAycK8kzOZMHeIBMMqvtsx71WMYyFrGIu7mbUYziEz4pX/8CL+DBQwtaEEccj/EYZ3FWzAAPEeJczmUzm5lIRY0a05jXeI33eZ961KM+9dnMZrrRrdoPgr3aX+g9vW/cIEtLA6+38ife+vWVP+m2yciI3d7ng0aN6maedSQ+OQ3j8VK0w1VsUd56ElOq2P9aCIeCfLvgOTr0v2SnN6s8Hi+NW3dn6/qKK9uFU66jyzHX0q7HmQA0bH4Q+bk/s+yDe+nQ/6LydpFwiE+eOYuNv61gyDUziU929zikkYYXb6Wr2PWsr3S1C7CWtaxkJReU/QcQIYLF4sPHVKaWfyXhwUM72gHQla58zdfcwz0cxVEA7Md+zGIWBRSwla00pSlDGVopxEOEOIuzWMEKZjKTRkTXaCAD+YEfyCEHHz5SSSWDjJ1+GOx1/oLv6X3jyjYQcB73mDYtevm0adC3b+xt+vSBjz+u3L57d/D762aedcTrC5DWKos1K6P3/7evp5G+XxX7Xws/LXuL4vwcOvS7aKdtrbVs/G05CfWbli8LBQsxnugrK+PxYm2k/OdIuJSPJwxl42/LGXLNDBLrZ/zheddWgABZZDGN6DpOYxp9qVzH5jRnBStYtt1/IxhBO9qxjGUxt9kmQoQSSiot3/ZY1yY28SEfRt0wK6WUoQxlOcuZwQwyqLpGaaSRSirTmc561nMiJ9akBHuPv+B7et+4sgUYNQqGDYOePaFfP+f5ut9/hxEjnPXnnef8+fzzzp8jRsDjj8NVV8Gll8LcuTBpErzyyh6Z/h/V5ehRzJg4jCaZPUnfrx9ffzqegi2/0/EwZ/9nTHT2/4gLni/fJufXZQAEi7aC8ZDz6zK83gANmnWK6vub2U/TvMNRpDRuW2ncJe/cSZO2vanfpD3B4q18Of0xctcsp//ZT5a3ad1lCF988G9S0jJp0PRAcn5dyoqPH6J9b2dOkXCIaU+dzoafF3HsP98BDIVbnCuUQEJ9fIGE3VeonRjFKIYxjJ70pB/9GM94fud3RuDU8TycOT/P8/jxV3qmtglNiCMuavnd3E0vetGWtpRQwlSm8gIvMJaKr1o+5EMiROhAB77ne67jOg7ggPIr5hAhTud0FrGId3gHgym/Aq9PfRJwajSRiXSgA01ownzmM5KRXM3VHMABdVe0uvIXe0/vO2E7dCjk5sKYMbB2LXTuDFOnQuvWzvpfdnhAPjPTWX/11fDkk9CsGTz22D7xPF4s+/UYSnFBLp9PHUPhlrU0bNaZwZdPpV4jZ/9j/QWBN8YcEvXzL8vfIblRa86+56fyZVs3/Mhvq6Zz1MWvxhy3pGgzs1/8O4Vbswkk1Cet5SGceO2nNMnsWd6m75ljWfz2rcx5+TLnq436TenQ/xK6nXAbAAWb1vDzF287c7o7K6r/AedP5IC+w2tdj101lKHkkssYxrCWtXSmM1OZSmucOu74lwhqIp98/sE/WMMaEkigAx14nuc5i7PK22xhC6MZzRrW0JCGnMqp3M3d+HGuyNawhrdxapRFdI0mMpHhDAdgFasYzWg2spE2tOFmbuZqrt6VUux5f7H39L7znO2fyK48ZyvRdvU5W4m2R5+z/bP4Uz1nKyKyj1PYioi4QGErIuICha2IiAsUtiIiLlDYioi4QGErIuICha2IiAsUtiIiLlDYioi4QGErIuICha2IiAsUtiIiLlDYioi4QGErIuICha2IiAsUtiIiLlDYioi4QGErIuICha2IiAsUtiIiLlDYioi4QGErIuICha2IiAsUtiIiLlDYioi4QGErIuICha2IiAsUtiIiLlDYioi4QGErIuICha2IiAsUtiIiLlDYioi4QGErIuICY62teWNjNgA/1910RET2Oa2ttY131qhWYSsiIrtGXyOIiLhAYSsi4gKFrYiICxS2IiIuUNiKiLhAYSsi4gKFrYiICxS2IiIuUNiKiLjg/wHEI6rdqRhp6gAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x7f07c1794b38>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "from plot_utils import plot_values\n",
    "\n",
    "# evaluate the policy \n",
    "V = policy_evaluation(env, random_policy)\n",
    "\n",
    "plot_values(V)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 0.01393977,  0.01163091,  0.02095297,  0.01047648,  0.01624865,\n",
       "        0.        ,  0.04075153,  0.        ,  0.03480619,  0.08816993,\n",
       "        0.14205316,  0.        ,  0.        ,  0.17582037,  0.43929118,  0.        ])"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "V"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "运行以下代码单元格以测试你的函数。如果代码单元格返回 **PASSED**，则表明你正确地实现了该函数！ \n",
    "\n",
    "**注意：**为了确保结果准确，确保你的 `policy_evaluation` 函数满足上文列出的要求（具有四个输入、一个输出，并且没有更改输入参数的默认值）。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "**<span style=\"color: green;\">PASSED</span>**"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import check_test\n",
    "\n",
    "check_test.run_check('policy_evaluation_check', policy_evaluation)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 第 2 部分：通过 $v_\\pi$ 获取 $q_\\pi$\n",
    "\n",
    "在此部分，你将编写一个函数，该函数的输入是状态值函数估值以及一些状态 $s\\in\\mathcal{S}$。它会返回输入状态 $s\\in\\mathcal{S}$ 对应的**动作值函数中的行**。即你的函数应同时接受输入 $v_\\pi$ 和 $s$，并针对所有 $a\\in\\mathcal{A}(s)$ 返回 $q_\\pi(s,a)$。\n",
    "\n",
    "你的算法应该有四个**输入**参数：\n",
    "- `env`：这是 OpenAI Gym 环境的实例，其中 `env.P` 会返回一步动态特性。\n",
    "- `V`：这是一个一维 numpy 数组，其中 `V.shape[0]` 等于状态数量 (`env.nS`)。`V[s]` 包含状态 `s` 的估值。\n",
    "- `s`：这是环境中的状态对应的整数。它应该是在 `0` 到 `(env.nS)-1`（含）之间的值。\n",
    "- `gamma`：这是折扣率。它必须是在 0 到 1（含）之间的值，默认值为：`1`。\n",
    "\n",
    "该算法会返回以下**输出结果**：\n",
    "\n",
    "- `q`：这是一个一维 numpy 数组，其中 `q.shape[0]` 等于动作数量 (`env.nA`)。`q[a]` 包含状态 `s` 和动作 `a` 的（估算）值。\n",
    "\n",
    "请完成以下代码单元格中的函数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "def q_from_v(env, V, s, gamma=1):\n",
    "    \n",
    "    q = np.zeros(env.nA)\n",
    "    \n",
    "    ## TODO: complete the function\n",
    "    for a in range(env.nA):\n",
    "        for prob, next_state, reward, done in env.P[s][a]:\n",
    "            q[a] += prob * (reward + gamma * V[next_state])\n",
    "\n",
    "    return q"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "请运行以下代码单元格以输出上述状态值函数对应的动作值函数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Action-Value Function:\n",
      "[[ 0.0147094   0.01393978  0.01393978  0.01317015]\n",
      " [ 0.00852356  0.01163091  0.0108613   0.01550788]\n",
      " [ 0.02444514  0.02095298  0.02406033  0.01435346]\n",
      " [ 0.01047649  0.01047649  0.00698432  0.01396865]\n",
      " [ 0.02166487  0.01701828  0.01624865  0.01006281]\n",
      " [ 0.          0.          0.          0.        ]\n",
      " [ 0.05433538  0.04735105  0.05433538  0.00698432]\n",
      " [ 0.          0.          0.          0.        ]\n",
      " [ 0.01701828  0.04099204  0.03480619  0.04640826]\n",
      " [ 0.07020885  0.11755991  0.10595784  0.05895312]\n",
      " [ 0.18940421  0.17582037  0.16001424  0.04297382]\n",
      " [ 0.          0.          0.          0.        ]\n",
      " [ 0.          0.          0.          0.        ]\n",
      " [ 0.08799677  0.20503718  0.23442716  0.17582037]\n",
      " [ 0.25238823  0.53837051  0.52711478  0.43929118]\n",
      " [ 0.          0.          0.          0.        ]]\n"
     ]
    }
   ],
   "source": [
    "Q = np.zeros([env.nS, env.nA])\n",
    "for s in range(env.nS):\n",
    "    Q[s] = q_from_v(env, V, s)\n",
    "print(\"Action-Value Function:\")\n",
    "print(Q)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "运行以下代码单元格以测试你的函数。如果代码单元格返回 **PASSED**，则表明你正确地实现了该函数！ \n",
    "\n",
    "**注意：**为了确保结果准确，确保 `q_from_v` 函数满足上文列出的要求（具有四个输入、一个输出，并且没有更改输入参数的默认值）。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "**<span style=\"color: green;\">PASSED</span>**"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "check_test.run_check('q_from_v_check', q_from_v)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 第 3 部分：策略改进\n",
    "\n",
    "在此部分，你将自己编写策略改进实现。 \n",
    "\n",
    "你的算法应该有三个**输入**参数：\n",
    "- `env`：这是 OpenAI Gym 环境的实例，其中 `env.P` 会返回一步动态特性。\n",
    "- `V`：这是一个一维 numpy 数组，其中 `V.shape[0]` 等于状态数量 (`env.nS`)。`V[s]` 包含状态 `s` 的估值。\n",
    "- `gamma`：这是折扣率。它必须是在 0 到 1（含）之间的值，默认值为：`1`。\n",
    "\n",
    "该算法会返回以下**输出结果**：\n",
    "\n",
    "- `policy`：这是一个二维 numpy 数组，其中 `policy.shape[0]` 等于状态数量 (`env.nS`) ， `policy.shape[1]` 等于动作数量 (`env.nA`) 。`policy[s][a]`  返回智能体在状态 `s` 时根据该策略选择动作 `a` 的概率。\n",
    "\n",
    "请完成以下代码单元格中的函数。建议你使用你在上文实现的 `q_from_v` 函数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "def policy_improvement(env, V, gamma=1):\n",
    "    policy = np.zeros([env.nS, env.nA]) / env.nA\n",
    "    for s in range(env.nS):\n",
    "        q = q_from_v(env, V, s, gamma)\n",
    "        policy[s][np.argmax(q)] = 1\n",
    "    ## TODO: complete the function\n",
    "#     for s in range(env.nS):\n",
    "#         q = q_from_v(env, V, s, gamma)\n",
    "#         best_a = np.argwhere(q==np.max(q)).flatten()\n",
    "#         policy[s] = np.sum([np.eye(env.nA)[i] for i in best_a], axis=0)/len(best_a)\n",
    "    \n",
    "    return policy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "运行以下代码单元格以测试你的函数。如果代码单元格返回 **PASSED**，则表明你正确地实现了该函数！ \n",
    "\n",
    "**注意：**为了确保结果准确，确保 `policy_improvement` 函数满足上文列出的要求（具有三个输入、一个输出，并且没有更改输入参数的默认值）。\n",
    "\n",
    "在继续转到该 notebook 的下个部分之前，强烈建议你参阅 **Dynamic_Programming_Solution.ipynb** 中的解决方案。该函数有很多正确的实现方式！"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "**<span style=\"color: green;\">PASSED</span>**"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "check_test.run_check('policy_improvement_check', policy_improvement)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 0.  0.  0.  0.]\n",
      " [ 0.  0.  0.  0.]\n",
      " [ 0.  0.  0.  0.]\n",
      " [ 0.  0.  0.  0.]\n",
      " [ 0.  0.  0.  0.]\n",
      " [ 0.  0.  0.  0.]\n",
      " [ 0.  0.  0.  0.]\n",
      " [ 0.  0.  0.  0.]\n",
      " [ 0.  0.  0.  0.]\n",
      " [ 0.  0.  0.  0.]\n",
      " [ 0.  0.  0.  0.]\n",
      " [ 0.  0.  0.  0.]\n",
      " [ 0.  0.  0.  0.]\n",
      " [ 0.  0.  0.  0.]\n",
      " [ 0.  0.  0.  0.]\n",
      " [ 0.  0.  0.  0.]]\n"
     ]
    }
   ],
   "source": [
    "policy = np.zeros([env.nS, env.nA]) / env.nA\n",
    "print(policy)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 0.0147094   0.01393978  0.01393978  0.01317015]\n",
      "[ 1.  0.  0.  0.]\n",
      "[ 0.00852356  0.01163091  0.0108613   0.01550788]\n",
      "[ 0.  0.  0.  1.]\n",
      "[ 0.02444514  0.02095298  0.02406033  0.01435346]\n",
      "[ 1.  0.  0.  0.]\n",
      "[ 0.01047649  0.01047649  0.00698432  0.01396865]\n",
      "[ 0.  0.  0.  1.]\n",
      "[ 0.02166487  0.01701828  0.01624865  0.01006281]\n",
      "[ 1.  0.  0.  0.]\n",
      "[ 0.  0.  0.  0.]\n",
      "[ 1.    0.25  0.25  0.25]\n",
      "[ 0.05433538  0.04735105  0.05433538  0.00698432]\n",
      "[ 1.   0.   0.5  0. ]\n",
      "[ 0.  0.  0.  0.]\n",
      "[ 1.    0.25  0.25  0.25]\n",
      "[ 0.01701828  0.04099204  0.03480619  0.04640826]\n",
      "[ 0.  0.  0.  1.]\n",
      "[ 0.07020885  0.11755991  0.10595784  0.05895312]\n",
      "[ 0.  1.  0.  0.]\n",
      "[ 0.18940421  0.17582037  0.16001424  0.04297382]\n",
      "[ 1.  0.  0.  0.]\n",
      "[ 0.  0.  0.  0.]\n",
      "[ 1.    0.25  0.25  0.25]\n",
      "[ 0.  0.  0.  0.]\n",
      "[ 1.    0.25  0.25  0.25]\n",
      "[ 0.08799677  0.20503718  0.23442716  0.17582037]\n",
      "[ 0.  0.  1.  0.]\n",
      "[ 0.25238823  0.53837051  0.52711478  0.43929118]\n",
      "[ 0.  1.  0.  0.]\n",
      "[ 0.  0.  0.  0.]\n",
      "[ 1.    0.25  0.25  0.25]\n"
     ]
    }
   ],
   "source": [
    "for s in range(env.nS):\n",
    "    q = q_from_v(env, V, s, 1)\n",
    "    print(q)\n",
    "    policy[s][np.argmax(q)] = 1\n",
    "    print(policy[s])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0]\n",
      "[ 1.  0.  0.  0.]\n",
      "[3]\n",
      "[ 0.  0.  0.  1.]\n",
      "[0]\n",
      "[ 1.  0.  0.  0.]\n",
      "[3]\n",
      "[ 0.  0.  0.  1.]\n",
      "[0]\n",
      "[ 1.  0.  0.  0.]\n",
      "[0 1 2 3]\n",
      "[ 0.25  0.25  0.25  0.25]\n",
      "[0 2]\n",
      "[ 0.5  0.   0.5  0. ]\n",
      "[0 1 2 3]\n",
      "[ 0.25  0.25  0.25  0.25]\n",
      "[3]\n",
      "[ 0.  0.  0.  1.]\n",
      "[1]\n",
      "[ 0.  1.  0.  0.]\n",
      "[0]\n",
      "[ 1.  0.  0.  0.]\n",
      "[0 1 2 3]\n",
      "[ 0.25  0.25  0.25  0.25]\n",
      "[0 1 2 3]\n",
      "[ 0.25  0.25  0.25  0.25]\n",
      "[2]\n",
      "[ 0.  0.  1.  0.]\n",
      "[1]\n",
      "[ 0.  1.  0.  0.]\n",
      "[0 1 2 3]\n",
      "[ 0.25  0.25  0.25  0.25]\n"
     ]
    }
   ],
   "source": [
    "policy = np.zeros([env.nS, env.nA]) / env.nA\n",
    "for s in range(env.nS):\n",
    "    q = q_from_v(env, V, s, 1)\n",
    "    best_a = np.argwhere(q==np.max(q)).flatten()\n",
    "    print(best_a)\n",
    "    policy[s] = np.sum([np.eye(env.nA)[i] for i in best_a], axis=0)/len(best_a)\n",
    "    print(policy[s])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 第 4 部分：策略迭代\n",
    "\n",
    "在此部分，你将自己编写策略迭代的实现。该算法会返回最优策略，以及相应的状态值函数。\n",
    "\n",
    "你的算法应该有三个**输入**参数：\n",
    "\n",
    "- `env`：这是 OpenAI Gym 环境的实例，其中 `env.P` 会返回一步动态特性。\n",
    "- `gamma`：这是折扣率。它必须是在 0 到 1（含）之间的值，默认值为：`1`。\n",
    "- `theta`：这是一个非常小的正数，用于判断策略评估步骤是否足够地收敛于真值函数 (默认值为：`1e-8`）。\n",
    "\n",
    "该算法会返回以下**输出结果**：\n",
    "\n",
    "- `policy`：这是一个二维 numpy 数组，其中 `policy.shape[0]` 等于状态数量 (`env.nS`) ， `policy.shape[1]` 等于动作数量 (`env.nA`) 。`policy[s][a]`  返回智能体在状态 `s` 时根据该策略选择动作 `a` 的概率。\n",
    "- `V`：这是一个一维 numpy 数组，其中 `V.shape[0]` 等于状态数量 (`env.nS`)。`V[s]` 包含状态 `s` 的估值。\n",
    "\n",
    "请完成以下代码单元格中的函数。强烈建议你使用你在上文实现的 `policy_evaluation` 和 `policy_improvement` 函数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [],
   "source": [
    "import copy\n",
    "\n",
    "def policy_iteration(env, gamma=1, theta=1e-8):\n",
    "    policy = np.ones([env.nS, env.nA]) / env.nA\n",
    "    \n",
    "    ## TODO: complete the function\n",
    "    while True:\n",
    "        V = policy_evaluation(env, policy, gamma, theta)\n",
    "        new_policy = policy_improvement(env, V)\n",
    "        if (new_policy == policy).all():\n",
    "            break;\n",
    "        policy = copy.copy(new_policy)\n",
    "    return policy, V"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "运行下个代码单元格以解决该 MDP 并可视化输出结果。最优状态值函数已调整形状，以匹配网格世界的形状。\n",
    "\n",
    "**将该最优状态值函数与此 notebook 第 1 部分的状态值函数进行比较**。_最优状态值函数一直都大于或等于等概率随机策略的状态值函数吗？_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Optimal Policy (LEFT = 0, DOWN = 1, RIGHT = 2, UP = 3):\n",
      "[[ 1.  0.  0.  0.]\n",
      " [ 0.  0.  0.  1.]\n",
      " [ 0.  0.  0.  1.]\n",
      " [ 0.  0.  0.  1.]\n",
      " [ 1.  0.  0.  0.]\n",
      " [ 1.  0.  0.  0.]\n",
      " [ 1.  0.  0.  0.]\n",
      " [ 1.  0.  0.  0.]\n",
      " [ 0.  0.  0.  1.]\n",
      " [ 0.  1.  0.  0.]\n",
      " [ 1.  0.  0.  0.]\n",
      " [ 1.  0.  0.  0.]\n",
      " [ 1.  0.  0.  0.]\n",
      " [ 0.  0.  1.  0.]\n",
      " [ 0.  1.  0.  0.]\n",
      " [ 1.  0.  0.  0.]] \n",
      "\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAVsAAAFoCAYAAAD5IVjuAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4wLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvpW3flQAAIABJREFUeJzt3Hl4VNX9x/H3yUwme0IgGxGBIBKs7CAKiBRFENdWtKiIYCvFtm5QteDSaqs/awWqVYGCCuICtoKKRVSwQmVxAUFQ3FABgQQSSMhGSDI5vz8mRIZMEEJyIvJ5+dynT8793nvP/c7kkzt3bjHWWkREpGGFNfYERESOBwpbEREHFLYiIg4obEVEHFDYiog4oLAVEXFAYSs/KMaYTcaYAY09j4ZgjBlmjHmzsechjUNhe4wzxpxpjFlhjNljjNltjFlujDmtat1IY8yyI9hXa2OMNcZ46ziX8caY/4UYTzLGlBljOtRlv/XBGDOzag5FByxDG/B4NXpprX3OWjuwoY4pP2wK22OYMSYe+A/wKNAUOAG4F9jXSFN6BuhtjMk4aPwKYL219uNGmNOB/matjT1geaGR5yPHEYXtsa0dgLV2trXWb63da61901q7zhhzCjAV6FV1FZcPYIy5wBizxhhTYIz51hhzzwH7239Vml+1Ta+qbX5pjPnUGJNnjHnDGNMq1GSstVuB/wLDD1p1DfB01b5OMsb81xizyxiTa4x5zhjTJNT+qq5G7zvg558aY7Ye8HO6MWauMSbHGPONMeamw+5c8HGsMaZtqOPuP6Yx5vfGmJ3GmCxjzLUH1EYZYyYaYzZXfbpYZoyJIkQvD/6kYYzpbYz5oGq7D4wxvQ9Yt8QY85eqTyqFxpg3jTFJdTk/+WFQ2B7bvgD8xpinjTGDjTGJ+1dYaz8FrgdWVl3F7Q+0YgLh1wS4APiNMeZnVevOqvrfJlXbrKxadwdwKZAMvAPMPsScnuaAsDXGZAJdDtjGAA8A6cApwInAPUd64saYMOBV4CMCV/TnALcYYwYd6b4OQxqQUHWcXwGPH9DrCUB3oDeBTxe3A5WE6OVB828KLAD+ATQDJgELjDHNDii7CrgWSAF8wK31f2riisL2GGatLQDOBCwwHcgxxsw3xqQeYpsl1tr11tpKa+06AiHY7xCHGQ08YK391FpbAfwf0KW2q1vgJSD1gKu0a4CF1tqcquNvtNYustbuqxqb9D3Hr81pQLK19s/W2jJr7dcEenDFIba51RiTX7XkHsGxyoE/W2vLrbWvAUVAZlXg/xK42Vq7rerTxQpr7eHcxrkA+NJa+4y1tsJaOxv4DLjogJoZ1tovrLV7gX8R+KMlxyiF7TGuKgRHWmtbAB0IXDE+XFu9MeZ0Y8zbVR+99xC4+j3Ux9NWwCP7QwrYTeDq9ARjzB0HfNk0tWo+JcC/gWuMMQYYRtUthKrjpxhj5hhjthljCoBnv+f4h5pX+gHhmU/gCrzWPzTABGttk6rlSI65q+oPzX4lQCyBeUcCXx3p5Am8TpsPGttM4Op5v+wQx5RjlML2R8Ra+xkwk0DoQuCK92DPA/OBE621CQTu65pD1H8LjD4gpJpYa6OqruD+74Avm64/YJungV8A5wJxBL7E2++BquN0stbGA1cfcPyDFQPRB/ycdtC8vjloXnHW2vNr2dehlBziOIeSC5QCJ4VY933/nN52An8wDtQS2HaYx5ZjjML2GGaMaV/1xU2Lqp9PBK4E3q0q2QG0MMb4DtgsDthtrS01xvQkcF9wvxwC9xvbHDA2FRhvjDm16hgJxpjLv2dq7wD5wDRgjrW27KDjFxH44ugE4LZD7GctcL4xpqkxJg245YB17wMFxpg/VH1J5THGdDBVj70dobXAVVX7OI/DvK1hra0EngImVX1Z56n6IiyC0L080GtAO2PMVcYYrwk8hvYTgv8wyY+IwvbYVgicDrxnjCkmELIfA7+vWv9f4BMg+4B7lL8F/myMKQT+SOBeIFB9C+B+YHnVR/MzrLUvAQ8Cc6o+9n8MDD7UpGzgH0meReDKbdZBq+8FugF7CHxBNO8Qu3qGwBdgm4A3gepHtay1fgL3N7sA3xC4ynyCwBdZR+rmqn3lE7jt8fIRbHsrsB74gMAtlgeBsFC9PHAja+0u4EICr9UuAl+sXWitPZJ7yXIMMfrHw0VEGp6ubEVEHFDYiog4oLAVEXFAYSsi4oDCVkTEgSP6p/SaepJsC2/rBpqKiMixZ2vFJnb7c2v7P+ZUO6KwbeFtzfz0VXWflYjIj8zF23scVp1uI4iIOKCwFRFxQGErIuKAwlZExAGFrYiIAwpbEREHFLYiIg4obEVEHFDYiog4oLAVEXFAYSsi4oDCVkTEAYWtiIgDClsREQcUtiIiDihsRUQcUNiKiDigsBURcUBhKyLigMJWRMQBha2IiAMKWxERBxS2IiIOKGxFRBxQ2IqIOKCwFRFxQGErIuKAwlZExAGFrYiIAwpbEREHFLYiIg4obEVEHFDYiog44CxsnymYTN+tGWRuiuSi7d15v/SdQ9a/UvQ852/rwimbozltSxq35FxNTkV29frZhdO5PKsvXbY0pdPmJlyZ3Z8PSpcF7WNWweOct60THTfH03FzPJdm9eK/JQuCam7NGUnGJhO0/Hz7GUE143JH0W/rSbTfHEX3LcmM2nEJG8s+PcqOHDn1sH6oj0dPPTxyTsL2P8Uv8OfdN/PbhDtYkL6GbhG9uXbHYLZVbAlZv6p0OWNzhzMkdgRvpn/CtJSX2Vi+gVtyh1XXvFe6hAtjhvJc6lu8lP4ebbyZjNgxiG/Kv6yuSfO2YFzig7ya/iGvpK+iV+TZjN75Mz4tWxd0vD6RA3i/RVb1MiP1taD1nSJ68FDSTBanf8rTqW9gsVy9YwDltrweu3Ro6mH9UB+PnnpYN8Zae9jFnSJ62Pnpq474ID/bfjrtfZ34a9L06rH+W09mcMxl3J74QI36aXsm8HTBoyw/cXP12L8LZ3DP7hv5pFVRyGNYa+n5bXN+1+RORsbfWOtcumxpyu2JD3BV3Ggg8JcwrzKXJ1P/c9jn82nZOs7f3pnFJ3zGSeGZh73d0VAP64f6ePTUw2AXb+/Bun2rzPfVNfiVbZkt4+Oy1fSNGhg0fmbUQFaXrgi5TY+IPuT4s1hc8irWWnb7c3m1eA4/jTq/9uNQxj5bSkJYYsj1fuvn1aI5lFQW0S2id9C6D0qX0WNLCv23tmNc7ihy/TtrPU5JZTEvFs0g3dOSFt7WtdbVJ/WwfqiPR089rDtvg+4dyPPn4sdPkic1aDzZk8py/+KQ23SL7MUjybMZkzOMUruXCio4M/JcJiY9XetxJubdRUxYLAOiLw4a/6xsPUOyerHPlhJtYpma8hLtfR2r1/eLOo9BMZdyojeDrRWbmJh3F8Oyz2Z++moiTER13TMFk/lr3u2U2GLaeDN5Lu2toPUNST2sH+rj0VMP687ZF2SG4Ktsi60xtt+XZRu4d/dN3NDkbuanr2Zm6uvk+LO5Y9fokPUzCh5hduE/mZIyj7iw+KB1bcIzWZC+lnnN3+Xq+N9wa+4IPi/7uHr9RbFXcG70xbT3dWRA9EXMTF3I1+Wf8/ZBN94viR3Gf9LXMCdtKRnh7fhdzuXsrSypSyvqTD2sH+rj0VMPj1yDX9kmepLw4CHHnx00nuvfWeOv436T9zxA54iejE64DYBT6ER0sxh+kd2XWxPvJ917YnXtjIJHmJh3FzNSF9IlomeNffmMj9bhbYHAjfF1+z7gqYK/82DSkyGPnepNJ83bgk0VXwaNx4clEB+WQEb4yXSNOIMuWxJZWDKXS2OHH34z6kg9rB/q49FTD+uuwa9sfcZHB193lu1dFDS+bO8iukf2DrlNqS0hDE/QmKfqZ8t3X+g9sWcSE/Lu5MnUBZwWeeZhzaeSSvbZfbWu3+3PZUfFNpI9zWutsVX/lR1iP/VJPawf6uPRUw/rrsGvbAGuSxjL2JzhdI7oSY+IPjxXOJWd/u1cFXc9AGNzrgFgUvIsAM6Juojxu0bxbMEUzooaxE5/Fn/ZfQsdfN04wdsSgH/ueYiJeXcyKflZ2njbVT+zFxEWRXxYAgAP7h5H/+gLSPecSJEtZH7x87xbuoSnUgIfKYori3g4/x4GRw8hxdOcrRWb+Fv+eJp5UhgU/XMANpVv5PWSufSJHEBTTzLZFVuZsuev+EwE50Rd6KJ96mE9Uh/Vw8bqoZOwvTBmKHn+XTyWfx85/iza+TrwVOprtPC2AmD7Qc/nXRY3kiJbyKzCx7g/7/fEhSXQK7I/4xL/Vl3zTMHjlFPOjTlDg7YdEjOCCckzAcjxZzMm52py/dnEhSXQ3teJGakL6Rc1CAj8df28bD0vFc2ioDKfZE9zekX257HkfxEbFgeAz0TwbukSntgzkYLKfJI8qfSMPIt5aStJ9qY1VMtqUA/rh/p49NTDunHynK2IyI/VD+Y5WxERUdiKiDihsBURcUBhKyLigMJWRMQBha2IiAMKWxERBxS2IiIOKGxFRBxQ2IqIOKCwFRFxQGErIuKAwlZExAGFrYiIAwpbEREHFLYiIg4obEVEHFDYiog4oLAVEXFAYSsi4oDCVkTEAYWtiIgDClsREQcUtiIiDihsRUQcUNiKiDigsBURcUBhKyLigMJWRMQBha2IiAMKWxERBxS2IiIOKGxFRBxQ2IqIOKCwFRFxwNvYEzgeZXzT2DM49v19TGPP4MdhzN8bewY/Aj0Or0xXtiIiDihsRUQcUNiKiDigsBURcUBhKyLigMJWRMQBha2IiAMKWxERBxS2IiIOKGxFRBxQ2IqIOKCwFRFxQGErIuKAwlZExAGFrYiIAwpbEREHFLYiIg4obEVEHFDYiog4oLAVEXFAYSsi4oDCVkTEAYWtiIgDClsREQcUtiIiDihsRUQcUNiKiDigsBURcUBhKyLigMJWRMQBha2IiAMKWxERBxS2IiIOKGxFRBxQ2IqIOOAsbJ8pmEzfrRlkborkou3deb/0nUPWv1L0POdv68Ipm6M5bUsat+RcTU5FdvX62YXTuTyrL122NKXT5iZcmd2fD0qXBe1jVsHjnLetEx03x9NxczyXZvXivyULgmpuzRlJxiYTtPx8+xlBNeNyR9Fv60m03xxF9y3JjNpxCRvLPj3KjjSiyZMhIwMiI6F7d3jn0K8FS5cG6iIjoU0bmDrVzTwbyLKPJvOXpzK47dFIJj7fna+21X7+G79dwpiHTY1lx+7PqmtWrp/OP/7VlzunNGX85CY8/mJ/vt4W/F4sLSvkpSW38OcnW3H7o1E88kJvtmR/UOtxX1j8a8Y8bHh79YSg8RXrp/H4i/0ZP7kJYx427N6zqW5N+KE4jt6LTsL2P8Uv8OfdN/PbhDtYkL6GbhG9uXbHYLZVbAlZv6p0OWNzhzMkdgRvpn/CtJSX2Vi+gVtyh1XXvFe6hAtjhvJc6lu8lP4ebbyZjNgxiG/Kv6yuSfO2YFzig7ya/iGvpK+iV+TZjN75Mz4tWxd0vD6RA3i/RVb1MiP1taD1nSJ68FDSTBanf8rTqW9gsVy9YwDltrweu+TICy/AzTfDHXfAmjXQuzcMHgxbQr8WfPMNnH9+oG7NGhg/Hm68EebOdTvverLm8xd4aenNDDjtDm4dtobWzXsz7eXB5BXUcv5V/jD8E+4dlVW9JDc5uXrdxq1L6NpuKL8Z8hZjrniP5MRM/vnSIHLyvnsvvrDoOj7b/AZXDXya24avJ7PlQKbMG0B+0bYax1r75Yt8u+MDEmLSa6wrLy8hs+VAzjvjnro34YfiOHsvOgnbJ/ZMYkjsSK6MG0Vb3ync2+xRUjzNea5wSsj6D/etJM3Tgl8ljOHE8Ay6Rp7BiLgbWbvvveqah5OfY0T8DZwa0ZWTwjO5r9kUYkwcS/e+Xl0zMPoSfho9mNbhbWkT3o7bEu8nJiyONftWBh0vwkSQ7E2rXpp4mgatvypuND0j+9IivDUdIrrx+8T72OHfzpaKr+uxS45MmgQjR8KoUXDKKfDoo9C8OUwJ/VowdSqkpwfqTjklsN2IETBhQuj6H7glH06i509G0qvjKFKbnsKQ/o8SH9Oc5etqOf8qsdEpxMekVS9hYZ7qdcMHP0ffLjfQIqUrKU0zufzsKUT44vh0c+C9WFaxl3Ub53LhmX+l7Yk/JblJW87rdQ9JTdqy4qDj7i7YzMtLbmb44OcJCwuvMY9+3W5hQM/xZJxwZj10o5EdZ+/FBg/bMlvGx2Wr6Rs1MGj8zKiBrC5dEXKbHhF9yPFnsbjkVay17Pbn8mrxHH4adX7tx6GMfbaUhLDEkOv91s+rRXMoqSyiW0TvoHUflC6jx5YU+m9tx7jcUeT6d9Z6nJLKYl4smkG6pyUtvK1rrftBKiuD1athYPBrwcCBsCL0a8HKlTXrBw2CVaug/Ni6sq/wl7F152oyWwafT2bLgWzKquX8q0x6vgd/nNacyXPP4ctv3z5krd9fRnlFKdERgfdiZWUFldZPuCcyqC7cGxV0u8FfWcEzC6/k3J53kdr0lCM5tWPPcfhebPCwzfPn4sdPkic1aDzZk0qOPzvkNt0ie/FI8mzG5Ayj3WYf3b9NxmKZmPR0rceZmHcXMWGxDIi+OGj8s7L1nLo5lszNEdy563qmprxEe1/H6vX9os5jYvIsnk17izubTuSjfe8zLPts9tl9Qft5pmAyp26O5dQtsSwpWchzaW8RYSKOtB2NKzcX/H5IDX4tSE2F7NCvBdnZoesrKgL7O4YU782l0vqJiw4+n7joVApKQp9/fExzLjt7CtdeOJdfXjiPlMRMpsw9h6+2/q/W47y28i4ifLF0aBN4L0b64mjdvBdvvn8f+UXbqKz0s+rTZ9mUtZKCkqzq7V5f+SeiI5vRp/Nv6uFsf+COw/ei19WBDCboZ4utMbbfl2UbuHf3TdzQ5G7OihrETn8WD+y+jTt2jWZS8qwa9TMKHmF24T95Jm0xcWHxQevahGeyIH0tBZX5vF4yl1tzRzA7bQmZvg4AXBR7RXVte19HOvq6c+bWVrxdsoDzYi6tXndJ7DDOjDqXnf4spu+ZwO9yLufFtOVEhUXXuSeNxhzUd2trjn1ffajxY4U5/PdiStNMUppmVv/cOr0Xuws28faHEzipxVk16peueYQV6//Jby5dTGTEd+/FYYOeYc6iX3LvEy0IMx5apHSjW+aVbN35IQAbty7lgw0zuXXY2vo4w2PHcfRebPCwTfQk4cFT4yo217+zxtXufpP3PEDniJ6MTrgNgFPoRHSzGH6R3ZdbE+8n3Xtide2MgkeYmHcXM1IX0iWiZ419+YyP1uFtgcAXXev2fcBTBX/nwaQnQx471ZtOmrcFmyq+DBqPD0sgPiyBjPCT6RpxBl22JLKwZC6Xxg4//GY0tqQk8HhqXjns3FnzimG/tLTQ9V4vNGvWMPNsIDFRSYQZD4XFwedTVLKzxtXuobRMO501n8+pMb50zSMsXHEXv/7ZQlqlBb8Xk5qcxA2XL2VfeTGlZQUkxDTn6QVDaRqfAcDGb9+moDiLP01vXr1NpfXz6rI/sHTNw9xz3dYjOdUfvuPwvdjgtxF8xkcHX3eW7V0UNL5s7yK6R/YOuU2pLSEMT9CYp+pni60ee2LPJCbk3cmTqQs4LfLwvjCopLLGLYID7fbnsqNiG8me5rXW2Kr/yg6xnx8kny/w2Myi4NeCRYsC3/CG0qsXLF5cs75HDwiv+QXOD5nX46NFSnc+3xJ8/l9sWUTr5rWcfwjbc9YSHxP8/ljy4SReW3Enoy5ZQJtDfHkVER5DQkxzSkrz+GzzG3Q46RIA+nT+LbddvY5bh62tXhJi0unXdQy/vfStIzjLY8Rx+F50chvhuoSxjM0ZTueInvSI6MNzhVPZ6d/OVXHXAzA25xqA6lsE50RdxPhdo3i2YEr1bYS/7L6FDr5unOBtCcA/9zzExLw7mZT8LG287aqfwY0IiyI+LAGAB3ePo3/0BaR7TqTIFjK/+HneLV3CUymBZ22LK4t4OP8eBkcPIcXTnK0Vm/hb/niaeVIYFP1zADaVb+T1krn0iRxAU08y2RVbmbLnr/hMBOdEXeiiffVr7FgYPhx69oQ+fQLf8G7fDtcHXguuCbwWzKq6XXP99fDYY3DLLTB6NCxfDjNnwuzZjTL9o/XTbmN57o3htErrSUZ6H5avm8qe4u307hQ4/+feCJz/sEGB81/64cM0jW9NWrNTqagsY/Wnz7L+q5e59sLvHjf676qHeG3FnQw771mSE9tRUHXlHO6NIioi8F78bNMbWFtJStP25OZvZP47t5GSmMnpP7kWgLjoFOKiU4LmGhYWTnxMWtBtjILibAqLs8nJ+wKA7N0b2LsvnybxLYmJDH6K5gfvOHsvOgnbC2OGkuffxWP595Hjz6KdrwNPpb5GC28rALYf9LztZXEjKbKFzCp8jPvzfk9cWAK9IvszLvFv1TXPFDxOOeXcmDM0aNshMSOYkDwTgBx/NmNyribXn01cWALtfZ2YkbqQflGDgMDV8udl63mpaBYFlfkke5rTK7I/jyX/i9iwOAB8JoJ3S5fwxJ6JFFTmk+RJpWfkWcxLW0myN62hWtZwhg6FXbvgvvsgKws6dIDXXoNWgdeixjOOGRmB9WPGBB7JSU+Hf/wDhgxxP/d60DVzKMWlu3jzvfsoKMmiebMO/PqS12gaHzj/g5+3ragsY/47t7KnaBvh3ihSm53KqEsW8JOM756MWfbR4/gry5n1WvB78bRTRnDVoJkA7C3bw4Ll48kv2kp0RFM6nzyE83vfj8dzZFdkK9ZN5Y337q3+eforFwBw5bkz6HnqyCPaV6M7zt6Lxlr7/VVVOkX0sPPTVzXgdI4PGd809gyOfX8f09gz+HEY8/fGnsGPQI8e2FWrvvcbOv3bCCIiDihsRUQcUNiKiDigsBURcUBhKyLigMJWRMQBha2IiAMKWxERBxS2IiIOKGxFRBxQ2IqIOKCwFRFxQGErIuKAwlZExAGFrYiIAwpbEREHFLYiIg4obEVEHFDYiog4oLAVEXFAYSsi4oDCVkTEAYWtiIgDClsREQcUtiIiDihsRUQcUNiKiDigsBURcUBhKyLigMJWRMQBha2IiAMKWxERBxS2IiIOKGxFRBzwNvYEjkffZDT2DI59+U0aewYiR0ZXtiIiDihsRUQcUNiKiDigsBURcUBhKyLigMJWRMQBha2IiAMKWxERBxS2IiIOKGxFRBxQ2IqIOKCwFRFxQGErIuKAwlZExAGFrYiIAwpbEREHFLYiIg4obEVEHFDYiog4oLAVEXFAYSsi4oDCVkTEAYWtiIgDClsREQcUtiIiDihsRUQcUNiKiDigsBURcUBhKyLigMJWRMQBha2IiAMKWxERBxS2IiIOKGxFRBxQ2IqIOOAsbJ8pmEzfrRlkborkou3deb/0nUPWv1L0POdv68Ipm6M5bUsat+RcTU5FdvX62YXTuTyrL122NKXT5iZcmd2fD0qXBe1jVsHjnLetEx03x9NxczyXZvXivyULgmpuzRlJxiYTtPx8+xlBNeNyR9Fv60m03xxF9y3JjNpxCRvLPj3Kjhw59fDo/St3MhdsyOD0jyK56vPufFhUew//uHkkXdeaGkuvdTFBdeWVZUzO+iMXbMig50cRDP6kJc/n/CPkPhfmzabrWsNNX18YNH7+J61DHuvGry+orlld9D9u/vpiBn5yAl3XGubvmln3RvxQTJ4MGRkQGQndu8M7h35Ps3RpoC4yEtq0galT3cyzHjgJ2/8Uv8Cfd9/MbxPuYEH6GrpF9ObaHYPZVrElZP2q0uWMzR3OkNgRvJn+CdNSXmZj+QZuyR1WXfNe6RIujBnKc6lv8VL6e7TxZjJixyC+Kf+yuibN24JxiQ/yavqHvJK+il6RZzN658/4tGxd0PH6RA7g/RZZ1cuM1NeC1neK6MFDSTNZnP4pT6e+gcVy9Y4BlNvyeuzSoamHR++NvBd4aOvN/Cr1DmZnrqFTTG9u+HowWWWhe3hbi0dYdGpW0NLC14aBTX4RVDdu85WsKHydu0+cxsvtP+dvrf9Nu8hONfa3dd/XPLz9NrrG9K2x7tnMD4KOM7vdhxgM5x5wrJLKItpGduC2Ex4h0kQdZTd+AF54AW6+Ge64A9asgd69YfBg2BL69eCbb+D88wN1a9bA+PFw440wd67bedeRsdYednGniB52fvqqIz7Iz7afTntfJ/6aNL16rP/Wkxkccxm3Jz5Qo37angk8XfAoy0/cXD3278IZ3LP7Rj5pVRTyGNZaen7bnN81uZOR8TfWOpcuW5pye+IDXBU3GghcleVV5vJk6n8O+3w+LVvH+ds7s/iEzzgpPPOwtzsa6mGw/CZHvAnDvzidkyM78ceW3/Xw4g0nM6DJZdyUXrOHB1tbtJxrN57JjJOX0yWmNwArC97k9k2XM/8nX5HoTap123Jbzi+/PJPLk37LqsK3yffn8o82tffriez7eXrnQ7zZYTtRYdE11vdeF8u4Ex7j4mYjv3feh9J1zVFtfnROPx06dYLp370enHwyXHYZPBDi9fjDH2DePPjyu4sBrrsOPvkEVq5s+PnWpkcP7KpV5vvKGvzKtsyW8XHZavpGDQwaPzNqIKtLV4TcpkdEH3L8WSwueRVrLbv9ubxaPIefRp1f+3EoY58tJSEsMeR6v/XzatEcSiqL6BbRO2jdB6XL6LElhf5b2zEudxS5/p21HqekspgXi2aQ7mlJC2/rWuvqk3p49Mory/i0ZDW94oN72Ct+IB8Vh+7hwebtms5JkadWBy3A23te5ifRp/HszkkM+qQFF284mQe33kSJP/gP2uNZd5Lua83FTUd873Gstby8+0kuaHp1yKD9USgrg9WrYWDw68HAgbCiltdj5cqa9YMGwapVUO7uE1JdeRv6AHn+XPz4SfKkBo0ne1JZ7l8ccptukb14JHk2Y3KGUWr3UkEFZ0aey8Skp2s9zsS8u4gJi2VA9MVB45+VrWdIVi/22VKiTSxTU16iva9j9fp+UecxKOZSTvRmsLViExPz7mJY9tnMT19NhImornumYDJ/zbudEltMG28mz6W9FbS+IamHR2/brScoAAASvElEQVR/D5t6g3vY1JvKrorQPTxQoX8Pi/b8mxub/1/Q+Layr1lbvAxfWAQTWs+l0J/Pg9tuJKd8OxMyXgQCV79v5L3AC5lrD2uu7xYuYlvZN/y86XWHeXbHoNxc8PshNfj1IDUVFtfyemRnw4ABNesrKgL7a968YeZaT5x9QWYIvsq22Bpj+31ZtoF7d9/EDU3uZn76amamvk6OP5s7do0OWT+j4BFmF/6TKSnziAuLD1rXJjyTBelrmdf8Xa6O/w235o7g87KPq9dfFHsF50ZfTHtfRwZEX8TM1IV8Xf45bx/0JdAlscP4T/oa5qQtJSO8Hb/LuZy9lSV1aUWdqYdHr2a/au/hgV7b/SyV1s8FicODxiupxGD4v1bP0zHmdHrHD2LcCY/x1p657CrfQV5FLn/cMpK/tHyaeG/oTwwHm7drOqdGn0ZmdJfDPa1jlzmo99bWHPu++lDjP0ANfmWb6EnCg4ccf3bQeK5/Z40rtf0m73mAzhE9GZ1wGwCn0InoZjH8IrsvtybeT7r3xOraGQWPMDHvLmakLqRLRM8a+/IZH63D2wKBL2nW7fuApwr+zoNJT4Y8dqo3nTRvCzZVfBk0Hh+WQHxYAhnhJ9M14gy6bElkYclcLo0dHnI/9Uk9PHr7e7irIriHuyt21rjaDWXerumc02QICd6mQeNJ3uakhJ9AnCeheiwj8hQAssu3sNdfTG5FFtd/9d0VWSWVAPRY6+XF9p/QOvK7e9a7y3eypOAVxrd4/MhP8liSlAQeT+Bq9UA7d9a82t0vLS10vdcLzZo1zDzrUYNf2fqMjw6+7izbuyhofNneRXSP7B1ym1JbQhieoDFP1c+W777Qe2LPJCbk3cmTqQs4LfLMw5pPJZXss/tqXb/bn8uOim0ke2r/SGKr/is7xH7qk3p49MLDfJwS3Z13C4N7+G7hIjrHhO7hfh8Xv88XpR9xadNRNdZ1ielDTvn2oHu0m/d9AUDz8FacGn0a/85cz5zMtdVLv/iL6RrTlzmZaznBlxG0v/m7Z+IzEQxqckVdT/XY4PMFHuFaFPx6sGhR4GmDUHr1qnmLYdEi6NEDwsMbZp71qMGvbAGuSxjL2JzhdI7oSY+IPjxXOJWd/u1cFXc9AGNzrgFgUvIsAM6Juojxu0bxbMEUzooaxE5/Fn/ZfQsdfN04wdsSgH/ueYiJeXcyKflZ2njbVT8/GhEWRXxY4Crjwd3j6B99AemeEymyhcwvfp53S5fwVErg421xZREP59/D4OghpHias7ViE3/LH08zTwqDon8OwKbyjbxeMpc+kQNo6kkmu2IrU/b8FZ+J4Jyo4Gcl1cMfdg+vTh7LXVuGc2p0T7rE9OHF3KnklG/nsqRAD+/aHOjhfa1mBW03d9c0WkacTPfYfjX2OTjxKqbv+At/2nIt16fdQ6E/n4e23cyAhMtoGp4CQNuoDkHbxHma4Keixri1lpd2P8GgJlcQ44mrcawSfxHf7ttYVVtJVvkWPi9ZS7y3Kc19LevYlUY0diwMHw49e0KfPoFnZrdvh+sDrwfXBF4PZlW9HtdfD489BrfcAqNHw/LlMHMmzJ7dKNM/Uk7C9sKYoeT5d/FY/n3k+LNo5+vAU6mv0cLbCoDtBz0relncSIpsIbMKH+P+vN8TF5ZAr8j+jEv8W3XNMwWPU045N+YMDdp2SMwIJiTPBCDHn82YnKvJ9WcTF5ZAe18nZqQupF/UICBwpfd52XpeKppFQWU+yZ7m9Irsz2PJ/yI2LPBm95kI3i1dwhN7JlJQmU+SJ5WekWcxL20lyd60hmpZDerh0RuUOJQ9/l08kX0fuRVZtI3swKNtXiPdF+hhdojnbYv9hbyRP4dfp/4RE+K+YLQnlqknLebBbTdy9RenEedNpH/Cz7ip+V+PeH6ripawZd+X3N/y2ZDrN5SsYtRX/at/npr9J6Zm/4mLEkfw51Yzj/h4jW7oUNi1C+67D7KyoEMHeO01aBV4PWo8b5uREVg/ZgxMmQLp6fCPf8CQIe7nXgdOnrMVqW91ec5WamrU52x/LH4oz9mKiIjCVkTECYWtiIgDClsREQcUtiIiDihsRUQcUNiKiDigsBURcUBhKyLigMJWRMQBha2IiAMKWxERBxS2IiIOKGxFRBxQ2IqIOKCwFRFxQGErIuKAwlZExAGFrYiIAwpbEREHFLYiIg4obEVEHFDYiog4oLAVEXFAYSsi4oDCVkTEAYWtiIgDClsREQcUtiIiDihsRUQcUNiKiDigsBURcUBhKyLigMJWRMQBha2IiAPeIyle3xEyVjXUVI4feYmNPYNjX+tNjT0DkSOjK1sREQcUtiIiDihsRUQcUNiKiDigsBURcUBhKyLigMJWRMQBha2IiAMKWxERBxS2IiIOKGxFRBxQ2IqIOKCwFRFxQGErIuKAwlZExAGFrYiIAwpbEREHFLYiIg4obEVEHFDYiog4oLAVEXFAYSsi4oDCVkTEAYWtiIgDClsREQcUtiIiDihsRUQcUNiKiDigsBURcUBhKyLigMJWRMQBha2IiAMKWxERBxS2IiIOKGxFRBw4tsJ28mTIyIDISOjeHd5559D1S5cG6iIjoU0bmDrVzTwbyBP7JtO5IIO0/Eh+WtidFRWHPv9/lz1P34IupOdHk7knjV8XX82Oyuygmqn7HqFnQXua50dx6p4W3FryO4psUfX6SaUPcHbhabTMj6ftnmSuKLqIDf6Pg/Zx/9676VnQnhPyY2i9J5FLis7hvYoVQTUXFv6UxHwTtPyy+Iqj7EjdTGYyGWQQSSTd6c47HLqPj/M4p3AKUUSRSSazmFVr7WxmYzBcyIVB4//jf1zMxZzACRgMM5lZY9t5zGMQg0gmGYNhCUtq1GSTzXCGk0YaMcTQmc48x3OHdd4/SMfT77S19rAXunc//OL6XubMsXi9lmnTLBs2WG64wRITY9m8OXT9119boqMDdRs2BLbzei0vvth451C15DU58uXJ6DnWi9c+HDXNvhu3wY7y3WBjiLHr4jeHrF8Yu8yGEWbvj5xk18Z9bd+MXWk7ebras7xnV9dMi37O+vDZKdGz7Edx39hXYt6yLcNa26t9v6yuOds70D4W9ZRdHrfeLotbZy8I/5lNMan26/hd1TVTo5+xL8cstmvivrIr4j62w32/snHE2c/js6tr+nj62WG+a+1n8VnVy6aE/Dr1Iq9J3Zs/h0AfpzHNbmCDvYFAHzezOWT9ZCbbGGLs8zxvv+IrO5vZNpZYO5/5NWq/4it7AifYvvS1F3BB0LoFLLDjGW//zb9tFFF2BjNqbD+LWfYe7rGzmGUB+zZv16g5l3Ntd7rbd3nXfsVXdgITrMHYpSytUz8a9Xfhx/I73b27PZyyI9pno4Ztz56W664LHmvb1jJuXOj6228PrD9w7Fe/spxxRuO+MLZu4dLd09Ne47suaKxNWFt7S8S4kPV/jnzItjAtg8Yei3rKxhBT/fN1vt/Z3p6zgmpuj/ijbR92aq3z+Dah0IYRZp+PmV9rzeaEPRawL8a8HhS21/l+V+dwra+w7UlPex3XBY21pa0dx7iQ9b3oZW/hlqCxsYy1fegTNFZGme1JTzuTmXYEI2qE7YFLDDEhw3b/kkNOrWEbQ4x9iqeCxlrS0j7EQ3XqR6P+LvxYfqcPM2yPjdsIZWWwejUMHBg8PnAgrFgRepuVK2vWDxoEq1ZBeXnDzLOBlNky1vpX098bfD79vQN5vyL0+Z/u7cMOm8XC8lex1rKrMpd55XM4N/z86pozvGey3r+WDyreBeDbyi0srJgfVHOwIltIJZU0MYm1zvXpfdOII56Oni5B6+aVz+GkPUn0KjiVu/feSqEtPKzzry9llLGa1QwkuI8DGcgKQvdxH/uIJDJoLIoo3ud9yvnufXQnd9Ka1oxgRP1P/ABncib/4l/sYheVVPIKr5BDDgMY0KDHrXfH4e/0sRG2ubng90NqavB4aipkZ4feJjs7dH1FRWB/x5BdNhc/fpLDgs8nJSyVnTb0+ff09uKJ6NmMLh5Gyh4fbQuSsVgmRz9dXTPEdwV3R/0fFxSdRXJ+OJ0KWvGTsI7cG/lgrXMZv/dmOnq60NPTK2j89fL/0CI/lrQ9kUzZ93deil1EygHzvcx3FdOin2N+7NvcGnk388vnck3xpXVpR53lEuhjKsF9TCWVbEL3cRCDeIqn+IAPsFhWsYoneIJyyskl8D56kzd5gReYSsPfP/wX/8JgSCKJCCIYxjBmM5sudPn+jX9IjsPf6WMjbPczJvhna2uOfV99qPFjhCF43hZbY2y/z/wbGLf3Jm6NvJu341bzYszr7KjMZkzJ6Oqa5RVLmVD6FyZETWZJ3Ic8Ez2PZRVLeKD0TyH3eefesbxbsYxZ0XPxGE/Qur7e/vwvbi1vxK7gnPDzuLb4F2RXZlWvHxnxa84JH8Spno4M8V3BU9EvsKRiMR9VfFjXdtTZkfTxbu7mAi6gN70JJ5xLuKT66tWDh1xyGclInuZpEgl9tV+f7uIucsllMYtZxSpu4zau4Ro+4qMGP3aDOI5+p72NPYHDkpQEHk/Nv3g7d9b8S7dfWlroeq8XmjVrmHk2kGYmCQ8edh70JEFO5U6STejz/3vpA3Tz9uSmyNsA6ODpRLSJ4fyivtxVeT8twk7kvr13McR3JddEXAfAqZ6OFFPMzSXXcXvkH/Ga794ed+wdw7yyOcyPfZvWnjY1jhdjYmjjaUsb2nKa9wy6F5zMM2VPcFvk3SHn19XTAw8evqr8ks50q1NfjlQSgT4efBW7k501rnb3iyKKp3iKf/JPdrCD5jRnGtOII44kkvgf/yOLrKCP8ZVUAuDFyyd8QiaZ9TL/r/iKR3mUtaylM50B6Exn3uEdHuVRnuCJejmOE8fh7/SxcWXr8wUe91i0KHh80SLo3Tv0Nr16weLFNet79IDw8IaZZwPxGR9dPN1ZUhF8/ksqFtHTG/r891KCh+Crz/0/W+wha/av329cyc28WPY8r8T+l3ae9oc150oq2Wf31br+k8r1gY/0Yc0Pa3/1wYeP7nRnEcF9XMQielPL+6hKOOG0oAUePMxhDhdyIWGEcRqnsZ71rD3gv4u5mL70ZS1rySCj3uZfQglAyNdsf8AfM47H3+kj+dKt0R/9Cg+3TJ8eeOzjppsCj4ls2hRYP3x4YNlfv/8xkZtvDtRPnx7YvrEfE7F1f/QrnHD7SNR0+27cBjvad5ONIcZ+FL/J5jWxdmj4cDs0fHh1/eNRM6wXr50QNdmuifvKLoxdZrt6etjOnm7VNX+I+JONI84+ET3bro372s6LedNmhJ1kLwq/tLrmV77f2jji7CsxbwU9tvVtQmH1kwe/j7jTLop9166L32zfjl1lh/mutT589p24j2xeE2s/jNtox0fea/8b+4H9KO4b+0LMAtsurL3t5OlqcxMqnD/6FU64nc50u4EN9iYCfdzEJmuxdjjD7XCGV9d/zud2FrPsF3xh3+M9O5ShtilN7Td8U+sxQj2NUEihXcMau4Y1Noooey/32jWsCXrkbBe77BrW2Ld52wJ2OtPtGtbYLLKsJfDEQ1va2r70te/xnt3IxupHv0I9inY4S6P+LvxYfqd/dI9+WWt5/HFLq1YWn8/SrZtl6dLv1vXrF1gOrF+yxNK1a6C+dWvLlCmNO/+qpa6POz0U9bg90bSyPny2s6eb/U/s0qBHq/p4+gXVPxj1D9s+7Cc2iiibatLskPAr7cfx31avz0kot+Mi77FtwtraSCJtumlhf+n7jf0mfnd1DRBy+UPEn2xeE2u3JRTbC8J/ZtNMc+vDZ9NMczvYe7FdFPtu9T7Wx2+xvT1n2UTT1Prw2Yywk+xo301Bz+q6CluLtY/zuG1FoI/d6Bb0jGo/+tl+9Kv+eQMbbBe62CiibDzx9hIusZ/x2SH3Hyps9wfowcsIRlTXzGBGyJo/8afqmi/4wl7KpTaFFBtNtO1EJzuTmXXuRWP/LvwofqcPM2yNtbbG1W5tTI8ellWr6u+y+jiV1/Dfo/zoNclv7Bn8OJjD//WX2vTogV216nu/oTs27tmKiBzjFLYiIg4obEVEHFDYiog4oLAVEXFAYSsi4oDCVkTEAYWtiIgDClsREQcUtiIiDihsRUQcUNiKiDigsBURcUBhKyLigMJWRMQBha2IiAMKWxERBxS2IiIOKGxFRBxQ2IqIOKCwFRFxQGErIuKAwlZExAGFrYiIAwpbEREHFLYiIg4obEVEHFDYiog4oLAVEXFAYSsi4oDCVkTEAYWtiIgDClsREQcUtiIiDihsRUQcMNbawy82JgfY3HDTERE55rSy1iZ/X9ERha2IiNSNbiOIiDigsBURcUBhKyLigMJWRMQBha2IiAMKWxERBxS2IiIOKGxFRBxQ2IqIOPD/bUn9655okNQAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x7f07c1818898>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# obtain the optimal policy and optimal state-value function\n",
    "policy_pi, V_pi = policy_iteration(env)\n",
    "\n",
    "# print the optimal policy\n",
    "print(\"\\nOptimal Policy (LEFT = 0, DOWN = 1, RIGHT = 2, UP = 3):\")\n",
    "print(policy_pi,\"\\n\")\n",
    "\n",
    "plot_values(V_pi)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "运行以下代码单元格以测试你的函数。如果代码单元格返回 **PASSED**，则表明你正确地实现了该函数！ \n",
    "\n",
    "**注意：**为了确保结果准确，确保 `policy_iteratio` 函数满足上文列出的要求（具有三个输入、两个输出，并且没有更改输入参数的默认值）。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "**<span style=\"color: green;\">PASSED</span>**"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "check_test.run_check('policy_iteration_check', policy_iteration)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 第 5 部分：截断策略迭代\n",
    "\n",
    "在此部分，你将自己编写截断策略迭代的实现。  \n",
    "\n",
    "首先，你将实现截断策略评估。你的算法应该有五个**输入**参数：\n",
    "- `env`：这是 OpenAI Gym 环境的实例，其中 `env.P` 会返回一步动态特性。\n",
    "- `policy`：这是一个二维 numpy 数组，其中 `policy.shape[0]` 等于状态数量 (`env.nS`) ， `policy.shape[1]` 等于动作数量 (`env.nA`) 。`policy[s][a]`  返回智能体在状态 `s` 时根据该策略选择动作 `a` 的概率。\n",
    "- `V`：这是一个一维 numpy 数组，其中 `V.shape[0]` 等于状态数量 (`env.nS`)。`V[s]` 包含状态 `s` 的估值。\n",
    "- `max_it`：这是一个正整数，对应的是经历状态空间的次数（默认值为：`1`）。\n",
    "- `gamma`：这是折扣率。它必须是在 0 到 1（含）之间的值，默认值为：`1`。\n",
    "\n",
    "该算法会返回以下**输出结果**：\n",
    "- `V`：这是一个一维 numpy 数组，其中 `V.shape[0]` 等于状态数量 (`env.nS`)。`V[s]` 包含状态 `s` 的估值。\n",
    "\n",
    "请完成以下代码单元格中的函数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [],
   "source": [
    "def truncated_policy_evaluation(env, policy, V, max_it=1, gamma=1):\n",
    "    \n",
    "    ## TODO: complete the function\n",
    "    num_it=0\n",
    "    while num_it < max_it:\n",
    "        for s in range(env.nS):\n",
    "            v = 0\n",
    "            q = q_from_v(env, V, s, gamma)\n",
    "            for a, action_prob in enumerate(policy[s]):\n",
    "                v += action_prob * q[a]\n",
    "            V[s] = v\n",
    "        num_it += 1\n",
    "    return V"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "接着，你将实现截断策略迭代。你的算法应该接受四个**输入**参数：\n",
    "- `env`：这是 OpenAI Gym 环境的实例，其中 `env.P` 会返回一步动态特性。\n",
    "- `max_it`：这是一个正整数，对应的是经历状态空间的次数（默认值为：`1`）。\n",
    "- `gamma`：这是折扣率。它必须是在 0 到 1（含）之间的值，默认值为：`1`。\n",
    "- `theta`：这是一个非常小的正整数，用作停止条件（默认值为：`1e-8`）。\n",
    "\n",
    "该算法会返回以下**输出结果**：\n",
    "- `policy`：这是一个二维 numpy 数组，其中 `policy.shape[0]` 等于状态数量 (`env.nS`) ， `policy.shape[1]` 等于动作数量 (`env.nA`) 。`policy[s][a]`  返回智能体在状态 `s` 时根据该策略选择动作 `a` 的概率。\n",
    "- `V`：这是一个一维 numpy 数组，其中 `V.shape[0]` 等于状态数量 (`env.nS`)。`V[s]` 包含状态 `s` 的估值。\n",
    "\n",
    "请完成以下代码单元格中的函数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [],
   "source": [
    "def truncated_policy_iteration(env, max_it=1, gamma=1, theta=1e-8):\n",
    "    V = np.zeros(env.nS)\n",
    "    policy = np.zeros([env.nS, env.nA]) / env.nA\n",
    "    \n",
    "    ## TODO: complete the function\n",
    "    V = np.zeros(env.nS)\n",
    "    policy = np.zeros([env.nS, env.nA]) / env.nA\n",
    "    while True:\n",
    "        policy = policy_improvement(env, V)\n",
    "        old_V = copy.copy(V)\n",
    "        V = truncated_policy_evaluation(env, policy, V, max_it, gamma)\n",
    "        if max(abs(V-old_V)) < theta:\n",
    "            break;\n",
    "    return policy, V"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "运行下个代码单元格以解决该 MDP 并可视化输出结果。状态值函数已调整形状，以匹配网格世界的形状。\n",
    "\n",
    "请实验不同的 `max_it` 参数值。始终都能获得最优状态值函数吗？"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Optimal Policy (LEFT = 0, DOWN = 1, RIGHT = 2, UP = 3):\n",
      "[[ 1.  0.  0.  0.]\n",
      " [ 0.  0.  0.  1.]\n",
      " [ 0.  0.  0.  1.]\n",
      " [ 0.  0.  0.  1.]\n",
      " [ 1.  0.  0.  0.]\n",
      " [ 1.  0.  0.  0.]\n",
      " [ 1.  0.  0.  0.]\n",
      " [ 1.  0.  0.  0.]\n",
      " [ 0.  0.  0.  1.]\n",
      " [ 0.  1.  0.  0.]\n",
      " [ 1.  0.  0.  0.]\n",
      " [ 1.  0.  0.  0.]\n",
      " [ 1.  0.  0.  0.]\n",
      " [ 0.  0.  1.  0.]\n",
      " [ 0.  1.  0.  0.]\n",
      " [ 1.  0.  0.  0.]] \n",
      "\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAVsAAAFoCAYAAAD5IVjuAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4wLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvpW3flQAAIABJREFUeJzt3Hl4VNX9x/H3yUwme0IgGxGBIBKs7CAKiBRFENdWtKiIYCvFtm5QteDSaqs/awWqVYGCCuICtoKKRVSwQmVxAUFQ3FABgQQSSMhGSDI5vz8mRIZMEEJyIvJ5+dynT8793nvP/c7kkzt3bjHWWkREpGGFNfYERESOBwpbEREHFLYiIg4obEVEHFDYiog4oLAVEXFAYSs/KMaYTcaYAY09j4ZgjBlmjHmzsechjUNhe4wzxpxpjFlhjNljjNltjFlujDmtat1IY8yyI9hXa2OMNcZ46ziX8caY/4UYTzLGlBljOtRlv/XBGDOzag5FByxDG/B4NXpprX3OWjuwoY4pP2wK22OYMSYe+A/wKNAUOAG4F9jXSFN6BuhtjMk4aPwKYL219uNGmNOB/matjT1geaGR5yPHEYXtsa0dgLV2trXWb63da61901q7zhhzCjAV6FV1FZcPYIy5wBizxhhTYIz51hhzzwH7239Vml+1Ta+qbX5pjPnUGJNnjHnDGNMq1GSstVuB/wLDD1p1DfB01b5OMsb81xizyxiTa4x5zhjTJNT+qq5G7zvg558aY7Ye8HO6MWauMSbHGPONMeamw+5c8HGsMaZtqOPuP6Yx5vfGmJ3GmCxjzLUH1EYZYyYaYzZXfbpYZoyJIkQvD/6kYYzpbYz5oGq7D4wxvQ9Yt8QY85eqTyqFxpg3jTFJdTk/+WFQ2B7bvgD8xpinjTGDjTGJ+1dYaz8FrgdWVl3F7Q+0YgLh1wS4APiNMeZnVevOqvrfJlXbrKxadwdwKZAMvAPMPsScnuaAsDXGZAJdDtjGAA8A6cApwInAPUd64saYMOBV4CMCV/TnALcYYwYd6b4OQxqQUHWcXwGPH9DrCUB3oDeBTxe3A5WE6OVB828KLAD+ATQDJgELjDHNDii7CrgWSAF8wK31f2riisL2GGatLQDOBCwwHcgxxsw3xqQeYpsl1tr11tpKa+06AiHY7xCHGQ08YK391FpbAfwf0KW2q1vgJSD1gKu0a4CF1tqcquNvtNYustbuqxqb9D3Hr81pQLK19s/W2jJr7dcEenDFIba51RiTX7XkHsGxyoE/W2vLrbWvAUVAZlXg/xK42Vq7rerTxQpr7eHcxrkA+NJa+4y1tsJaOxv4DLjogJoZ1tovrLV7gX8R+KMlxyiF7TGuKgRHWmtbAB0IXDE+XFu9MeZ0Y8zbVR+99xC4+j3Ux9NWwCP7QwrYTeDq9ARjzB0HfNk0tWo+JcC/gWuMMQYYRtUthKrjpxhj5hhjthljCoBnv+f4h5pX+gHhmU/gCrzWPzTABGttk6rlSI65q+oPzX4lQCyBeUcCXx3p5Am8TpsPGttM4Op5v+wQx5RjlML2R8Ra+xkwk0DoQuCK92DPA/OBE621CQTu65pD1H8LjD4gpJpYa6OqruD+74Avm64/YJungV8A5wJxBL7E2++BquN0stbGA1cfcPyDFQPRB/ycdtC8vjloXnHW2vNr2dehlBziOIeSC5QCJ4VY933/nN52An8wDtQS2HaYx5ZjjML2GGaMaV/1xU2Lqp9PBK4E3q0q2QG0MMb4DtgsDthtrS01xvQkcF9wvxwC9xvbHDA2FRhvjDm16hgJxpjLv2dq7wD5wDRgjrW27KDjFxH44ugE4LZD7GctcL4xpqkxJg245YB17wMFxpg/VH1J5THGdDBVj70dobXAVVX7OI/DvK1hra0EngImVX1Z56n6IiyC0L080GtAO2PMVcYYrwk8hvYTgv8wyY+IwvbYVgicDrxnjCkmELIfA7+vWv9f4BMg+4B7lL8F/myMKQT+SOBeIFB9C+B+YHnVR/MzrLUvAQ8Cc6o+9n8MDD7UpGzgH0meReDKbdZBq+8FugF7CHxBNO8Qu3qGwBdgm4A3gepHtay1fgL3N7sA3xC4ynyCwBdZR+rmqn3lE7jt8fIRbHsrsB74gMAtlgeBsFC9PHAja+0u4EICr9UuAl+sXWitPZJ7yXIMMfrHw0VEGp6ubEVEHFDYiog4oLAVEXFAYSsi4oDCVkTEgSP6p/SaepJsC2/rBpqKiMixZ2vFJnb7c2v7P+ZUO6KwbeFtzfz0VXWflYjIj8zF23scVp1uI4iIOKCwFRFxQGErIuKAwlZExAGFrYiIAwpbEREHFLYiIg4obEVEHFDYiog4oLAVEXFAYSsi4oDCVkTEAYWtiIgDClsREQcUtiIiDihsRUQcUNiKiDigsBURcUBhKyLigMJWRMQBha2IiAMKWxERBxS2IiIOKGxFRBxQ2IqIOKCwFRFxQGErIuKAwlZExAGFrYiIAwpbEREHFLYiIg4obEVEHFDYiog44CxsnymYTN+tGWRuiuSi7d15v/SdQ9a/UvQ852/rwimbozltSxq35FxNTkV29frZhdO5PKsvXbY0pdPmJlyZ3Z8PSpcF7WNWweOct60THTfH03FzPJdm9eK/JQuCam7NGUnGJhO0/Hz7GUE143JH0W/rSbTfHEX3LcmM2nEJG8s+PcqOHDn1sH6oj0dPPTxyTsL2P8Uv8OfdN/PbhDtYkL6GbhG9uXbHYLZVbAlZv6p0OWNzhzMkdgRvpn/CtJSX2Vi+gVtyh1XXvFe6hAtjhvJc6lu8lP4ebbyZjNgxiG/Kv6yuSfO2YFzig7ya/iGvpK+iV+TZjN75Mz4tWxd0vD6RA3i/RVb1MiP1taD1nSJ68FDSTBanf8rTqW9gsVy9YwDltrweu3Ro6mH9UB+PnnpYN8Zae9jFnSJ62Pnpq474ID/bfjrtfZ34a9L06rH+W09mcMxl3J74QI36aXsm8HTBoyw/cXP12L8LZ3DP7hv5pFVRyGNYa+n5bXN+1+RORsbfWOtcumxpyu2JD3BV3Ggg8JcwrzKXJ1P/c9jn82nZOs7f3pnFJ3zGSeGZh73d0VAP64f6ePTUw2AXb+/Bun2rzPfVNfiVbZkt4+Oy1fSNGhg0fmbUQFaXrgi5TY+IPuT4s1hc8irWWnb7c3m1eA4/jTq/9uNQxj5bSkJYYsj1fuvn1aI5lFQW0S2id9C6D0qX0WNLCv23tmNc7ihy/TtrPU5JZTEvFs0g3dOSFt7WtdbVJ/WwfqiPR089rDtvg+4dyPPn4sdPkic1aDzZk8py/+KQ23SL7MUjybMZkzOMUruXCio4M/JcJiY9XetxJubdRUxYLAOiLw4a/6xsPUOyerHPlhJtYpma8hLtfR2r1/eLOo9BMZdyojeDrRWbmJh3F8Oyz2Z++moiTER13TMFk/lr3u2U2GLaeDN5Lu2toPUNST2sH+rj0VMP687ZF2SG4Ktsi60xtt+XZRu4d/dN3NDkbuanr2Zm6uvk+LO5Y9fokPUzCh5hduE/mZIyj7iw+KB1bcIzWZC+lnnN3+Xq+N9wa+4IPi/7uHr9RbFXcG70xbT3dWRA9EXMTF3I1+Wf8/ZBN94viR3Gf9LXMCdtKRnh7fhdzuXsrSypSyvqTD2sH+rj0VMPj1yDX9kmepLw4CHHnx00nuvfWeOv436T9zxA54iejE64DYBT6ER0sxh+kd2XWxPvJ917YnXtjIJHmJh3FzNSF9IlomeNffmMj9bhbYHAjfF1+z7gqYK/82DSkyGPnepNJ83bgk0VXwaNx4clEB+WQEb4yXSNOIMuWxJZWDKXS2OHH34z6kg9rB/q49FTD+uuwa9sfcZHB193lu1dFDS+bO8iukf2DrlNqS0hDE/QmKfqZ8t3X+g9sWcSE/Lu5MnUBZwWeeZhzaeSSvbZfbWu3+3PZUfFNpI9zWutsVX/lR1iP/VJPawf6uPRUw/rrsGvbAGuSxjL2JzhdI7oSY+IPjxXOJWd/u1cFXc9AGNzrgFgUvIsAM6Juojxu0bxbMEUzooaxE5/Fn/ZfQsdfN04wdsSgH/ueYiJeXcyKflZ2njbVT+zFxEWRXxYAgAP7h5H/+gLSPecSJEtZH7x87xbuoSnUgIfKYori3g4/x4GRw8hxdOcrRWb+Fv+eJp5UhgU/XMANpVv5PWSufSJHEBTTzLZFVuZsuev+EwE50Rd6KJ96mE9Uh/Vw8bqoZOwvTBmKHn+XTyWfx85/iza+TrwVOprtPC2AmD7Qc/nXRY3kiJbyKzCx7g/7/fEhSXQK7I/4xL/Vl3zTMHjlFPOjTlDg7YdEjOCCckzAcjxZzMm52py/dnEhSXQ3teJGakL6Rc1CAj8df28bD0vFc2ioDKfZE9zekX257HkfxEbFgeAz0TwbukSntgzkYLKfJI8qfSMPIt5aStJ9qY1VMtqUA/rh/p49NTDunHynK2IyI/VD+Y5WxERUdiKiDihsBURcUBhKyLigMJWRMQBha2IiAMKWxERBxS2IiIOKGxFRBxQ2IqIOKCwFRFxQGErIuKAwlZExAGFrYiIAwpbEREHFLYiIg4obEVEHFDYiog4oLAVEXFAYSsi4oDCVkTEAYWtiIgDClsREQcUtiIiDihsRUQcUNiKiDigsBURcUBhKyLigMJWRMQBha2IiAMKWxERBxS2IiIOKGxFRBxQ2IqIOKCwFRFxwNvYEzgeZXzT2DM49v19TGPP4MdhzN8bewY/Aj0Or0xXtiIiDihsRUQcUNiKiDigsBURcUBhKyLigMJWRMQBha2IiAMKWxERBxS2IiIOKGxFRBxQ2IqIOKCwFRFxQGErIuKAwlZExAGFrYiIAwpbEREHFLYiIg4obEVEHFDYiog4oLAVEXFAYSsi4oDCVkTEAYWtiIgDClsREQcUtiIiDihsRUQcUNiKiDigsBURcUBhKyLigMJWRMQBha2IiAMKWxERBxS2IiIOKGxFRBxQ2IqIOOAsbJ8pmEzfrRlkborkou3deb/0nUPWv1L0POdv68Ipm6M5bUsat+RcTU5FdvX62YXTuTyrL122NKXT5iZcmd2fD0qXBe1jVsHjnLetEx03x9NxczyXZvXivyULgmpuzRlJxiYTtPx8+xlBNeNyR9Fv60m03xxF9y3JjNpxCRvLPj3KjjSiyZMhIwMiI6F7d3jn0K8FS5cG6iIjoU0bmDrVzTwbyLKPJvOXpzK47dFIJj7fna+21X7+G79dwpiHTY1lx+7PqmtWrp/OP/7VlzunNGX85CY8/mJ/vt4W/F4sLSvkpSW38OcnW3H7o1E88kJvtmR/UOtxX1j8a8Y8bHh79YSg8RXrp/H4i/0ZP7kJYx427N6zqW5N+KE4jt6LTsL2P8Uv8OfdN/PbhDtYkL6GbhG9uXbHYLZVbAlZv6p0OWNzhzMkdgRvpn/CtJSX2Vi+gVtyh1XXvFe6hAtjhvJc6lu8lP4ebbyZjNgxiG/Kv6yuSfO2YFzig7ya/iGvpK+iV+TZjN75Mz4tWxd0vD6RA3i/RVb1MiP1taD1nSJ68FDSTBanf8rTqW9gsVy9YwDltrweu+TICy/AzTfDHXfAmjXQuzcMHgxbQr8WfPMNnH9+oG7NGhg/Hm68EebOdTvverLm8xd4aenNDDjtDm4dtobWzXsz7eXB5BXUcv5V/jD8E+4dlVW9JDc5uXrdxq1L6NpuKL8Z8hZjrniP5MRM/vnSIHLyvnsvvrDoOj7b/AZXDXya24avJ7PlQKbMG0B+0bYax1r75Yt8u+MDEmLSa6wrLy8hs+VAzjvjnro34YfiOHsvOgnbJ/ZMYkjsSK6MG0Vb3ync2+xRUjzNea5wSsj6D/etJM3Tgl8ljOHE8Ay6Rp7BiLgbWbvvveqah5OfY0T8DZwa0ZWTwjO5r9kUYkwcS/e+Xl0zMPoSfho9mNbhbWkT3o7bEu8nJiyONftWBh0vwkSQ7E2rXpp4mgatvypuND0j+9IivDUdIrrx+8T72OHfzpaKr+uxS45MmgQjR8KoUXDKKfDoo9C8OUwJ/VowdSqkpwfqTjklsN2IETBhQuj6H7glH06i509G0qvjKFKbnsKQ/o8SH9Oc5etqOf8qsdEpxMekVS9hYZ7qdcMHP0ffLjfQIqUrKU0zufzsKUT44vh0c+C9WFaxl3Ub53LhmX+l7Yk/JblJW87rdQ9JTdqy4qDj7i7YzMtLbmb44OcJCwuvMY9+3W5hQM/xZJxwZj10o5EdZ+/FBg/bMlvGx2Wr6Rs1MGj8zKiBrC5dEXKbHhF9yPFnsbjkVay17Pbn8mrxHH4adX7tx6GMfbaUhLDEkOv91s+rRXMoqSyiW0TvoHUflC6jx5YU+m9tx7jcUeT6d9Z6nJLKYl4smkG6pyUtvK1rrftBKiuD1athYPBrwcCBsCL0a8HKlTXrBw2CVaug/Ni6sq/wl7F152oyWwafT2bLgWzKquX8q0x6vgd/nNacyXPP4ctv3z5krd9fRnlFKdERgfdiZWUFldZPuCcyqC7cGxV0u8FfWcEzC6/k3J53kdr0lCM5tWPPcfhebPCwzfPn4sdPkic1aDzZk0qOPzvkNt0ie/FI8mzG5Ayj3WYf3b9NxmKZmPR0rceZmHcXMWGxDIi+OGj8s7L1nLo5lszNEdy563qmprxEe1/H6vX9os5jYvIsnk17izubTuSjfe8zLPts9tl9Qft5pmAyp26O5dQtsSwpWchzaW8RYSKOtB2NKzcX/H5IDX4tSE2F7NCvBdnZoesrKgL7O4YU782l0vqJiw4+n7joVApKQp9/fExzLjt7CtdeOJdfXjiPlMRMpsw9h6+2/q/W47y28i4ifLF0aBN4L0b64mjdvBdvvn8f+UXbqKz0s+rTZ9mUtZKCkqzq7V5f+SeiI5vRp/Nv6uFsf+COw/ei19WBDCboZ4utMbbfl2UbuHf3TdzQ5G7OihrETn8WD+y+jTt2jWZS8qwa9TMKHmF24T95Jm0xcWHxQevahGeyIH0tBZX5vF4yl1tzRzA7bQmZvg4AXBR7RXVte19HOvq6c+bWVrxdsoDzYi6tXndJ7DDOjDqXnf4spu+ZwO9yLufFtOVEhUXXuSeNxhzUd2trjn1ffajxY4U5/PdiStNMUppmVv/cOr0Xuws28faHEzipxVk16peueYQV6//Jby5dTGTEd+/FYYOeYc6iX3LvEy0IMx5apHSjW+aVbN35IQAbty7lgw0zuXXY2vo4w2PHcfRebPCwTfQk4cFT4yo217+zxtXufpP3PEDniJ6MTrgNgFPoRHSzGH6R3ZdbE+8n3Xtide2MgkeYmHcXM1IX0iWiZ419+YyP1uFtgcAXXev2fcBTBX/nwaQnQx471ZtOmrcFmyq+DBqPD0sgPiyBjPCT6RpxBl22JLKwZC6Xxg4//GY0tqQk8HhqXjns3FnzimG/tLTQ9V4vNGvWMPNsIDFRSYQZD4XFwedTVLKzxtXuobRMO501n8+pMb50zSMsXHEXv/7ZQlqlBb8Xk5qcxA2XL2VfeTGlZQUkxDTn6QVDaRqfAcDGb9+moDiLP01vXr1NpfXz6rI/sHTNw9xz3dYjOdUfvuPwvdjgtxF8xkcHX3eW7V0UNL5s7yK6R/YOuU2pLSEMT9CYp+pni60ee2LPJCbk3cmTqQs4LfLwvjCopLLGLYID7fbnsqNiG8me5rXW2Kr/yg6xnx8kny/w2Myi4NeCRYsC3/CG0qsXLF5cs75HDwiv+QXOD5nX46NFSnc+3xJ8/l9sWUTr5rWcfwjbc9YSHxP8/ljy4SReW3Enoy5ZQJtDfHkVER5DQkxzSkrz+GzzG3Q46RIA+nT+LbddvY5bh62tXhJi0unXdQy/vfStIzjLY8Rx+F50chvhuoSxjM0ZTueInvSI6MNzhVPZ6d/OVXHXAzA25xqA6lsE50RdxPhdo3i2YEr1bYS/7L6FDr5unOBtCcA/9zzExLw7mZT8LG287aqfwY0IiyI+LAGAB3ePo3/0BaR7TqTIFjK/+HneLV3CUymBZ22LK4t4OP8eBkcPIcXTnK0Vm/hb/niaeVIYFP1zADaVb+T1krn0iRxAU08y2RVbmbLnr/hMBOdEXeiiffVr7FgYPhx69oQ+fQLf8G7fDtcHXguuCbwWzKq6XXP99fDYY3DLLTB6NCxfDjNnwuzZjTL9o/XTbmN57o3htErrSUZ6H5avm8qe4u307hQ4/+feCJz/sEGB81/64cM0jW9NWrNTqagsY/Wnz7L+q5e59sLvHjf676qHeG3FnQw771mSE9tRUHXlHO6NIioi8F78bNMbWFtJStP25OZvZP47t5GSmMnpP7kWgLjoFOKiU4LmGhYWTnxMWtBtjILibAqLs8nJ+wKA7N0b2LsvnybxLYmJDH6K5gfvOHsvOgnbC2OGkuffxWP595Hjz6KdrwNPpb5GC28rALYf9LztZXEjKbKFzCp8jPvzfk9cWAK9IvszLvFv1TXPFDxOOeXcmDM0aNshMSOYkDwTgBx/NmNyribXn01cWALtfZ2YkbqQflGDgMDV8udl63mpaBYFlfkke5rTK7I/jyX/i9iwOAB8JoJ3S5fwxJ6JFFTmk+RJpWfkWcxLW0myN62hWtZwhg6FXbvgvvsgKws6dIDXXoNWgdeixjOOGRmB9WPGBB7JSU+Hf/wDhgxxP/d60DVzKMWlu3jzvfsoKMmiebMO/PqS12gaHzj/g5+3ragsY/47t7KnaBvh3ihSm53KqEsW8JOM756MWfbR4/gry5n1WvB78bRTRnDVoJkA7C3bw4Ll48kv2kp0RFM6nzyE83vfj8dzZFdkK9ZN5Y337q3+eforFwBw5bkz6HnqyCPaV6M7zt6Lxlr7/VVVOkX0sPPTVzXgdI4PGd809gyOfX8f09gz+HEY8/fGnsGPQI8e2FWrvvcbOv3bCCIiDihsRUQcUNiKiDigsBURcUBhKyLigMJWRMQBha2IiAMKWxERBxS2IiIOKGxFRBxQ2IqIOKCwFRFxQGErIuKAwlZExAGFrYiIAwpbEREHFLYiIg4obEVEHFDYiog4oLAVEXFAYSsi4oDCVkTEAYWtiIgDClsREQcUtiIiDihsRUQcUNiKiDigsBURcUBhKyLigMJWRMQBha2IiAMKWxERBxS2IiIOKGxFRBzwNvYEjkffZDT2DI59+U0aewYiR0ZXtiIiDihsRUQcUNiKiDigsBURcUBhKyLigMJWRMQBha2IiAMKWxERBxS2IiIOKGxFRBxQ2IqIOKCwFRFxQGErIuKAwlZExAGFrYiIAwpbEREHFLYiIg4obEVEHFDYiog4oLAVEXFAYSsi4oDCVkTEAYWtiIgDClsREQcUtiIiDihsRUQcUNiKiDigsBURcUBhKyLigMJWRMQBha2IiAMKWxERBxS2IiIOKGxFRBxQ2IqIOOAsbJ8pmEzfrRlkborkou3deb/0nUPWv1L0POdv68Ipm6M5bUsat+RcTU5FdvX62YXTuTyrL122NKXT5iZcmd2fD0qXBe1jVsHjnLetEx03x9NxczyXZvXivyULgmpuzRlJxiYTtPx8+xlBNeNyR9Fv60m03xxF9y3JjNpxCRvLPj3Kjhw59fDo/St3MhdsyOD0jyK56vPufFhUew//uHkkXdeaGkuvdTFBdeWVZUzO+iMXbMig50cRDP6kJc/n/CPkPhfmzabrWsNNX18YNH7+J61DHuvGry+orlld9D9u/vpiBn5yAl3XGubvmln3RvxQTJ4MGRkQGQndu8M7h35Ps3RpoC4yEtq0galT3cyzHjgJ2/8Uv8Cfd9/MbxPuYEH6GrpF9ObaHYPZVrElZP2q0uWMzR3OkNgRvJn+CdNSXmZj+QZuyR1WXfNe6RIujBnKc6lv8VL6e7TxZjJixyC+Kf+yuibN24JxiQ/yavqHvJK+il6RZzN658/4tGxd0PH6RA7g/RZZ1cuM1NeC1neK6MFDSTNZnP4pT6e+gcVy9Y4BlNvyeuzSoamHR++NvBd4aOvN/Cr1DmZnrqFTTG9u+HowWWWhe3hbi0dYdGpW0NLC14aBTX4RVDdu85WsKHydu0+cxsvtP+dvrf9Nu8hONfa3dd/XPLz9NrrG9K2x7tnMD4KOM7vdhxgM5x5wrJLKItpGduC2Ex4h0kQdZTd+AF54AW6+Ge64A9asgd69YfBg2BL69eCbb+D88wN1a9bA+PFw440wd67bedeRsdYednGniB52fvqqIz7Iz7afTntfJ/6aNL16rP/Wkxkccxm3Jz5Qo37angk8XfAoy0/cXD3278IZ3LP7Rj5pVRTyGNZaen7bnN81uZOR8TfWOpcuW5pye+IDXBU3GghcleVV5vJk6n8O+3w+LVvH+ds7s/iEzzgpPPOwtzsa6mGw/CZHvAnDvzidkyM78ceW3/Xw4g0nM6DJZdyUXrOHB1tbtJxrN57JjJOX0yWmNwArC97k9k2XM/8nX5HoTap123Jbzi+/PJPLk37LqsK3yffn8o82tffriez7eXrnQ7zZYTtRYdE11vdeF8u4Ex7j4mYjv3feh9J1zVFtfnROPx06dYLp370enHwyXHYZPBDi9fjDH2DePPjyu4sBrrsOPvkEVq5s+PnWpkcP7KpV5vvKGvzKtsyW8XHZavpGDQwaPzNqIKtLV4TcpkdEH3L8WSwueRVrLbv9ubxaPIefRp1f+3EoY58tJSEsMeR6v/XzatEcSiqL6BbRO2jdB6XL6LElhf5b2zEudxS5/p21HqekspgXi2aQ7mlJC2/rWuvqk3p49Mory/i0ZDW94oN72Ct+IB8Vh+7hwebtms5JkadWBy3A23te5ifRp/HszkkM+qQFF284mQe33kSJP/gP2uNZd5Lua83FTUd873Gstby8+0kuaHp1yKD9USgrg9WrYWDw68HAgbCiltdj5cqa9YMGwapVUO7uE1JdeRv6AHn+XPz4SfKkBo0ne1JZ7l8ccptukb14JHk2Y3KGUWr3UkEFZ0aey8Skp2s9zsS8u4gJi2VA9MVB45+VrWdIVi/22VKiTSxTU16iva9j9fp+UecxKOZSTvRmsLViExPz7mJY9tnMT19NhImornumYDJ/zbudEltMG28mz6W9FbS+IamHR2/brScoAAASvElEQVR/D5t6g3vY1JvKrorQPTxQoX8Pi/b8mxub/1/Q+Layr1lbvAxfWAQTWs+l0J/Pg9tuJKd8OxMyXgQCV79v5L3AC5lrD2uu7xYuYlvZN/y86XWHeXbHoNxc8PshNfj1IDUVFtfyemRnw4ABNesrKgL7a968YeZaT5x9QWYIvsq22Bpj+31ZtoF7d9/EDU3uZn76amamvk6OP5s7do0OWT+j4BFmF/6TKSnziAuLD1rXJjyTBelrmdf8Xa6O/w235o7g87KPq9dfFHsF50ZfTHtfRwZEX8TM1IV8Xf45bx/0JdAlscP4T/oa5qQtJSO8Hb/LuZy9lSV1aUWdqYdHr2a/au/hgV7b/SyV1s8FicODxiupxGD4v1bP0zHmdHrHD2LcCY/x1p657CrfQV5FLn/cMpK/tHyaeG/oTwwHm7drOqdGn0ZmdJfDPa1jlzmo99bWHPu++lDjP0ANfmWb6EnCg4ccf3bQeK5/Z40rtf0m73mAzhE9GZ1wGwCn0InoZjH8IrsvtybeT7r3xOraGQWPMDHvLmakLqRLRM8a+/IZH63D2wKBL2nW7fuApwr+zoNJT4Y8dqo3nTRvCzZVfBk0Hh+WQHxYAhnhJ9M14gy6bElkYclcLo0dHnI/9Uk9PHr7e7irIriHuyt21rjaDWXerumc02QICd6mQeNJ3uakhJ9AnCeheiwj8hQAssu3sNdfTG5FFtd/9d0VWSWVAPRY6+XF9p/QOvK7e9a7y3eypOAVxrd4/MhP8liSlAQeT+Bq9UA7d9a82t0vLS10vdcLzZo1zDzrUYNf2fqMjw6+7izbuyhofNneRXSP7B1ym1JbQhieoDFP1c+W777Qe2LPJCbk3cmTqQs4LfLMw5pPJZXss/tqXb/bn8uOim0ke2r/SGKr/is7xH7qk3p49MLDfJwS3Z13C4N7+G7hIjrHhO7hfh8Xv88XpR9xadNRNdZ1ielDTvn2oHu0m/d9AUDz8FacGn0a/85cz5zMtdVLv/iL6RrTlzmZaznBlxG0v/m7Z+IzEQxqckVdT/XY4PMFHuFaFPx6sGhR4GmDUHr1qnmLYdEi6NEDwsMbZp71qMGvbAGuSxjL2JzhdI7oSY+IPjxXOJWd/u1cFXc9AGNzrgFgUvIsAM6Juojxu0bxbMEUzooaxE5/Fn/ZfQsdfN04wdsSgH/ueYiJeXcyKflZ2njbVT8/GhEWRXxY4Crjwd3j6B99AemeEymyhcwvfp53S5fwVErg421xZREP59/D4OghpHias7ViE3/LH08zTwqDon8OwKbyjbxeMpc+kQNo6kkmu2IrU/b8FZ+J4Jyo4Gcl1cMfdg+vTh7LXVuGc2p0T7rE9OHF3KnklG/nsqRAD+/aHOjhfa1mBW03d9c0WkacTPfYfjX2OTjxKqbv+At/2nIt16fdQ6E/n4e23cyAhMtoGp4CQNuoDkHbxHma4Keixri1lpd2P8GgJlcQ44mrcawSfxHf7ttYVVtJVvkWPi9ZS7y3Kc19LevYlUY0diwMHw49e0KfPoFnZrdvh+sDrwfXBF4PZlW9HtdfD489BrfcAqNHw/LlMHMmzJ7dKNM/Uk7C9sKYoeT5d/FY/n3k+LNo5+vAU6mv0cLbCoDtBz0relncSIpsIbMKH+P+vN8TF5ZAr8j+jEv8W3XNMwWPU045N+YMDdp2SMwIJiTPBCDHn82YnKvJ9WcTF5ZAe18nZqQupF/UICBwpfd52XpeKppFQWU+yZ7m9Irsz2PJ/yI2LPBm95kI3i1dwhN7JlJQmU+SJ5WekWcxL20lyd60hmpZDerh0RuUOJQ9/l08kX0fuRVZtI3swKNtXiPdF+hhdojnbYv9hbyRP4dfp/4RE+K+YLQnlqknLebBbTdy9RenEedNpH/Cz7ip+V+PeH6ripawZd+X3N/y2ZDrN5SsYtRX/at/npr9J6Zm/4mLEkfw51Yzj/h4jW7oUNi1C+67D7KyoEMHeO01aBV4PWo8b5uREVg/ZgxMmQLp6fCPf8CQIe7nXgdOnrMVqW91ec5WamrU52x/LH4oz9mKiIjCVkTECYWtiIgDClsREQcUtiIiDihsRUQcUNiKiDigsBURcUBhKyLigMJWRMQBha2IiAMKWxERBxS2IiIOKGxFRBxQ2IqIOKCwFRFxQGErIuKAwlZExAGFrYiIAwpbEREHFLYiIg4obEVEHFDYiog4oLAVEXFAYSsi4oDCVkTEAYWtiIgDClsREQcUtiIiDihsRUQcUNiKiDigsBURcUBhKyLigMJWRMQBha2IiAPeIyle3xEyVjXUVI4feYmNPYNjX+tNjT0DkSOjK1sREQcUtiIiDihsRUQcUNiKiDigsBURcUBhKyLigMJWRMQBha2IiAMKWxERBxS2IiIOKGxFRBxQ2IqIOKCwFRFxQGErIuKAwlZExAGFrYiIAwpbEREHFLYiIg4obEVEHFDYiog4oLAVEXFAYSsi4oDCVkTEAYWtiIgDClsREQcUtiIiDihsRUQcUNiKiDigsBURcUBhKyLigMJWRMQBha2IiAMKWxERBxS2IiIOKGxFRBw4tsJ28mTIyIDISOjeHd5559D1S5cG6iIjoU0bmDrVzTwbyBP7JtO5IIO0/Eh+WtidFRWHPv9/lz1P34IupOdHk7knjV8XX82Oyuygmqn7HqFnQXua50dx6p4W3FryO4psUfX6SaUPcHbhabTMj6ftnmSuKLqIDf6Pg/Zx/9676VnQnhPyY2i9J5FLis7hvYoVQTUXFv6UxHwTtPyy+Iqj7EjdTGYyGWQQSSTd6c47HLqPj/M4p3AKUUSRSSazmFVr7WxmYzBcyIVB4//jf1zMxZzACRgMM5lZY9t5zGMQg0gmGYNhCUtq1GSTzXCGk0YaMcTQmc48x3OHdd4/SMfT77S19rAXunc//OL6XubMsXi9lmnTLBs2WG64wRITY9m8OXT9119boqMDdRs2BLbzei0vvth451C15DU58uXJ6DnWi9c+HDXNvhu3wY7y3WBjiLHr4jeHrF8Yu8yGEWbvj5xk18Z9bd+MXWk7ebras7xnV9dMi37O+vDZKdGz7Edx39hXYt6yLcNa26t9v6yuOds70D4W9ZRdHrfeLotbZy8I/5lNMan26/hd1TVTo5+xL8cstmvivrIr4j62w32/snHE2c/js6tr+nj62WG+a+1n8VnVy6aE/Dr1Iq9J3Zs/h0AfpzHNbmCDvYFAHzezOWT9ZCbbGGLs8zxvv+IrO5vZNpZYO5/5NWq/4it7AifYvvS1F3BB0LoFLLDjGW//zb9tFFF2BjNqbD+LWfYe7rGzmGUB+zZv16g5l3Ntd7rbd3nXfsVXdgITrMHYpSytUz8a9Xfhx/I73b27PZyyI9pno4Ztz56W664LHmvb1jJuXOj6228PrD9w7Fe/spxxRuO+MLZu4dLd09Ne47suaKxNWFt7S8S4kPV/jnzItjAtg8Yei3rKxhBT/fN1vt/Z3p6zgmpuj/ijbR92aq3z+Dah0IYRZp+PmV9rzeaEPRawL8a8HhS21/l+V+dwra+w7UlPex3XBY21pa0dx7iQ9b3oZW/hlqCxsYy1fegTNFZGme1JTzuTmXYEI2qE7YFLDDEhw3b/kkNOrWEbQ4x9iqeCxlrS0j7EQ3XqR6P+LvxYfqcPM2yPjdsIZWWwejUMHBg8PnAgrFgRepuVK2vWDxoEq1ZBeXnDzLOBlNky1vpX098bfD79vQN5vyL0+Z/u7cMOm8XC8lex1rKrMpd55XM4N/z86pozvGey3r+WDyreBeDbyi0srJgfVHOwIltIJZU0MYm1zvXpfdOII56Oni5B6+aVz+GkPUn0KjiVu/feSqEtPKzzry9llLGa1QwkuI8DGcgKQvdxH/uIJDJoLIoo3ud9yvnufXQnd9Ka1oxgRP1P/ABncib/4l/sYheVVPIKr5BDDgMY0KDHrXfH4e/0sRG2ubng90NqavB4aipkZ4feJjs7dH1FRWB/x5BdNhc/fpLDgs8nJSyVnTb0+ff09uKJ6NmMLh5Gyh4fbQuSsVgmRz9dXTPEdwV3R/0fFxSdRXJ+OJ0KWvGTsI7cG/lgrXMZv/dmOnq60NPTK2j89fL/0CI/lrQ9kUzZ93deil1EygHzvcx3FdOin2N+7NvcGnk388vnck3xpXVpR53lEuhjKsF9TCWVbEL3cRCDeIqn+IAPsFhWsYoneIJyyskl8D56kzd5gReYSsPfP/wX/8JgSCKJCCIYxjBmM5sudPn+jX9IjsPf6WMjbPczJvhna2uOfV99qPFjhCF43hZbY2y/z/wbGLf3Jm6NvJu341bzYszr7KjMZkzJ6Oqa5RVLmVD6FyZETWZJ3Ic8Ez2PZRVLeKD0TyH3eefesbxbsYxZ0XPxGE/Qur7e/vwvbi1vxK7gnPDzuLb4F2RXZlWvHxnxa84JH8Spno4M8V3BU9EvsKRiMR9VfFjXdtTZkfTxbu7mAi6gN70JJ5xLuKT66tWDh1xyGclInuZpEgl9tV+f7uIucsllMYtZxSpu4zau4Ro+4qMGP3aDOI5+p72NPYHDkpQEHk/Nv3g7d9b8S7dfWlroeq8XmjVrmHk2kGYmCQ8edh70JEFO5U6STejz/3vpA3Tz9uSmyNsA6ODpRLSJ4fyivtxVeT8twk7kvr13McR3JddEXAfAqZ6OFFPMzSXXcXvkH/Ga794ed+wdw7yyOcyPfZvWnjY1jhdjYmjjaUsb2nKa9wy6F5zMM2VPcFvk3SHn19XTAw8evqr8ks50q1NfjlQSgT4efBW7k501rnb3iyKKp3iKf/JPdrCD5jRnGtOII44kkvgf/yOLrKCP8ZVUAuDFyyd8QiaZ9TL/r/iKR3mUtaylM50B6Exn3uEdHuVRnuCJejmOE8fh7/SxcWXr8wUe91i0KHh80SLo3Tv0Nr16weLFNet79IDw8IaZZwPxGR9dPN1ZUhF8/ksqFtHTG/r891KCh+Crz/0/W+wha/av329cyc28WPY8r8T+l3ae9oc150oq2Wf31br+k8r1gY/0Yc0Pa3/1wYeP7nRnEcF9XMQielPL+6hKOOG0oAUePMxhDhdyIWGEcRqnsZ71rD3gv4u5mL70ZS1rySCj3uZfQglAyNdsf8AfM47H3+kj+dKt0R/9Cg+3TJ8eeOzjppsCj4ls2hRYP3x4YNlfv/8xkZtvDtRPnx7YvrEfE7F1f/QrnHD7SNR0+27cBjvad5ONIcZ+FL/J5jWxdmj4cDs0fHh1/eNRM6wXr50QNdmuifvKLoxdZrt6etjOnm7VNX+I+JONI84+ET3bro372s6LedNmhJ1kLwq/tLrmV77f2jji7CsxbwU9tvVtQmH1kwe/j7jTLop9166L32zfjl1lh/mutT589p24j2xeE2s/jNtox0fea/8b+4H9KO4b+0LMAtsurL3t5OlqcxMqnD/6FU64nc50u4EN9iYCfdzEJmuxdjjD7XCGV9d/zud2FrPsF3xh3+M9O5ShtilN7Td8U+sxQj2NUEihXcMau4Y1Noooey/32jWsCXrkbBe77BrW2Ld52wJ2OtPtGtbYLLKsJfDEQ1va2r70te/xnt3IxupHv0I9inY4S6P+LvxYfqd/dI9+WWt5/HFLq1YWn8/SrZtl6dLv1vXrF1gOrF+yxNK1a6C+dWvLlCmNO/+qpa6POz0U9bg90bSyPny2s6eb/U/s0qBHq/p4+gXVPxj1D9s+7Cc2iiibatLskPAr7cfx31avz0kot+Mi77FtwtraSCJtumlhf+n7jf0mfnd1DRBy+UPEn2xeE2u3JRTbC8J/ZtNMc+vDZ9NMczvYe7FdFPtu9T7Wx2+xvT1n2UTT1Prw2Yywk+xo301Bz+q6CluLtY/zuG1FoI/d6Bb0jGo/+tl+9Kv+eQMbbBe62CiibDzx9hIusZ/x2SH3Hyps9wfowcsIRlTXzGBGyJo/8afqmi/4wl7KpTaFFBtNtO1EJzuTmXXuRWP/LvwofqcPM2yNtbbG1W5tTI8ellWr6u+y+jiV1/Dfo/zoNclv7Bn8OJjD//WX2vTogV216nu/oTs27tmKiBzjFLYiIg4obEVEHFDYiog4oLAVEXFAYSsi4oDCVkTEAYWtiIgDClsREQcUtiIiDihsRUQcUNiKiDigsBURcUBhKyLigMJWRMQBha2IiAMKWxERBxS2IiIOKGxFRBxQ2IqIOKCwFRFxQGErIuKAwlZExAGFrYiIAwpbEREHFLYiIg4obEVEHFDYiog4oLAVEXFAYSsi4oDCVkTEAYWtiIgDClsREQcUtiIiDihsRUQcMNbawy82JgfY3HDTERE55rSy1iZ/X9ERha2IiNSNbiOIiDigsBURcUBhKyLigMJWRMQBha2IiAMKWxERBxS2IiIOKGxFRBxQ2IqIOPD/bUn9655okNQAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x7f07c17adf98>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "policy_tpi, V_tpi = truncated_policy_iteration(env, max_it=2)\n",
    "\n",
    "# print the optimal policy\n",
    "print(\"\\nOptimal Policy (LEFT = 0, DOWN = 1, RIGHT = 2, UP = 3):\")\n",
    "print(policy_tpi,\"\\n\")\n",
    "\n",
    "# plot the optimal state-value function\n",
    "plot_values(V_tpi)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "运行以下代码单元格以测试你的函数。如果代码单元格返回 **PASSED**，则表明你正确地实现了该函数！ \n",
    "\n",
    "**注意：**为了确保结果准确，确保 `truncated_policy_iteration` 函数满足上文列出的要求（具有四个输入、两个输出，并且没有更改输入参数的默认值）。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "**<span style=\"color: green;\">PASSED</span>**"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "check_test.run_check('truncated_policy_iteration_check', truncated_policy_iteration)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 第 6 部分：值迭代\n",
    "\n",
    "在此部分，你将自己编写值迭代的实现。\n",
    "\n",
    "你的算法应该接受三个输入参数：\n",
    "- `env`：这是 OpenAI Gym 环境的实例，其中 `env.P` 会返回一步动态特性。\n",
    "- `gamma`：这是折扣率。它必须是在 0 到 1（含）之间的值，默认值为：`1`。 \n",
    "- `theta`：这是一个非常小的正整数，用作停止条件（默认值为：`1e-8`）。\n",
    "\n",
    "该算法会返回以下**输出结果**：\n",
    "- `policy`：这是一个二维 numpy 数组，其中 `policy.shape[0]` 等于状态数量 (`env.nS`) ， `policy.shape[1]` 等于动作数量 (`env.nA`) 。`policy[s][a]`  返回智能体在状态 `s` 时根据该策略选择动作 `a` 的概率。\n",
    "- `V`：这是一个一维 numpy 数组，其中 `V.shape[0]` 等于状态数量 (`env.nS`)。`V[s]` 包含状态 `s` 的估值。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [],
   "source": [
    "def value_iteration(env, gamma=1, theta=1e-8):\n",
    "    V = np.zeros(env.nS)\n",
    "    \n",
    "    ## TODO: complete the function\n",
    "    while True:\n",
    "        delta = 0\n",
    "        for s in range(env.nS):\n",
    "            v = V[s]\n",
    "            V[s] = max(q_from_v(env, V, s, gamma))\n",
    "            delta = max(delta,abs(V[s]-v))\n",
    "        if delta < theta:\n",
    "            break\n",
    "    policy = policy_improvement(env, V, gamma)\n",
    "    return policy, V"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "运行下个代码单元格以解决该 MDP 并可视化输出结果。状态值函数已调整形状，以匹配网格世界的形状。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Optimal Policy (LEFT = 0, DOWN = 1, RIGHT = 2, UP = 3):\n",
      "[[ 1.  0.  0.  0.]\n",
      " [ 0.  0.  0.  1.]\n",
      " [ 0.  0.  0.  1.]\n",
      " [ 0.  0.  0.  1.]\n",
      " [ 1.  0.  0.  0.]\n",
      " [ 1.  0.  0.  0.]\n",
      " [ 1.  0.  0.  0.]\n",
      " [ 1.  0.  0.  0.]\n",
      " [ 0.  0.  0.  1.]\n",
      " [ 0.  1.  0.  0.]\n",
      " [ 1.  0.  0.  0.]\n",
      " [ 1.  0.  0.  0.]\n",
      " [ 1.  0.  0.  0.]\n",
      " [ 0.  0.  1.  0.]\n",
      " [ 0.  1.  0.  0.]\n",
      " [ 1.  0.  0.  0.]] \n",
      "\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAVsAAAFoCAYAAAD5IVjuAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4wLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvpW3flQAAIABJREFUeJzt3Hl4VNX9x/H3yUwme0IgGxGBIBKs7CAKiBRFENdWtKiIYCvFtm5QteDSaqs/awWqVYGCCuICtoKKRVSwQmVxAUFQ3FABgQQSSMhGSDI5vz8mRIZMEEJyIvJ5+dynT8793nvP/c7kkzt3bjHWWkREpGGFNfYERESOBwpbEREHFLYiIg4obEVEHFDYiog4oLAVEXFAYSs/KMaYTcaYAY09j4ZgjBlmjHmzsechjUNhe4wzxpxpjFlhjNljjNltjFlujDmtat1IY8yyI9hXa2OMNcZ46ziX8caY/4UYTzLGlBljOtRlv/XBGDOzag5FByxDG/B4NXpprX3OWjuwoY4pP2wK22OYMSYe+A/wKNAUOAG4F9jXSFN6BuhtjMk4aPwKYL219uNGmNOB/matjT1geaGR5yPHEYXtsa0dgLV2trXWb63da61901q7zhhzCjAV6FV1FZcPYIy5wBizxhhTYIz51hhzzwH7239Vml+1Ta+qbX5pjPnUGJNnjHnDGNMq1GSstVuB/wLDD1p1DfB01b5OMsb81xizyxiTa4x5zhjTJNT+qq5G7zvg558aY7Ye8HO6MWauMSbHGPONMeamw+5c8HGsMaZtqOPuP6Yx5vfGmJ3GmCxjzLUH1EYZYyYaYzZXfbpYZoyJIkQvD/6kYYzpbYz5oGq7D4wxvQ9Yt8QY85eqTyqFxpg3jTFJdTk/+WFQ2B7bvgD8xpinjTGDjTGJ+1dYaz8FrgdWVl3F7Q+0YgLh1wS4APiNMeZnVevOqvrfJlXbrKxadwdwKZAMvAPMPsScnuaAsDXGZAJdDtjGAA8A6cApwInAPUd64saYMOBV4CMCV/TnALcYYwYd6b4OQxqQUHWcXwGPH9DrCUB3oDeBTxe3A5WE6OVB828KLAD+ATQDJgELjDHNDii7CrgWSAF8wK31f2riisL2GGatLQDOBCwwHcgxxsw3xqQeYpsl1tr11tpKa+06AiHY7xCHGQ08YK391FpbAfwf0KW2q1vgJSD1gKu0a4CF1tqcquNvtNYustbuqxqb9D3Hr81pQLK19s/W2jJr7dcEenDFIba51RiTX7XkHsGxyoE/W2vLrbWvAUVAZlXg/xK42Vq7rerTxQpr7eHcxrkA+NJa+4y1tsJaOxv4DLjogJoZ1tovrLV7gX8R+KMlxyiF7TGuKgRHWmtbAB0IXDE+XFu9MeZ0Y8zbVR+99xC4+j3Ux9NWwCP7QwrYTeDq9ARjzB0HfNk0tWo+JcC/gWuMMQYYRtUthKrjpxhj5hhjthljCoBnv+f4h5pX+gHhmU/gCrzWPzTABGttk6rlSI65q+oPzX4lQCyBeUcCXx3p5Am8TpsPGttM4Op5v+wQx5RjlML2R8Ra+xkwk0DoQuCK92DPA/OBE621CQTu65pD1H8LjD4gpJpYa6OqruD+74Avm64/YJungV8A5wJxBL7E2++BquN0stbGA1cfcPyDFQPRB/ycdtC8vjloXnHW2vNr2dehlBziOIeSC5QCJ4VY933/nN52An8wDtQS2HaYx5ZjjML2GGaMaV/1xU2Lqp9PBK4E3q0q2QG0MMb4DtgsDthtrS01xvQkcF9wvxwC9xvbHDA2FRhvjDm16hgJxpjLv2dq7wD5wDRgjrW27KDjFxH44ugE4LZD7GctcL4xpqkxJg245YB17wMFxpg/VH1J5THGdDBVj70dobXAVVX7OI/DvK1hra0EngImVX1Z56n6IiyC0L080GtAO2PMVcYYrwk8hvYTgv8wyY+IwvbYVgicDrxnjCkmELIfA7+vWv9f4BMg+4B7lL8F/myMKQT+SOBeIFB9C+B+YHnVR/MzrLUvAQ8Cc6o+9n8MDD7UpGzgH0meReDKbdZBq+8FugF7CHxBNO8Qu3qGwBdgm4A3gepHtay1fgL3N7sA3xC4ynyCwBdZR+rmqn3lE7jt8fIRbHsrsB74gMAtlgeBsFC9PHAja+0u4EICr9UuAl+sXWitPZJ7yXIMMfrHw0VEGp6ubEVEHFDYiog4oLAVEXFAYSsi4oDCVkTEgSP6p/SaepJsC2/rBpqKiMixZ2vFJnb7c2v7P+ZUO6KwbeFtzfz0VXWflYjIj8zF23scVp1uI4iIOKCwFRFxQGErIuKAwlZExAGFrYiIAwpbEREHFLYiIg4obEVEHFDYiog4oLAVEXFAYSsi4oDCVkTEAYWtiIgDClsREQcUtiIiDihsRUQcUNiKiDigsBURcUBhKyLigMJWRMQBha2IiAMKWxERBxS2IiIOKGxFRBxQ2IqIOKCwFRFxQGErIuKAwlZExAGFrYiIAwpbEREHFLYiIg4obEVEHFDYiog44CxsnymYTN+tGWRuiuSi7d15v/SdQ9a/UvQ852/rwimbozltSxq35FxNTkV29frZhdO5PKsvXbY0pdPmJlyZ3Z8PSpcF7WNWweOct60THTfH03FzPJdm9eK/JQuCam7NGUnGJhO0/Hz7GUE143JH0W/rSbTfHEX3LcmM2nEJG8s+PcqOHDn1sH6oj0dPPTxyTsL2P8Uv8OfdN/PbhDtYkL6GbhG9uXbHYLZVbAlZv6p0OWNzhzMkdgRvpn/CtJSX2Vi+gVtyh1XXvFe6hAtjhvJc6lu8lP4ebbyZjNgxiG/Kv6yuSfO2YFzig7ya/iGvpK+iV+TZjN75Mz4tWxd0vD6RA3i/RVb1MiP1taD1nSJ68FDSTBanf8rTqW9gsVy9YwDltrweu3Ro6mH9UB+PnnpYN8Zae9jFnSJ62Pnpq474ID/bfjrtfZ34a9L06rH+W09mcMxl3J74QI36aXsm8HTBoyw/cXP12L8LZ3DP7hv5pFVRyGNYa+n5bXN+1+RORsbfWOtcumxpyu2JD3BV3Ggg8JcwrzKXJ1P/c9jn82nZOs7f3pnFJ3zGSeGZh73d0VAP64f6ePTUw2AXb+/Bun2rzPfVNfiVbZkt4+Oy1fSNGhg0fmbUQFaXrgi5TY+IPuT4s1hc8irWWnb7c3m1eA4/jTq/9uNQxj5bSkJYYsj1fuvn1aI5lFQW0S2id9C6D0qX0WNLCv23tmNc7ihy/TtrPU5JZTEvFs0g3dOSFt7WtdbVJ/WwfqiPR089rDtvg+4dyPPn4sdPkic1aDzZk8py/+KQ23SL7MUjybMZkzOMUruXCio4M/JcJiY9XetxJubdRUxYLAOiLw4a/6xsPUOyerHPlhJtYpma8hLtfR2r1/eLOo9BMZdyojeDrRWbmJh3F8Oyz2Z++moiTER13TMFk/lr3u2U2GLaeDN5Lu2toPUNST2sH+rj0VMP687ZF2SG4Ktsi60xtt+XZRu4d/dN3NDkbuanr2Zm6uvk+LO5Y9fokPUzCh5hduE/mZIyj7iw+KB1bcIzWZC+lnnN3+Xq+N9wa+4IPi/7uHr9RbFXcG70xbT3dWRA9EXMTF3I1+Wf8/ZBN94viR3Gf9LXMCdtKRnh7fhdzuXsrSypSyvqTD2sH+rj0VMPj1yDX9kmepLw4CHHnx00nuvfWeOv436T9zxA54iejE64DYBT6ER0sxh+kd2XWxPvJ917YnXtjIJHmJh3FzNSF9IlomeNffmMj9bhbYHAjfF1+z7gqYK/82DSkyGPnepNJ83bgk0VXwaNx4clEB+WQEb4yXSNOIMuWxJZWDKXS2OHH34z6kg9rB/q49FTD+uuwa9sfcZHB193lu1dFDS+bO8iukf2DrlNqS0hDE/QmKfqZ8t3X+g9sWcSE/Lu5MnUBZwWeeZhzaeSSvbZfbWu3+3PZUfFNpI9zWutsVX/lR1iP/VJPawf6uPRUw/rrsGvbAGuSxjL2JzhdI7oSY+IPjxXOJWd/u1cFXc9AGNzrgFgUvIsAM6Juojxu0bxbMEUzooaxE5/Fn/ZfQsdfN04wdsSgH/ueYiJeXcyKflZ2njbVT+zFxEWRXxYAgAP7h5H/+gLSPecSJEtZH7x87xbuoSnUgIfKYori3g4/x4GRw8hxdOcrRWb+Fv+eJp5UhgU/XMANpVv5PWSufSJHEBTTzLZFVuZsuev+EwE50Rd6KJ96mE9Uh/Vw8bqoZOwvTBmKHn+XTyWfx85/iza+TrwVOprtPC2AmD7Qc/nXRY3kiJbyKzCx7g/7/fEhSXQK7I/4xL/Vl3zTMHjlFPOjTlDg7YdEjOCCckzAcjxZzMm52py/dnEhSXQ3teJGakL6Rc1CAj8df28bD0vFc2ioDKfZE9zekX257HkfxEbFgeAz0TwbukSntgzkYLKfJI8qfSMPIt5aStJ9qY1VMtqUA/rh/p49NTDunHynK2IyI/VD+Y5WxERUdiKiDihsBURcUBhKyLigMJWRMQBha2IiAMKWxERBxS2IiIOKGxFRBxQ2IqIOKCwFRFxQGErIuKAwlZExAGFrYiIAwpbEREHFLYiIg4obEVEHFDYiog4oLAVEXFAYSsi4oDCVkTEAYWtiIgDClsREQcUtiIiDihsRUQcUNiKiDigsBURcUBhKyLigMJWRMQBha2IiAMKWxERBxS2IiIOKGxFRBxQ2IqIOKCwFRFxwNvYEzgeZXzT2DM49v19TGPP4MdhzN8bewY/Aj0Or0xXtiIiDihsRUQcUNiKiDigsBURcUBhKyLigMJWRMQBha2IiAMKWxERBxS2IiIOKGxFRBxQ2IqIOKCwFRFxQGErIuKAwlZExAGFrYiIAwpbEREHFLYiIg4obEVEHFDYiog4oLAVEXFAYSsi4oDCVkTEAYWtiIgDClsREQcUtiIiDihsRUQcUNiKiDigsBURcUBhKyLigMJWRMQBha2IiAMKWxERBxS2IiIOKGxFRBxQ2IqIOOAsbJ8pmEzfrRlkborkou3deb/0nUPWv1L0POdv68Ipm6M5bUsat+RcTU5FdvX62YXTuTyrL122NKXT5iZcmd2fD0qXBe1jVsHjnLetEx03x9NxczyXZvXivyULgmpuzRlJxiYTtPx8+xlBNeNyR9Fv60m03xxF9y3JjNpxCRvLPj3KjjSiyZMhIwMiI6F7d3jn0K8FS5cG6iIjoU0bmDrVzTwbyLKPJvOXpzK47dFIJj7fna+21X7+G79dwpiHTY1lx+7PqmtWrp/OP/7VlzunNGX85CY8/mJ/vt4W/F4sLSvkpSW38OcnW3H7o1E88kJvtmR/UOtxX1j8a8Y8bHh79YSg8RXrp/H4i/0ZP7kJYx427N6zqW5N+KE4jt6LTsL2P8Uv8OfdN/PbhDtYkL6GbhG9uXbHYLZVbAlZv6p0OWNzhzMkdgRvpn/CtJSX2Vi+gVtyh1XXvFe6hAtjhvJc6lu8lP4ebbyZjNgxiG/Kv6yuSfO2YFzig7ya/iGvpK+iV+TZjN75Mz4tWxd0vD6RA3i/RVb1MiP1taD1nSJ68FDSTBanf8rTqW9gsVy9YwDltrweu+TICy/AzTfDHXfAmjXQuzcMHgxbQr8WfPMNnH9+oG7NGhg/Hm68EebOdTvverLm8xd4aenNDDjtDm4dtobWzXsz7eXB5BXUcv5V/jD8E+4dlVW9JDc5uXrdxq1L6NpuKL8Z8hZjrniP5MRM/vnSIHLyvnsvvrDoOj7b/AZXDXya24avJ7PlQKbMG0B+0bYax1r75Yt8u+MDEmLSa6wrLy8hs+VAzjvjnro34YfiOHsvOgnbJ/ZMYkjsSK6MG0Vb3ync2+xRUjzNea5wSsj6D/etJM3Tgl8ljOHE8Ay6Rp7BiLgbWbvvveqah5OfY0T8DZwa0ZWTwjO5r9kUYkwcS/e+Xl0zMPoSfho9mNbhbWkT3o7bEu8nJiyONftWBh0vwkSQ7E2rXpp4mgatvypuND0j+9IivDUdIrrx+8T72OHfzpaKr+uxS45MmgQjR8KoUXDKKfDoo9C8OUwJ/VowdSqkpwfqTjklsN2IETBhQuj6H7glH06i509G0qvjKFKbnsKQ/o8SH9Oc5etqOf8qsdEpxMekVS9hYZ7qdcMHP0ffLjfQIqUrKU0zufzsKUT44vh0c+C9WFaxl3Ub53LhmX+l7Yk/JblJW87rdQ9JTdqy4qDj7i7YzMtLbmb44OcJCwuvMY9+3W5hQM/xZJxwZj10o5EdZ+/FBg/bMlvGx2Wr6Rs1MGj8zKiBrC5dEXKbHhF9yPFnsbjkVay17Pbn8mrxHH4adX7tx6GMfbaUhLDEkOv91s+rRXMoqSyiW0TvoHUflC6jx5YU+m9tx7jcUeT6d9Z6nJLKYl4smkG6pyUtvK1rrftBKiuD1athYPBrwcCBsCL0a8HKlTXrBw2CVaug/Ni6sq/wl7F152oyWwafT2bLgWzKquX8q0x6vgd/nNacyXPP4ctv3z5krd9fRnlFKdERgfdiZWUFldZPuCcyqC7cGxV0u8FfWcEzC6/k3J53kdr0lCM5tWPPcfhebPCwzfPn4sdPkic1aDzZk0qOPzvkNt0ie/FI8mzG5Ayj3WYf3b9NxmKZmPR0rceZmHcXMWGxDIi+OGj8s7L1nLo5lszNEdy563qmprxEe1/H6vX9os5jYvIsnk17izubTuSjfe8zLPts9tl9Qft5pmAyp26O5dQtsSwpWchzaW8RYSKOtB2NKzcX/H5IDX4tSE2F7NCvBdnZoesrKgL7O4YU782l0vqJiw4+n7joVApKQp9/fExzLjt7CtdeOJdfXjiPlMRMpsw9h6+2/q/W47y28i4ifLF0aBN4L0b64mjdvBdvvn8f+UXbqKz0s+rTZ9mUtZKCkqzq7V5f+SeiI5vRp/Nv6uFsf+COw/ei19WBDCboZ4utMbbfl2UbuHf3TdzQ5G7OihrETn8WD+y+jTt2jWZS8qwa9TMKHmF24T95Jm0xcWHxQevahGeyIH0tBZX5vF4yl1tzRzA7bQmZvg4AXBR7RXVte19HOvq6c+bWVrxdsoDzYi6tXndJ7DDOjDqXnf4spu+ZwO9yLufFtOVEhUXXuSeNxhzUd2trjn1ffajxY4U5/PdiStNMUppmVv/cOr0Xuws28faHEzipxVk16peueYQV6//Jby5dTGTEd+/FYYOeYc6iX3LvEy0IMx5apHSjW+aVbN35IQAbty7lgw0zuXXY2vo4w2PHcfRebPCwTfQk4cFT4yo217+zxtXufpP3PEDniJ6MTrgNgFPoRHSzGH6R3ZdbE+8n3Xtide2MgkeYmHcXM1IX0iWiZ419+YyP1uFtgcAXXev2fcBTBX/nwaQnQx471ZtOmrcFmyq+DBqPD0sgPiyBjPCT6RpxBl22JLKwZC6Xxg4//GY0tqQk8HhqXjns3FnzimG/tLTQ9V4vNGvWMPNsIDFRSYQZD4XFwedTVLKzxtXuobRMO501n8+pMb50zSMsXHEXv/7ZQlqlBb8Xk5qcxA2XL2VfeTGlZQUkxDTn6QVDaRqfAcDGb9+moDiLP01vXr1NpfXz6rI/sHTNw9xz3dYjOdUfvuPwvdjgtxF8xkcHX3eW7V0UNL5s7yK6R/YOuU2pLSEMT9CYp+pni60ee2LPJCbk3cmTqQs4LfLwvjCopLLGLYID7fbnsqNiG8me5rXW2Kr/yg6xnx8kny/w2Myi4NeCRYsC3/CG0qsXLF5cs75HDwiv+QXOD5nX46NFSnc+3xJ8/l9sWUTr5rWcfwjbc9YSHxP8/ljy4SReW3Enoy5ZQJtDfHkVER5DQkxzSkrz+GzzG3Q46RIA+nT+LbddvY5bh62tXhJi0unXdQy/vfStIzjLY8Rx+F50chvhuoSxjM0ZTueInvSI6MNzhVPZ6d/OVXHXAzA25xqA6lsE50RdxPhdo3i2YEr1bYS/7L6FDr5unOBtCcA/9zzExLw7mZT8LG287aqfwY0IiyI+LAGAB3ePo3/0BaR7TqTIFjK/+HneLV3CUymBZ22LK4t4OP8eBkcPIcXTnK0Vm/hb/niaeVIYFP1zADaVb+T1krn0iRxAU08y2RVbmbLnr/hMBOdEXeiiffVr7FgYPhx69oQ+fQLf8G7fDtcHXguuCbwWzKq6XXP99fDYY3DLLTB6NCxfDjNnwuzZjTL9o/XTbmN57o3htErrSUZ6H5avm8qe4u307hQ4/+feCJz/sEGB81/64cM0jW9NWrNTqagsY/Wnz7L+q5e59sLvHjf676qHeG3FnQw771mSE9tRUHXlHO6NIioi8F78bNMbWFtJStP25OZvZP47t5GSmMnpP7kWgLjoFOKiU4LmGhYWTnxMWtBtjILibAqLs8nJ+wKA7N0b2LsvnybxLYmJDH6K5gfvOHsvOgnbC2OGkuffxWP595Hjz6KdrwNPpb5GC28rALYf9LztZXEjKbKFzCp8jPvzfk9cWAK9IvszLvFv1TXPFDxOOeXcmDM0aNshMSOYkDwTgBx/NmNyribXn01cWALtfZ2YkbqQflGDgMDV8udl63mpaBYFlfkke5rTK7I/jyX/i9iwOAB8JoJ3S5fwxJ6JFFTmk+RJpWfkWcxLW0myN62hWtZwhg6FXbvgvvsgKws6dIDXXoNWgdeixjOOGRmB9WPGBB7JSU+Hf/wDhgxxP/d60DVzKMWlu3jzvfsoKMmiebMO/PqS12gaHzj/g5+3ragsY/47t7KnaBvh3ihSm53KqEsW8JOM756MWfbR4/gry5n1WvB78bRTRnDVoJkA7C3bw4Ll48kv2kp0RFM6nzyE83vfj8dzZFdkK9ZN5Y337q3+eforFwBw5bkz6HnqyCPaV6M7zt6Lxlr7/VVVOkX0sPPTVzXgdI4PGd809gyOfX8f09gz+HEY8/fGnsGPQI8e2FWrvvcbOv3bCCIiDihsRUQcUNiKiDigsBURcUBhKyLigMJWRMQBha2IiAMKWxERBxS2IiIOKGxFRBxQ2IqIOKCwFRFxQGErIuKAwlZExAGFrYiIAwpbEREHFLYiIg4obEVEHFDYiog4oLAVEXFAYSsi4oDCVkTEAYWtiIgDClsREQcUtiIiDihsRUQcUNiKiDigsBURcUBhKyLigMJWRMQBha2IiAMKWxERBxS2IiIOKGxFRBzwNvYEjkffZDT2DI59+U0aewYiR0ZXtiIiDihsRUQcUNiKiDigsBURcUBhKyLigMJWRMQBha2IiAMKWxERBxS2IiIOKGxFRBxQ2IqIOKCwFRFxQGErIuKAwlZExAGFrYiIAwpbEREHFLYiIg4obEVEHFDYiog4oLAVEXFAYSsi4oDCVkTEAYWtiIgDClsREQcUtiIiDihsRUQcUNiKiDigsBURcUBhKyLigMJWRMQBha2IiAMKWxERBxS2IiIOKGxFRBxQ2IqIOOAsbJ8pmEzfrRlkborkou3deb/0nUPWv1L0POdv68Ipm6M5bUsat+RcTU5FdvX62YXTuTyrL122NKXT5iZcmd2fD0qXBe1jVsHjnLetEx03x9NxczyXZvXivyULgmpuzRlJxiYTtPx8+xlBNeNyR9Fv60m03xxF9y3JjNpxCRvLPj3Kjhw59fDo/St3MhdsyOD0jyK56vPufFhUew//uHkkXdeaGkuvdTFBdeWVZUzO+iMXbMig50cRDP6kJc/n/CPkPhfmzabrWsNNX18YNH7+J61DHuvGry+orlld9D9u/vpiBn5yAl3XGubvmln3RvxQTJ4MGRkQGQndu8M7h35Ps3RpoC4yEtq0galT3cyzHjgJ2/8Uv8Cfd9/MbxPuYEH6GrpF9ObaHYPZVrElZP2q0uWMzR3OkNgRvJn+CdNSXmZj+QZuyR1WXfNe6RIujBnKc6lv8VL6e7TxZjJixyC+Kf+yuibN24JxiQ/yavqHvJK+il6RZzN658/4tGxd0PH6RA7g/RZZ1cuM1NeC1neK6MFDSTNZnP4pT6e+gcVy9Y4BlNvyeuzSoamHR++NvBd4aOvN/Cr1DmZnrqFTTG9u+HowWWWhe3hbi0dYdGpW0NLC14aBTX4RVDdu85WsKHydu0+cxsvtP+dvrf9Nu8hONfa3dd/XPLz9NrrG9K2x7tnMD4KOM7vdhxgM5x5wrJLKItpGduC2Ex4h0kQdZTd+AF54AW6+Ge64A9asgd69YfBg2BL69eCbb+D88wN1a9bA+PFw440wd67bedeRsdYednGniB52fvqqIz7Iz7afTntfJ/6aNL16rP/Wkxkccxm3Jz5Qo37angk8XfAoy0/cXD3278IZ3LP7Rj5pVRTyGNZaen7bnN81uZOR8TfWOpcuW5pye+IDXBU3GghcleVV5vJk6n8O+3w+LVvH+ds7s/iEzzgpPPOwtzsa6mGw/CZHvAnDvzidkyM78ceW3/Xw4g0nM6DJZdyUXrOHB1tbtJxrN57JjJOX0yWmNwArC97k9k2XM/8nX5HoTap123Jbzi+/PJPLk37LqsK3yffn8o82tffriez7eXrnQ7zZYTtRYdE11vdeF8u4Ex7j4mYjv3feh9J1zVFtfnROPx06dYLp370enHwyXHYZPBDi9fjDH2DePPjyu4sBrrsOPvkEVq5s+PnWpkcP7KpV5vvKGvzKtsyW8XHZavpGDQwaPzNqIKtLV4TcpkdEH3L8WSwueRVrLbv9ubxaPIefRp1f+3EoY58tJSEsMeR6v/XzatEcSiqL6BbRO2jdB6XL6LElhf5b2zEudxS5/p21HqekspgXi2aQ7mlJC2/rWuvqk3p49Mory/i0ZDW94oN72Ct+IB8Vh+7hwebtms5JkadWBy3A23te5ifRp/HszkkM+qQFF284mQe33kSJP/gP2uNZd5Lua83FTUd873Gstby8+0kuaHp1yKD9USgrg9WrYWDw68HAgbCiltdj5cqa9YMGwapVUO7uE1JdeRv6AHn+XPz4SfKkBo0ne1JZ7l8ccptukb14JHk2Y3KGUWr3UkEFZ0aey8Skp2s9zsS8u4gJi2VA9MVB45+VrWdIVi/22VKiTSxTU16iva9j9fp+UecxKOZSTvRmsLViExPz7mJY9tnMT19NhImornumYDJ/zbudEltMG28mz6W9FbS+IamHR2/brScoAAASvElEQVR/D5t6g3vY1JvKrorQPTxQoX8Pi/b8mxub/1/Q+Layr1lbvAxfWAQTWs+l0J/Pg9tuJKd8OxMyXgQCV79v5L3AC5lrD2uu7xYuYlvZN/y86XWHeXbHoNxc8PshNfj1IDUVFtfyemRnw4ABNesrKgL7a968YeZaT5x9QWYIvsq22Bpj+31ZtoF7d9/EDU3uZn76amamvk6OP5s7do0OWT+j4BFmF/6TKSnziAuLD1rXJjyTBelrmdf8Xa6O/w235o7g87KPq9dfFHsF50ZfTHtfRwZEX8TM1IV8Xf45bx/0JdAlscP4T/oa5qQtJSO8Hb/LuZy9lSV1aUWdqYdHr2a/au/hgV7b/SyV1s8FicODxiupxGD4v1bP0zHmdHrHD2LcCY/x1p657CrfQV5FLn/cMpK/tHyaeG/oTwwHm7drOqdGn0ZmdJfDPa1jlzmo99bWHPu++lDjP0ANfmWb6EnCg4ccf3bQeK5/Z40rtf0m73mAzhE9GZ1wGwCn0InoZjH8IrsvtybeT7r3xOraGQWPMDHvLmakLqRLRM8a+/IZH63D2wKBL2nW7fuApwr+zoNJT4Y8dqo3nTRvCzZVfBk0Hh+WQHxYAhnhJ9M14gy6bElkYclcLo0dHnI/9Uk9PHr7e7irIriHuyt21rjaDWXerumc02QICd6mQeNJ3uakhJ9AnCeheiwj8hQAssu3sNdfTG5FFtd/9d0VWSWVAPRY6+XF9p/QOvK7e9a7y3eypOAVxrd4/MhP8liSlAQeT+Bq9UA7d9a82t0vLS10vdcLzZo1zDzrUYNf2fqMjw6+7izbuyhofNneRXSP7B1ym1JbQhieoDFP1c+W777Qe2LPJCbk3cmTqQs4LfLMw5pPJZXss/tqXb/bn8uOim0ke2r/SGKr/is7xH7qk3p49MLDfJwS3Z13C4N7+G7hIjrHhO7hfh8Xv88XpR9xadNRNdZ1ielDTvn2oHu0m/d9AUDz8FacGn0a/85cz5zMtdVLv/iL6RrTlzmZaznBlxG0v/m7Z+IzEQxqckVdT/XY4PMFHuFaFPx6sGhR4GmDUHr1qnmLYdEi6NEDwsMbZp71qMGvbAGuSxjL2JzhdI7oSY+IPjxXOJWd/u1cFXc9AGNzrgFgUvIsAM6Juojxu0bxbMEUzooaxE5/Fn/ZfQsdfN04wdsSgH/ueYiJeXcyKflZ2njbVT8/GhEWRXxY4Crjwd3j6B99AemeEymyhcwvfp53S5fwVErg421xZREP59/D4OghpHias7ViE3/LH08zTwqDon8OwKbyjbxeMpc+kQNo6kkmu2IrU/b8FZ+J4Jyo4Gcl1cMfdg+vTh7LXVuGc2p0T7rE9OHF3KnklG/nsqRAD+/aHOjhfa1mBW03d9c0WkacTPfYfjX2OTjxKqbv+At/2nIt16fdQ6E/n4e23cyAhMtoGp4CQNuoDkHbxHma4Keixri1lpd2P8GgJlcQ44mrcawSfxHf7ttYVVtJVvkWPi9ZS7y3Kc19LevYlUY0diwMHw49e0KfPoFnZrdvh+sDrwfXBF4PZlW9HtdfD489BrfcAqNHw/LlMHMmzJ7dKNM/Uk7C9sKYoeT5d/FY/n3k+LNo5+vAU6mv0cLbCoDtBz0relncSIpsIbMKH+P+vN8TF5ZAr8j+jEv8W3XNMwWPU045N+YMDdp2SMwIJiTPBCDHn82YnKvJ9WcTF5ZAe18nZqQupF/UICBwpfd52XpeKppFQWU+yZ7m9Irsz2PJ/yI2LPBm95kI3i1dwhN7JlJQmU+SJ5WekWcxL20lyd60hmpZDerh0RuUOJQ9/l08kX0fuRVZtI3swKNtXiPdF+hhdojnbYv9hbyRP4dfp/4RE+K+YLQnlqknLebBbTdy9RenEedNpH/Cz7ip+V+PeH6ripawZd+X3N/y2ZDrN5SsYtRX/at/npr9J6Zm/4mLEkfw51Yzj/h4jW7oUNi1C+67D7KyoEMHeO01aBV4PWo8b5uREVg/ZgxMmQLp6fCPf8CQIe7nXgdOnrMVqW91ec5WamrU52x/LH4oz9mKiIjCVkTECYWtiIgDClsREQcUtiIiDihsRUQcUNiKiDigsBURcUBhKyLigMJWRMQBha2IiAMKWxERBxS2IiIOKGxFRBxQ2IqIOKCwFRFxQGErIuKAwlZExAGFrYiIAwpbEREHFLYiIg4obEVEHFDYiog4oLAVEXFAYSsi4oDCVkTEAYWtiIgDClsREQcUtiIiDihsRUQcUNiKiDigsBURcUBhKyLigMJWRMQBha2IiAPeIyle3xEyVjXUVI4feYmNPYNjX+tNjT0DkSOjK1sREQcUtiIiDihsRUQcUNiKiDigsBURcUBhKyLigMJWRMQBha2IiAMKWxERBxS2IiIOKGxFRBxQ2IqIOKCwFRFxQGErIuKAwlZExAGFrYiIAwpbEREHFLYiIg4obEVEHFDYiog4oLAVEXFAYSsi4oDCVkTEAYWtiIgDClsREQcUtiIiDihsRUQcUNiKiDigsBURcUBhKyLigMJWRMQBha2IiAMKWxERBxS2IiIOKGxFRBw4tsJ28mTIyIDISOjeHd5559D1S5cG6iIjoU0bmDrVzTwbyBP7JtO5IIO0/Eh+WtidFRWHPv9/lz1P34IupOdHk7knjV8XX82Oyuygmqn7HqFnQXua50dx6p4W3FryO4psUfX6SaUPcHbhabTMj6ftnmSuKLqIDf6Pg/Zx/9676VnQnhPyY2i9J5FLis7hvYoVQTUXFv6UxHwTtPyy+Iqj7EjdTGYyGWQQSSTd6c47HLqPj/M4p3AKUUSRSSazmFVr7WxmYzBcyIVB4//jf1zMxZzACRgMM5lZY9t5zGMQg0gmGYNhCUtq1GSTzXCGk0YaMcTQmc48x3OHdd4/SMfT77S19rAXunc//OL6XubMsXi9lmnTLBs2WG64wRITY9m8OXT9119boqMDdRs2BLbzei0vvth451C15DU58uXJ6DnWi9c+HDXNvhu3wY7y3WBjiLHr4jeHrF8Yu8yGEWbvj5xk18Z9bd+MXWk7ebras7xnV9dMi37O+vDZKdGz7Edx39hXYt6yLcNa26t9v6yuOds70D4W9ZRdHrfeLotbZy8I/5lNMan26/hd1TVTo5+xL8cstmvivrIr4j62w32/snHE2c/js6tr+nj62WG+a+1n8VnVy6aE/Dr1Iq9J3Zs/h0AfpzHNbmCDvYFAHzezOWT9ZCbbGGLs8zxvv+IrO5vZNpZYO5/5NWq/4it7AifYvvS1F3BB0LoFLLDjGW//zb9tFFF2BjNqbD+LWfYe7rGzmGUB+zZv16g5l3Ntd7rbd3nXfsVXdgITrMHYpSytUz8a9Xfhx/I73b27PZyyI9pno4Ztz56W664LHmvb1jJuXOj6228PrD9w7Fe/spxxRuO+MLZu4dLd09Ne47suaKxNWFt7S8S4kPV/jnzItjAtg8Yei3rKxhBT/fN1vt/Z3p6zgmpuj/ijbR92aq3z+Dah0IYRZp+PmV9rzeaEPRawL8a8HhS21/l+V+dwra+w7UlPex3XBY21pa0dx7iQ9b3oZW/hlqCxsYy1fegTNFZGme1JTzuTmXYEI2qE7YFLDDEhw3b/kkNOrWEbQ4x9iqeCxlrS0j7EQ3XqR6P+LvxYfqcPM2yPjdsIZWWwejUMHBg8PnAgrFgRepuVK2vWDxoEq1ZBeXnDzLOBlNky1vpX098bfD79vQN5vyL0+Z/u7cMOm8XC8lex1rKrMpd55XM4N/z86pozvGey3r+WDyreBeDbyi0srJgfVHOwIltIJZU0MYm1zvXpfdOII56Oni5B6+aVz+GkPUn0KjiVu/feSqEtPKzzry9llLGa1QwkuI8DGcgKQvdxH/uIJDJoLIoo3ud9yvnufXQnd9Ka1oxgRP1P/ABncib/4l/sYheVVPIKr5BDDgMY0KDHrXfH4e/0sRG2ubng90NqavB4aipkZ4feJjs7dH1FRWB/x5BdNhc/fpLDgs8nJSyVnTb0+ff09uKJ6NmMLh5Gyh4fbQuSsVgmRz9dXTPEdwV3R/0fFxSdRXJ+OJ0KWvGTsI7cG/lgrXMZv/dmOnq60NPTK2j89fL/0CI/lrQ9kUzZ93deil1EygHzvcx3FdOin2N+7NvcGnk388vnck3xpXVpR53lEuhjKsF9TCWVbEL3cRCDeIqn+IAPsFhWsYoneIJyyskl8D56kzd5gReYSsPfP/wX/8JgSCKJCCIYxjBmM5sudPn+jX9IjsPf6WMjbPczJvhna2uOfV99qPFjhCF43hZbY2y/z/wbGLf3Jm6NvJu341bzYszr7KjMZkzJ6Oqa5RVLmVD6FyZETWZJ3Ic8Ez2PZRVLeKD0TyH3eefesbxbsYxZ0XPxGE/Qur7e/vwvbi1vxK7gnPDzuLb4F2RXZlWvHxnxa84JH8Spno4M8V3BU9EvsKRiMR9VfFjXdtTZkfTxbu7mAi6gN70JJ5xLuKT66tWDh1xyGclInuZpEgl9tV+f7uIucsllMYtZxSpu4zau4Ro+4qMGP3aDOI5+p72NPYHDkpQEHk/Nv3g7d9b8S7dfWlroeq8XmjVrmHk2kGYmCQ8edh70JEFO5U6STejz/3vpA3Tz9uSmyNsA6ODpRLSJ4fyivtxVeT8twk7kvr13McR3JddEXAfAqZ6OFFPMzSXXcXvkH/Ga794ed+wdw7yyOcyPfZvWnjY1jhdjYmjjaUsb2nKa9wy6F5zMM2VPcFvk3SHn19XTAw8evqr8ks50q1NfjlQSgT4efBW7k501rnb3iyKKp3iKf/JPdrCD5jRnGtOII44kkvgf/yOLrKCP8ZVUAuDFyyd8QiaZ9TL/r/iKR3mUtaylM50B6Exn3uEdHuVRnuCJejmOE8fh7/SxcWXr8wUe91i0KHh80SLo3Tv0Nr16weLFNet79IDw8IaZZwPxGR9dPN1ZUhF8/ksqFtHTG/r891KCh+Crz/0/W+wha/av329cyc28WPY8r8T+l3ae9oc150oq2Wf31br+k8r1gY/0Yc0Pa3/1wYeP7nRnEcF9XMQielPL+6hKOOG0oAUePMxhDhdyIWGEcRqnsZ71rD3gv4u5mL70ZS1rySCj3uZfQglAyNdsf8AfM47H3+kj+dKt0R/9Cg+3TJ8eeOzjppsCj4ls2hRYP3x4YNlfv/8xkZtvDtRPnx7YvrEfE7F1f/QrnHD7SNR0+27cBjvad5ONIcZ+FL/J5jWxdmj4cDs0fHh1/eNRM6wXr50QNdmuifvKLoxdZrt6etjOnm7VNX+I+JONI84+ET3bro372s6LedNmhJ1kLwq/tLrmV77f2jji7CsxbwU9tvVtQmH1kwe/j7jTLop9166L32zfjl1lh/mutT589p24j2xeE2s/jNtox0fea/8b+4H9KO4b+0LMAtsurL3t5OlqcxMqnD/6FU64nc50u4EN9iYCfdzEJmuxdjjD7XCGV9d/zud2FrPsF3xh3+M9O5ShtilN7Td8U+sxQj2NUEihXcMau4Y1Noooey/32jWsCXrkbBe77BrW2Ld52wJ2OtPtGtbYLLKsJfDEQ1va2r70te/xnt3IxupHv0I9inY4S6P+LvxYfqd/dI9+WWt5/HFLq1YWn8/SrZtl6dLv1vXrF1gOrF+yxNK1a6C+dWvLlCmNO/+qpa6POz0U9bg90bSyPny2s6eb/U/s0qBHq/p4+gXVPxj1D9s+7Cc2iiibatLskPAr7cfx31avz0kot+Mi77FtwtraSCJtumlhf+n7jf0mfnd1DRBy+UPEn2xeE2u3JRTbC8J/ZtNMc+vDZ9NMczvYe7FdFPtu9T7Wx2+xvT1n2UTT1Prw2Yywk+xo301Bz+q6CluLtY/zuG1FoI/d6Bb0jGo/+tl+9Kv+eQMbbBe62CiibDzx9hIusZ/x2SH3Hyps9wfowcsIRlTXzGBGyJo/8afqmi/4wl7KpTaFFBtNtO1EJzuTmXXuRWP/LvwofqcPM2yNtbbG1W5tTI8ellWr6u+y+jiV1/Dfo/zoNclv7Bn8OJjD//WX2vTogV216nu/oTs27tmKiBzjFLYiIg4obEVEHFDYiog4oLAVEXFAYSsi4oDCVkTEAYWtiIgDClsREQcUtiIiDihsRUQcUNiKiDigsBURcUBhKyLigMJWRMQBha2IiAMKWxERBxS2IiIOKGxFRBxQ2IqIOKCwFRFxQGErIuKAwlZExAGFrYiIAwpbEREHFLYiIg4obEVEHFDYiog4oLAVEXFAYSsi4oDCVkTEAYWtiIgDClsREQcUtiIiDihsRUQcMNbawy82JgfY3HDTERE55rSy1iZ/X9ERha2IiNSNbiOIiDigsBURcUBhKyLigMJWRMQBha2IiAMKWxERBxS2IiIOKGxFRBxQ2IqIOPD/bUn9655okNQAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x7f07c16890f0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "policy_vi, V_vi = value_iteration(env)\n",
    "\n",
    "# print the optimal policy\n",
    "print(\"\\nOptimal Policy (LEFT = 0, DOWN = 1, RIGHT = 2, UP = 3):\")\n",
    "print(policy_vi,\"\\n\")\n",
    "\n",
    "# plot the optimal state-value function\n",
    "plot_values(V_vi)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "运行以下代码单元格以测试你的函数。如果代码单元格返回 **PASSED**，则表明你正确地实现了该函数！ \n",
    "\n",
    "**注意：**为了确保结果准确，确保 `truncated_policy_iteration` 函数满足上文列出的要求（具有三个输入、两个输出，并且没有更改输入参数的默认值）。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "**<span style=\"color: green;\">PASSED</span>**"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "check_test.run_check('value_iteration_check', value_iteration)"
   ]
  },
  {
   "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.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}