Monte_Carlo_Control_and_MCTS.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "2eecc88c",
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "ERROR: Invalid requirement: \"'git+https://github.com/sarah-keren/multi-taxi'\"\n"
     ]
    }
   ],
   "source": [
    "!pip install -q 'git+https://github.com/sarah-keren/multi-taxi'"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "88a017c5",
   "metadata": {},
   "source": [
    "# Our Problem\n",
    "The problem that we will focus on today is to make a taxi move towards a single passenger and to pick it up, without dropping it at its destination."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "f954d24b",
   "metadata": {},
   "source": [
    "![Taxi_domain_show](https://raw.githubusercontent.com/GabrieleSerussi/mcts/main/Taxi_domain_show.png)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "503b615e",
   "metadata": {},
   "source": [
    "The only guidance that we will provide to our agent is a **reward function** that prizes the agent for picking up the passenger and that penalizes the agent for taking too many steps to reach the goal.\n",
    "\n",
    "In particular, the reward function is defined as follows:\n",
    "- +100 points for a successful drop-off\n",
    "- -5 point for every bad pick-up\n",
    "- -2 points for hitting an obstacle (e.g. a wall)\n",
    "- -1 for every step taken"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "7716d5be",
   "metadata": {},
   "outputs": [],
   "source": [
    "from multi_taxi import Event\n",
    "\n",
    "customized_reward = {\n",
    "    Event.PICKUP: 100,\n",
    "    Event.BAD_PICKUP: -5,\n",
    "    Event.HIT_OBSTACLE: -2,\n",
    "    Event.STEP: -1\n",
    "}"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "bb119675",
   "metadata": {},
   "source": [
    "# Our Tools\n",
    "In our case we are **not** given access to a model, i.e. we don't know the transition function $ T: \\mathcal{S} \\times \\mathcal{A} \\rightarrow \\mathcal{S} $ and the reward function $ R: \\mathcal{S} \\times \\mathcal{A} \\rightarrow \\mathcal{S} $, where $\\mathcal{S}$ is the set of states and $\\mathcal{A}$ is the set of actions. \n",
    "\n",
    "We can only interact with the environment by taking actions and observing the resulting state and reward.\n",
    "This approach is thus based on Monte Carlo simulations and it is called **model-free**.\n",
    "\n",
    "## Monte Carlo Simulation\n",
    "To understand how Monte Carlo simulations work, let's see it in action.\n",
    "First, we will create a helper function which will allow us to create an environment by specifying the position of the taxi and the passenger."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "5d9818b6",
   "metadata": {},
   "outputs": [],
   "source": [
    "from multi_taxi import multi_taxi_v0\n",
    "from multi_taxi.world.maps import DEFAULT_MAP, BIG_MAP\n",
    "\n",
    "def new_environment_creator(taxi_pos, passenger_pos, \n",
    "                            num_taxis=1,num_passengers=1, \n",
    "                            pickup_only=True, can_see_other_taxi_info=False, \n",
    "                            domain_map=DEFAULT_MAP,reward_table=customized_reward):\n",
    "    \"\"\"\n",
    "    A helper function to setup a new environment with predefined taxi and passenger locations\n",
    "    :param taxi_pos: The location of the taxi\n",
    "    :param passenger_pos: The location of the passenger\n",
    "    :param num_taxis: The number of taxis in the environment (default: 1)\n",
    "    :param num_passengers: The number of passengers in the environment (default: 1)\n",
    "    :param pickup_only: Whether the passenger can be dropped off or not (default: True)\n",
    "    :param can_see_other_taxi_info: Whether the taxi can see the other taxis' locations (default: False)\n",
    "    :param domain_map: The map of the environment (default: DEFAULT_MAP)\n",
    "    :param reward_table: The reward table of the environment (default: customized_reward)\n",
    "    :return: The new environment\n",
    "    \"\"\"\n",
    "    new_env = multi_taxi_v0.env(num_taxis=num_taxis, num_passengers=num_passengers, pickup_only=pickup_only, domain_map=domain_map,\n",
    "                                can_see_other_taxi_info=can_see_other_taxi_info,reward_table=reward_table, \n",
    "                                render_mode='human', allow_arrived_passengers_on_reset=False)\n",
    "    new_env.reset()\n",
    "\n",
    "    state = new_env.state()\n",
    "    state.taxis[0].location = taxi_pos\n",
    "    state.passengers[0].location = passenger_pos\n",
    "    new_env.unwrapped.set_state(state)\n",
    "\n",
    "    return new_env\n",
    "\n",
    "\n",
    "# Create the environment from which we will run the Monte Carlo Simulations\n",
    "taxi_position = (0,0)\n",
    "passenger_position = (3,3)\n",
    "env = new_environment_creator(taxi_position, passenger_position)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "e787dcf4",
   "metadata": {},
   "source": [
    "Next, we will create a function that will allow us to simulate a single episode, i.e. a single run of the environment, by taking random actions until the episode ends."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "3fdfb4c8",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from IPython.display import clear_output\n",
    "from copy import deepcopy\n",
    "\n",
    "def run_monte_carlo_simulation(environment, gamma, max_number_of_steps: int =100_000, verbose: bool = False, render: bool = False):\n",
    "    \"\"\"\n",
    "    Runs a Monte Carlo simulation on a given environment\n",
    "    :param environment: The environment on which to run the simulation\n",
    "    :param gamma: The discount factor\n",
    "    :param max_number_of_steps: The maximum number of steps to run the simulation for (default: 100_000)\n",
    "    :param verbose: Whether to print the results of the simulation (default: False)\n",
    "    :param render: Whether to render the environment (default: False)\n",
    "    :return: The accumulated reward\n",
    "    \"\"\"\n",
    "    # Copy the environment so we don't change the original\n",
    "    env = deepcopy(environment)\n",
    "\n",
    "    number_of_actions = len(env.unwrapped.get_action_map('taxi_0').values())\n",
    "    accumulated_reward = 0\n",
    "    # Run the simulation for at most max_number_of_steps steps\n",
    "    for step in range(max_number_of_steps):\n",
    "        # Choose a random action\n",
    "        action = np.random.choice(number_of_actions)\n",
    "        # Take the action\n",
    "        env.step(action)\n",
    "        # Get the last state\n",
    "        obs, reward, done, trunc, info = env.last()\n",
    "        # Accumulate the reward\n",
    "        accumulated_reward += reward * (gamma ** step)\n",
    "        if render:\n",
    "            clear_output(wait=True)\n",
    "            if verbose:\n",
    "                print(f\"Step {step}: Accumulated reward: {accumulated_reward}\")\n",
    "            env.render()\n",
    "        # If the simulation is done, stop\n",
    "        if done:\n",
    "            break\n",
    "    del env\n",
    "\n",
    "    return accumulated_reward"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "e6cb3f56",
   "metadata": {},
   "source": [
    "Now we are ready to simulate a single episode.\n",
    "\n",
    "Try to run the next cell multiple times and see what happens."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "d184b8a1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Step 138: Accumulated reward: -214.0\n",
      "+-----------------------+\n",
      "| : |F: | : | : | : |F: |\n",
      "| : | : : : | : | : | : |\n",
      "| : : : : : : : : : : : |\n",
      "| : : :\u001b[43m \u001b[0m: : | : : : : : |\n",
      "| : : : : : | : : : : : |\n",
      "| : : : : : : : : : : : |\n",
      "| | :G| | | :G| | | : | |\n",
      "+-----------------------+\n",
      "Taxi0-YELLOW: Fuel: inf, Location: (3, 3), Engine: ON, Collided: False, Step: 139, ALIVE\n",
      "Passenger0-YELLOW: Location: Taxi0 (3, 3), Destination: (-1, -1)\n",
      "Env done: True\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "-214.0"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "GAMMA = 1.0\n",
    "run_monte_carlo_simulation(env, gamma=GAMMA, render=True, verbose=True)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "e7a3d1af",
   "metadata": {},
   "source": [
    "It is possible to notice that some simulations are really long and some are short. This shows the **variance** to which Monte Carlo simulations are exposed. This variance will be propagated to our estimates and it is the reason why we will need to run many Monte Carlo simulations to obtain a good estimate.\n",
    "\n",
    "Another important thing that we need to pay attention to is the impact of the **discount factor** $\\gamma$. Try to see what happens as you lower the value of $\\gamma$.\n",
    "\n",
    "Run the next cell multiple times and see what happens."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "9fe49c38",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Step 528: Accumulated reward: -7.384256467457955\n",
      "+-----------------------+\n",
      "| : |F: | : | : | : |F: |\n",
      "| : | : : : | : | : | : |\n",
      "| : : : : : : : : : : : |\n",
      "| : : :\u001b[43m \u001b[0m: : | : : : : : |\n",
      "| : : : : : | : : : : : |\n",
      "| : : : : : : : : : : : |\n",
      "| | :G| | | :G| | | : | |\n",
      "+-----------------------+\n",
      "Taxi0-YELLOW: Fuel: inf, Location: (3, 3), Engine: ON, Collided: False, Step: 529, ALIVE\n",
      "Passenger0-YELLOW: Location: Taxi0 (3, 3), Destination: (-1, -1)\n",
      "Env done: True\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "-7.384256467457955"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "GAMMA = 0.70\n",
    "run_monte_carlo_simulation(env, gamma=GAMMA, render=True, verbose=True)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "6402daae",
   "metadata": {},
   "source": [
    "As you can see, with a **lower value** of $\\gamma$ the actions taken after a **high number of steps** have a very **limited impact** on the accumulated reward. This is because the reward is discounted by a factor of $\\gamma$ at each step. For this reason, the agent will care less about the actions taken after a high number of steps, limiting the horizon of its planning. For example, the agent will not care too much if it reached the passenger in 1_000 steps or in 1_100 steps. This will lead to a more **short-sighted** behaviour. \n",
    "\n",
    "More importantly, it will lower the variance of our estimates, requiring less Monte Carlo simulations to converge.\n",
    "\n",
    "Now we will see how to use Monte Carlo simulations to solve our problem."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "ba05337f",
   "metadata": {},
   "source": [
    "# Monte Carlo Control\n",
    "\n",
    "The most immediate way to exploit Monte Carlo simulations to solve our problem is to use them to estimate the **q-value function** $Q(s,a)$, i.e. the expected reward that we will get by executing action $a$ in the state $s$.\n",
    "\n",
    "## Algorithm Structure\n",
    "Monte Carlo Control follows the paradigm of Generalised Policy Iteration (GPI), which is composed of two main steps:\n",
    "1. **Policy Evaluation** (Monte Carlo Estimation for Action Values):\n",
    "   - Use Monte Carlo simulations to estimate $Q(s,a)$\n",
    "2. **Policy Improvement** (Greedy Policy Improvement):\n",
    "   - Improve the policy $\\pi$ by acting greedily with respect to $Q(s,a)$\n",
    "3. Repeat until convergence"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "4b2b713c",
   "metadata": {
    "id": "4b2b713c"
   },
   "source": [
    "![monte_carlo_control_schema](https://raw.githubusercontent.com/GabrieleSerussi/mcts/main/Monte_Carlo_Control_small.png)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "4b0d407c",
   "metadata": {},
   "source": [
    "On top of this basic algorithm, we will add a **decaying $\\epsilon$-greedy policy** to allow the agent to explore the environment.\n",
    "\n",
    "Here is the complete algorithm:\n",
    "\n",
    "P.S. Ignore the line \"Unless the pair $S_t, A_t$ appears in $S_0, A_0, S_1, A_1, ..., S_{t-1}, A_{t-1}$\". This is just a technicality that can be ignored (this is a detail of the first-visit version of Monte Carlo Control, the every-visit version, which is the one we are going to use, does not check if this condition is verified)."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "20a23c14",
   "metadata": {},
   "source": [
    "# Monte Carlo Control algorithm"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "beef176e",
   "metadata": {},
   "source": [
    "![monte_carlo_control_algorithm](https://raw.githubusercontent.com/GabrieleSerussi/mcts/main/Monte_carlo_control_algorithm_book.png)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "82d8ee6f",
   "metadata": {},
   "source": [
    "Now that we have seen the pseudocode, let's see how to implement it.\n",
    "\n",
    "We have chosen to make the agent run a certain number of episodes with which the policy is updated and then the agent will take a step in the environment."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "1929d562",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "import time\n",
    "\n",
    "class MonteCarloControl:\n",
    "    def __init__(self, state, gamma:float = 0.9, train_episode_number:int=1_000,\n",
    "                 max_steps_per_episode:int = 1_000) -> None:\n",
    "        '''\n",
    "        :args state: environment with the initial state\n",
    "        :args gamma: discount factor\n",
    "        :args train_episode_number: number of episodes used to train the agent (it is only used in the function train)\n",
    "        :args max_steps_per_episode: maximum number of steps \n",
    "        '''\n",
    "        self.state = state\n",
    "        self.Q = defaultdict(lambda: defaultdict(lambda: 0))\n",
    "        self.N = defaultdict(lambda: defaultdict(lambda: 0))\n",
    "        self.visited = set()\n",
    "        self.episode_number = 0\n",
    "        self.gamma = gamma\n",
    "        self.train_episode_number = train_episode_number\n",
    "        self.max_steps_per_episode = max_steps_per_episode\n",
    "\n",
    "    def _policy(self, state, epsilon = None):\n",
    "        \"\"\"\n",
    "        Compute the action to take in a given state using the epsilon-greedy policy\n",
    "        :param state: The state in which to take the action\n",
    "        :param epsilon: The epsilon value to use for the epsilon-greedy policy (default: 1/sqrt(episode_number + 1))\n",
    "        :return: The action to take\n",
    "        \"\"\"\n",
    "        # epsilon-greedy policy\n",
    "        if epsilon is None:\n",
    "            epsilon = 1/np.sqrt(self.episode_number + 1)\n",
    "        else:\n",
    "            epsilon = epsilon\n",
    "        number_of_actions = len(self.state.unwrapped.get_action_map('taxi_0').values())\n",
    "        if np.random.random() < epsilon:\n",
    "            action = np.random.choice(number_of_actions)\n",
    "        else:\n",
    "            # convert state to use as key in Q\n",
    "            state = state.unwrapped.state().taxis[0].location\n",
    "            \n",
    "            if len(self.Q[state]) == 0:\n",
    "                action = np.random.choice(number_of_actions)\n",
    "            else:\n",
    "                action = max(self.Q[state], key=self.Q[state].get)\n",
    "        return action\n",
    "    \n",
    "    def _update(self, episode):\n",
    "        \"\"\"\n",
    "        Update the Q values using the episode\n",
    "        :param episode: The episode to use to update the Q values\n",
    "        \"\"\"\n",
    "        G = 0\n",
    "        for i, (state, action, reward) in enumerate(reversed(episode)):\n",
    "            G = (self.gamma**i) * G + reward\n",
    "            # convert state to use as key in Q\n",
    "            state = state.unwrapped.state().taxis[0].location\n",
    "            self.visited.add(state)\n",
    "            self.N[state][action] += 1\n",
    "            self.Q[state][action] += (G - self.Q[state][action]) / self.N[state][action]\n",
    "    \n",
    "    \n",
    "    def _train(self, starting_state):\n",
    "        \"\"\"\n",
    "        Generate an episode from the starting state and update the Q values\n",
    "        :args starting_state: environment with the initial state\n",
    "        \"\"\"\n",
    "        self.episode_number += 1\n",
    "        current_episode_state = deepcopy(starting_state)\n",
    "        episode = []\n",
    "        for _ in range(self.max_steps_per_episode):\n",
    "\n",
    "            action = self._policy(current_episode_state)\n",
    "            old_state = deepcopy(current_episode_state)\n",
    "            current_episode_state.step(action)\n",
    "            obs, reward, done, trunc, info = current_episode_state.last()\n",
    "            episode.append((old_state, action, reward))\n",
    "            if done:\n",
    "                break\n",
    "        self._update(episode)\n",
    "    \n",
    "    def _step(self, current_state, render:bool, step_number:int):\n",
    "        \"\"\"\n",
    "        Make a step in the environment using the current policy\n",
    "        :args current_state: environment with the current state\n",
    "        :args render: if True render the environment after the step (default False)\n",
    "        :args verbose: if True print the action executed and the Q values (default False)\n",
    "        \"\"\"\n",
    "        action = self._policy(current_state, epsilon=0)\n",
    "        old_state = current_state.unwrapped.state().taxis[0].location\n",
    "        current_state.step(action)\n",
    "        obs, reward, done, trunc, info = current_state.last()\n",
    "        if render:\n",
    "            time.sleep(1)\n",
    "            clear_output(wait=True)\n",
    "            print(f\"Step number: {step_number}\")\n",
    "            print(f\"Action executed: {current_state.unwrapped.get_action_meanings('taxi_0')[action]}\")\n",
    "            print(\"Names: | Average reward: | Number of visits:\")\n",
    "            for act, action_name in current_state.unwrapped.get_action_meanings('taxi_0').items():\n",
    "                if act == action:\n",
    "                    print(f\"{action_name}| {round(self.Q[old_state][act], 3)} | {self.N[old_state][act]} <--\")\n",
    "                else:\n",
    "                    print(f\"{action_name}| {round(self.Q[old_state][act], 3)} | {self.N[old_state][act]}\")\n",
    "            current_state.unwrapped.render()\n",
    "        return current_state, done\n",
    "\n",
    "    def run_and_update(self, number_of_simulated_episodes:int=100, max_number_of_steps:int=150, render:bool=False)-> int: \n",
    "        \"\"\"\n",
    "        Continuosly train the policy for number_of_simulated_episodes and then make a step until the simulation is done\n",
    "        or until max_number_of_steps is reached\n",
    "        :args number_of_simulated_episodes: number of episodes used to train the agent during each step (default 100)\n",
    "        :args max_number_of_steps: maximum number of steps allowed (default 150)\n",
    "        :return: the number of steps executed to reach the end of the simulation\n",
    "        \"\"\"\n",
    "        current_state = deepcopy(self.state)\n",
    "        steps = 0\n",
    "        for i in range(1,max_number_of_steps+1):\n",
    "            steps = i\n",
    "            # TRAINING STEP\n",
    "            self.episode_number = 0\n",
    "            for _ in range(number_of_simulated_episodes):\n",
    "                self._train(current_state)\n",
    "            \n",
    "            # ACTUAL STEP\n",
    "            current_state, done = self._step(current_state, render=render, step_number=i)\n",
    "            if done:\n",
    "                break\n",
    "        return steps\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "c7ad491d",
   "metadata": {},
   "source": [
    "Let's see the agent in action.\n",
    "Try to play with GAMMA and run multiple times the next cell to see how the agent behaves."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "8aa1c51c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Step number: 9\n",
      "Action executed: pickup\n",
      "Names: | Average reward: | Number of visits:\n",
      "south| 41.228 | 17\n",
      "north| 72.405 | 16\n",
      "east| 51.569 | 7\n",
      "west| 53.605 | 11\n",
      "pickup| 99.0 | 88 <--\n",
      "+-----------------------+\n",
      "| : |F: | : | : | : |F: |\n",
      "| : | : : : | : | : | : |\n",
      "| : : : : : : : : : : : |\n",
      "| : : :\u001b[43m \u001b[0m: : | : : : : : |\n",
      "| : : : : : | : : : : : |\n",
      "| : : : : : : : : : : : |\n",
      "| | :G| | | :G| | | : | |\n",
      "+-----------------------+\n",
      "Taxi0-YELLOW: Fuel: inf, Location: (3, 3), Engine: ON, Collided: False, Step: 9, ALIVE\n",
      "Passenger0-YELLOW: Location: Taxi0 (3, 3), Destination: (-1, -1)\n",
      "Env done: True\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "9"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "env = new_environment_creator(taxi_pos=(0,0), passenger_pos=(3,3))\n",
    "GAMMA = 0.99\n",
    "monte_carlo_control = MonteCarloControl(env, gamma=GAMMA, max_steps_per_episode=1_000)\n",
    "monte_carlo_control.run_and_update(number_of_simulated_episodes=10, render=True)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "d7a76d6e",
   "metadata": {},
   "source": [
    "### Considerations\n",
    "As you can see Monte Carlo Control behaves really well! Indeed it often **learns** **the optimal policy** or a policy that is really close to the optimal one (the optimal policy takes 7 steps).\n",
    "\n",
    "If so, are we done? Can we always use Monte Carlo Control to solve any problem?\n",
    "\n",
    "Unfortunately, the answer is no. Monte Carlo Control is not always applicable. In particular, it needs to store all the visited states and actions in memory. This is not always possible. For example, if we are playing a game like chess or Go where the state space and the action space are too big to fit in memory, we cannot store the Q-table that contains of all the states and actions.\n",
    "\n",
    "For this reason, we will need to use a different algorithm, which is more scalable and that collects trajectories in a wiser way: **Monte Carlo Tree Search**."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "10cac94c",
   "metadata": {},
   "source": [
    "# Monte Carlo Tree Search (MCTS)\n",
    "\n",
    "Monte Carlo Tree Search follows a different approach compared to Monte Carlo Control. Instead of storing all the visited states and actions, it will store only the **most promising** ones. This will allow us to scale to bigger problems.\n",
    "\n",
    "In order to do so, Monte Carlo Tree Search will build a **search tree** that will be used to store the most promising states and actions.\n",
    "\n",
    "A state and action are considered promising if they present good statistical values. Indeed, in order to manage the exploration-exploitation trade-off, Monte Carlo Tree Search will use the **Upper Confidence Bound** (UCB), which in our use case is called UCT, to select the most promising state and action.\n",
    "\n",
    "Let's see how it works in more detail.\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "4d2b174d",
   "metadata": {
    "id": "4d2b174d"
   },
   "source": [
    "# The 4 steps of MCTS\n",
    "\n",
    "MCTS consists of four main steps: selection, expansion, simulation, and backpropagation.\n",
    "\n",
    "1. **Selection.** Select a leaf node using **tree policy**.\n",
    "2. **Expansion.** **Add children** to the selected leaf using unexplored actions\n",
    "3. **Rollout.** From the selected child **simulate** an **episode** using the **rollout policy**\n",
    "4. **Backpropagation**. **Update** the average **value** of the nodes starting **from** the selected **child** up **to** the **root** using the results of the rollout episode\n",
    "    - ATTENTION: No values are saved for the states and actions visited by the rollout policy beyond the tree! \n",
    "\n",
    "![mcts_4_steps](https://raw.githubusercontent.com/GabrieleSerussi/mcts/main/mcts_4_steps.png)\n",
    "\n",
    "MCTS **repeats** this cycle until **no time** is left (starting at the root node each time). **Finally**, MCTS **chooses** the **action** to make from the root node according to some statistics."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "05be701a",
   "metadata": {
    "id": "05be701a"
   },
   "source": [
    "# Rollout policy and Tree policy\n",
    "\n",
    "* **Rollout policy**: a simple and cheap policy that takes care of generating actions in the **simulated trajectories**\n",
    "\n",
    "* **Tree policy**: a policy that decises how to grow the tree and that **selects** a **child node** that is most **promising** according to a selection policy, which balances exploration and exploitation of the search space. \n",
    "    * examples : $\\epsilon$-greedy, UCT\n",
    "    \n",
    "    * $ \\text{UCT} = \\underbrace{Q}_ {\\textbf{Exploitation}} + \\underbrace{C \\sqrt{\\frac{\\log(N)}{n}}}_{\\textbf{Exploration}} $\n",
    "   \n",
    "   Where: \n",
    "   - $Q$ is the average Q-value of the considered state-action pair\n",
    "   - $C$ is a constant that balances exploration and exploitation\n",
    "   - $N$ is the total number of times that the current node has been visited\n",
    "   - $n$ is the number of times that the considered child node has been visited\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "b13865a9",
   "metadata": {},
   "source": [
    "Now that we got the gist of how MCTS works we'll see its implementation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "4fc385bf",
   "metadata": {
    "id": "4fc385bf"
   },
   "outputs": [],
   "source": [
    "from copy import deepcopy\n",
    "import time\n",
    "class MonteCarloTreeSearchNode():\n",
    "    def __init__(self, state, n_simulations=100, parent=None, parent_action=None, gamma = 0.9):\n",
    "        # environment holding the current state\n",
    "        self.state = state\n",
    "        # None for the root node, otherwise it is equal to the node it is derived from.\n",
    "        self.parent = parent\n",
    "        # None for the root node, otherwise it is equal to the action which its parent carried out.\n",
    "        self.parent_action = parent_action \n",
    "        # Contains all possible actions from the current node.\n",
    "        self.children = []\n",
    "        # Number of times current node is visited.\n",
    "        self.number_of_visits = 0 \n",
    "        self.average_reward = 0\n",
    "        # Set of all of the possible actions\n",
    "        self._untried_actions = self._get_legal_actions()\n",
    "        self.terminal_state = False\n",
    "        self.gamma = gamma\n",
    "        # Number of loops with the four stages\n",
    "        self.n_simulations = n_simulations\n",
    "        # Function used to evaluate the nodes (it will be used in rendering)\n",
    "        self._evaluate_function = self._uct\n",
    "    \n",
    "    def run_and_update(self, max_number_of_steps:int = 10_000, render:bool=False)-> int:\n",
    "        \"\"\"\n",
    "        Run Monte Carlo Tree Search for at most max_number_of_steps steps.\n",
    "        :args max_number_of_steps: maximum number of steps allowed (default 10_000)\n",
    "        :args render: if True render the environment after the step (default False)\n",
    "        \"\"\"\n",
    "        if render:\n",
    "            self.state.unwrapped.render()\n",
    "        steps = 0\n",
    "        selected_node = self._best_action()\n",
    "        for i in range(1,max_number_of_steps+1):\n",
    "            steps = i\n",
    "            if not render:\n",
    "                selected_node = selected_node._best_action()\n",
    "            else:\n",
    "                selected_node, before_move_node = selected_node._best_action(render=render)\n",
    "                time.sleep(1)\n",
    "                clear_output(wait=True)\n",
    "                print(f\"Step number: {i+1}\")\n",
    "                print(f\"Action executed: {self.state.unwrapped.get_action_meanings('taxi_0')[selected_node.parent_action]}\")\n",
    "                print(\"Names: | Values: | Average reward: | Number of visits:\")\n",
    "                for child in before_move_node.children:\n",
    "                    action_name = self.state.unwrapped.get_action_meanings('taxi_0')[child.parent_action]\n",
    "                    if child.parent_action == selected_node.parent_action:\n",
    "                        print(f\"{action_name}| {round(before_move_node._evaluate_function(child, c_param=0.8), 3)} | {round(child.average_reward, 3)} | {child.number_of_visits} <--\")\n",
    "                    else:\n",
    "                        print(f\"{action_name}| {round(before_move_node._evaluate_function(child, c_param=0.8), 3)} | {round(child.average_reward, 3)} | {child.number_of_visits}\")\n",
    "                del before_move_node\n",
    "                selected_node.state.unwrapped.render()\n",
    "            \n",
    "            if selected_node.terminal_state:\n",
    "                break\n",
    "        \n",
    "        return steps+1\n",
    "    \n",
    "    def _best_action(self, render:bool=False):\n",
    "        \"\"\"\n",
    "        Execute the four stages to find the best action from the current state.\n",
    "        \"\"\"\n",
    "        for _ in range(self.n_simulations):\n",
    "            node = self._tree_policy()\n",
    "            reward = node._rollout()\n",
    "            node._backpropagate(reward)\n",
    "        if not render:\n",
    "            return self._best_child(c_param=0.)\n",
    "            #return self.children[np.argmax([child.number_of_visits for child in self.children])]\n",
    "        else:\n",
    "            return self._best_child(c_param=0.), self\n",
    "            #return self.children[np.argmax([child.number_of_visits for child in self.children])], self\n",
    "\n",
    "    def _tree_policy(self):\n",
    "        \"\"\"\n",
    "        Select node from which we run the rollout.\n",
    "        \"\"\"\n",
    "        current_node = self\n",
    "        while not current_node._is_terminal_node():\n",
    "            # if there is an action that has not been tried yet, return the child node corresponding to this action\n",
    "            if not current_node._is_fully_expanded():\n",
    "                return current_node._expand()\n",
    "            # else select the best child node\n",
    "            else:\n",
    "                current_node = current_node._best_child()\n",
    "        return current_node\n",
    "\n",
    "    def _is_terminal_node(self):\n",
    "        \"\"\"\n",
    "        This is used to check if the current node is terminal or not. \n",
    "        Terminal node is reached when the game is over.\n",
    "        \"\"\"\n",
    "        return self.terminal_state\n",
    "    \n",
    "    def _is_fully_expanded(self):\n",
    "        \"\"\"\n",
    "        All the actions are poped out of _untried_actions one by one. \n",
    "        When it becomes empty, that is when the size is zero, it is fully expanded.\n",
    "        \"\"\"\n",
    "        return len(self._untried_actions) == 0\n",
    "\n",
    "    def _expand(self):\n",
    "        \"\"\"\n",
    "        Select an action that has not been tried yet and return the corresponding child node.\n",
    "        \"\"\"\n",
    "        # select an action that has not been tried yet\n",
    "        action = self._untried_actions.pop()\n",
    "        \n",
    "        new_state = deepcopy(self.state)\n",
    "        new_state.step(action)\n",
    "        obs, reward, done, trunc, info = new_state.last()\n",
    "        child_node = MonteCarloTreeSearchNode(state = new_state, n_simulations=self.n_simulations,\n",
    "                                            parent=self, parent_action=action, gamma=self.gamma)\n",
    "        child_node.terminal_state = done\n",
    "        child_node.average_reward = reward\n",
    "        child_node.number_of_visits = 1\n",
    "        self.children.append(child_node)\n",
    "\n",
    "        return child_node\n",
    "    \n",
    "    def _best_child(self, c_param=0.8):\n",
    "        \"\"\"\n",
    "        Once fully expanded, this function selects the best child out of \n",
    "        the children array. The first term in the formula corresponds to \n",
    "        exploitation and the second term corresponds to exploration.\n",
    "        \"\"\"\n",
    "        choices_weights = [self._uct(child, c_param) for child in self.children] \n",
    "        return self.children[np.argmax(choices_weights)]\n",
    "    \n",
    "    def _uct(self, child, c_param):\n",
    "        if self.number_of_visits == 0 or child.number_of_visits == 0:\n",
    "            return float(\"inf\")\n",
    "        return child.average_reward + \\\n",
    "                c_param*np.sqrt(np.log(self.number_of_visits)/child.number_of_visits)\n",
    "    \n",
    "    def _rollout(self):\n",
    "        \"\"\"\n",
    "        From the current state, entire game is simulated till there is an \n",
    "        outcome for the game. This outcome of the game is returned.\n",
    "        \"\"\"\n",
    "        current_rollout_state = deepcopy(self.state)\n",
    "\n",
    "        _reward = 0\n",
    "        step = 0\n",
    "        done = current_rollout_state.last()[2]\n",
    "        while not done:\n",
    "            possible_moves = self._get_legal_actions()\n",
    "            action = self._rollout_policy(possible_moves)\n",
    "            current_rollout_state.step(action)\n",
    "            obs, reward, done, trunc, info = current_rollout_state.last()\n",
    "            _reward += reward *(self.gamma ** step)\n",
    "            step += 1\n",
    "        return _reward\n",
    "    \n",
    "    def _get_legal_actions(self): \n",
    "        ''' \n",
    "        Returns a list of all of the possible actions from current state.\n",
    "        '''\n",
    "        return list(self.state.unwrapped.get_action_map('taxi_0').values())\n",
    "    \n",
    "    def _rollout_policy(self, possible_moves):\n",
    "        \"\"\"\n",
    "        Randomly selects a move out of possible moves.\n",
    "        \"\"\"\n",
    "        return possible_moves[np.random.randint(len(possible_moves))]\n",
    "\n",
    "    def _backpropagate(self, reward):\n",
    "        \"\"\"\n",
    "        In this step all the statistics for the nodes are updated. \n",
    "        Untill the parent node is reached, the number of visits for \n",
    "        each node is incremented by 1.\n",
    "        \"\"\"\n",
    "        self.number_of_visits += 1.\n",
    "        self.average_reward = self.average_reward + (1/self.number_of_visits)*(reward-self.average_reward)\n",
    "        if self.parent:\n",
    "            self.parent._backpropagate(reward)  "
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "e6b41c21",
   "metadata": {},
   "source": [
    "Now let's see how Monte Carlo Tree Search behaves in our problem."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "8711d99d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Step number: 11\n",
      "Action executed: pickup\n",
      "Names: | Values: | Average reward: | Number of visits:\n",
      "pickup| 1.495 | 1.303 | 76.0 <--\n",
      "west| -2.417 | -3.603 | 2.0\n",
      "east| -4.873 | -6.059 | 2.0\n",
      "north| -3.739 | -4.925 | 2.0\n",
      "south| -2.191 | -3.376 | 2.0\n",
      "+-----------------------+\n",
      "| : |F: | : | : | : |F: |\n",
      "| : | : : : | : | : | : |\n",
      "| : : : : : : : : : : : |\n",
      "| : : :\u001b[43m \u001b[0m: : | : : : : : |\n",
      "| : : : : : | : : : : : |\n",
      "| : : : : : : : : : : : |\n",
      "| | :G| | | :G| | | : | |\n",
      "+-----------------------+\n",
      "Taxi0-YELLOW: Fuel: inf, Location: (3, 3), Engine: ON, Collided: False, Step: 11, ALIVE\n",
      "Passenger0-YELLOW: Location: Taxi0 (3, 3), Destination: (-1, -1)\n",
      "Env done: True\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "11"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "env = new_environment_creator(taxi_pos=(0,0), passenger_pos=(3,3))\n",
    "N_SIMULATIONS = 20\n",
    "GAMMA = 0.78\n",
    "mcts = MonteCarloTreeSearchNode(state=env, n_simulations=N_SIMULATIONS, gamma=GAMMA)\n",
    "mcts.run_and_update(max_number_of_steps=1000, render=True)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "1cc340cd",
   "metadata": {},
   "source": [
    "As you can see, despite the fact that we are using much less data, Monte Carlo Tree Search is still able to learn a good policy."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "da0a5e14",
   "metadata": {},
   "source": [
    "We've seen **Monte Carlo Control** and **Monte Carlo Tree Search** algorithms.\n",
    "\n",
    "In order to make a more rigorous comparison between the two, we define a helper function *evaluate_policy* that runs a specific algorithm (either MCC or MCTS) for a specific number of simulations and *plot_steps_per_simulations* which will take care of creating a plot out of it. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "78402ad8",
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "\n",
    "def evaluate_policy(problem, algorithm, simulations, render:bool=True):\n",
    "    if not algorithm in [\"Monte Carlo Control\", \"Monte Carlo Tree Search\"]:\n",
    "        raise ValueError(\"Algorithm must be one among: Monte Carlo Control, Monte Carlo Tree Search\")\n",
    "      \n",
    "    env = new_environment_creator(taxi_pos=problem[\"taxi_pos\"], passenger_pos=problem[\"passenger_pos\"],domain_map=problem[\"domain_map\"])\n",
    "\n",
    "    if algorithm == \"Monte Carlo Control\":\n",
    "        # Monte Carlo Control\n",
    "        monte_carlo_control = MonteCarloControl(env, gamma=0.99, max_steps_per_episode=1_000)\n",
    "        step = monte_carlo_control.run_and_update(number_of_simulated_episodes=simulations, render=render)\n",
    "        return step\n",
    "\n",
    "    elif (algorithm==\"Monte Carlo Tree Search\"):\n",
    "        # Monte Carlo Tree Search\n",
    "        mcts = MonteCarloTreeSearchNode(state = env, n_simulations=simulations, gamma=0.78)\n",
    "        step = mcts.run_and_update(max_number_of_steps=1000, render=render)\n",
    "        return step\n",
    "    \n",
    "def plot_steps_per_simulations(filename, problem, algorithms, simulations_per_step, number_of_experiments, render:bool=False):\n",
    "\n",
    "    data_to_plot = [[] for _ in range(len(algorithms))]\n",
    "\n",
    "    \n",
    "    for sim in simulations_per_step:\n",
    "        for i, algorithm in enumerate(algorithms): \n",
    "            print(f\"{algorithm} for {sim} simulations\")\n",
    "            steps=0\n",
    "            for _ in range(number_of_experiments):\n",
    "                steps += evaluate_policy(problem, algorithm ,sim, render=render)\n",
    "            data_to_plot[i].append(steps/number_of_experiments)\n",
    "\n",
    "    print(\"Experiments' results:\")\n",
    "    print(data_to_plot)\n",
    "\n",
    "    _, ax = plt.subplots(1, 1, figsize=(12, 3))\n",
    "    ax.set_title(f\"Performance\")\n",
    "    for i, algorithm in enumerate(algorithms): \n",
    "        ax.plot(simulations_per_step, data_to_plot[i], '-o', label=algorithm)\n",
    "    ax.set_xlabel(\"Simulations per step\")\n",
    "    ax.set_ylabel(\"Steps\")\n",
    "    ax.grid()\n",
    "    ax.legend()\n",
    "    plt.savefig(filename)\n",
    "    plt.show()\n",
    "\n",
    "    return data_to_plot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "2d6f9021",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Monte Carlo Control for 20 simulations\n",
      "Monte Carlo Tree Search for 20 simulations\n",
      "Monte Carlo Control for 50 simulations\n",
      "Monte Carlo Tree Search for 50 simulations\n",
      "Monte Carlo Control for 100 simulations\n",
      "Monte Carlo Tree Search for 100 simulations\n",
      "Experiments' results:\n",
      "[[8.2, 7.8, 7.0], [11.2, 10.4, 8.2]]\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAs0AAADgCAYAAAD44ltAAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAAsTAAALEwEAmpwYAABEiUlEQVR4nO3deXzU1b3/8ddnluwbENaggqJUQQRE0dpqXCpXaxWrdbne24Va7XJFW9tqW7fa5adXe1u1rVVbq62KtaJota24xX1hlUVERNkCIlsgeybJ+f3x/U4yM5lJMpAV3s/H4/vI5Hy3M4chfDj5fM/HnHOIiIiIiEhqgd7ugIiIiIhIX6egWURERESkAwqaRUREREQ6oKBZRERERKQDCppFRERERDqgoFlEREREpAMKmkVE+hAzG2pmL5tZpZn9qrf7IyIinlBvd0BEZG9gZmuAoUATUA38C/gf51xVmpe6BNgKFDgtpC8i0mdopllEpOt8wTmXB0wGpgDXdPZE8wSAA4B3dydgNjNNhIiIdBMFzSIiXcw5V4430zzezI4xs9fNrMLM3jGz0uhxZlZmZr8ws9eAGuAvwFeAH5pZlZmdYmaZZvYbM9vob78xs0z//FIz22BmV5nZx8CfzewGM/u7mT3gp3gsNbNDzOxHZvaJma03s1Nj+vA1M1vhH/uhmV0asy96/Sv9czeZ2ddi9meb2a/MbK2Z7TSzV80s29+X8n2LiPRHCppFRLqYme0HnA5sAp4Gfg4MBL4PzDazwTGH/zdeSkY+8DXgQeB/nXN5zrnngJ8AxwATgSOAo4mfwR7mX/sA/zoAXwD+CgwAFgHP4P28LwFuBO6KOf8T4AygwL//r81scsL1C/1zvw78zswG+PtuBY4EPu334YdAs5mVdOJ9i4j0KwqaRUS6zhwzqwBeBV4CNgD/dM790znX7Jx7FpiPF1BH3eecW+6ca3TORZJc8yLgRufcJ865LcBP8QLtqGbgeudcvXOu1m97xTn3jHOuEfg7MBi4yb/+w8AoMysCcM497Zxb7TwvAXOBz8ZcP+LfP+Kc+ydQBYz1U0lmAJc758qdc03Oudedc/XAf3XifYuI9CsKmkVEus5051yRc+4A59y38R4M/JKfolDhB9SfAYbHnLO+g2uOANbGfL/Wb4va4pyrSzhnc8zrWmCrc64p5nuAPAAzO83M3jSz7X7/TgeKY87f5gffUTX+ucVAFrA6SZ8PoOP3LSLSr+ihERGR7rMe+Ktz7hvtHNPRA38b8YLQ5f73+/ttnT0/JT83ejbwZeAJ51zEzOYA1onTtwJ1wEHAOwn7OvO+RUT6Fc00i4h0nweAL5jZNDMLmlmW/3DdyDSuMQu4xswGm1kxcJ1/3a6QAWQCW4BGMzsNOLX9UzzOuWbgXuD/zGyE//6O9QPxrnjfIiJ9ioJmEZFu4pxbD5wF/BgvMF0P/ID0fvb+HC8feAmwFFjot3VF/yqBmcAjwA7gP4En07jE9/0+zQO2AzcDgS563yIifYpp7XwRERERkfbpf/0iIiIiIh1Q0CwiIiIi0gEFzSIiIiIiHVDQLCIiIiLSAQXNIiIiIiId6BfFTYqLi92oUaN6/L7V1dXk5ub2+H37K41X+jRm6dF4pUfjlR6NV3o0XunReKWnN8drwYIFW51zgxPb+0XQPGrUKObPn9/j9y0rK6O0tLTH79tfabzSpzFLj8YrPRqv9Gi80qPxSo/GKz29OV5mtjZZu9IzREREREQ6oKBZRERERKQDCpqTWfII/Ho8J5RNh1+P974XERERkX1Wv8hp7lFLHoF/zIRILQawc733PcCE83qzZyIiInutSCTChg0bqKur6+2udIvCwkJWrFjR293oN3pivLKyshg5ciThcLhTxytoTvT8jRCpjW+L1MIzP4H9j4WCERAI9k7fRERE9lIbNmwgPz+fUaNGYWa93Z0uV1lZSX5+fm93o9/o7vFyzrFt2zY2bNjA6NGjO3WOguZEOzckb6/+BH4zHgIhKCiBov1bt8L9Wl8XlEBQwyoiIpKOurq6vTZglr7HzBg0aBBbtmzp9DmK7hIVjvRSMhLlDoaTroGKda3b6hehchPgWo+zQGtQHRtMF/mvC0ZCKKPH3o6IiEh/oYBZelK6nzcFzYlOvq4lp7lFOBum/TJ5TnNjvTc7vXN9TEDtv177Gix9BFxzzAkG+cPbBtNF+0Ph/l7QHs7q9rcpIiIi8cyMiy66iAceeACAxsZGhg8fztSpU3nqqafSvl5FRQUPPfQQ3/72t9M6r6qqiiuvvJLnnnuOoqIi8vPzufnmm5k6dWqnr1FaWsqtt97KlClTOnV8JBLh2muvZfbs2eTn55OZmcl1113HaaedllbfAebMmcMhhxzCYYcdltZ56fa5pyloThQNjJ+/EbdzA1Y40gukUz0EGMqEQQd5WzJNEdhV3hpIR7ed62H9m7BsNrim+HPyhiUE0/tB0QGtQXY4u+ver4iISD80Z1E5tzyzko0VtYwoyuYH08YyfVLJHl0zNzeXZcuWUVtbS3Z2Ns8++ywlJbt/zYqKCn7/+9+nHTRffPHFjB49mlWrVhEIBPjoo4949913O31+U1NTxwcluPbaa9m0aRPLli0jMzOTzZs389JLL6V9HfCC5jPOOCNp0NzY2Ego1D/Dz27rtZndC5wBfOKcG++3fQm4ATgUONo51/Nl/jpjwnkw4Txe6opqNMEwDBjlbck0NXopHrHBdMVa73X5Qnj3SWiOxJ+TOzhJ+kdMgJ2Zt2d9FhER6cPmLCrnR48tpTbiBYflFbX86LGlAHscOJ9++uk8/fTTnHvuucyaNYsLL7yQV155BYDt27czY8YMPvzwQ3Jycrj77ruZMGECN9xwA+vWrePDDz9k3bp1XHHFFcycOZOrr76a1atXM3HiRE444QRuu+02brnlFh555BHq6+s5++yz+elPfxp3/9WrV/PWW2/x4IMPEgh4KwOPHj265WG16dOns379eurq6rj88su55JJLAMjLy+PSSy/lueee43e/+13cNWfNmsUvf/lLnHN8/vOf5+abb47bX1NTwz333MNHH31EZmYmAEOHDuW8885r9/y8vDwuv/xynnrqKbKzs3niiSdYvXo1Tz75JC+99BI///nPmT17Nl//+teZOHEir776KhdeeCETJ07k+9//Po2NjRx11FHceeedLffty7oz1L8P+C3wl5i2ZcAXgbu68b79SzDkzyrvBxzXdn9zE1R+HJP+sbZ11vrjpbDyX9BUH39O9sC2wXRsUJ1V0CNvTUREZHf89B/LeXfjrpT7F62roKGpOa6tNtLEDx9dwqy31yU957ARBVz/hXEd3vuCCy7gxhtv5IwzzmDJkiXMmDGjJWi+/vrrmTRpEnPmzOGFF17gy1/+MosXLwbgvffe48UXX6SyspKxY8fyrW99i5tuuolly5axePFiKisrmTt3LqtWreLtt9/GOceZZ57Jyy+/zPHHH99y/+XLlzNx4kSCweQrdd17770MHDiQ2tpajjrqKM455xwGDRpEdXU1U6dO5Ve/+lXc8Rs3buSqq65iwYIFDBgwgFNPPZU5c+Ywffr0lmM++OAD9t9/fwoK2sYH7Z1fXV3NMcccwy9+8Qt++MMfcs8993DNNddw5plncsYZZ3Duuee2XKehoYH58+dTV1fHwQcfzPPPP88hhxzCl7/8Ze68806uuOKKDv9selu3Bc3OuZfNbFRC2wpQon9aAkEoLPG2/Y9pu7+52VvZIzb1IzpjveU9WDUXGhPWvMwqSh5MR19nF/XEOxMREdktiQFzR+3pmDBhAmvWrGHWrFmcfvrpcfteffVVZs+eDcBJJ53Etm3b2LXLC+4///nPk5mZSWZmJkOGDGHz5s1trj137lzmzp3LpEmTAC93edWqVXFBc0duv/12Hn/8cQDWr1/PqlWrGDRoEMFgkHPOOafN8fPmzaO0tJTBgwcDcNFFF/Hyyy/HBc3tae/8jIwMzjjjDACOPPJInn322ZTXOf/88wFYuXIlo0eP5pBDDgHgK1/5Cr/73e/27aB5T5nZJcAl4P2KoKysrMf7UFVV1Sv33X3F3pY/GfKBkYBzhCM7yar7pO22bglZ7z9HsDk+qG4M5lCXNcTfBlOXNTTm9RAaQ/mQ5D8+/W+8ep/GLD0ar/RovNKj8UpPV49XYWEhlZWVAHyvdP92jz31jrfYtKu+Tfvwgkz++J/jU54XvX57KisrmTZtGldeeSX//Oc/2b59O42NjVRWVtLc3ExVVVXLdZxzVFZWUl9fTzgcbmk3MyoqKgBobm6msrKSpqYm6uvr+e53v8uMGTNS9uuAAw5g8eLFVFRUtJltfuWVV3jmmWeYO3cuOTk5nH766Wzfvp3KykqysrKoqalpObapqYnq6mpqa2uJRCIt96irq6OhoSHunkOHDmXt2rWUl5e3mW1u7/xwOExVVRXgzSTX1tZSWVlJJBJpeR3tS/R9VldX09TU1LKvpqamZXyjfY6+7syf156qq6vr9Oe4zwbNzrm7gbsBpkyZ4vY4t3g3lHVFTnNf5xzUbIedrbPUoYr15FWsI69iHWxZAQ0JH9qMvKTL6S3YtZUjp0yH3OKkQbW0tU98xrqQxis9Gq/0aLzS09XjtWLFik4Xs7jqtEPjcpoBssNBrjrt0D0uiJGfn8+3vvUthg4dyjHHHENZWRmhUIj8/HxOOOEEnnjiCa699lrKysoYPHgwJSUlLTPM0XsHAgHy8vLIz8+nurqa/Px8Kisr+cIXvsC1117L17/+dfLy8igvLyccDjNkyJCW+x9xxBEcddRR3HrrrfzsZz/DzFizZg3Lly+nsbGR4uJihg4dynvvvce8efPIyclpuW/sew8Gg+Tm5nLCCSdw1VVXUV9fz4ABA3j88ce57LLL4o7Nz8/n4osv5pprruGuu+4iIyODLVu2UFZW1uH50a/Z2dmEw2Hy8/MZOHAgjY2NLfuifcnPz2fy5MmsX7+ezZs3M2bMGGbPns3JJ59Mfn5+3HE9VQwmKyurZea/I302aJYeYga5g7xtRJIPjXNQVxG/lF7sA4vr34S6nQAcCbDw+xDKTrKcXswKIHlDFFSLiMhuiz7s19WrZ0SNHDmSmTNntmm/4YYbmDFjBhMmTCAnJ4f777+/3esMGjSI4447jvHjx3PyySdz2223sWLFCo499ljAe5DugQceiAuaAf74xz9y5ZVXMmbMGLKzsykuLuaWW25hwoQJ/OEPf+DQQw9l7NixHHNMkrTNBMOHD+emm27ixBNPbHmQ76yzzmpz3M9//nOuueYaDjvsMLKyssjNzeXGG2/s9PmxLrjgAr7xjW9w++238+ijj8bty8rK4s9//jNf+tKXWh4E/OY3v9nh++gLzDnX8VG7e3Evp/mp6OoZMe1lwPc7u3rGlClT3Pz5Pb/QhmYdOqluJ1SsZ+mrT3P4fkVtH1is3R5/fDCzNaBumbE+oLUtbxj4Twzv7fQZS4/GKz0ar/RovNLTHTPNhx56aJddr69RGe309NR4JfvcmdkC51ybxaK7c8m5WUApUGxmG4Drge3AHcBg4GkzW+ycm9ZdfZAeklUIwwrZVrwVppa23V9flVD8JWb7eClUJ5SwDGa0LVUeO2NdMMJ7QFJERESkh3Tn6hkXptj1eHfdU/qozDwYcqi3JdNQ4wfVMWtUR4PsVXOhKuEJ5ECobVAdm2NdUOIt5SciIiLSRRRZSO/LyIHBY70tmUidV6q8Ym3bcuWrX/SKwxCTZmSB1qA6yQOLFIyEUEaPvDURERHZOyholr4vnAXFY7wtmcYG2LUhPpiOvl77Gix9BFzs2p0G+cPbBtNF+0Ph/lA40runiIiIiE9Bs/R/oQwYeKC3JdMUgV3l8cF0NAVk/ZuwbDa4pvhz8oalXv2jaD8IZ3f/+xIREZE+Q0Gz7P2CYRgwytuSaWr0UjwSl9OrWAflC+HdJ6E5En9O7uAk6R8xAXZmXne/KxEREelBCppFgiF/Vnk/4Li2+5uboPLjmHzqmOX0Pl4KK/8FTQmVqbIHJl/9IxpUZxW0vY+IiPQqM+Oiiy7igQceAKCxsZHhw4czdepUnnrqqbSvV1FRwUMPPcS3v/3ttM6rqqriyiuv5LnnnqOoqIj8/Hxuvvlmpk6d2ulrlJaWcuuttzJlSpuV09o4++yz+eijj6iqqmLLli2MHj0agN///vd8+tOfTqvvqfziF7/goYceIhgMEggEuOuuu9J6P+koKyvj1ltv3a0/s/YoaBbpSCAIhSXetn+SheSbm6H6k7bL6e1cD1ve81YAaYwvVU5WERTtz7jGbKh7pu2sdXZRT7wzEZH+a8kj8PyN3oPihSPh5Otgwnl7dMnc3FyWLVtGbW0t2dnZPPvss5SU7H7BlIqKCn7/+9+nHTRffPHFjB49mlWrVhEIBPjoo4949913O31+tGx1Zz3+uLewWapgs7GxkVBo90PGN954g6eeeoqFCxeSmZnJ1q1baWho2O3rdVW/0qWgWWRPBQKQP8zb9ju67X7noHpr6yx1zAogOeXvwYL7IVIdf05mQfLl9Ir83OrsAaqqKCL7riWPwD9mQqTW+37neu972OPA+fTTT+fpp5/m3HPPZdasWVx44YW88sorAGzfvp0ZM2bw4YcfkpOTw913382ECRO44YYbWLduHR9++CHr1q3jiiuuYObMmVx99dWsXr2aiRMncsIJJ3Dbbbdxyy238Mgjj1BfX8/ZZ5/NT3/607j7r169mrfeeosHH3yQgF/oa/To0S2zv9OnT2f9+vXU1dVx+eWXc8kllwBedcFLL72U5557jt/97ndx15w1axa//OUvWyr63XzzzR2Ow3333cdjjz1GVVUVTU1N/POf/+Syyy5j2bJlRCIRbrjhBs466yyampq4+uqrKSsro76+nu985ztceumlcdfatGkTxcXFZGZmAlBcXNyyb8GCBXzve9+jqqqK4uJi7rvvPoYPH859993HX/7yFxoaGhgzZgx//etfycnJ4atf/SpZWVksWrSI4447jm9/+9t885vfZMuWLQSDQf7+978D3mz9ueeey7JlyzjyyCN54IEHsD38d1NBs0h3M4O8wd428si4XfPKyig94QSo2Q4717VdAWTHWvjoFWiojL9mRl7y5fSiK4DkFiuoFpH+619Xe+lvqWyY1zYtLlILT/yPNxGRzLDD4bSbOrz1BRdcwI033sgZZ5zBkiVLmDFjRkvQfP311zNp0iTmzJnDCy+8wJe//GUWL14MwHvvvceLL75IZWUlY8eO5Vvf+hY33XQTy5YtY/HixVRWVjJ37lxWrVrF22+/jXOOM888k5dffpnjjz++5f7Lly9n4sSJBIPJi3jde++9DBw4kNraWo466ijOOeccBg0aRHV1NVOnTuVXv/pV3PEbN27kqquuYsGCBQwYMIBTTz2VOXPmMH369A7HYuHChSxZsoSBAwfy4x//mJNOOol7772XiooKjj76aE455RQefPBBCgsLmTdvHvX19Rx33HGceuqpLUE+wKmnnsqNN97IIYccwimnnML555/PCSecQCQS4bLLLuOJJ55g8ODB/O1vf+MnP/kJ9957L1/4whe47LLLALjmmmv405/+1PL9hg0beP311wkGg0ydOpWrr76as88+m7q6Opqbm1m/fj2LFi1i+fLljBgxguOOO47XXnuNz3zmMx2+5/YoaBbpbWaQO8jbRkxqu985qKtou5xe9IHF9W96pcxjhbKTBNMxK4DkDVFQLSL9V2LA3FF7GiZMmMCaNWuYNWsWp59+ety+V199ldmzZwNw0kknsW3bNnbt2gXA5z//eTIzM8nMzGTIkCFs3ry5zbXnzp3L3LlzmTTJ+1lfVVXFqlWr4oLmjtx+++0t6RTr169n1apVDBo0iGAwyDnnnNPm+Hnz5lFaWsrgwYMBuOiii3j55Zc7FTR/7nOfY+DAgS19f/LJJ7n11lsBqKurY926dcydO5clS5bw6KOPArBz505WrVoVFzTn5eWxYMECXnnlFV588UXOP/98brrpJqZMmcKyZcv43Oc+B3hpJcOHDwe88tb//d//TUVFBVVVVUyb1lpA+ktf+hLBYJDKykrKy8s5++yzAcjKal0u9uijj2bkyJEATJw4kTVr1ihoFtnrmXnpGNkDYPgRyY+p29kaUCc+sFi+EGq3xx8fzGwNqFtmrA9obcsb5qWdiIj0ho5mhH893vtZl6hwP/ja03t8+zPPPJPvf//7lJWVsW3btk6dE009AAgGgzQ2NrY5xjnHj370ozbpC7HGjRvHO++8Q1NTU5vZ5rKyMp577jneeOMNcnJyKC0tpa7Oe2YmKysr5ez07srNzY3r++zZsxk7Nr4QmXOOO+64Iy6oTSYYDFJaWkppaSmHH344999/P0ceeSTjxo3jjTfeaHP8t771LZ544gmOOOII7rvvPsrKypL2K5XO/HmkS0GzyN4gqxCGFcKw8cn311clVFOM2T5eCtVb4o8PZrQtVR47Y10wwntAUkSkN5x8XXxOM3jr5598XZdcfsaMGRQVFXH44YfHBWuf/exnefDBB7n22mspKyujuLiYgoLUqyHl5+dTWdmaXjdt2jSuvfZaLrroIvLy8igvLyccDjNkyJCWYw466CCmTJnC9ddfz89+9jPMjDVr1rB8+XIaGxsZMGAAOTk5vPfee7z55psdvpejjz6amTNnsnXrVgYMGMCsWbNa0hzSMW3aNO644w7uuOMOzIxFixYxadIkpk2bxp133slJJ51EOBzm/fffp6SkJC6wXblyJYFAgIMPPhiAxYsXc8ABBzB27Fi2bNnCG2+8wbHHHkskEuH9999n3LhxVFZWMnz4cCKRCA8++GDSBzLz8/MZOXJkS7pJfX192g9BpkNBs8i+IDMPhhzqbck01PhBdcwa1dEge9VcqEr4NWMg1Daojs2xLijxlvITEekO0Yf9unj1jKiRI0cyc+bMNu033HADM2bMYMKECeTk5HD//Snyp32DBg3iuOOOY/z48Zx88sncdtttrFixgmOPPRbw0hYeeOCBuKAZ4I9//CNXXnklY8aMITs7m+LiYm655RYmTJjAH/7wBw499FDGjh3LMcckWdEpwfDhw7nppps48cQTWx4EPOuss9IYDc+1117LFVdcwYQJE2hubmb06NE89dRTXHzxxaxZs4bJkyfjnGPw4MHMmTMn7tyqqiouu+wyKioqCIVCjBkzhrvvvpuMjAweffRRZs6cyc6dO2lsbOSKK65g3LhxXHPNNUydOpXBgwczderUuP98xPrrX//KpZdeynXXXUc4HG55ELA7mHOu2y7eVaZMmeLmz5/f4/ctKyujtLS0x+/bX2m80tdvxixS5/3DlLD6R0tKSOUmIOZniQVag+pkDywWjPQqOXaWv7SU27kB6+J/HPdm/ebz1UdovNLT1eO1YsUKDj00xX/s9wKVlZXk5+f3djf6jZ4ar2SfOzNb4Jxrs8C1poJEpGPhLCge423JNDbArg1tg+mKdbD2NVj6CLjmmBMM8oenXv2jcKR3T4hbWsqgS5eWEhER6SwFzSKy50IZMPBAb0umKQK7ypOs/rHOW/1j2WxwCXloecO8YHrzsvi8RfC+f/5GBc0iItJjFDSLSPcLhmHAKG9LpqnRS/FItvpHYsActXM9zPuTt0zf0PHppXuIiIikSUGziPS+YMhP0div7b5US0tZAJ7+nn9+Bgwd5wXQIybBiMkw+FN6GFGkn3HO7XHVNpHOSve5Pv2LIiJ9W6qlpb5wO+w3FTYu8reFsHQ2zL/XOyaU7VUAGzEJSiZ7XweN0VJ5In1UVlYW27ZtY9CgQQqcpds559i2bVtcQZSOKGgWkb4tZmmppKtnDDgAxk33Xjc3w46PvCC6fKH3ddED8PZd3v6MPK9ATMuM9CQvD1v/QIv0upEjR7Jhwwa2bNnS8cH9UF1dXVoB2r6uJ8YrKyurpWpgZyhoFpG+b8J5MOE8XupoiatAAAYd5G2Hn+u1NTfB1vdjZqQXwdv3tJbbzSqMD6JHTPKWyVMgLdKjwuFwXOnlvU1ZWVlL+WzpWF8cLwXNIrJ3CwRbC7tM/E+vrSkCn6yIT+14/Q5o9sus5hTHB9ElkyF/WO+9BxER6XUKmkVk3xMMw/AJ3nbkV7y2SB18srw1kC5fBKufb11fOn94/IOGIyZCbnGvvQUREelZCppFRMArplJypLdFNdTAx0tbZ6M3LoKV/6Kl+mHh/l7wHH3QcPhEyC7q+b6LiEi3U9AsIpJKRg7sP9Xboup2waZ34nOkVzzZun/ggf5MtD8rPXwCZKp0rohIf6egWUQkHVkFMPqz3hZVsx02LW4Note9Ccse9XcaDB4bnyM97HBv2TwREek3FDSLiOypnIFw0EneFlX1CWxc3Jra8cHz8M4sb58FYchhXmpH9EHDIeNU1VBEpA/rtqDZzO4FzgA+cc6N99sGAn8DRgFrgPOcczu6qw8iIr0mbwgccqq3ATjnlQqPXUP6vadh0V+9/S1VDWNSO1TVUESkz+jOn8b3Ab8F/hLTdjXwvHPuJjO72v/+qm7sg4hI32AGBSO87VOf99qcg4p1rQ8ZblwES/8O8//k7Q9leznRsakdqmooItIrui1ods69bGajEprPAkr91/cDZShoFpF9lZlX0XDAATDubK+tuRm2fxj/oOHCv8Jbf/D2Z+R5q3REUztU1VBEpEeYc677Lu4FzU/FpGdUOOeK/NcG7Ih+n+TcS4BLAIYOHXrkww8/3G39TKWqqoq8vLwev29/pfFKn8YsPfvseLkmcmrKya/8gPzKDyjYtYq8qo8IuAgAkVAulflj/O1gKvPHUJ9ZTFV19b45Xrtpn/187SaNV3o0XunpzfE68cQTFzjnpiS291qynHPOmVnKiN05dzdwN8CUKVNcu6Vzu0lZRyV7JY7GK30as/RovGLEVDUMb1zIwI2LGLjhibiqhtuyDmDQ4ae0zkirqmG79PlKj8YrPRqv9PTF8erpoHmzmQ13zm0ys+HAJz18fxGRvUOqqoabl/s50ovJXPUKvHxLQlXDyfE50rmDeu89iIj0Iz0dND8JfAW4yf/6RA/fX0Rk7xXOgpFHehswv6yM0k8fFVPV0N9W/pOWqoZF+8cH0apqKCKSVHcuOTcL76G/YjPbAFyPFyw/YmZfB9YC53XX/UVEBMjIhf2P8baoNlUNF8K7MXMYAw9qDaJLJsOwCZCpXEwR2bd15+oZF6bYdXJ33VNERDqhvaqG0TWkU1Y19NM7ho1XVUMR2ado1XwREWmnqmFMWkeyqoYlMakdqmooInsxBc0iIpJc3hA4ZJq3gVeMZdfG+EB6xT9goV/DKpgBQ8fH50irqqGI7CX0k0xERDrHDApLvO3QM7w256BibWsQXb6wnaqGk2OqGgZ6732IiOwGBc0iIrL7zGDAKG9LWtXQz5Fe+JeYqob5MPwIr6phiR9IDxitqoYi0qcpaBYRka4VCEDxGG+b8CWvrbkJtr7f+qDhxkXw9j3QVO/tzyryS4PHrCNdOFKBtIj0GQqaRUSk+wWCMORQb5t0kdfWFIFP3o3PkX799taqhrmD4/OjVdVQRHqRgmYREekdwbCXpjH8CDjyq15bQlVDNi6ED56LqWo4ImYN6UkwXFUNRaRnKGgWEZG+I6GqIQAN1a1VDaPpHSufbt3fUtXQT+0YfoSqGopIl1PQLCIifVvSqoY7YdOS1gcNNy5qW9WwJCY/WlUNRWQPKWgWEZH+J6sweVXD2PzotW94y98BrVUNYwNpVTUUkc5T0CwiInuHnIEw5mRvi6rc7JUHb6lq+By885C3LxDyHkz0g+i8SgeNn1ZVQxFJSkGziIjsvfKHQn6qqoYL46oaTgFYfHVrVcNoekfxWFU1FBEFzSIisg9pp6rh8mcfZFxRnRdIJ61qGJPaoaqGIvscBc0iIrJv86sabhlyHJSWem0tVQ1jHjRceD+8dae3PyPfL8YysTWQVlVDkb2agmYREZFEcVUNz/Pamptgy8qYhw0Xwlt3J1Q1jCnEUjIZCkoUSIvsJdIOms1sALCfc25JN/RHRESkbwoEYehh3hatatjYAFtWxK8hnbKqoZ/ekT+0996DiOy2TgXNZlYGnOkfvwD4xMxec859rxv7JiIi0reFMjqoahizakdiVcMSP5hWVUORfqGzM82FzrldZnYx8Bfn3PVmpplmERGRRKmqGm5aEr+OdJuqhjEPGo6Y6K1FLSJ9RmeD5pCZDQfOA37Sjf0RERHZ+2TkwgHHeltU3U7Y9E5rEF2+EN6d07p/0Jj4HGlVNRTpVZ0Nmm8EngFec87NM7MDgVXd1y0REZG9XFYhjD7e26LaVDV8vbWqoQW8NaNjHzQcOt6b2RaRbtepoNk593fg7zHffwic012dEhER2Se1V9Uw+qDhB8+mqGrop3cMOUxVDUW6QWcfBDwQuA04BnDAG8B3/eBZREREukvKqoYxDxr6VQ0BCGZ4M9AlMTnSqmoossc6+zfoIeB3wNn+9xcAs4Cp3dEpERERSSGuquEXvDbnYMea+NSOd/4G8/7o7Q/neDnRsakdAw9SVUORNHQ2aM5xzv015vsHzOwH3dEhERERSZMZDBztbeO/6LU1N8P21fEPGqasaujPSg8YpWIsIil0Nmj+l5ldDTyMl55xPvBPMxsI4Jzb3k39ExERkd0RCEDxwd4WrWrY1Ahb32+taLhxEbx1FzQ1ePtjqxpG0ztU1VAE6HzQ7P9t49KE9gvwgugDu6xHIiIi0j2CodRVDctjcqTbVDWcHL/8naoayj6os6tnjO7Km5rZ5cA3AAPucc79piuvLyIiIp0UW9WQr3ltkTrYvCw+teODZ1urGhaUMC5jJATmta7ckTOw196CSE/o7OoZOcD3gP2dc5eY2cHAWOfcU+ne0MzG4wXMRwMNwL/N7Cnn3AfpXktERES6QTgLRk7xtqj6Kvh4aUtqR+4Hr8ELP2/dX3RAfGrH8CNU1VD2Kp1Nz/gzsAD4tP99Od66zWkHzcChwFvOuRoAM3sJ+CLwv7txLREREekJmXlxVQ3fLiuj9JhJXlXD2NSOpFUN/fSO4RO86ogi/VBng+aDnHPnm9mFAM65GrPdfipgGfALMxsE1AKnA/N381oiIiLSW9qtargQNi5OXtUwdg1pVTWUfsKccx0fZPY6cDJeGe3JZnYQMMs5d/Ru3dTs68C3gWpgOVDvnLsi4ZhLgEsAhg4deuTDDz+8O7faI1VVVeTl5fX4ffsrjVf6NGbp0XilR+OVHo1XetIZr4z6HeRXfhCzrSIjshOAZgtSnXsAlfljWrbq3P1xgXB3dr/H6fOVnt4crxNPPHGBc25KYntng+ZTgZ8AhwFzgeOArznnXtzTjpnZL4ENzrnfpzpmypQpbv78np+MLisro7S0tMfv219pvNKnMUuPxis9Gq/0aLzSs0fj5RzsKo9/0HDjIqir8PYHM2HY+JgVOyZD8SH9uqqhPl/p6c3xMrOkQXNnV8+Ya2YL8MpoG3C5c27rHnRmiHPuEzPbHy+f+ZjdvZaIiIj0M2ZQONLbklY19FM7UlU1jKZ3qKqh9KDOrp7xvHPuZODpJG27Y7af0xwBvuOcq9jN64iIiMjeoL2qhrEPGi64L0lVw5g1pFXVULpJu0GzmWUBOUCxmQ3Am2UGKABKdvemzrnP7u65IiIiso+IrWp4xPleW1MjbF3ZGkRvXARv/aG1qmH2gPggWlUNpYt0NNN8KXAFMAJvybmoSuC33dQnERERkeSCIRg6ztsm/ZfX1tgAn7wbE0gvhNdui6lqOCQ+iC6ZDHlDeu89SL/UUdD8OvAIcK5z7g4z+wpwDrAGeKib+yYiIiLSsVCGn6YxkdaqhrWweXn8g4YJVQ29IHpi6zrSqmoo7egoaL4LOMUPmI8H/h9wGTARuBs4t3u7JyIiIrIbwtntVDWMyZF+L6ZOW9EB8WtIq6qhxOgoaA4657b7r88H7nbOzcZ7kG9xt/ZMREREpCslVDUEoLbCq2rYsvzdAlj+eOv+QQfHp3aoquE+q8Og2cxCzrlGvOIml6RxroiIiEjfll0EB57gbVHV22BTND96Max5FZY+4u2zAAz+VPwa0kPHqarhPqCjwHcW8JKZbcUref0KgJmNAXZ2c99EREREel7uIBhzirdFVX7sBdDRBw3ffwYWP+jtC4RgyGHxa0gPOQyCe1dVw31du0Gzc+4XZvY8MByY61rLBwbwcptFRERE9n75w2Dsf3gbxFc1jD5o+O4TsPB+b39LVUMviM6taoTmJggEe+89yB7pMMXCOfdmkrb3u6c7IiIiIv1AyqqGH8UsfbcY3nkY5t3DUQDvXO09XBibI62qhv2G8pJFREREuoIZDDzQ28af47U1N8O2D1jx/EMcWljnpXbM/zM0/t7bn1kQH0iXTPZW8VAxlj5HQbOIiIhIdwkEYPAhbB5WyqGlpV5bbFXDaGpHyqqGfo50wQgF0r1MQbOIiIhIT2q3qmHMGtKv/gZck7c/WtUwdh1pVTXsUQqaRURERHpbXFVDX6QWPl4WkyO9CFbNBfx1GVqqGsZsqmrYbRQ0i4iIiPRF4WzY7yhvi6qvgo+XxBRjWRhf1XDAqIRiLBMhq6Cne75XUtAsIiIi0l9k5sEBn/a2qLiqhgtTVzWMpnYMO1xVDXeDgmYRERGR/qy9qobl/ox00qqGk/2UEFU17AwFzSIiIiJ7m5RVDWPyo9//Nyx+wNsXrWoY+6ChqhrGUdAsIiIisi/IHwZjT/M28Iqx7NwQH0gvnwML7vP2BzO9VI7YHOnBY/fZqoYKmkVERET2RWZQtJ+3HXam15ZY1bB8EbwzC+bd4+0P58QUY/FnpQceuE9UNVTQLCIiIiKedqoaxq0hnayqYWxqx15Y1VBBs4iIiIik5lc1ZPAhcMQFXltTI2x5Lz614807Y6oaDmy7hnQ/r2qooDmJOYvKueWZlZRX1FLy5gv8YNpYpk8q6e1uiYiIiPQNwRAMG+9tk//ba2tsgE+WxwfSr/66taph3tC2gXRiVcMlj8DzN3LCzg2waCScfB1MOK9n31sKCpoTzFlUzo8eW0ptxPsDLq+o5UePLQVQ4CwiIiKSSiijNRiOalPVcCG8/wytVQ1H+sveTYL6SnjrLmisxQB2rod/zPSO6wOBs4LmBLc8s7IlYI6qjTRxzZxlbNxZS0FWmPysEAXZYQqywhRmhyjIClOQHSYzFMD68a8dRERERLpUe1UNy2NypGOrGsaK1MLzNypo7os2VtQmba+qb+R//72y3XPDQWsJoAtiAuvWILu1rSA7RH5W6+uCrDA5GUEF3SIiIrJ3S1XV8OZRtMxAx9q5oYc61j4FzQlGFGVTniRwLinK5vkrT2BXXYRdtY3+1wi76hqpTNK2qzZCZV2ETTvr/LYIdZHmdu8dDBgFWX4wHZ3BThFgR4PwlmOzw+RlhAgEFHSLiIhIP5NdBIUjvZSMRIUje7w7yShoTvCDaWPjcpoBssNBfjBtLFnhIFnhIEPyd+/a9Y1NVNY1UukH1YkBeGVd28D7w61VLcdXNzS1e30zyM/0AmgvyI6f2U5MLYm2FWZ77flZYYIKukVERKQ3nHydl8MciZm8DGd77X2AguYE0Yf9WlbPKMrustUzMkNBMvOCFOdl7tb5jU3NMYG19zXVLPcu/7j122tagu7K+sYO75GXGdqt1JKC7DCNzUl+pSIiIiLSGdG85edvxO3cgBVq9QzM7LvAxXiJK0uBrznn6nqjL8lMn1TC9EkllJWVUVpa2tvdaREKBhiQm8GA3IzdOr+p2VFV39Esd2wAHuHjXXW8/0klu2q9NJSO4uLsF//dJoWkwJ/Jbm1LPfOdGdo3S3OKiIgIXoA84Txe6mMxGPRC0GxmJcBM4DDnXK2ZPQJcANzX033Z1wQDRmG2l46xO5qbHdUNjfF53C0BeIR3VqyiePjI1sC7LsLWqgY+3FrdMtvd0Wx0ZiiQJMhuf+a7MGbmOyusFUxERESk6/VWekYIyDazCJADbOylfkgaAgEjP8vLl4bsNvvLImspLT0s5fnOOWojTW1msytjU0oSZsF31kbYsL2mpa2hqf2HKRNXMMlP8vBkezPfWsFEREREkjHnej4P1cwuB34B1AJznXMXJTnmEuASgKFDhx758MMP92wngaqqKvLy8nr8vv1Vd4+Xc45IM9Q0Omoi0a+OmkaoiThq22v3Xze0H3MTMMgOQU7IyAkbOSH8rwmvw97r7IT2rBAE0gi69RlLj8YrPRqv9Gi80qPxSo/GKz29OV4nnnjiAufclMT2Hg+azWwAMBs4H6gA/g486px7INU5U6ZMcfPnz++ZDsboaznNfV1/GK/oCibt5XG3N/Nd08kVTPKTpJa0PkDZ2vbRyuV89pgpcfu1gklq/eEz1pdovNKj8UqPxis9Gq/09OZ4mVnSoLk30jNOAT5yzm0BMLPHgE8DKYNmka6ypyuYRJqaqUoSbCdbLtDL627scAWTm+e9Gvd9dAWTdFNLovvCwcBuvTcRERFJrTeC5nXAMWaWg5eecTLQ89PIIrsh3BUrmNS1Pij58hvzOfBT49oplOMVyImuYLKrLkJHvxzKDgdTF8FJCLaTreetFUxERETa6vGg2Tn3lpk9CiwEGoFFwN093Q+R3hAMGIU5YQpzvBVMtgwKUjpuWKfPj13BZFdt+7Pc0fboCibR/U2dWMEk2Sx3qpnvgoSZ7+5YwWTOovLWtdPffKHL1k4XERHprF5ZPcM5dz1wfW/cW6Q/i13BpKSo7QomHUm1gkl0He6OVjDZWRsh0tR+0B1dwSRZ9cmC7HBL1crEme/o8bkJK5jMWVQeV6WzvKKWHz22FECBs4iI9BhVBBTZh5gZORkhcjJCDCvMSvt85xz1jc1xVSeTznAntG3aWdsy810XaX8Jk2DAYvK2Q7y/uYqGxvhzaiNN3PiP5QwtyGJAbpgBORkU5YSVWiIiIt1GQbOIdJqZkRUOkhUOMqRg964Ru4JJqjzu1jLxjSwr35X0OttrIlx4z5txbTkZwZYAOvbrgJwwRTkZDMj1v8a0FWSFtDa3iIh0SEGziPSodFcwOe6mFyivqG3TPjg/k9+cP5EdNQ3sqIlQUe1/rWloaduwo4YdNZF2H6AMBoyi7HBMoO0F1ANykwTdMa8zQlqlRERkX6KgWUT6tB9MGxuX0wzeCiE/Of1QjhtT3KlrNDU7dtZG2FHT4AXV1dHXkdag2w+2N+yoYWm515aYFhIrNyPYMnsdG2y3BN1xM90ZFOV6+dya1RYR6Z8UNItInxZ92K9l9Yyi7LRXzwgGjIG5GQxMY6nA6EOTO2oi7KhuDbAr/CA7Mehet72GHdUN7KpruxZ3VChgFMUE1vEBdkJbzEy31t4WEel9CppFpM+bPqmE6ZNKerRCVOxDk+msVNLY1OzPakcSAuyYGW1/pnvdthreWe8F3w1NqWe18zJDqfO0WwLs+BnuvEz9eBcR6Ur6qSoi0oVCwQCD8jIZlEbVSeccNQ1NyVNGqtsG3Wu31bCjpoHKdma1w0EjOwhDF74U/3Bkbuo87aKcsGa1RURSUNAsItLLzIzczBC5mSFGDuj8eY1NzVTUxsxoV8cH3e+uXkt2YS47aiKs2VbNovUVVNQ0tLvWdn5mqCWwTpafHZen7c9yJ66tLSKyN1LQLCLST4WCAYrzMlOuRFJW9jGlpVPi2pxzVDc0JQTYsTnb8TPdH22toqI6QmV96lntjGCAwpxwyjzt2AC7ZVY7O0xIs9oi0o8oaBYR2YeYGXmZIfIyQ+w3sPPnRZqaqUiRp72jpoGKmBVJPtxSzY4ab1a7sZ2y7flZoTb52S0pI7nJVyLJ0ay2iPQSBc0iItKhcDDA4PxMBuenl6tdVd+YJE+7oc2DkturG1i9pYqKmghV7c1qhwIUZSekiuQmCboTAvFgQIG2iOwZBc0iItItzIz8rDD5WWH2G5jT6fMaGpupqPVTRRIC7NjiNRU1DXywpYqKtd73Te3MahdkhZKuMhIbYK/b2kRx+U4G5GYwMCeD7AyVZReRVgqaRUSkT8kIBRiSn8WQ/KxOn+Oco7K+sSVNJHnxGu/r1qp6Vm2uoqKmgeqGprjr3DL/1ZbXmaFAyhntVAVtCrLDmtUW2UspaBYRkX7PzCjIClOQFWb/QZ2f1a5vbGJnjbeu9ouvv82oQw6LL14TM9O98uNKL6+7NvWsthkUZqdacSRJ+oi/UklWWLPaIn2dgmYREdlnZYaCDCkIMqQgi00Dg5SOH97hOc3N/qx24kOR1YkPSkbYvKuOlR9XsqOmgZqEWe1YWeEAHS7zlxsfdBdkhQloVlukxyhoFhERSUMgYBRmhynMDnPAoM6fV9/Y1Joy0ibAjk8jWfHxrpbVSlKlageSzmq3LcOeuLa2ZrVFdo+CZhERkR6QGQoytCDI0ILO52o3Nzsq6xrbydNufb1pZx0rNu1iR02E2kjqWe3scDAuPaTdtbX9YDs/K6RZbdnnKWgWERHpowIBozAnTGFOmFHkdvq8ukjMrHZi8Zrq+KB7U8UudtQ0sLM20u6sdlFCfnbdrnpeq343ZZ52UU6YzJBmtWXvoaBZRERkL5MVDjKsMMiwwvRmtXfVRdrkaSerGFleUcfmHU3M/2QtdZHmlNfMyQi2/1BkbtuHIwuyQipgI32SgmYREREhEDB/NjmD0Z2Y1S4rK6O0tJS6SFO7edrxwXZty6y2SzGrHQwYRdnhdvO0k61EkhFSWXbpXgqaRUREZLdlhYMML8xmeGF2p89panbsqk2+jnZ89cgIG3bUsKzcO7a+MfWsdm5GMCE9pO062nEPReaGyc/UrLZ0noJmERER6VHBgDEgN4MBuRlpnVfb0JT8ocjqtkH3+u017KiJsLM2kvJ6oYBRlJNYhj1F0O3PdBdla1Z7X6WgWURERPqF7Iwg2RnZjChKb1Z7Z23qPO3YYHv99hqWbPDaGtqZ1c7LDLVTvCactGS7S5WPIv2GgmYRERHZawUDxsDcDAamMavtnKM20uTlZFfHPgjZNk97R02Eddtr2FHdwK66xtT9MBjw2nNti9fkps7TLsoJEw5qVruvUNAsIiIiEsPMyMkIkZMRoiSNWe3GpmZ/VrvtQ5HvrFhNweAhLTPda7fVsHh9BRU1ERqaUs9q52eGWgLrditGRl/nZpCbEVSudjdQ0CwiIiLSBULBAIPyMhmUl9lmX1nzekpLJ7Rpd85R4+dqt0kZqW5bMXLN1mp21DRQ2c6sdjho7eZpxwbYLbPa2WFCmtVuV48HzWY2FvhbTNOBwHXOud/0dF9EREREepOZkZsZIjczxMgBnT8v4s9qt8xoV6euGPnR1moW1lRQUdNApCl1bnV+VqhNfnZLykib6pHe15wuntWes6icW55ZSXlFLSVvvsAPpo1l+qSSLrv+nujxoNk5txKYCGBmQaAceLyn+yEiIiLSX4WDAYrzMilOMqudinOO6oamhAC7bfGaaFrJh1urqKiOUFmfelY7IxhomyqSmyTojgnEC1PMas9ZVM6PHlvaUga+vKKWHz22FKBPBM69nZ5xMrDaObe2l/shIiIislczM/IyQ+RlhthvYOfPizQ1U5EkT7vldcyKJKu3VLFjrXdsY6q67EBBVqjNKiNz3/24JWCOqo00ccszK/tE0Gy9uQSKmd0LLHTO/TbJvkuASwCGDh165MMPP9zT3aOqqoq8vLwev29/pfFKn8YsPRqv9Gi80qPxSo/GKz372ng556hrgqoGR1XE+V+Jee2ojjiqGvy2iGNrbeqY9L7/6LhKZVc58cQTFzjnpiS291rQbGYZwEZgnHNuc3vHTpkyxc2fP79nOhYjWiJUOkfjlT6NWXo0XunReKVH45UejVd6NF4dO+6mFyivqG3TXlKUzWtXn9Rj/TCzpEFzbz4meRreLHO7AbOIiIiI7P1+MG0s2eFgXFt2OMgPpo3tpR7F682c5guBWb14fxERERHpI6J5yy2rZxRl79urZwCYWS7wOeDS3ri/iIiIiPQ90yeVMH1SSZ9MZ+mVoNk5Vw0M6o17i4iIiIikS6VfREREREQ6oKBZRERERKQDvbpOc2eZ2RagNwqgFANbe+G+/ZXGK30as/RovNKj8UqPxis9Gq/0aLzS05vjdYBzbnBiY78ImnuLmc1Ptk6fJKfxSp/GLD0ar/RovNKj8UqPxis9Gq/09MXxUnqGiIiIiEgHFDSLiIiIiHRAQXP77u7tDvQzGq/0aczSo/FKj8YrPRqv9Gi80qPxSk+fGy/lNIuIiIiIdEAzzSIiIiIiHVDQ7DOz/czsRTN718yWm9nlfvtAM3vWzFb5Xwf0dl/7AjPLMrO3zewdf7x+6rePNrO3zOwDM/ubmWX0dl/7EjMLmtkiM3vK/17jlYKZrTGzpWa22Mzm+236+5iCmRWZ2aNm9p6ZrTCzYzVeyZnZWP9zFd12mdkVGq/UzOy7/s/6ZWY2y/83QD+/UjCzy/2xWm5mV/ht+nzFMLN7zewTM1sW05Z0jMxzu/9ZW2Jmk3ujzwqaWzUCVzrnDgOOAb5jZocBVwPPO+cOBp73vxeoB05yzh0BTAT+w8yOAW4Gfu2cGwPsAL7ee13sky4HVsR8r/Fq34nOuYkxyw7p72NqtwH/ds59CjgC73Om8UrCObfS/1xNBI4EaoDH0XglZWYlwExginNuPBAELkA/v5Iys/HAN4Cj8f4unmFmY9DnK9F9wH8ktKUao9OAg/3tEuDOHupjHAXNPufcJufcQv91Jd4/OCXAWcD9/mH3A9N7pYN9jPNU+d+G/c0BJwGP+u0arxhmNhL4PPBH/3tD45Uu/X1MwswKgeOBPwE45xqccxVovDrjZGC1c24tGq/2hIBsMwsBOcAm9PMrlUOBt5xzNc65RuAl4Ivo8xXHOfcysD2hOdUYnQX8xY893gSKzGx4j3Q0hoLmJMxsFDAJeAsY6pzb5O/6GBjaW/3qa/xUg8XAJ8CzwGqgwv8hAbAB7z8e4vkN8EOg2f9+EBqv9jhgrpktMLNL/Db9fUxuNLAF+LOf/vNHM8tF49UZFwCz/NcaryScc+XArcA6vGB5J7AA/fxKZRnwWTMbZGY5wOnAfujz1RmpxqgEWB9zXK983hQ0JzCzPGA2cIVzblfsPuctNaLlRnzOuSb/15sj8X4N9ane7VHfZWZnAJ845xb0dl/6kc845ybj/VruO2Z2fOxO/X2MEwImA3c65yYB1ST86lfj1Zafg3sm8PfEfRqvVn5e6Vl4/zkbAeTS9tfq4nPOrcBLXZkL/BtYDDQlHKPPVwf64hgpaI5hZmG8gPlB59xjfvPm6K8A/K+f9Fb/+ir/18AvAsfi/cok5O8aCZT3Vr/6mOOAM81sDfAw3q81b0PjlZI/u4Vz7hO8fNOj0d/HVDYAG5xzb/nfP4oXRGu82ncasNA5t9n/XuOV3CnAR865Lc65CPAY3s80/fxKwTn3J+fckc654/Hyvd9Hn6/OSDVG5Xiz9VG98nlT0Ozz80v/BKxwzv1fzK4nga/4r78CPNHTfeuLzGywmRX5r7OBz+Hlgb8InOsfpvHyOed+5Jwb6Zwbhffr4Beccxeh8UrKzHLNLD/6GjgV71ee+vuYhHPuY2C9mY31m04G3kXj1ZELaU3NAI1XKuuAY8wsx/+3Mvr50s+vFMxsiP91f7x85ofQ56szUo3Rk8CX/VU0jgF2xqRx9BgVN/GZ2WeAV4CltOac/hgvr/kRYH9gLXCecy4xcX2fY2YT8JL0g3j/+XrEOXejmR2IN5M6EFgE/Jdzrr73etr3mFkp8H3n3Bkar+T8cXnc/zYEPOSc+4WZDUJ/H5Mys4l4D5lmAB8CX8P/u4nGqw3/P2PrgAOdczv9Nn2+UjBvWdHz8VaaWgRcjJdTqp9fSZjZK3jPrUSA7znnntfnK56ZzQJKgWJgM3A9MIckY+T/Z+23eGlBNcDXnHPze7zPCppFRERERNqn9AwRERERkQ4oaBYRERER6YCCZhERERGRDihoFhERERHpgIJmEREREZEOKGgWEYlhZj8xs+VmtsTMFpvZVL/9j2Z2WBfdY42ZFXdwzI8Tvn+9K+7dW8xseleNn4hIb9CScyIiPjM7Fvg/oNQ5V+8HthnOuY1dfJ81wBTn3NZ2jqlyzuV15X27g79+qjnnmjs47j7gKefcoz3SMRGRLqaZZhGRVsOBrdECDc65rdGA2czKzGyK/7rKzG7xZ6SfM7Oj/f0fmtmZ/jFfNbPfRi9sZk/5hW3imNkcM1vgX+sSv+0mINuf6X4wek//q/n3XmZmS83sfL+91O/Do2b2npk96Ae0mNlNZvauP3t+a5I+3GBmfzWzN8xslZl9I2bfD8xsnn/uT/22UWa20sz+glepcb+E68Xdz8w+DZwJ3OK/p4P87d/+e3/FzD7ln3ufmf3BzOab2ftmdkb6f4wiIl0v1PEhIiL7jLnAdWb2PvAc8Dfn3EtJjsvFK4X+AzN7HPg5Xin5w/AqZT6Zxj1n+BWvsoF5ZjbbOXe1mf2Pc25ikuO/CEwEjsCrpDXPzF72900CxgEbgdeA48xsBXA28CnnnDOzohT9mAAc47+3RWb2NDAeOBg4GjDgSTM7Hq+S3sHAV5xzb8ZexK96Fnc/51yFmT1JzEyzmT0PfNM5t8pPgfk9cJJ/mVH+PQ8CXjSzMc65uk6MpYhIt9FMs4iIzzlXBRwJXAJsAf5mZl9NcmgD8G//9VLgJedcxH89Ks3bzjSzd4A38WZsD+7g+M8As5xzTc65zcBLwFH+vredcxv8VInFfl92AnXAn8zsi3glaJN5wjlX66eMvIgXtJ7qb4uAhcCnYvq3NjFg9nV4PzPLAz4N/N3MFgN34c3yRz3inGt2zq3CKwn+qfaHRESk+2mmWUQkhnOuCSgDysxsKfAV4L6EwyKu9YGQZiCaztFsZtGfq43ET0xkJd7LT9c4BTjWOVdjZmXJjktDfczrJiDknGs0s6OBk4Fzgf+hdUY3VuIDLg5vdvn/OefuSuj3KKA6WQc6eb8AUJFiJj1VX0REepVmmkVEfGY21sxiZ3onAmt383JrgIlmFjCz/fBmbhMVAjv8gPlTeOkRUREzCyc55xXgfDMLmtlg4Hjg7VSd8Gd1C51z/wS+i5fWkcxZZpblp1eUAvOAZ4AZ/jUwsxIzG5L6Lbd7v0ogH8A5twv4yMy+5J9jZhbbry/543YQcCCwsr17ioj0BM00i4i0ygPu8PN+G4EP8FI1dsdrwEfAu8AKvPSGRP8GvunnHa/ES9GIuhtYYmYLnXMXxbQ/DhwLvIM3A/tD59zH0QfpksgHnjCzLLyZ4++lOG4JXlpGMfAz/wHIjWZ2KPCG/0xhFfBfeLPYqaS638PAPWY2E28G+iLgTjO7Bgj7+9/xj12H9x+BAry8Z+Uzi0iv05JzIiL7ODO7AahyzrVZWaMX+nIfWppORPogpWeIiIiIiHRAM80iIiIiIh3QTLOIiIiISAcUNIuIiIiIdEBBs4iIiIhIBxQ0i4iIiIh0QEGziIiIiEgHFDSLiIiIiHTg/wN+4cUiYR6+5QAAAABJRU5ErkJggg==",
      "text/plain": [
       "<Figure size 864x216 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[[8.2, 7.8, 7.0], [11.2, 10.4, 8.2]]"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Uncomment to run the experiments (it takes around 6 minutes to run)\n",
    "\n",
    "# problem={\"taxi_pos\":(0,0),\"passenger_pos\":(3,3),\"domain_map\":DEFAULT_MAP}\n",
    "# plot_steps_per_simulations(\"mcc_vs_mcts.png\", problem, [\"Monte Carlo Control\",\"Monte Carlo Tree Search\"], [20,50,100], 5)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "765227db",
   "metadata": {},
   "source": [
    "![mcc_vs_mcts](https://raw.githubusercontent.com/GabrieleSerussi/mcts/main/mcc_vs_mcts.png)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "8749aa08",
   "metadata": {},
   "source": [
    "As we can see from the graph, Monte Carlo Control (MCC) outperforms Monte Carlo Tree Search (MCTS).\n",
    "\n",
    "We relate it to the fact that **MCC** **uses a lot more data** than MCTS.\n",
    "\n",
    "Indeed, while **MCTS** maintains the values **only** for nodes (state-action pairs) **in the tree**, **MCC** maintains a value **for each state-action pair it ever encountered** and thus it has access to more data.\n",
    "\n",
    "This allows **MCC** to have a **better estimate** of the value of each state-action pair and therefore to have a better policy. However, this comes at the cost of **a lot more memory usage**.\n",
    "\n",
    "On the other hand, **MCTS** is more **scalable** and can be used in problems where the state-action space is too big to fit in memory. This is the case of games like chess or Go. In fact, MCTS (with the extension that we're going to present in the next section, i.e. RAVE, and with neural networks) is the algorithm that allowed DeepMind to create AlphaGo, the first AI that was able to beat the world champion in Go. \n",
    "\n",
    "However, **MCTS** does **not always find the optimal policy**, as we have seen in this example."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "ed7771ea",
   "metadata": {},
   "source": [
    "Without further ado, let's take a look at an extension of Monte Carlo Tree Search called **Rapid Action Value Estimation** (RAVE)."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "e3fe3ed3",
   "metadata": {
    "id": "e3fe3ed3"
   },
   "source": [
    "# Rapid Action Value Estimation (RAVE)\n",
    "- RAVE is a family of heuristics which created the first program to achieve dan (master) level in Go. [[Gelly, Silver 2011]](https://www.sciencedirect.com/science/article/pii/S000437021100052X)\n",
    "- **MCTS** requires a **lot of simulations** to sample several pairs of state and action\n",
    "- To **speed up** this estimate we can introduce a **bias**\n",
    "- We will **update** the pair $\\langle s, a \\rangle$ **with** the **reward** obtained **using** $a$ **from** any state in the **subtree** of $s$ (AMAF heuristic)\n",
    "![rave](https://raw.githubusercontent.com/GabrieleSerussi/mcts/main/rave.png)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "79943ab4",
   "metadata": {},
   "source": [
    "RAVE shares the value of actions across subtrees of the search tree. \n",
    "\n",
    "It is in this way that **RAVE** forms a very **fast** and **rough**\n",
    "estimate of the action value, whereas the value estimated by **Monte-Carlo Tree Search** is **slower** **but** more **accurate**.\n",
    "\n",
    "It is possible to **combine** these two value estimates in a principled fashion\n",
    "\n",
    "There are multiple ways to weight these two values. In particular, we will use **UCT-RAVE**"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "19d57ed4",
   "metadata": {
    "id": "19d57ed4"
   },
   "source": [
    "The value of a state-action pair is given by this combination:\n",
    "$$\n",
    "\\tilde{Q}(s,a) = (1-\\beta(s,a))*Q(s,a) + \\beta(s,a)*RAVE(s,a)\n",
    "$$\n",
    "Where:\n",
    "- $\\tilde{Q}(s,a)$ is the  value attributed to the pair $\\langle s, a \\rangle$ which is called **MC-RAVE**\n",
    "- $\\beta(s,a)$ is a parameter which dynamically balances these two estimates\n",
    "- $Q(s,a)$ is the average Q-value of $\\langle s, a \\rangle$\n",
    "- $RAVE(s,a)$ is the RAVE value of $\\langle s, a \\rangle$\n",
    "\n",
    "$$\\beta(s,a) = \\sqrt{\\frac{k}{3N(s,a)+k}}$$\n",
    "Where:\n",
    "- $N(s,a)$ is the number of times that we visited the current node\n",
    "- $k$ is an hyperparameter that sets the number of simulation at which $Q$ and $RAVE$ are given the same weight\n",
    "\n",
    "![beta](https://raw.githubusercontent.com/GabrieleSerussi/mcts/main/beta.png)\n",
    "\n",
    "\n",
    "In order to balance the exploration-exploitation trade-off, **UCT-RAVE** uses UCT by using $\\tilde{Q}$ instead of $Q$.\n",
    "\n",
    "In detail we will have:\n",
    "\n",
    "$$\n",
    "Q_{*}(s,a) = \\tilde{Q}(s,a) + C \\sqrt{\\frac{\\log(N(s))}{N(s,a)}} \n",
    "$$"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "93b0440f",
   "metadata": {},
   "source": [
    "Now we are going to implement UCT-RAVE.\n",
    "In order to keep track of the action values taken in the subtree we will need to override several functions of the MonteCarloTreeSearchNode class.\n",
    "\n",
    "We will highlight the biggest conceptual differences in the code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "539f0487",
   "metadata": {
    "id": "539f0487"
   },
   "outputs": [],
   "source": [
    "class RAVEMonteCarloTreeSearchNode(MonteCarloTreeSearchNode):\n",
    "    '''Introduce RAVE optimization to MCTS'''\n",
    "    def __init__(self, state, n_simulations=100, parent=None, parent_action=None, k=3, gamma=0.78):\n",
    "        super().__init__(state, n_simulations, parent,parent_action, gamma=gamma)\n",
    "        self.average_reward_rave = 0\n",
    "        self.number_of_visits_rave = 0\n",
    "        self.k = k\n",
    "        # We need to override the evaluate function to use the rave value in rendering\n",
    "        self._evaluate_function = self._uct_rave\n",
    "\n",
    "    def _best_action(self, render:bool=False):\n",
    "        \"\"\"\n",
    "        Execute the four stages to find the best action from the current state.\n",
    "        \"\"\"\n",
    "        for _ in range(self.n_simulations):\n",
    "          node = self._tree_policy()\n",
    "          reward, taken_actions = node._rollout()\n",
    "          node._backpropagate(reward, taken_actions)\n",
    "        if not render:\n",
    "            return self._best_child(c_param=0.)\n",
    "        else:\n",
    "            return self._best_child(c_param=0.), self\n",
    "    \n",
    "    def _tree_policy(self):\n",
    "      \"\"\"\n",
    "      Selects node to run rollout.\n",
    "      \"\"\"\n",
    "      current_node = self\n",
    "      while not current_node._is_terminal_node():\n",
    "\n",
    "          if current_node._is_leaf():\n",
    "              # Differently from what we did in Monte Carlo Tree Search, even if we do not select\n",
    "              # a certain child from the current node, we still need to create it so that \n",
    "              # we will be able to update its rave value in the backpropagation step.\n",
    "              current_node._create_all_children()\n",
    "              return current_node._best_child()\n",
    "          \n",
    "          current_node = current_node._best_child()\n",
    "      return current_node\n",
    "\n",
    "    def _is_leaf(self):\n",
    "        \"\"\"\n",
    "        Returns True if the node is a leaf node, False otherwise.\n",
    "        \"\"\"\n",
    "        return len(self.children) == 0\n",
    "\n",
    "    def _create_all_children(self):\n",
    "        \"\"\"\n",
    "        Create all possible child nodes for the current node.\n",
    "        \"\"\"\n",
    "        for action in self._untried_actions:\n",
    "            \n",
    "            new_state = deepcopy(self.state)\n",
    "            new_state.step(action)\n",
    "            obs, reward, done, trunc, info = new_state.last()\n",
    "            child_node = RAVEMonteCarloTreeSearchNode(state = new_state, n_simulations=self.n_simulations,\n",
    "                            parent=self, parent_action=action, k=self.k, gamma=self.gamma)\n",
    "            child_node.terminal_state = done\n",
    "            child_node.average_reward = reward\n",
    "            child_node.number_of_visits = 1\n",
    "            child_node.average_reward_rave = reward\n",
    "            child_node.number_of_visits_rave = 1\n",
    "            \n",
    "\n",
    "            self.children.append(child_node)\n",
    "\n",
    "    def _best_child(self, c_param=0.8):\n",
    "        \"\"\"\n",
    "        Select the best child from the children array according to the MC-RAVE formula.\n",
    "        :param c_param: Exploration parameter.\n",
    "        :return: The child with the highest MC-RAVE value.\n",
    "        \"\"\"\n",
    "        choices_weights = [self._uct_rave(child, c_param) for child in self.children] \n",
    "        return self.children[np.argmax(choices_weights)]\n",
    "\n",
    "    def _uct_rave(self, child, c_param):\n",
    "        \"\"\"\n",
    "        Returns the UCT-RAVE value for a child node.\n",
    "        :param child: The child node for which the MC-RAVE value is calculated.\n",
    "        :param c_param: Exploration parameter.\n",
    "        :return: The UCT-RAVE value for the child node.\n",
    "        \"\"\"\n",
    "        \n",
    "        mc = float('inf') if child.number_of_visits == 0 else child.average_reward\n",
    "        rave = float('inf') if child.number_of_visits_rave == 0 else child.average_reward_rave\n",
    "        beta = np.sqrt(self.k / (3 * self.number_of_visits + self.k))\n",
    "        # mc_rave value which combines the mc and the rave values:\n",
    "        q_star = (1-beta)*mc + beta*rave\n",
    "        uct_rave =  float('inf') if (child.number_of_visits == 0 or self.number_of_visits == 0) else q_star + \\\n",
    "        c_param*np.sqrt( \\\n",
    "            np.log(self.number_of_visits)/ child.number_of_visits \\\n",
    "            )\n",
    "        return uct_rave\n",
    "\n",
    "    def _rollout(self):\n",
    "        \"\"\"\n",
    "        Conducts a rollout from the current node.\n",
    "        :return: a tuple containing the reward obtained and the actions taken during the rollout.\n",
    "        \"\"\"\n",
    "        current_rollout_state = deepcopy(self.state)\n",
    "\n",
    "        _reward = 0\n",
    "        step = 0\n",
    "        done = current_rollout_state.last()[2]\n",
    "        taken_actions = []\n",
    "        while not done:\n",
    "            possible_moves = self._get_legal_actions()\n",
    "\n",
    "            action = self._rollout_policy(possible_moves)\n",
    "            current_rollout_state.step(action)\n",
    "            obs, reward, done, trunc, info = current_rollout_state.last()\n",
    "            _reward += reward*(self.gamma**step)\n",
    "            # DIFFERENCE FROM MONTE CARLO TREE SEARCH: we need to keep track of the actions taken\n",
    "            taken_actions.append(action)\n",
    "            ##############################\n",
    "            step += 1\n",
    "        return _reward, taken_actions\n",
    "\n",
    "    def _backpropagate(self, reward, taken_actions):\n",
    "        \"\"\"\n",
    "        Backpropagates the reward obtained during the rollout to the parents of the current node.\n",
    "        :param reward: The reward obtained during the rollout.\n",
    "        :param taken_actions: The actions taken during the rollout.\n",
    "        \"\"\"\n",
    "        self.number_of_visits += 1\n",
    "        self.average_reward = self.average_reward + (1/self.number_of_visits)*(reward-self.average_reward)\n",
    "\n",
    "        # DIFFERENCE FROM MONTE CARLO TREE SEARCH: we need to update the rave estimates of the children\n",
    "        for action in taken_actions:\n",
    "            for child in self.children:\n",
    "                if child.parent_action == action:\n",
    "                    child._update_rave_estimate(reward)\n",
    "        ###############################################\n",
    "        \n",
    "        if self.parent is not None:\n",
    "            self.parent._backpropagate(reward, taken_actions)\n",
    "    \n",
    "    def _update_rave_estimate(self, reward):\n",
    "        \"\"\"\n",
    "        Updates the rave estimate of the current node.\n",
    "        :param reward: The reward obtained during the rollout.\n",
    "        \"\"\"\n",
    "        self.number_of_visits_rave += 1\n",
    "        self.average_reward_rave = self.average_reward_rave + (1/self.number_of_visits_rave)*(reward-self.average_reward_rave)\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "6e316251",
   "metadata": {},
   "source": [
    "Now let's see RAVE in action."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "be33ddba",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Step number: 14\n",
      "Action executed: pickup\n",
      "Names: | Values: | Average reward: | Number of visits:\n",
      "south| 0.657 | -1 | 1\n",
      "north| 0.657 | -1 | 1\n",
      "east| 0.657 | -1 | 1\n",
      "west| 0.657 | -1 | 1\n",
      "pickup| 8.133 | 1.356 | 73 <--\n",
      "+-----------------------+\n",
      "| : |F: | : | : | : |F: |\n",
      "| : | : : : | : | : | : |\n",
      "| : : : : : : : : : : : |\n",
      "| : : :\u001b[43m \u001b[0m: : | : : : : : |\n",
      "| : : : : : | : : : : : |\n",
      "| : : : : : : : : : : : |\n",
      "| | :G| | | :G| | | : | |\n",
      "+-----------------------+\n",
      "Taxi0-YELLOW: Fuel: inf, Location: (3, 3), Engine: ON, Collided: False, Step: 14, ALIVE\n",
      "Passenger0-YELLOW: Location: Taxi0 (3, 3), Destination: (-1, -1)\n",
      "Env done: True\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "14"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "env = new_environment_creator(taxi_pos=(0,0),passenger_pos=(3,3))\n",
    "rave = RAVEMonteCarloTreeSearchNode(state = env, n_simulations = 20, k=1, gamma=0.78)\n",
    "rave.run_and_update(max_number_of_steps=1000, render=True)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "25668105",
   "metadata": {},
   "source": [
    "As we can see, despite having access to the **same** amount of **data** **as MCTS**, RAVE is able to learn a **better policy** than the one learned by MCTS.\n",
    "\n",
    "This is due to the fact that RAVE is able to use the data in a **more efficient** way, by means of its **heuristic**."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "299186ce",
   "metadata": {},
   "source": [
    "To make a more rigorous comparison, we will evaluate each of the algorithms for a variety of simulations. We redefine evaluate_policy to executes one of the algorithms: \"Monte Carlo Control\", \"Monte Carlo Tree Search\", \"RAVE\" for any given of number of simulations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "fac9868e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def evaluate_policy(problem, algorithm, simulations, render:bool=True):\n",
    "    if not algorithm in [\"Monte Carlo Control\", \"Monte Carlo Tree Search\", \"RAVE\"]:\n",
    "        raise ValueError(\"Algorithm must be one among: Monte Carlo Control, Monte Carlo Tree Search, RAVE and NewRAVE\")\n",
    "      \n",
    "    env = new_environment_creator(taxi_pos=problem[\"taxi_pos\"], passenger_pos=problem[\"passenger_pos\"],domain_map=problem[\"domain_map\"])\n",
    "\n",
    "    if algorithm == \"Monte Carlo Control\":\n",
    "        # Monte Carlo Control\n",
    "        monte_carlo_control = MonteCarloControl(env, gamma=0.99, max_steps_per_episode=1_000)\n",
    "        step = monte_carlo_control.run_and_update(number_of_simulated_episodes=simulations, render=render)\n",
    "        return step\n",
    "\n",
    "    elif (algorithm==\"Monte Carlo Tree Search\"):\n",
    "        # Monte Carlo Tree Search\n",
    "        mcts = MonteCarloTreeSearchNode(state = env, n_simulations=simulations, gamma=0.78)\n",
    "        step = mcts.run_and_update(max_number_of_steps=1000, render=render)\n",
    "        return step\n",
    "    \n",
    "    elif (algorithm ==\"RAVE\"):\n",
    "        # RAVE\n",
    "        rave = RAVEMonteCarloTreeSearchNode(state = env, n_simulations = simulations, k=1, gamma=0.78)\n",
    "        step = rave.run_and_update(max_number_of_steps=1000, render=render)\n",
    "        return step"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "6287cd82",
   "metadata": {},
   "source": [
    "Finally we plot the performance of the algorithms according to number of simulations.\n",
    "\n",
    "P.S. By default render is set to False to make the notebook run faster. If you want to see the agent in action, set render to True."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "518ebeda",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Monte Carlo Control for 10 simulations\n",
      "Monte Carlo Tree Search for 10 simulations\n",
      "RAVE for 10 simulations\n",
      "Monte Carlo Control for 20 simulations\n",
      "Monte Carlo Tree Search for 20 simulations\n",
      "RAVE for 20 simulations\n",
      "Monte Carlo Control for 30 simulations\n",
      "Monte Carlo Tree Search for 30 simulations\n",
      "RAVE for 30 simulations\n",
      "Monte Carlo Control for 50 simulations\n",
      "Monte Carlo Tree Search for 50 simulations\n",
      "RAVE for 50 simulations\n",
      "Experiments' results:\n",
      "[[7.0, 7.9, 7.4, 7.0], [18.5, 13.4, 9.4, 9.4], [18.9, 10.6, 9.6, 8.7]]\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAs0AAADgCAYAAAD44ltAAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAAsTAAALEwEAmpwYAABVhUlEQVR4nO3dd3hUVfrA8e87k55ACL1KVXoIvYkEVEDpimJD+KELuruKa0VBwbq4WLGtoigqgghSBAuIRKRI703ERek1gfQyOb8/7iQkYSbJQCaThPfzPPPMzJl773nncEnee3LuOWKMQSmllFJKKeWezdcBKKWUUkopVdJp0qyUUkoppVQBNGlWSimllFKqAJo0K6WUUkopVQBNmpVSSimllCqAJs1KKaWUUkoVQJNmpZQqQUSkmoisEJF4EXnV1/EopZSy+Pk6AKWUKgtE5ABQDXAAicB3wD+NMQkeHmoUcAoob3QifaWUKjG0p1kppYpOf2NMGNAGaAeML+yOYrEBdYFdF5Mwi4h2hCillJdo0qyUUkXMGHMYq6e5hYh0EpHVIhInIltFJDprOxGJEZEXRWQVkAR8CgwHHheRBBG5TkQCReQNETnifLwhIoHO/aNF5JCIPCEix4CPRWSiiHwlIp87h3hsF5GrRORJETkhIgdFpFeOGP5PRHY7t/1DREbn+Czr+I849z0qIv+X4/NgEXlVRP4UkbMislJEgp2fuf3eSilVGmnSrJRSRUxE6gA3AkeBxcALQEXgUWCuiFTJsfkwrCEZ5YD/A2YA/zHGhBljfgTGAZ2AKKAV0IHcPdjVnceu6zwOQH/gMyAC2Az8gPXzvhbwHPB+jv1PAP2A8s76XxeRNnmOH+7c9x7gHRGJcH72CtAW6OKM4XEgU0RqFeJ7K6VUqaJJs1JKFZ35IhIHrAR+Bg4B3xpjvjXGZBpjlgIbsBLqLJ8YY3YaYzKMMekujnkn8Jwx5oQx5iTwLFainSUTmGCMSTXGJDvLfjHG/GCMyQC+AqoAk5zHnwXUE5EKAMaYxcaY/cbyM7AE6Jbj+OnO+tONMd8CCUBj51CSkcAYY8xhY4zDGLPaGJMK3FWI762UUqWKJs1KKVV0BhljKhhj6hpj/o51Y+AtziEKcc6E+mqgRo59DhZwzJrAnzne/+ksy3LSGJOSZ5/jOV4nA6eMMY4c7wHCAETkBhH5VUTOOOO7EaicY//TzuQ7S5Jz38pAELDfRcx1Kfh7K6VUqaI3jSillPccBD4zxvwtn20KuuHvCFYSutP5/gpnWWH3d8s5NnoucDewwBiTLiLzASnE7qeAFKAhsDXPZ4X53kopVapoT7NSSnnP50B/EektInYRCXLeXFfbg2PMBMaLSBURqQw84zxuUQgAAoGTQIaI3AD0yn8XizEmE5gGvCYiNZ3fr7MzES+K762UUiWKJs1KKeUlxpiDwEDgKazE9CDwGJ797H0BazzwNmA7sMlZVhTxxQMPArOBWOAOYKEHh3jUGdN64AzwMmArou+tlFIliujc+UoppZRSSuVPr/qVUkoppZQqgCbNSimllFJKFUCTZqWUUkoppQqgSbNSSimllFIF0KRZKaWUUkqpApSKxU0qV65s6tWrV+z1JiYmEhoaWuz1llbaXp7TNvOMtpdntL08o+3lGW0vz2h7ecaX7bVx48ZTxpgqectLRdJcr149NmzYUOz1xsTEEB0dXez1llbaXp7TNvOMtpdntL08o+3lGW0vz2h7ecaX7SUif7oq1+EZSimllFJKFUCTZqWUUkoppQqgSbMLi/9YTK85vXjgzwfoNacXi/9Y7OuQlFJKKaWUD5WKMc3FafEfi5m4eiIpjhQAjiYeZeLqiQD0bdDXh5EppZRSZVd6ejqHDh0iJSXF16F4RXh4OLt37/Z1GKVGcbRXUFAQtWvXxt/fv1Dba9Kcx5ub3sxOmLOkOFJ4c9ObmjQrpZRSXnLo0CHKlStHvXr1EBFfh1Pk4uPjKVeunK/DKDW83V7GGE6fPs2hQ4eoX79+ofbR4Rl5HEs85lG5UkoppS5dSkoKlSpVKpMJsyp5RIRKlSp59JcNTZrzqB5a3WV5oD2Q2JTYYo5GKaWUunxowqyKk6fnmybNeYxpM4YgyT22xQ8bqY5UBi8YzPK/lvsoMqWUUkp5k4hw1113Zb/PyMigSpUq9OvX76KOFxcXx7vvvuvxfgkJCYwePZqGDRvStm1boqOjWbt2rUfHiI6O9miNi/T0dMaOHcuVV15JmzZt6Ny5M999952noQMwf/58du3a5fF+nsZc3DRpzqNvQiITT52mRnoGYgw10jN44XQcXzW+l0rBlXhw+YOMXzme+LR4X4eqlFJKXbbmbz5M10k/UX/sYrpO+on5mw9f8jFDQ0PZsWMHycnJACxdupRatWpd9PEuNmm+9957qVixIvv27WPjxo18/PHHnDp1qtD7OxwOj+t8+umnOXr0KDt27GDTpk3Mnz+f+PiLy3XyS5ozMjIu6pglgSbNeS17jr7n4lhy6AjbDhxkyaEj9D0XR+M1HzCr7yz+1vJvfPPHN9y08CbWHFnj62iVUkqpy878zYd58uvtHI5LxgCH45J58uvtRZI433jjjSxebE01O3PmTG6//fbsz86cOcOgQYOIjIykU6dObNu2DYCJEycycuRIoqOjadCgAVOmTAFg7Nix7N+/n6ioKMaPHw/A5MmTad++PZGRkUyYMOGC+vfv38/atWt54YUXsNmsNK1+/fr07WtNRjBo0CDatm1L8+bN+eCDD7L3CwsL45FHHqFVq1asWZM7P5k5cyYtW7akRYsWPPHEExfUmZSUxNSpU3nrrbcIDAwEoFq1atx666357h8WFsa4ceNo1aoVnTp14vjx46xevZqFCxfy2GOPERUVxf79+4mOjuahhx6iXbt2vPnmmyxbtozWrVvTsmVLRo4cSWpqqif/RD6js2fkdfaQm/KD+DvSeLDNg0TXiWbcynGMWjqKoY2H8nDbhwnxDyneOJVSSqky6tlvdrLryDm3n2/+K440R2ausuR0B4/P2cbMdX+53KdZzfJM6N+8wLpvu+02nnvuOfr168e2bdsYOXIkv/zyCwATJkygdevWzJ8/n59++om7776bLVu2ALBnzx6WL19OfHw8jRs35v7772fSpEns2LGDLVu2EB8fz5IlS9i3bx/r1q3DGMOAAQNYsWIF11xzTXb9O3fuJCoqCrvd7jK+adOmUbFiRZKTk2nfvj0333wzlSpVIjExkY4dO/Lqq6/m2v7IkSM88cQTbNy4kYiICHr16sX8+fMZNGhQ9ja///47V1xxBeXLl7+gvvz2T0xMpFOnTrz44os8/vjjTJ06lfHjxzNgwAD69evHkCFDso+TlpbGhg0bSElJ4corr2TZsmVcddVV3H333bz33ns89NBDBf7b+Jr2NOcVXtv9Z682he/GEikhfNX/K4Y1G8bsvbMZ8s0QNh3fVHwxKqWUUpexvAlzQeWeiIyM5MCBA8ycOZMbb7wx12crV65k2LBhAPTs2ZPTp09z7pyV3Pft25fAwEAqV65M1apVOX78+AXHXrJkCUuWLKF169a0adOGPXv2sG/fPo/imzJlSnbP7sGDB7P3t9vt3HzzzRdsv379eqKjo6lSpQp+fn7ceeedrFixotD15bd/QEBA9njvtm3bcuDAAbfHGTp0KAB79+6lfv36XHXVVQAMHz7co3h8SXua87r2GfjmQUhPPl/mHwxdHoTT+2H9h7D2PYIa9ODxDn+j5/VTGb9mAiO+H8Hdze7mgTYPEGgP9F38SimlVClXUI9w10k/cTgu+YLyWhWC+XJ050uuf8CAATz66KPExMRw+vTpQu2TNawBrATW1dhdYwxPPvkko0ePdnuc5s2bs3XrVhwOxwW9zTExMfz444+sWbOGkJAQoqOjs6dMCwoKcts7XZBGjRrx119/ce7cOZe9ze74+/tnz0Dh7jtnCQ0NvajYShKv9TSLyDQROSEiO3KURYnIryKyRUQ2iEgHb9V/0SJvhf5TILwOBoHwOtb7Hk/BkI/g4V3Qczyc+g1m3UG7L+/h60rduaV+P6bvms6t39zKzlM7ff0tlFJKqTLrsd6NCfbPnSAG+9t5rHfjIjn+yJEjmTBhAi1btsxV3q1bN2bMmAFYCWzlypXzTTLLlSuX62a63r17M23aNBISEgA4fPgwJ06cyLVPw4YNadeuHRMmTMAYA8CBAwdYvHgxZ8+eJSIigpCQEPbs2cOvv/5a4Hfp0KEDP//8M6dOncLhcDBz5ky6d++ea5uQkBDuuecexowZQ1paGgAnT57kq6++KtT+BX3vnBo3bsyBAwf4/fffAfjss88KPF5J4c3hGZ8AffKU/Qd41hgTBTzjfF/yRN4K/9rBz9Hz4V87rPdZwqrCNY/BmG0w9HOo2ICQmEk8/fNU/hvUhISUWO789k7e3vw26Y50n30FpZRSqqwa1LoW/76pJbUqBCNYPcz/vqklg1pf/EwXOdWuXZsHH3zwgvKJEyeyceNGIiMjGTt2LNOnT8/3OJUqVaJr1660aNGC8ePH06tXL+644w46d+5My5YtGTJkiMvk8sMPP+T48eM0atSIFi1aMGLECKpWrUqfPn3IyMigadOmjB07lk6dOhX4XWrUqMGkSZPo0aMHrVq1om3btgwcOPCC7V544QWqVKlCs2bNaNGiBf369aN8+fKF3j+n2267jcmTJ9O6dWv279+f67OgoCA+/vhjbrnlFlq2bInNZuO+++4r8HuUBJJ1FeOVg4vUAxYZY1o43/8ATDPGfCkitwP9jTF3FHScdu3aGV/M2xcTE0N0dHTBG578zRq2sXUm59LjeblWAxb6pdOkwlW8eM2/uSriKq/HWhIUur1UNm0zz2h7eUbbyzPaXp4p6vbavXs3TZs2LbLjlTS6jLZniqu9XJ13IrLRGNMu77bFnTQ3BX4ABKuXu4sx5k83+44CRgFUq1at7axZs7wWpzsJCQmEhYUVent7RjLVjsdQ88h3rDUneK5yJc7Z7AwI6841lQZhl4sba1RaeNpeStvMU9pentH28oy2l2eKur3Cw8Np1KhRkR2vpHE1Rlm5V1zt9fvvv3P27NlcZT169CgRSfMU4GdjzFwRuRUYZYy5rqDjlPie5ryMgb/WcGbtu7xw6leWhgYTSRAvtnqAepF3gq1s/qfRXhrPaZt5RtvLM9pentH28oz2NHtGe5o9UxJ7mot7yrnhwNfO118BJe9GwKIgAnW7UPHWz3n1rl94uXJXDmQmc8vml5nxfhSZv7wGiYW7G1cppZRSSvlecSfNR4CsWyR7Ap5NTlgKSfka3Nj3v8wbsoT2EU2YFAL37nyPw282h3n3waENVs+0UkoppZQqsbw55dxMYA3QWEQOicg9wN+AV0VkK/ASzjHLl4Oq5WryzsA5PNvlWXaFRXBT7erM/XMJ5sNr4YNo2Px57rmhlVJKKaVUieG1xU2MMbe7+aitt+os6USEm668iU41OvH0qqeZaNbxY+1mPHviOFUX/AOWjIfWd0G7e6BifV+Hq5RSSimlnHQZbR+oGVaTqb2mMrbDWDakHGdwRACLb5iAqdcN1rwLU1rDjFvgtyWQeelLgiqllFKqYCLCXXfdlf0+IyODKlWqZC8V7am4uDjeffddj/dLSEhg9OjRNGzYkLZt2xIdHc3atWs9OkZ0dDSFnURh8ODBREVF0ahRI8LDw4mKiiIqKorVq1d7HLs7L774Is2bNycyMpKoqCiPv48nYmJiLvrfLD+6jLaP2MTGnU3vpGvNroxbNY6xez5mWd3rGd9zJRV3zIeNn8AXt0CFutD+Hmg9DEIq+jpspZRSqmTYNhuWPQdnD0F4bbj2mdyLkV2E0NBQduzYQXJyMsHBwSxdupRatS5+wZSspPnvf/+7R/vde++91K9fn3379mGz2fjf//7Hrl27Cr2/w+HwqL558+YBVrL5yiuvsGjRolyfZ2Rk4Od38SnjmjVrWLRoEZs2bSIwMJBTp05lrzx4KS41Lk9pT7OP1Quvx6d9PuVfbf9FzMEYBv90P8sadIR/7YQhH1s/CJY+A681hfl/h8ObfB2yUkop5VvbZsM3D8LZg4Cxnr950Cq/RDfeeCOLFy8GYObMmdx++/nRpmfOnGHQoEFERkbSqVMntm3bBlgrBY4cOZLo6GgaNGjAlClTABg7diz79+8nKiqK8ePHAzB58mTat29PZGQkEyZMuKD+/fv3s3btWl544QVsNitNq1+/Pn379gVg0KBBtG3blubNm/PBBx9k7xcWFsYjjzxCq1atWLNmTa5jzpw5k5YtW9KiRQueeOKJQrXDJ598woABA+jZsyfXXnstiYmJjBw5kg4dOtC6dWsWLFgAWAn6Y489lv2d3n///QuOdfToUSpXrkxgYCAAlStXpmbNmgBs3LiR7t2707ZtW3r37s3Ro0ez62/fvj2tWrXi5ptvJikpCYARI0Zw33330bFjRx5//HF+//13rrvuOlq1akWbNm2yVyBMSEhgyJAhNGnShDvvvJOimGJZe5pLALvNzsgWI+lWqxvjVo7joZiH6NegH2M7jCW8xU1wfKdzxcEvYcsMqNUW2v8Nmg8G/yBfh6+UUkoVre/GwrHt7j8/tB4cqbnL0pNhwT9ho5ulrau3hBsmFVj1bbfdxnPPPUe/fv3Ytm0bI0eO5JdffgFgwoQJtG7dmvnz5/PTTz9x9913s2XLFgD27NnD8uXLiY+Pp3Hjxtx///1MmjSJHTt2sGXLFuLj41myZAn79u1j3bp1GGMYMGAAK1as4Jprrsmuf+fOnURFRbld2GPatGlUrFiR5ORk2rdvz80330ylSpVITEykY8eOvPrqq7m2P3LkCE888QQbN24kIiKCXr16MX/+fAYNGlRgW2zatIlt27ZRsWJFnnrqKXr27Mm0adOIi4ujQ4cOXHfddcyYMYPw8HDWr19PamoqXbt2pVevXtSvf/7erF69evHcc89x1VVXcd111zF06FC6d+9Oeno6DzzwAAsWLKBKlSp8+eWXjBs3jmnTptG/f38eeOABAMaPH89HH32U/f7QoUOsXr0au91Ox44dGTt2LIMHDyYlJYXMzEwOHjzI5s2b2blzJzVr1qRr166sWrWKq6++usDvnB9NmkuQKyOuZEbfGUzdNpUPtn3AumPreK7Lc3St1RX6vQ7XTYSts6wEev598MNT0GaYdeNgRF1fh6+UUkoVj7wJc0HlHoiMjOTAgQPMnDmTG2+8MddnK1euZO7cuQD07NmT06dPc+7cOQD69u1LYGAggYGBVK1alePHj19w7CVLlrBkyRJat24NWL2h+/bty5U0F2TKlCnZwykOHjzIvn37qFSpEna7nZtvvvmC7devX090dDRVqlQB4M4772TFihWFSpqvv/56KlasmB37woULeeWVVwBISUnhr7/+YsmSJWzbto05c+YAcPbsWfbt25craQ4LC2Pjxo388ssvLF++nKFDhzJp0iTatWvHjh07uP766wGr17pGjRqAtejIsGHDiIuLIyEhgd69e2cf75ZbbsFutxMfH8/hw4cZPHgwAEFB5zsSO3ToQO3atQGIioriwIEDmjSXNf42f/4e9Xe61+7OuJXjuO/H+xhy1RAebfcooUHh0HE0dBgF/1sB66fC6rdh1RS4qrfV+9ywJ9h01I1SSqlSrKAe4ddbOIdm5BFeB/5v8SVXP2DAAB599FFiYmI4fbpwi5FlDT0AsNvtZGRkXLCNMYYnn3yS0aNHuz1O8+bN2bp1q8tlpGNiYvjxxx9Zs2YNISEhREdHk5KSAlgJY1EvOx0aGpor9rlz59K4ceNc2xhjeOutt3Ilta7Y7Xaio6OJjo6mZcuWTJ8+PXuYSd7hJAD3338/CxYsoFWrVnzyySfExMS4jMudwvx7eEqzqxKqeeXmfNn/S/6v+f8x97e53LzwZtYfW299KAINusPQz+Gh7XDNo9ZY5xk3w9ttrUQ6Oda3X0AppZTylmufAf/g3GX+wVZ5ERg5ciQTJkygZcuWucq7devGjBkzACuBrVy5MuXLl3d7nHLlyhEfH5/9vnfv3kybNo2EhAQADh8+zIkTJ3Lt07BhQ9q1a8eECROyx+EeOHCAxYsXc/bsWSIiIggJCWHPnj38+uuvBX6XDh068PPPP3Pq1CkcDgczZ86ke/fuBe6XV+/evXnrrbeyY9q8eXN2+XvvvUd6ejoAv/32G4mJibn23bt3L/v2nV/PbsuWLdStW5fGjRtz8uTJ7KQ5PT2dnTt3AtYy2jVq1CA9PT27zfMqV64ctWvXZv78+QCkpqZmj332Bk2aS7BAeyAPt3uY6TdMxyY2Rv4wkpfXvUxKRsr5jcJrQc/x1o2DN38EoVVhyTh4tak1tuvoVt99AaWUUsobIm+F/lOsnmXEeu4/5ZJnz8hSu3ZtHnzwwQvKJ06cyMaNG4mMjGTs2LFMn+5m/LRTpUqV6Nq1Ky1atGD8+PH06tWLO+64g86dO9OyZUuGDBmSK6nO8uGHH3L8+HEaNWpEixYtGDFiBFWrVqVPnz5kZGTQtGlTxo4dS6dOnQr8LjVq1GDSpEn06NGDVq1a0bZtWwYOHFj4xnB6+umnSU9PJzIykubNm/P0008D1kwfzZo1o02bNrRo0YLRo0df0KubkJDA8OHDadasGZGRkezatYuJEycSEBDAnDlzeOKJJ2jVqlWuae7Gjx9Px44d6dq1K02aNHEb12effcaUKVOIjIykS5cuHDt2zOPvVlhSFHcTelu7du1MYecaLEoxMTFER0cXe72uJKUn8frG15m1dxb1ytfjxatfJLJKpOuNj22HdVNh+1eQngS1O0D7e6H5IPALdL1PEShJ7VVaaJt5RtvLM9pentH28kxRt9fu3btp2rRpkR2vpImPj6dcuXK+DqPUKK72cnXeichGY0y7vNtqT3MpEeIfwrhO4/jg+g9IcaQw7LthTNk0hTSHi3kOq7eEAVPg4d3QZxIkn4F5o+C1ZvDjsxDnYhyYUkoppZRyS5PmUqZzzc58PeBrBjQcwNTtU7l98e3sPbPX9cbBFaDT/fCP9TBsHtTpCKvegDcjYeYdsP8nXXFQKaWUUqoQNGkuhcoFlOP5rs/zds+3OZNyhtsW38YH2z4gI9PNnaE2mzWrxu1fwJht0PUhOLgWPhsM77S3lu5OjivOr6CUUkopVapo0lyKda/TnXkD5nH9Fdfz1ua3GPbtMP44+0f+O1WoA9dNgId3wU1TIbgi/PCkteLgwgfzn0xeKaWUUuoypUlzKVchqAL/6f4fJnefzKGEQ9z6za18uvNTMk0Bwy78Aq27jO9dCqN+hhY3W8uP/vdq+Kg3bJ8DGZe+LrxSSimlVFmgSXMZ0adeH+YNnEfnGp2ZvGEyI38YycH4Qt7wVzMKBr4Nj+yGXi9CwnGYew+83hx+egHOHvZq7EoppZRSJZ0mzWVI5eDKTOk5hRe6vsDeM3u5eeHNzN47m0JPKxgcAV3+CQ9sgjvnQq22sOIVeKMlfHkX/BEDpWCKQqWUUupi2O12oqKiaNGiBf379ycuLi7X51FRUdx2220AJCUlUalSpexltLMMGjSIL7/8kk8++YQqVaoQFRVFVFQUXbt2ZdeuXcX1VZQXeC1pFpFpInJCRHbkKX9ARPaIyE4R+Y+36r9ciQgDGw1k3sB5tKrSiud/fZ77fryPY4keTPZts8GV18Eds2DMVujyABxYBZ8OhHc6wNr3IeWs976EUkopVYDFfyym15xeRE6PpNecXiz+49KXzw4ODmbLli3s2LGDihUr8s4772R/tnv3bhwOB7/88guJiYmEhITQu3dv5s2bl73N2bNnWblyJf379wdg6NChbNmyhS1btrBq1SqaNWt2yTEq3/FmT/MnQJ+cBSLSAxgItDLGNAde8WL9l7XqodX54PoPGN9xPJtPbOamBTexcP/Cwvc6Z4moC9c/a835POi/EFgOvnvcWnFw0b/guF41K6WUKl6L/1jMxNUTOZp4FIPhaOJRJq6eWCSJc5bOnTtz+PD54YkzZ85k2LBh9OrViwULFgBw++23M2vWrOxt5s2bR+/evQkJCSmyOFTJ4eetAxtjVohIvTzF9wOTjDGpzm1OXLCjKjIiwtAmQ+lcszNPr3qacSvH8eOfP/JM52eoHFzZs4P5B0HU7dbj8CZY/yFs+QI2TIO6XaH9PUhmuHe+iFJKqcvKy+teZs+ZPW4/33ZyG2mZuW9WT3Gk8MyqZ5jz2xyX+zSp2IQnOjxRqPodDgfLli3jnnvuyS778ssvWbp0KXv27OGtt97ijjvuoHfv3tx7772cPn2aSpUqMWvWLP75z3/m2mflypUAZGZmsnbtWoKDgwsVgyp5vJY0u3EV0E1EXgRSgEeNMetdbSgio4BRANWqVSMmJqbYgsySkJDgk3q9YXjQcK6IuIJFBxfR73A/hlYcSuvQ1hd/wAq34texDzWOLqPmke8JnjOSjv4VOPBnb47U7E1aYKWiC74MK0vnWHHQ9vKMtpdntL08U9TtFR4eTnx8PABpaWk4HA632+ZNmHOWu9svLS0t+/juJCcnExkZyZEjR2jcuDGdOnUiPj6eTZs2ERERQUREBB06dGDTpk38+eefVKxYkRtuuIHPP/+cgQMHsmnTJrp06UJ8fDwpKSkMHjyYV199FbAS8YyMjAJjUBaHw1EsbZWSklLo87i4k2Y/oCLQCWgPzBaRBsbFmAFjzAfABwDt2rUzRbm+fWHFxMTgi3q9pSc9GRE3gnErxzHt1DRuKHcD4zqOIzzwUnqIB1irCv7+I4nfT6Len7Op99ccaNoP2v8N6l0NIkX2HcqasnaOeZu2l2e0vTyj7eWZom6v3bt3U65cOQCevvrpfLftNacXRxOPXlBeI7QGn/b99KJjCA4OZtu2bSQlJdG7d28+/fRTHnzwQRYuXMi+ffto2bIlAPHx8SxZsoS//e1v3H333Tz//PMEBgYyaNAgKlasCEBQUBABAQHZ3yk+Pj77tSpYcbVXUFAQrVsXrhOxuGfPOAR8bSzrgEzAw3EC6lI0rNCQz278jH9E/YOlB5YyeMFgVhxacWkHtdngql5sj3wGHtwEnf8O/1sB0/vBu51h3VRI1StrpZRSRWNMmzEE2YNylQXZgxjTZkyRHD8kJIQpU6bw6quvkpaWxuzZs9m+fTsHDhzgwIEDLFiwgJkzZwIQHR3Nvn37eOedd7j99tuLpH5VMhV30jwf6AEgIlcBAcCpYo7hsudv8+e+VvfxRd8vCA8M5x/L/sGE1RNISEu49INXbAC9XrBuHBz4rjUW+ttH4dUmsPgROOF+jJpSSilVGH0b9GVil4nUCK2BINQIrcHELhPp26BvkdXRunVrIiMj+fe//02tWrWoWbNm9mfXXHMNu3bt4ujRo9hsNoYMGcLp06fp3r17rmN8+eWXuaacW716dZHFp4qf14ZniMhMIBqoLCKHgAnANGCacxq6NGC4q6EZqng0rdSUL/t9ybtb3uXjnR+z5sganu/6PB1rdLz0g/sHQ+s7rcehjbB+Kmz6zLqBsF43aH8vNOkLdv9Lr0sppdRlp2+DvkWaJIM1Tjunb775BoAJEybkKrfb7Rw7dn4q1zfeeIM33ngj1zYjRoxgxIgR2e91eEbp57WeZmPM7caYGsYYf2NMbWPMR8aYNGPMXcaYFsaYNsaYn7xVvyqcAHsAD7V9iE9v+JRAeyD3LrmXf6/9N8kZyUVXSe22MPi/Vu/zdRMh9k/4ari1aErMyxDvwRzSSimllFI+oCsCKgBaVWnF7P6zuavpXXyx5wtu+eYWtpzYUrSVhFaCq/8FY7bA7bOgajOIeclarvur/7MWUNE/PCillFKqBNKkWWUL9gvmiQ5P8FGvj0h3pDP8++G8vvF10hyup/a5aDY7NL4Bhn1tLdndYTTsXwaf3AjvdYX1H0FqEYyvVkoppZQqIpo0qwt0qNGBuQPmMrjRYKbtmMbQRUPZddpLK/9Vagh9XoKH98CAt6yEevHD8FpT+PZxOPmbd+pVSilV4uhtTqo4eXq+adKsXAoLCGNil4m8e+27nE09y52L7+S9Le+RnpnunQoDQqDN3TB6BdyzFK7qAxs/hnfaw/QBsGshODK8U7dSSimfCwoK4vTp05o4q2JhjOH06dMEBQUVvLFTcS9uokqZbrW7MW/gPP697t+8u/Vdlh9czktXv0SjiEbeqVAE6nSwHr1fgs2fwoaPYfYwKF8L2v4ftB0OYVW9U79SSimfqF27NocOHeLkyZO+DsUrUlJSPErQLnfF0V5BQUHUrl270Ntr0qwKFB4YzqRuk7j2imt5fs3z3LroVh5o/QB3N7sbu83uvYrDqkC3R6DLGNj3g7VIyvIX4OeXodlA6PA3qNNRVxxUSqkywN/fn/r16/s6DK+JiYkp9MpzqmS2lw7PUIV2fd3rmTdwHt1qdeO1ja8x4vsR/HXuL+9XbPez5nS+ez78c4M1x/O+pTCtN/y3G2z8BNISvR+HUkoppS5bmjQrj1QKrsQbPd7gpatfYn/cfoZ8M4SZe2aSaTKLJ4DKV8INk+CR3dDvDcDAN2Pg1abw/ZNw6vfiiUMppZRSlxVNmpXHRIT+Dfvz9cCvaVO1DS+tfYlRS0dxJuNM8QUREArt/g/uWwkjf4Arr7eGb7zdFj4dBHsWQ6aj+OJRSimlVJmmY5rVRaseWp33rnuPufvmMnn9ZLY6tiL7hEGNBiHFNc5YBK7oZD3iX4JNn1qzbsy6A8LrWIl1m+EQWrl44lFKKaVUmaQ9zeqSiAhDrhrC3AFzqR1Qm2dWP8MDPz3AySQf3P1crhp0fwzGbINbP4OK9WHZc9acz1+PgoPrdcVBpZRSSl0UTZpVkahdrjYPVHuAx9s/zq9Hf2XwwsF8/7/vfROM3Q+aDYDh38A/1kHbEbDnW/joOnj/Gqs3Oi3JN7EppZRSqlTSpFkVGZvYGNZsGF/1/4q65ery2IrHePTnR4lNifVdUFUaw42T4ZE90Pc1yMyAhQ9Yvc8/jIPT+30Xm1JKKaVKDU2aVZGrH16f6TdMZ0ybMSz7axmDFwxm+V/LfRtUYBi0vwfuXw0jvoWGPWDtf+GtNvD5zbD3e71xUCmllFJuadKsvMLP5se9Le9lVt9ZVA6uzIPLH2T8yvHEp8X7NjARqNcVbvkEHtoB0U/C8Z0wcyhMiYKVr0Piad/GqJRSSqkSR5Nm5VWNKzZmZt+ZjIocxaI/FjF4wWBWH1nt67As5WtA9Fh4aDvcMh0q1IUfJ1pDN+bdB4c2+jpCpZRSSpUQXkuaRWSaiJwQkR0uPntERIyI6DxglwF/uz8PtH6Az274jBD/EEYvHc0Lv75AUnoJuRnP7g/NB8GIRfD3X6HNMNj9DXzYEz6Ihs0zID3Z11EqpZRSyoe82dP8CdAnb6GI1AF6AcWw/rIqSVpWacnsfrO5u9ndzN47myHfDGHT8U2+Diu3qk2h76vw8G648RVrlo0Ff7d6n5c8DbEHfB2hUkoppXzAa0mzMWYF4GqJuNeBxwGdMPcyFOQXxGPtH2Na72lkmkxGfD+CV9a/Qqoj1deh5RZUHjr8Df6x1pq6rl43WPMOvBkFM26B35ZAZjEtHa6UUkopnxPjxcUeRKQesMgY08L5fiDQ0xgzRkQOAO2MMafc7DsKGAVQrVq1trNmzfJanO4kJCQQFhZW7PWWVp62V2pmKvNj57MyYSXV/atzV6W7qBtY14sRXprAlFPUOLqEGkeXEJgWS3JQdY7U7MPRGteR4V/uoo6p55hntL08o+3lGW0vz2h7eUbbyzO+bK8ePXpsNMa0y1tebEmziIQAy4FexpizBSXNObVr185s2LDBa3G6ExMTQ3R0dLHXW1pdbHutOryKZ1Y/w+nk09zb8l5GR47G3+5f9AEWlYw02PMNrPsQ/loNfkHQYgh0uBdqtvboUHqOeUbbyzPaXp7R9vKMtpdntL0848v2EhGXSbPHwzNEJEJEIi8ihoZAfWCrM2GuDWwSkeoXcSxVhnSt1ZV5A+fRt0Ff3t/2Pnd8ewe/xf7m67Dc8wuAFjfDyO+seZ9b3Q4751k3DU7tCVtmQnqKr6NUSimlVBEqVNIsIjEiUl5EKgKbgKki8ponFRljthtjqhpj6hlj6gGHgDbGmGMeR63KnPIB5Xnx6hd5s8ebnEg6wdBFQ/lw+4dkZGb4OrT8VWsO/d+AR3bDDf+BlHMw/z54vRksnQCxf/o6QqWUUkoVgcL2NIcbY84BNwGfGmM6Atflt4OIzATWAI1F5JCI3HNpoarLQc8rejJ/4Hx61OnBm5veZPj3wzlw9oCvwypYUDh0HA3/XA93L4ArOsPqKfBmK/jiNvj9R71xUCmllCrFCps0+4lIDeBWYFFhdjDG3G6MqWGM8TfG1DbGfJTn83qFGc+sLj8RQRG82v1VXu72MgfOHuCWb27h812fk2lKQdIpAg2i4bYZ1qIp3R6BwxuspbrfbmvNwJEcC9tmw+st6B4zCF5vYb1XSimlVIlV2KT5OeAHYL8xZr2INAD2eS8sdbkTEW5scCPzBs6jQ40OvLz+Ze5dci+HEw77OrTCC68N1z4N/9oJN30IoVXgh6fgP1daKw6ePYhg4OxB+OZBTZyVUkqpEqxQSbMx5itjTKQx5n7n+z+MMTd7NzSloGpIVd7u+TbPdXmOXad3cdOCm5j721y8OetLkfMLhMhb4J4lMPoX60ZC48i9TXoyLHvON/EppZRSqkCFvRGwgYh8IyInnUtjL3D2NivldSLC4CsH8/WAr2lRuQUT10zk78v+zvHE474OzXM1IsHd8uFnD8KPz8KRLVCaLgqUUkqpy0Bhh2d8AcwGagA1ga+Amd4KSilXaobVZGqvqTzZ4Uk2HNvA4IWDWfTHotLV6wzWsA1X/AJh1ZvwQXfrBsIlT8OhjZpAK6WUUiVAYZPmEGPMZ8aYDOfjcyDIm4Ep5YpNbNzR9A7mDJhDg/AGPPnLkzwc8zBnUlyt2F5CXfsM+AfnLvMPhgFvw2O/W8+Vr4Jf34MPe1o3Cn7/JPz1q87AoZRSSvlIYZPm70RkrIjUE5G6IvI48K2IVHTO3axUsapbvi7T+0znX23/xc+HfmbwgsEs+3OZr8MqnMhbof8UCK+DQSC8jvU+8lYIqQhthsFdc+CxfTDov9aQjvUfwbTe8FpT+PYxOLASMh0F16WUUkqpIuFXyO1udT6PzlN+G2AAHd+sip3dZmdki5F0q9WNcSvH8VDMQ/Rr0I+xHcYSHhju6/DyF3krRN7Kz/ktExocAVG3W4+Uc7BvCeyaD5s+hXUfWLNxNOkHzQZCvW5gL+x/Z6WUUkp5qlC/ZY0x9b0diFIX68qIK5nRdwZTt03lg20fsO7oOp7t+ixX17ra16EVnaDy0HKI9UhNgN+Xwq4F1jR1Gz+G4IrQpK+VQNfvbs3QoZRSSqkiU9jZM0JEZLyIfOB8f6WI9PNuaEoVnr/Nn79H/Z0ZfWdQLqAc9/94P8+ueZbE9ERfh1b0AsOg+WC45RN4fD8MnQGNroOd82HGEJjcyJoHeu93kJ7i62iVUkqpMqGwf8/9GNgIdHG+P4w1g0ahVgdUqrg0r9ScL/t/yTtb3uGTHZ+w5sganu/6PO2rt/d1aN7hHwxN+1mPjFTYvxx2L4Q9i2DrTAgoB437WD3QDa+FgBBfR6yUUkqVSoW9EbChMeY/QDqAMSYJEK9FpdQlCLQH8nDbh5l+w3TsYmfkDyN5ed3LpGSU8V5Xv0ArQR70Ljz6O9w1F1oMht+XwZd3weSGMHs47PjaGuKhlFJKqUIrbE9zmogEY930h4g0BFK9FpVSRaB11dZ81f8r3tj0Bp/v/pyVh1fy4tUvElkl0teheZ9fgDVko9F10Pd1+HOlNQZ69yLrZkK/IOuzZgPhqt4QVMJvnFRKKaV8rLA9zROB74E6IjIDWAY84a2glCoqIf4hPNXxKab2mkqKI4Vh3w3jzU1vkuZI83VoxcfuBw2iod/r8MgeGPEttBkOhzfC13+zxkB/MRS2fAHJsb6OVimllCqRCjt7xhIR2Qh0whqWMcYYc8qrkSlVhDrV6MTXA75m8vrJfLj9Q1YcWsFLV79E44qNfR1a8bLZoV5X69FnEhxab42B3rUAfvsebM4Eu9lAaNwXQiv5OmKllFKqRCjs7BnLjDGnjTGLjTGLjDGnRKSUrCShlKVcQDme6/ocb/d8mzMpZ7ht8W18sO0DMjIzfB2ab9hscEVH6P0iPLQd/vYTdP4HnP4dFj4Ar1wJ0wdYC6sknPB1tEoppZRP5Zs0i0iQc8W/yiISkbUCoIjUA2oVS4RKFbHudbozb8A8rr/iet7a/BbDvh3GH3F/+Dos3xKBWm3h+ufgwS0w+he4+l9w7jAsfhheuQo+7gtr34dzR3wdrVJKKVXsCuppHo011VwT5/MG52MB8HZ+O4rINBE5ISI7cpRNFpE9IrJNROaJSIVLil6pi1QhqAL/6f4fJnefzKGEQ9zyzS1M3zkdhy5NbSXQNSLh2qfhnxvg/jXQ/QlIOg3fPW4t5f1RL1jzDsQd9HW0SimlVLEoKGlejTU386PGmAbAs8AO4GfgiwL2/QTok6dsKdDCGBMJ/AY86WnAShWlPvX6MG/gPLrU6sIrG15h5A8jORiviWA2EajWDHo8Cf/4Ff6xHnqOh/Qk+OEpeKMFTO0Jq96EM//zdbRKKaWU1xSUNL8PpBpj3hKRa4B/A9OBs8AH+e1ojFkBnMlTtsQYkzWA9Feg9kVFrVQRqhxcmSk9pvBC1xf4LfY3bl54M7P3zsYY4+vQSp4qV8E1j8F9K+GBTXDdRDCZsPQZmBIF/+0GK16BU7/7OlKllFKqSEl+iYGIbDXGtHK+fgc4aYyZ6Hy/xRgTle/BrbHPi4wxLVx89g3wpTHmczf7jgJGAVSrVq3trFmzCvN9ilRCQgJhYWHFXm9pVRbaKzYjli9Of8GelD00CWrCHZXuIMIvwmv1lYU2AwhKPk7lU79S5eQqws/tBSAhtC4nq3ThZJUuJIXUsXqtL1FZaa/iou3lGW0vz2h7eUbbyzO+bK8ePXpsNMa0y1teUNK8A4gyxmSIyB5glLMHGRHZ4SoZzrN/PVwkzSIyDmgH3GQK0Z3Xrl07s2HDhoI2K3IxMTFER0cXe72lVVlpL2MMs/fO5tWNr+InfoztOJb+DfojRZD05VVW2iyXs4dh9zfWNHZ/rQEMVL7Kmsau2UCo1uKiE+gy2V5epO3lGW0vz2h7eUbbyzO+bC8RcZk0FzQ8Yybws4gsAJKBX5wHa4Q1RONiAhkB9APuLEzCrFRxExGGNhnK3P5zuTLiSsatHMeY5WM4laxTkxdKeC3odB+M/A4e2Qt9X4Vy1eGXV+G/V8NbbeDHiXB4E+iPAKWUUqVEvkmzMeZF4BGsm/quzpHk2oAHPK1MRPoAjwMDjDFJnu6vVHGqU74O03pP49F2j7Lq8CoGLxjMkgNLfB1W6VKuGrS/F4Z/A4/ug/5vQkQ9WP0WTO0Bb0TCD+Pg4HrIzPR1tEoppZRbBa4IaIz51UXZbwXtJyIzgWisOZ4PAROwZssIBJY6/9T9qzHmPg9jVqrY2G12hjcfTrda3Xhq5VM88vMj3PDXDYzrOI7wwHBfh1e6hFaGtiOsR9IZ2PudNYRj7fuw5m0oXwua9reGcNTpaK1eqJRSSpUQhVpG+2IYY253UfyRt+pTypsaVGjA5zd+zkfbP+K/W//L+mPrebbLs1xT+xpfh1Y6hVSE1ndaj+Q4+O0HK4He8DGs/S+EVTufQF/RBexe+1GllFJKFYr+JlKqkPxsfoxuNZpral/DuFXj+MeyfzC40WAeb/84YQF6R/RFC64ArYZaj9R42LfESqA3z4D1H0JIZWjaD5oOQDJ1DLRSSinf0KRZKQ81rdSUWX1n8d7W95i2Yxq/Hv2V57s+T8caHX0dWukXWA5a3Gw90hLh9x+tBHr7HNj4CV38wuDcIKsHukF38Av0dcRKKaUuEwXNnqGUciHAHsCYNmP49IZPCbQHcu+Se3lp7Uskpev9rUUmINRKjodMg8f2w20zOV2pHexeCF/cApOvhK9HwZ7FkJ7s62iVUkqVcdrTrNQlaFWlFbP7z2bKpil8vvtzVh1exYtXv0hU1Shfh1a2+AdBkxvZcyyE6ld3hj9+tnqg9yyCbV9CQBhc1dtKshtdDwEhvo5YKaVUGaM9zUpdomC/YJ7o8AQf9fqIjMwMhn8/nNc2vkaqI9XXoZVNfoFwVS8Y9A489jsMmwcth1iJ9Oy7YXJD63n7HGuMtFJKKVUEtKdZqSLSoUYHvh74NZPXT+bjHR/zy6FfePHqF2lWqZmvQyu77P7QsKf1uPFV+Gu11QOdtSKhPRAaXWf1QDfuA0E6TaBSSqmLoz3NShWhUP9QJnaZyLvXvsu51HPcufhO3tvyHumZ6b4Oreyz+0H9a6wVCB/eDf/3PbQbCUc2w7xR8J+GMOMW2Py5NU+0Ukop5QHtaVbKC7rV7sbXA79m0rpJvLv1XZYfXM5LV79Eo4hGvg7t8mCzQ93O1qP3S3B4I+yaD7sWWlPa2ZwJdrOB0KSftfCKUkoplQ/taVbKS8IDw/l3t3/zevTrHE86zq2LbuXjHR/jyHT4OrTLi80GddpD7xfhoW0wKga6PACxB+CbMfDKlTC9P6ybCvHHfB2tUkqpEkp7mpXysuvqXkfrqq15/tfneW3ja/z0109cV/c6ZuyewdHEo9SYU4MxbcbQt0FfX4da9olAzdbW49oJcHyHNfZ51wL49lH49jG4orPVA920P4TX8nXESimlSghNmpUqBpWCK/F69Oss/t9iJq6eyJaTW7I/O5p4lImrJwJo4lycRKB6S+vRczyc2HM+gf7+CetRu70zgR4AEXV9HbFSSikf0qRZqWIiIvRr0I/XN77OiaQTuT5LcaTw1MqnmLZjGhFBEVQMrEhEUIT1Osj5OvD86/DAcGyio6uKVNUm1iP6CTj1O+x2JtBLxluPmq3PJ9CVGvo6WqWUUsVMk2alitnJpJMuyzNNJjVDa3Im9Qw7EnYQmxJLQnqCy21tYqNCYAUqBFY4n1gHRrhNtCsEVcDf5u/Nr1W2VG4E3R6xHmf+Z61CuGsB/DjRelRvCU0HWkl0lat8Ha1SSqlioEmzUsWsemh1jiYevaC8RmgN3rr2rVxl6Y50YlNjiU2J5UzKGWJTYolNzfHaWf573O/EpsRyNvUsBuOy3nIB5XIl1zkT65zvs54D7YFe+f6lTsX60HWM9Yj7yzkH9EJY/oL1qNLUSp6bDYSqTa1hH0oppcocTZqVKmZj2oxh4uqJpDhSssuC7EGMaTPmgm397f5UDalK1ZCqhTp2RmYGZ1PPuk2usxLwg/EH2XZyG3GpcTiM69k8QvxCciXV7oaKZJWH+IUgZT1hrHAFdP6H9Th3BHYvsnqgf34Zfp4ElRqdT6CrR2oCrZRSZYjXkmYRmQb0A04YY1o4yyoCXwL1gAPArcaYWG/FoFRJlHWz35ub3rRmzwgtutkz/Gx+VAquRKXgSoXaPtNkEp8WX2CSfSr5FL/F/kZsSixpmWkujxVgC8idWLtJrrOS8PIB5Ut3kl2+JnQcZT0STsAeZwK98g345VWIqOccAz0QarXRBFoppUo5b/Y0fwK8DXyao2wssMwYM0lExjrfP+HFGJQqkfo26EvfBn2JiYkhOjraZ3HYxEZ4YDjhgeHUo16B2xtjSMpIcptc5yz/89yfnEk5Q3JGsstj+Ykf4YHhBfZgZyXZFQIrFO2XL0phVa3VB9uNhMTTsHexlUCveQdWvQnhdawbCJsNtGbksOlNnEopVdp4LWk2xqwQkXp5igcC0c7X04EYNGlWqtQQEUL9Qwn1D6VOuTqF2iclI4W41LjshDrn2Oyc7/ec2cOZlDPEp8W7rhshxBZC1flV802ucybg/nYf3PwYWgna3G09kmNh73fWGOj1U+HXd6BcjfMJ9BWdrNULlVJKlXjFPaa5mjEm6w6oY0C1Yq5fKVXMgvyCqO5Xneqh1Qu1fXpmOnEpcS57sHf+sZPgCsGcSTnDH2f/IPZ4LHGpcW5vfgzzDzufWBcwjV9EUATBfsFF+dUhOAKi7rAeKefgtx+s5bw3TYd170NoFWsRlWYDoe7VYNfbTJRSqqQSY1z/simSg1s9zYtyjGmOM8ZUyPF5rDEmws2+o4BRANWqVWs7a9Ysr8XpTkJCAmFhYcVeb2ml7eU5bTPPuGqvTJNJUmYSCZkJJDicj8zzz/GO+FzvExwJZJLp8vgBEkCYLYwwe9j555yv8zwHSdBFjcu2ZyRT8cwmqpxcRaXTG7BnppLuV46TVTpxqnIXYiNaYopgikA9vzyj7eUZbS/PaHt5xpft1aNHj43GmHZ5y4s7ad4LRBtjjopIDSDGGNO4oOO0a9fObNiwwWtxuuPr8aaljbaX57TNPFMU7WWMIT49PveY7AJuhEx1pLo8lr/N3/UMI3mHijh7ussHlr9wUZq0JNi/zBoDvfd7SIuHoHBo3NfqgW7YA/wubvo/Pb88o+3lGW0vz2h7ecaX7SUiLpPm4v5b4EJgODDJ+bygmOtXSl3mRITyAeUpH1CeuuULXhrbGENyRrLLmx3PpJ5/HZsSy6H4Q8SmxpKYnujyWHaxEx4Y7nqO7ObXEtFqIBXPHCDir/VE7PuWClu/wC+wPFzVx0qgG10L/gUPIVn8x+Lzs7PMKbrZWZRS6nLmzSnnZmLd9FdZRA4BE7CS5dkicg/wJ3Crt+pXSqmiICKE+IcQ4h9CrbBahdon1ZGaK5nOmVzn7Nn+LfY3zqSc4VzauQsPUq08UJ5w8SMibjURK2KI+NlGRFhNKlZpRkSNNkSEVbtgrPbSP5fmmgf8aOJRJq6eCKCJs1JKXQJvzp5xu5uPrvVWnUopVRIE2gOpHurZzY/Zi9K4SrKTzxB79gB/JRxhS/pJ4o7+TOaxFS6PJcgFN0amOFJ4ds2zbD6xmSB7EIF+gQT7BRNoDyTIL4ggexBBfkHW+xyvc23jF0SALaB0z62tlCr5ts2GZc/R/ewh2Fwbrn0GIktGH6veqq2UUj7mb/OncnBlKgdXLnjjTAeZf67i3M65nNn3vZVc+wdwplozYqteydtukunkjGR+OPADqY5Ut3NnF0SQ88l13mTb+d7VZ3mT7wvK3OynCbpSl5lts+GbByE9GQE4e9B6DyUicdakWSmlShObHVv9a6hQ/xoqZGbCoXXWPNC7FsD+tcytXZOj/hf+aK/hyGRJh+cBa5x2mskgxZFGSmY6KZnWc6rj/OsURxqpmekkZ1rPqZnpJDvL8m6Tkp5CSuo5zjnOb5/iPFZqZjqZbqYELEiQzZ9Amz+BtgCC7dbrIFsAQTZ/guwBzvdWWaDNn+DsMmubQHuO7W0BBNnPb5v3GDaxUSF2K/xxSf86lxVtL89oexXCD09Bep6L+vRkWPacJs1KKaUugc1mLZByRSfo/SIc3sSYmf2YWLkiKTlWHQzKzGTM6TPw6UAABAh0PsK9HKIB0oEUm5AiNlJFSBYhVcRZJufLnNtklaW42SZVhJPOY+XdxnGRvdMBmYYgk0nQckOgMQQZQ1Cm9RxoDMHO58BMQ7DJdLlNkPNxwTbZZdZ2ZWU5myiArT4OohSJAm2vi3X2kK8jADRpVkqpskEEarelr18lOHWaNyMqcMzPTvUMB2Ni4+hLGPzf3OIPCwhwPsoXQ33pmQ6rh9uRlqPXOy271zu7d91ZZm1r9YofPH6E8hXDL9gvNjOdo46cvetWeYZxPd93QfzFL09Pd8D51/acPeM5P8/qJQ/I7lHP+TrnfoE5Xvt5ccXJzZs307p1a68dv6zR9iqE2cMh8cSF5eG1iz8WFzRpVkqpsuTaZ+j7zYP0PXTkfJl/MPR/Eep28V1cxcTf+Sh3Eft6Oi9sRmZG9hjxVEcqKRkppDhSSMlIITUj9fxrF9vk3T7r+WxGKsczErL3y/osPTP9Ir4R+InfhePO/c7f8HnBjaEuxqm7229/aDXqVL0qe1v/IliQpyw7+7+0y+L/4CXp/WL2mOZs/sHWzYAlgCbNSilVlmSN+1v2HObsISS8ZN19Xpb42fzws/kR6h/q9bocmQ4ric6TZGcn5Bmp7hN4h+sEPj4tnpOOk1aCn2P7tMy0Qsf17Oxns1/bxZ7vjaCBfoEE24NzJ98FzdqSldRn7ecs87f5642iZVEJ//mlSbNSSpU1kbdC5K38rCuQlRl2m50QmzVfuLdlmszsBNtdIp7iSGHrjq3Ua1TPZUKed7/EjEROp5zO3dvu7I2/GDaxFSrZdtej7mp7lz3sOtVi8SvBP780aVZKKaVUNpvYshf0yU/QgSCim0RfUl3GmHyHrVyQtBdiuEtyRjJxqXEXJOcpGSkXzGFeGDmnWixMsp03Wc/6/I/EP5CDkm+SH2gPxCa2goNSPqFJs1JKKaV8QkSye3S9zRhDWmZaruQ733HnOZLt/Ia7nEs6l/sz57aZLm4UnfbTtALjzEqkc/akFzY5zy7PMf95fkl+SUzQF/+xmDc3vcnRxKPUmFODMW3GlJjVTDVpVkoppVSZJyLZvcXhgd6dbNEYQ0ZmBsmO5Owx47/8+guRbSLdjzvPkay760lPSE9wmeQ7jOOi4gywBbgcM+7x2PR8etiz9rMXYiaXxX8sZuLqidnDdo4mHmXi6okAJSJx1qRZKaWUUqoIiQj+dn/87f7WfItAzYCatKjcwiv1pWemX9Aznu+No45UKznPSupd7BebEuuyBz4jM+OiYvSz+RWYbK86vOqCce4pjhTe3PSmJs1KKaWUUurS+Nv88Q/wJ4wwr9eVNdVirp7xPMm3qxtHcyXnefY7l3aO40nH3d4YeizxmNe/V2Fo0qyUUkoppQrFm1Mt9prTi6OJRy8orx5avcjruhglbwS4UkoppZS67IxpM4Yge+6bQoPsQYxpM8ZHEeWmPc1KKaWUUsrnssYtZ8+eEaqzZyillFJKKXWBvg360rdBX4+XtS8OPhmeISL/EpGdIrJDRGaKiPcnaFRKKaWUUuoiFXvSLCK1gAeBdsaYFoAduK2441BKKaWUUqqwfDU8ww8IFpF0IAQ44qM4lPKJ+ZsPM/mHvRyOS6bWrz/xWO/GDGpdy9dhKaWUUsqNYu9pNsYcBl4B/gKOAmeNMUuKOw6lfGX+5sM8+fV2DsclA3A4Lpknv97O/M2HfRyZUkoppdwRY0zxVigSAcwFhgJxwFfAHGPM53m2GwWMAqhWrVrbWbNmFWucAAkJCYSFeX+i8LJC2ys3YwxJGZCYbkhINySkGRLS4fNdqSS5WFAp1A9uaxJAoF0IsEOgXQi0Q0CO99Yz2ESK/wuVAHqOeUbbyzPaXp7R9vKMtpdnfNlePXr02GiMaZe33BdJ8y1AH2PMPc73dwOdjDF/d7dPu3btzIYNG4orxGwl8c7Nkqwst1dKuoOzyenEJqURm5hOXFIasUnW+7ikNOKS0olNyiq33sclp+PI9M7/rwA/GyEBdoL97QQ7n0MC7AQ5n61yv+zy4BzbZm13wT4BdkL8/QgKsBFgtyElMDEvy+eYN2h7eUbbyzPaXp7R9vKML9tLRFwmzb4Y0/wX0ElEQoBk4Fqg+DNidVnKzDScS0nPlfDGJqbnSHTTzie/OZLj5HSH22MG+tmICAmgQog/ESEBNK5ejgohAUQ434cHW88Rof5UCAngrg/XcvTshUuFVg8P4qvRnUlOd5Cc5iApzUFKuvVslWWQnOu985F+/jk+JYOT8am5tklKy8DT3N1ukwIS8hzlOV7nTdaD3CXtfnZstpKXlCullFLuFHvSbIxZKyJzgE1ABrAZ+KC441ClX3Kaw+r5ze7ptRLcs7l6gXM/n01Ox90fV2xCdoJbIcSfGuFBNK1RnogQfyqE+DsT4QDneysJjggJIMjf7lHcT/RpwpNfb8+ViAf72xnbpwl1KoZcSpO4ZIwhzZFJSlomSekZbhJyR3ZCnpIjac+brGf1uOfdJy0j0+O4gvxtzuTajyB/GyHOZDtngp03aT/yZzrH1v2Vo9yP4AAbwf5+uXrRQwLs+Nt1wVOllFJFxyezZxhjJgATfFG3KnkyHJnOoQ/ne3bj8iTCuYY9OMtT80nUQgLsuXp/a1UIzn6dsxc4qywiJIByQX7F0vuZNUtG9uwZFYK9OnuGiBDoZyfQz044/l6pw5FpLuj9TnIm23l7w/NP2jOIS07n6NnkXMdLSnecv9jZs71QMfnZJHcCnqOn+3yPuM2ZtLvvRQ/JM6wlK7kP8i+ZQ1hAZ2dRSilv0BUBVZExxpCQmkFsouuhDtnDIbKS4uR0YhPTOJfi4q44J7tNzvfshvhTp2IILWv5ExGaM+E93wtcwdkrHOjnWe9vcRvUuhaDWtcqM2Pc7DYhLNCPsEDv/EgxxpCakcmPy1fQpkMnN0l3BslpmSSlZeTbi56U5iA2MT3X8JWU9EzSHJ73lrtKyN0l4Bck6jkS8pz75EzW/S6itzxrdpasv2Rkzc4CaOKslFKXQJNm5VK6I9MazpCUZ/xv1uusJDj5fO/wmYRUHD/84PaY5QL9qBB6fpxv3UqhuRJiKxEOoELWEIlQf8oF+pXY3jxVfESEIH87YQFCzQrBXqkjw5FpJdJ5E+001wm4q6ErSc6e8TOJaS571D3lb5ccCXk+PeI5yj9c+ccFdSWnO3h+0S4qhgbgZxP87DbsNsHPJtazXfCz2XK9t9sEf5sNuz3HdjZrP6WUuhxp0lzGGWM4l5LhTH4vHP8b52Lcb1xSOgmp7nt/A+y27B7dCiEB1K8cSpuQAM6dOkarJg1z9Pie7wWuEOKvY0xVieZnt1HObqNckHeGsGT1ludKuJ094+56xPMOUcnqUU9Ky+BUQqo1/jzHPukO93d8nk5M4+5p6y75e4hwQRLtlyPxzp2M50jEnc/+hUzYs8uyk3ZbjnrOv7eOmfu9n5u6c5W5OG5caiZnEtNyHNOKwyboxbtSSpPm0iQ1w3E+4c0z7dlZ51AHT6c9Cw8+n/xWCgugUdWwXMMewl2M/w0JsLv8BRITc4bo7g292QRKlVpZveWe3jjqiXRHJtf8Z7nL2VmqhAXy3l1tyMg0ODKN8zmTdEfu9xkO63VGpsHhyMy1fYbDuU2ussw8xzSkOzJzvc+5XXK644K6rG0yceSoO8PFMYrF8qUui91dGOS9CHB3YWC32fDP894vxwVHrouQS7owcHUR4vqC44J6c+yvFwpKXUiTZhe8fRONu2nPzg91KNppzyoE5xj/G3p+/G94sL/+qVWpMsTfbnM7O8u4vk1pV6+iD6O7NMYYl4m4u+Tc7YWA870j05Ce5/2uPXtp0LDRBRcBhb0wcHcRkpKeSUamI1ddGXkuFNwd05fc/nXA+ReA9JQUym362YMLg7wXAUX51wk3dbu4AHE5RMn5rBcKvleSb2TWpDkPT2+icTXtWVxS3sUvcpefTU53O29ucU17ppQqm4p7dpbiIuJMgLz4oy4m6Q+iu9b3XgUeMsaQaXCRTOdOvrN6/8/33Lu/MMhwuX/BFxzZfw3INNkXBkeOHqNSlTCXFyWp6Zmk57lQKOxfJ3wp34Q9v158FxcGef8acOJ4Kktjt7u8CHGVxOcdTuTuwuCihyiVwAuFkn4jsybNeUz+Ya/Lm2iemredH3Ye8+q0ZxVC/Ckf5K+LPiilLklZm53lciUi2AXstpLZKWKdX22L9JhZFwoZbhL2XBcGbi4UCjNMKN+/DmQPRcpdb0EXIanZf1E4X3fO+hOTHeyMPXbBxU9Ju1DISqxzXijkHL5TmOTc3YVB7u1sOf4SYD2//uM+lznY5B/2atJcEh2JS3ZZnpTmYN+JBCJC/KkdUTamPVNKKaVKkpwXCl6awdJn3F3E5rxQyHn/QN6EPeOChL7wQ5RcXRg4HDkuApzvs4cN5a3HzUVJmvPm5sL+dSLne0+4y82KWxk7JS9dzQrBHHbxj1OrQjA/PtzdBxEppZRSqqwq6X9R8JZcPfnOpP2GN3/h2LkLb2T21lSjntI5wPJ4rHdjgvOMDw72t/NY78Y+ikgppZRSqmyx26zVakMC/CgfZP31fuwNTUp0DqY9zXmU1ZtolFJKKaVKspKeg2nS7ILeRKOUUkopVfxKcg6mwzOUUkoppZQqgCbNSimllFJKFUCTZqWUUkoppQogxvh2Uu3CEJGTwJ8+qLoycMoH9ZZW2l6e0zbzjLaXZ7S9PKPt5RltL89oe3nGl+1V1xhTJW9hqUiafUVENhhj2vk6jtJC28tz2mae0fbyjLaXZ7S9PKPt5RltL8+UxPbS4RlKKaWUUkoVQJNmpZRSSimlCqBJc/4+8HUApYy2l+e0zTyj7eUZbS/PaHt5RtvLM9penilx7aVjmpVSSimllCqA9jQrpZRSSilVAE2anURkmoicEJEdOcoqishSEdnnfI7wZYwliZv2migih0Vki/Nxoy9jLElEpI6ILBeRXSKyU0TGOMv1HHMhn/bSc8wFEQkSkXUistXZXs86y+uLyFoR+V1EvhSRAF/HWhLk016fiMj/cpxfUT4OtUQREbuIbBaRRc73en7lw0V76fmVDxE5ICLbnW2zwVlWon5HatJ83idAnzxlY4FlxpgrgWXO98ryCRe2F8Drxpgo5+PbYo6pJMsAHjHGNAM6Af8QkWboOeaOu/YCPcdcSQV6GmNaAVFAHxHpBLyM1V6NgFjgHt+FWKK4ay+Ax3KcX1t8FWAJNQbYneO9nl/5y9teoOdXQXo42yZrqrkS9TtSk2YnY8wK4Eye4oHAdOfr6cCg4oypJHPTXsoNY8xRY8wm5+t4rB+ktdBzzKV82ku5YCwJzrf+zocBegJznOV6fjnl017KDRGpDfQFPnS+F/T8citve6mLVqJ+R2rSnL9qxpijztfHgGq+DKaU+KeIbHMO39ChBi6ISD2gNbAWPccKlKe9QM8xl5x/Ct4CnACWAvuBOGNMhnOTQ+iFR7a87WWMyTq/XnSeX6+LSKDvIixx3gAeBzKd7yuh51d+3iB3e2XR88s9AywRkY0iMspZVqJ+R2rSXEjGmmZEeyLy9x7QEOvPnUeBV30aTQkkImHAXOAhY8y5nJ/pOXYhF+2l55gbxhiHMSYKqA10AJr4NqKSLW97iUgL4EmsdmsPVASe8F2EJYeI9ANOGGM2+jqW0iCf9tLzK39XG2PaADdgDcm7JueHJeF3pCbN+TsuIjUAnM8nfBxPiWaMOe78RZQJTMX6xa2cRMQfKwGcYYz52lms55gbrtpLz7GCGWPigOVAZ6CCiPg5P6oNHPZVXCVVjvbq4xwWZIwxqcDH6PmVpSswQEQOALOwhmW8iZ5f7lzQXiLyuZ5f+TPGHHY+nwDmYbVPifodqUlz/hYCw52vhwMLfBhLiZd1YjsNBna42/Zy4xz/9xGw2xjzWo6P9BxzwV176TnmmohUEZEKztfBwPVY48CXA0Ocm+n55eSmvfbk+OUsWGMn9fwCjDFPGmNqG2PqAbcBPxlj7kTPL5fctNdden65JyKhIlIu6zXQC6t9StTvSL+CN7k8iMhMIBqoLCKHgAnAJGC2iNwD/Anc6rsISxY37RXtnELHAAeA0b6KrwTqCgwDtjvHUQI8hZ5j7rhrr9v1HHOpBjBdROxYnSGzjTGLRGQXMEtEXgA2Y12IKPft9ZOIVAEE2ALc58MYS4Mn0PPLEzP0/HKrGjDPup7AD/jCGPO9iKynBP2O1BUBlVJKKaWUKoAOz1BKKaWUUqoAmjQrpZRSSilVAE2alVJKKaWUKoAmzUoppZRSShVAk2allFJKKaUKoEmzUkrlICLjRGSnc6nbLSLS0Vn+oYg0K6I6DohI5QK2eSrP+9VFUbeviMigomo/pZTyBZ1yTimlnESkM/AaEG2MSXUmtgHGmCNFXM8BoJ0x5lQ+2yQYY8KKsl5vcC7UIM5VGvPb7hNgkTFmTrEEppRSRUx7mpVS6rwawCnnMrcYY05lJcwiEiMi7ZyvE0RksrNH+kcR6eD8/A8RGeDcZoSIvJ11YBFZJCLReSsUkfkistF5rFHOsklAsLOne0ZWnc5ncda9Q0S2i8hQZ3m0M4Y5IrJHRGY4E1pEZJKI7HL2nr/iIoaJIvKZiKwRkX0i8rccnz0mIuud+z7rLKsnIntF5FOsVbvq5DlervpEpAswAJjs/E4NnY/vnd/9FxFp4tz3ExH5r4hsEJHfRKSf5/+MSilV9HRFQKWUOm8J8IyI/Ab8CHxpjPnZxXahWEvjPiYi84AXsJZibgZMx1r6tbBGGmPOOJdzXi8ic40xY0Xkn8aYKBfb3wREAa2Ays59Vjg/aw00B44Aq4CuIrIba8nxJsYYI87lo12IBDo5v9tmEVkMtACuBDpgrWK2UESuAf5ylg83xvya8yAiUilvfcaYOBFZSI6eZhFZBtxnjNnnHALzLtDTeZh6zjobAstFpJExJqUQbamUUl6jPc1KKeVkjEkA2gKjgJPAlyIywsWmacD3ztfbgZ+NMenO1/U8rPZBEdkK/IrVY3tlAdtfDcw0xjiMMceBn4H2zs/WGWMOOYdKbHHGchZIAT4SkZuAJDfHXWCMSXYOGVmOlbT2cj42A5uAJjni+zNvwuxUYH0iEgZ0Ab5yLpP+PlYvf5bZxphMY8w+4A9nvUop5VPa06yUUjkYYxxADBAjItuB4cAneTZLN+dvCMkEsoZzZIpI1s/VDHJ3TATlrcs5XOM6oLMxJklEYlxt54HUHK8dgJ8xJkNEOgDXAkOAf3K+RzenvDe4GKze5X8bY97PE3c9INFVAIWszwbEuelJdxeLUkr5lPY0K6WUk4g0FpGcPb1RwJ8XebgDQJSI2ESkDlbPbV7hQKwzYW6CNTwiS7qI+LvY5xdgqIjYRaQKcA2wzl0Qzl7dcGPMt8C/sIZ1uDJQRIKcwyuigfXAD8BI5zEQkVoiUtX9V863vnigHIAx5hzwPxG5xbmPiEjOuG5xtltDoAGwN786lVKqOGhPs1JKnRcGvOUc95sB/I41VONirAL+B+wCdmMNb8jre+A+57jjvVhDNLJ8AGwTkU3GmDtzlM8DOgNbsXpgHzfGHMu6kc6FcsACEQnC6jl+2M1227CGZVQGnnfeAHlERJoCa5z3FCYAd2H1Yrvjrr5ZwFQReRCrB/pO4D0RGQ/4Oz/f6tz2L6wLgfJY4551PLNSyud0yjmllLrMichEIMEYc8HMGj6I5RN0ajqlVAmkwzOUUkoppZQqgPY0K6WUUkopVQDtaVZKKaWUUqoAmjQrpZRSSilVAE2alVJKKaWUKoAmzUoppZRSShVAk2allFJKKaUKoEmzUkoppZRSBfh/cpCF8KnRjFIAAAAASUVORK5CYII=",
      "text/plain": [
       "<Figure size 864x216 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Uncomment to execute the code (it takes around 16 minutes)\n",
    "\n",
    "# problem={\"taxi_pos\":(0,0),\"passenger_pos\":(3,3),\"domain_map\":DEFAULT_MAP}\n",
    "# results = plot_steps_per_simulations(\"new_comparison_mcc_vs_mcts_vs_rave.png\", problem, [\"Monte Carlo Control\", \"Monte Carlo Tree Search\", \"RAVE\"],[10,20,30,50],10)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "06723efa",
   "metadata": {},
   "source": [
    "![comparison](https://raw.githubusercontent.com/GabrieleSerussi/mcts/main/new_comparison_mcc_vs_mcts_vs_rave.png)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "b1c49ec5",
   "metadata": {},
   "source": [
    "Our previous hypothesis seems to be confirmed by the last plot.\n",
    "\n",
    "In summary:\n",
    "- **MCC** (Monte Carlo Control) is the **best** algorithm among these ones in terms of **performance** but it **requires** a **lot of data** to learn a good policy\n",
    "- **MCTS** (Monte Carlo Tree Search) is **scalable** and can be used in problems where the state-action space is too big to fit in memory, but it **does not always find the optimal policy**\n",
    "- **RAVE** (Rapid Action Value Estimation) is an **extension** of **MCTS** that **speeds up** the **learning** of the **action values** by **introducing a bias**. This leads to a **more efficient** **use of data** and to a **better policy** than the one learned by vanilla MCTS."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "0ec0f9d3",
   "metadata": {},
   "source": [
    "# TODO 1\n",
    "\n",
    "In this exercise you will try to see how the algorithms behave in a harder problem.\n",
    "In this case we will bring the passenger **farther** away from the taxi, so that the agent will need to take **more actions** to achieve the goal.\n",
    "\n",
    "Please, follow the instructions below:\n",
    "\n",
    "1. Define a problem with the passenger location = (5,4), the taxi location = (0,0) and the map = DEFAULT_MAP\n",
    "2. Run plot_steps_per_simulations with this new problem for Monte Carlo Control, Monte Carlo Tree Search and RAVE with [10,20] simulations and 3 experiments\n",
    "3. Compare the performance of the algorithms in this new problem"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "48097737",
   "metadata": {},
   "source": [
    "# TODO 2\n",
    "\n",
    "In this exercise you will try to see how the algorithms behave in a bigger map. In this case, despite the taxi being as close to the passenger as before, the **map will be bigger** and thus the **Monte Carlo Simulations** are likely to be longer, more expensive and **noisier**.\n",
    "\n",
    "Please, follow the instructions below:\n",
    "\n",
    "1. Define a problem with the taxi location = (2,0), the passenger location = (3,3) and the map = BIG_MAP\n",
    "2. Run plot_steps_per_simulations with this new problem for Monte Carlo Control, Monte Carlo Tree Search and RAVE with [10,30] simulations and 3 experiments\n",
    "3. Compare the performance of the algorithms in this new problem"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "6ed4588b",
   "metadata": {},
   "source": [
    "# TODO 3 (Optional)\n",
    "\n",
    "In this exercise you will modify the way RAVE balances the two estimates. In particular you will need to modify the function with which we estimate the value of a node, so that the reliance on the RAVE value decays slower compared to what happens in RAVE with the same value of k.\n",
    "\n",
    "Please, follow the instructions below:\n",
    "\n",
    "1. Implement the TODO in the function _mc_rave of the class NewRAVENode\n",
    "2. Define a problem with the taxi location = (0,0), the passenger location = (3,3) and the map = DEFAULT_MAP\n",
    "3. Run plot_steps_per_simulations with this problem for NewRAVE with 20 simulations and 3 experiments\n",
    "4. Compare the performance of NewRAVE with the performance of Monte Carlo Control and Monte Carlo Tree Search and RAVE"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "id": "81bcc47b",
   "metadata": {},
   "outputs": [],
   "source": [
    "class NewRAVENode(RAVEMonteCarloTreeSearchNode):\n",
    "    def __init__(self, state, n_simulations=100, parent=None, parent_action=None, k=3, gamma=0.78):\n",
    "        super().__init__(state, n_simulations, parent,parent_action, k=k, gamma=gamma)\n",
    "    \n",
    "    def _uct_rave(self, child, c_param=0.8):\n",
    "        \"\"\"\n",
    "        Returns the UCT-RAVE value for a child node.\n",
    "        :param child: The child node for which the MC-RAVE value is calculated.\n",
    "        :param c_param: Exploration parameter.\n",
    "        :return: The UCT-RAVE value for the child node.\n",
    "        \"\"\"\n",
    "        mc = float('inf') if child.number_of_visits == 0 else child.average_reward\n",
    "        rave = float('inf') if child.number_of_visits_rave == 0 else child.average_reward_rave\n",
    "        \n",
    "        ##############################\n",
    "        \"\"\"\n",
    "        TODO: modify beta so that the reliance on the RAVE value decays slower compared\n",
    "            to what happens in RAVE with the same value of k.\n",
    "            Hint: Can we replace the squared root with a different function?\n",
    "        \"\"\"\n",
    "        beta = None\n",
    "        ##############################\n",
    "        q_star = (1-beta)*mc + beta*rave\n",
    "        uct_rave =  float('inf') if (child.number_of_visits == 0 or self.number_of_visits == 0) else q_star + \\\n",
    "        c_param*np.sqrt( \\\n",
    "            np.log(self.number_of_visits)/ child.number_of_visits \\\n",
    "            )\n",
    "        return uct_rave"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "72882e0d",
   "metadata": {},
   "source": [
    "Now we will extend evaluate_policy so that it will be able to evaluate also the NewRAVE algorithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 117,
   "id": "fffc8681",
   "metadata": {},
   "outputs": [],
   "source": [
    "def evaluate_policy(problem, algorithm, simulations, render:bool=False):\n",
    "    if not algorithm in [\"Monte Carlo Control\", \"Monte Carlo Tree Search\", \"RAVE\", \"NewRAVE\"]:\n",
    "        raise ValueError(\"Algorithm must be one among: Monte Carlo Control, Monte Carlo Tree Search, RAVE and NewRAVE\")\n",
    "      \n",
    "    env = new_environment_creator(taxi_pos=problem[\"taxi_pos\"], passenger_pos=problem[\"passenger_pos\"],domain_map=problem[\"domain_map\"])\n",
    "\n",
    "    if algorithm == \"Monte Carlo Control\":\n",
    "        # Monte Carlo Control\n",
    "        monte_carlo_control = MonteCarloControl(env, gamma=0.99, max_steps_per_episode=1_000)\n",
    "        step = monte_carlo_control.run_and_update(number_of_simulated_episodes=simulations, render=render)\n",
    "        return step\n",
    "\n",
    "    elif (algorithm==\"Monte Carlo Tree Search\"):\n",
    "        # Monte Carlo Tree Search\n",
    "        mcts = MonteCarloTreeSearchNode(state = env, n_simulations=simulations, gamma=0.78)\n",
    "        step = mcts.run_and_update(max_number_of_steps=1000, render=render)\n",
    "        return step\n",
    "    \n",
    "    elif (algorithm ==\"RAVE\"):\n",
    "        # RAVE\n",
    "        rave = RAVEMonteCarloTreeSearchNode(state = env, n_simulations = simulations, k=1, gamma=0.78)\n",
    "        step = rave.run_and_update(max_number_of_steps=1000, render=render)\n",
    "        return step\n",
    "    \n",
    "    elif (algorithm ==\"NewRAVE\"):\n",
    "        # NewRAVE\n",
    "        rave = NewRAVENode(state = env, n_simulations = simulations, k=1, gamma=0.78)\n",
    "        step = rave.run_and_update(max_number_of_steps=1000, render=render)\n",
    "        return step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c78a0c65",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "colab": {
   "provenance": []
  },
  "kernelspec": {
   "display_name": "cs224n",
   "language": "python",
   "name": "cs224n"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}