Games/assignment_mean_connect4.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Adversarial Search: Playing \"Mean\" Connect 4\n",
    "\n",
    "\n",
    "## Instructions\n",
    "\n",
    "Total Points: Undegraduates 10, graduate students 11\n",
    "\n",
    "Complete this notebook and submit it. The notebook needs to be a complete project report with your implementation, documentation including a short discussion of how your implementation works and your design choices, and experimental results (e.g., tables and charts with simulation results) with a short discussion of what they mean. Use the provided notebook cells and insert additional code and markdown cells as needed.\n",
    "\n",
    "## Introduction\n",
    "\n",
    "You will implement different versions of agents that play \"Mean\" Connect 4:\n",
    "\n",
    "> \"Connect 4 is a two-player connection board game, in which the players choose a color and then take turns dropping colored discs into a seven-column, six-row vertically suspended grid. The pieces fall straight down, occupying the lowest available space within the column. The objective of the game is to be the first to form a horizontal, vertical, or diagonal line of four of one's own discs.\" (see [Connect Four on Wikipedia](https://en.wikipedia.org/wiki/Connect_Four))\n",
    "\n",
    "> **The mean part:** This game has an additional rule. Every time it is a player's turn, the player can decide to instead of playing a new disk, take a bottom row disk of the opponent and place it in any column. All disks above the removed disk will fall down one position. Note that a player can only move an _opponent's disc_ that is in the _bottom row_ of the board.\n",
    "\n",
    "Note that normal [Connect-4 has been solved](https://en.wikipedia.org/wiki/Connect_Four#Mathematical_solution)\n",
    "in 1988. A connect-4 solver with a discussion of how to solve different parts of the problem can be found here: https://connect4.gamesolver.org/en/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task 1: Defining the Search Problem [1 point]\n",
    "\n",
    "Define the components of the search problem associated with this game:\n",
    "\n",
    "* Initial state\n",
    "* Actions\n",
    "* Transition model\n",
    "* Test for the terminal state\n",
    "* Utility for terminal states"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Your code/answer goes here."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How big is the state space? Give an estimate and explain it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Your code/ answer goes here."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How big is the game tree that minimax search will go through? Give an estimate and explain it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Your code/ answer goes here."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task 2: Game Environment and Random Agent [3 point]\n",
    "\n",
    "You can use a numpy character array as the board. Note that the following function can create boards of different sizes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0 0 0 0 0 0 0]\n",
      " [0 0 0 0 0 0 0]\n",
      " [0 0 0 0 0 0 0]\n",
      " [0 0 0 0 0 0 0]\n",
      " [0 0 0 0 0 0 0]\n",
      " [0 0 0 0 0 0 0]]\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "def empty_board(shape=(6, 7)):\n",
    "    return np.full(shape=shape, fill_value=0)\n",
    "\n",
    "print(empty_board())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Instead of colors (red and yellow), you can use 1 and -1 to represent the players Max and Min. Make sure that your agent functions all have the from: `agent_type(board, player = 1)`, where board is the current board position and player is the player (1, -1) whose next move it is and who the agent should play."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Visualization code by Randolph Rankin:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAASEAAAD4CAYAAACjW1BIAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8rg+JYAAAACXBIWXMAAAsTAAALEwEAmpwYAABAy0lEQVR4nO2dd3xUVfr/Pye9k9BbNPQOgYSiKCiCIuqCurqyuiw21J/Y29rXtrr2r6uIKJYFEbsCYgFRpJMJvQqEFiAklJBC2kye3x+HIVmYufeee8+ZC+N5v17npWQm97xz7swzZ+4953kYEUGj0WjcIsJtAY1G88dGByGNRuMqOghpNBpX0UFIo9G4ig5CGo3GVaLc6LRx48aUkZHhRtcajcYlcnNzDxBRkxN/7koQysjIgMfjcaNrjUbjEoyxnYF+rr+OaTQaV9FBSKPRuIoOQhqNxlV0ENJoNK6ig5BGo3EVHYQ0Go2r6CCk0WhcRQchjUbjKq4sVhSBMbcNNBpNIGSlItMzIY1G4yo6CGk0Glc55b+O2SEqCujWDcjMBBo25D8rKgJWrAA2bQJqa9U7REcDPXoAvXoBqal86lpYyB02b5Y3lTUiJob337MnkJLC+9y3jzts2aK+fwCIi+PnoUcPIDkZ8PmAvXuB3FwgLy80DgkJ3KF7dyApiTvs3s0ddgbczSSfpCSgd2/+ukxIALxeYNcu7rB7d2gcUlKAPn2ALl2A+HigpgbYsYM77N0bGoeAEFHIW1ZWFlmFv3WstUGDiKZPJzp6NPjxSkqI3n+fKCtL7NhW29ChRF9+SVRZGdyhuJho4kSinj3l988Y0YgRRDNnElVVBXc4eJDojTeIOneW7xARQTRyJNEPPxDV1AR3KCwkevllonbt5DtERRFddRXRvHlEXm9wh717if71L6Izz5TvEBNDdO21RAsWEPl8wR127SJ66imili3lO8TFEY0dS7R0qbFDXh7Ro48SNW1q/diiAPAQnRwPTvpBKJrsINSuHdH8+eKDMnMmUYsWck52165Ey5aJO3z2GVHjxnIcevcmWrVK3OGjj4hSU+U4DBhAtHGjWP8+Hw/KSUlyHM47j2jbNjEHr5fotdeI4uPlOAwfzoOLCNXVPCDGxMhxuPxyon37xBwqK4kee4woMtL8+KKEbRC68Uai8nLxAfFz6BA/WU5O9p13ElVU2HcoLCS66CJnDg8/zF/Edtmzh88knTg8+6zxrMOM7duJ+va1339EBA8kRp/4Zvz+O1GPHvYdoqKIJk2y3z8R0dq1RB072neIjSWaOtWZQ26u+exQlLAMQvfeKz4QgfB6if72N3sn/J//lONQVWU/GL7yihyHo0eJLrzQnsO778pxKCkhOuccewHok0/kOBw6RNSnj70ANGOGHIf9+/nsWtQhLo7o55/lOOzeTdS2rQ5CQQfg6qvFB8GImhqi888XO+E33STXobKSqF8/MQdZgdhPWRlR9+5iDrICsZ/iYuMXf6D26qtyHQoLxa/RvPeeXIfdu4kaNhRz+OwzuQ5btwb/mixKWAWhZs2IDhwQHwQztm+3fl3izDP5p7ZsNmzg02krDl26OPsaGAyPx9o1AYBf4De6+GyXX3+1/sYbPNjZV7BgzJpl3eGSS+T3T0Q0bZp1h9Gj1ThMnKiD0Elt+nTxAbDKa69ZO+GzZ6tzeOopaw4LFqhzuO8+aw52LoRb5eabzfuPjCTaskWdw1/+Yu4QF0eUn6/O4eKLzR1SUtR8MPsJ9BVZlLAJQunpaj55/ZSUECUnG5/wzp3V9U9EVFRkPhvq10+tw86d/DqLkcPQoWodNmwwf/NdcYVah2XLzB3GjlXrMGeOucOdd6p1+PJLdUHotFsxPW4cX4yoiuRkYMwY4+fcdpu6/gGgcWPg6qvddTjjDOCyy9x16NIFOP98dx369QOystx1GDIE6NjRXYc//Qlo1UrNsU+7IHTxxer7GD5cO5g5MAZceKG7DnFxwHnnuevQsCEPVCqJiAAuuij44xkZQOfOah2iooChQ9UcW0oQYowNZ4xtZoxtZYz9Q8YxAxEdzZfeq8boky8lBWjXzl2HVq2AZs3cdejcmW9FcNOhVy+1s2IrDmazpD+KgxMcByHGWCSAtwBcDKArgNGMsa5OjxuIDh2A2FgVR/5fWrSo23N2Il278k8m1XTowPd+BaJbN/X9A8YBXztoB1nIeDv1A7CViPKIqBrAdAAjJRz3JBITVRw1MME+5UPlEBHBNzq66RAfHzzghsrBaLalHU4dByfICEKtANTfB5x/7Gf/A2NsHGPMwxjzFBUV2erI57MnaAevVzvU1gbPOBAqh2BjoB1OLQcnyAhCgXIf0kk/IJpERNlElN2kyUnlqC0RqpQHlZU87YabDocPA2Vl7jrk5wd/LFQORv1oh1PHwQkyglA+gPR6/24NQEl2kqKi0Az4mjXBo/62bUBxsXqH3Nzgj61bB1RVqXfweII/tmJFaPIyGTkYjZF2CK2DE2QEoRwAHRhjbRhjMQCuATBDwnEDsmSJqiPXsXSps8dVO9TUhOaFZ+RQWgps2OCuw969PDGYmw6bNwOHDrnrsHo1UF7uroMTHAchIvICGA/gRwAbAXxGROudHjcYH3yg6sh1TJ7srkNtrXkfqh2qq4EpU9x1KC8Hpk931+HQIeDrr4M/TgR89JFahz17gB9+CP54VZX5ODnl99+BBQsUHTzQMmrVzeneMZV7hRYtMl8iHxXFM/Kp4vvvzR3i43nKCVV8+qm5Q1qas1xOZrz7rrlDy5bO8iiZ8cor5g7t26vZQOvnySfNHXr3Vtc/EdE996jbtnFaBqGRI8UHwApeL9FZZ5mfcIDnH1JBVZX1tK+3367Gobycv7GsODz8sBqHw4eJWrWy5vD882oc9u+3nvXyrbfUOOzcab6X0d+mTFHjsGkT36Srg9AJzWnmuEC89JK1k+1vshJY1efxx8Uc5s2T73DXXdb7j4ggWr5cvsP111t3iIkhWrdOvsOVV1p3SEzkeZplM2yYdYe0NPkzdKMPZlHCLgilpPAUlLKYO1c8t2+jRkTr18tz+PZb63l8/K1FC/F8ykZMm8aT5Ys4ZGTITWUxaZJY/wDPbFBYKM/h5ZfFHXr35gnZZPHEE+IOZ5/NE9PJ4u67g/clStgFIYBnnVu6VHwwTuTHH4kSEsRPOMATrK1e7dzhq6/sJzg/4wyizZudO0yZIh4E/a1DB6IdO5w7TJwoHgT9rXt3OTMB0Rlx/da3L0/F4hQr14GCtUGDnAdDn49n7TTqR5SwDEIAf+M+/7y9HEMVFUQPPmieN8esxccTvf66vYuTZWVEd9zhrH+AXzewm2C9uJinqnXqkJZm/7rEgQNEf/2rc4cmTYi++MKeQ0GB86IHAL+W9d139hx277aWxMysZWTY/6qel8crlpj1IUrYBiF/y8oi+vxza3dKKip4mRvZNbfOPpt/pbJScaK8nOckFs2lbNbOP5/fXbMSEEtKiCZM4IniZDoMH2492frhwzyAN2sm12HUKOuZJ4uKiF58kX+9lunwl79Yn6kXFPBqJQ0ayHUYM4ZoxQprDvn5/CtgYqK1Y4sSLAgx/lhoyc7OJo/F5Zcs0KYQA1q2BEaN4mkHevcG0tL4z/0VWD0evu7j4EGx44pwxhnAyJHcITOTV2Ctra2rwLp8OXc4ckSdQ7t2PClZVhZPeZGSwh0KCvhCR79DsK0hMujcGRgxAsjO5hVYU1L4SnR/BdZly4BvvgEqKtQ59OjB8wFlZfH/T0riDvn5/LWwdCkwY4baFeh9+vDcS1lZfMd7YiJfcOqvwLp4MTBrFv+ZKvr1A4YN4w5duvDN0TU1wPbt3GHRImD2bLF9aKKhgzGWS0TZJ/083IKQRqMJDbKC0GmXWVGj0YQXOghpNBpX0UFIo9G4ig5CGo3GVXQQ0mg0rhKCWgWhJymJ357PzKxLWO+/Rb9qFc+cqJqUFH5rtlcvfoueqO4W/erVoUlKlprKb8n27Ml9iIB9+7jDmjVqbwn7adiw7hZ9cjK/Bey/Rb9unbqUofVp0oSPQ/fu/LXh8/HkeLm5PCdSKNKjNm9ed4s+IYH/3f5b9Bs3hiZBXKtWdbfo4+P5+d+xgzts3ix+t0sagRYPqW4qFisyRnTppbw8s9FiwepqvqJ2yBC5i8IAvuXhiit4xUyjxYKVlXyPVqDSuk5bdDTRNdcQzZ9vPK5HjxJ9+CGv5CrbITaWZxlYvNjYobSUr/LOzJTvEB9PdOONRB6PsUNxMdGbbxJ16ybfISmJ6LbbzLf1HDzIy4936CDfoUEDXp11wwZjh8JCon//m6hNG+vHFgXhvGK6Rw97m1l//VXeiuXsbHs7uX/4gah1azkO55xD9Pvv4g5ffy1vxfLQofb2kE2bxvcCynC47DKiPXvEHSZP5hujZThcfbX4hlqfjwdEu/sYT2xjx4rnnPJ6+epxszLkOgjVa3ffzXPw2KWsjH9qOznZjz1mb++an+JisbQRgdrzzztLrHXggLM9SxERRG+8Yb9/IqJ9+4gGD7bvEBXFA4kTdu1yNjuMiyOaPt2Zw7ZtRL162XdITHSeZmbjRqJOnYz7ESUsg9CTT4oPRCB8Pj5ttnPCX3lFjoPXS3TddfYc7G5cPZGqKr7nSrR/xog++USOw9GjYjl06gcgWfmdSkuJBg4Ud4iNtb5nzoxDh4j69LEXgMy+Bltl/36iLl10EAo6ANdfLz4IRvh8RCNGiJ3wu+6S61BTw9MwiDg8/rhch8pKvhlYxOGll+Q6lJUZv/gDtXfeketw+DDRmWeKOcgKxH727xf/mjxrllyHXbuIUlN1EDqppacTHTkiPghm7NkTfMBPbB078k9t2Wzdav2aQGammvzKa9fyC9xWHAYOtJY1QJSlS62nWLnoIvn9E/FZjdU3/1VXqXH45hvrDjfeqMbhv//VQeik9vXX4gNglQkTrJ1wWdPuQLzwgjWHnBx1Do88Yt4/Y/zagSrGjzd3iI7meZhVMWaMuUNCAp+1qMLKV+SGDeVmdTyRCy7QQeh4a9NGbWWD8nLz2VDPnur6J+LXA+LjjR3OOUetw549/DqLkcOIEWodtmwxf/Ndc41ah5UrzR3GjVPrMH++ucP996t1mDlTXRA67VZM33ILEKHQOiEBGDvW+Dm33qquf4DnQBo92l0Hf14mNx3at+d5eNx0yMwEBgxw12HQIKBrV3cdLr4YOPNMNcc+7YKQ2YsyFH1oB/5BcMEF7jrExwMDB7rr0LgxX53vpkPbtjyJnUoiI9Wdb0dBiDF2FWNsPWOsljF2UrIi2cTE8GXvqsnKCv5Yaqr6E27mkJ7OtyK46eDPzuemQ2YmEBWCjUdGDkaP/ZEcnOB0JrQOwBUAfpPgYkqHDjwQqaZpU/4JF4guXdT3D/CvIrGxgR8zm5rLwijgawftIAtHnyNEtBEAWIhysCYmhqQbAME/5UPpEB8feKNrqBxiY/nXrkCbK0PlYDTb0g6njoMTQnZNiDE2jjHmYYx5ioqKbB0jFLu+zfr6IznU1gbf3R0qB6N+tMOp4+AE05kQY2wugOYBHnqUiL612hERTQIwCeCJ7i0b1mPnTju/JU5FBU+74abDwYNAebm7Dkb9aAftIAvTIEREQ9V0Lc6hQzz/SUaG2n5Wrw6eY2bHDh4gGjVS65CbG/yx9et5oIyPd89h5Uo+RpGR7jkYPaYdQuvghNPuFv3ixer7WLTI+PElS9x18PmAnBx3HcrLgbVr3XXYvx/Iy3PXYcuW4LPmUDmsXQuUlrrr4ASnt+gvZ4zlAzgLwHeMsR/laAVn8mTVPZj3odrB5wM++MBdh8pKYOpUdx1KSoDPPnPXobCQF0c0wuxcOWXHDmDOnOCPV1ebnyunrF/PC0UqIdAyatXN6d4xsyxxTpg3z3yJfESE2v1KVjYtxsby8sWqCLZpsX5LTualpFXx5pvmDk2a8J3/qvjXv8wdMjLUbOL1849/mDt0766ufyKi//f/1G3bOC2D0IUXig+AFaqriXr3Nj/hANGf/6zG4ehR82RS/nbDDWocjhwhOuMMaw53363GoaiIqGlTaw5PPKHGIT/fem34l19W47Bli/k+Qn+TlVfqRNasCZxVQZSwCkIA0bvvig+CGU8/be1k+9unn8p3uP9+MYfZs+U7jBtnvX/GiH77Tb7DNddYd4iKIlqxQr6DSH6puDiiTZvk9u/zieWXSk6WP0Ovrg6eXE2UsAtC8fFECxeKD0QwZszgiepFAkBKir3c1sH45BP+phZxaNRI7tfTSZPE+geIWrYkysuT5/DKK+IObdrwmYssnnxS3KFLF/G80kbcc4+4Q+/eclN63HRT8L5ECbsg5I/8v/wiPhgn8uWXRDEx4iccIEpL4wm4nPLf/4oHQX9r1oxo1SrnDhMmiAdBf0tPlzMTePFFe/0DRO3bE23f7tzh8cftO3Tvbi/Jfn18PnsByN/69nV+vbCmhujmm437ESUsgxDA37iPPGLv4mRpqf3c0vVbdDTRM8/Yy3J4+DCviuDUIS6OX5ewc4G0sJBXh3DqkJjIA5mdfE979/IqGU4dGjQg+uAD8f6JeJWQoUOdOzRqZD/Z/ZYtROee69yheXP7ObfXreOBzKwPUcI2CPlb58680kJ5ufkxi4uJ/vMf8RzCZq1nT6IpU4gqKswdDh7kXztatpTr0Lcvv1ZlpQJJYSHP4tikiVyHgQN59ksrFUj27uXX4tLS5DoMGUL03XfWgvKuXbxiSnKyXIeLLyb66SdrQTkvj+jBB61fhLbaRo3ipa2ssHkzv9Fg9VuBKMGCEOOPhZbs7GzyeDyWniu6NzYtDbjkEp52oHdv/m+grgKrxwN8913wLREyaNy4ziEzk6f/qK2tq8C6fDkwe7baSrDNmwMjRnCHXr14BdbaWqCggK98Xb4c+P57vsZEFa1bA8OH11VgTUnhlUf9FViXLQN+/FFtFdaMDOCii/g49OjBK7B6vUB+Pn8tLF3K1+CorIDaoQMwbFhdBdbERL4Py1+BdfFiYN48/tZWRZcuwNChdRVYExK4w/bt3GHRImD+fLFjivoyxnKJ6KSUP2EXhDQaTWiQFYROu20bGo0mvNBBSKPRuIoOQhqNxlV0ENJoNK6ig5BGo3GVENQqCD3NmvHbwpmZQMOG/Gf+W/S5uTwpmWpatuQOvXrxW/REdbfoPR6guFi9Q3o6d+jZk98eJwL27asbh5IS9Q4ZGXW36JOTeZoS/y36FSuAsjL1Du3a8VvT3bvzW/Q+H7B7N3dYuRI4elS9Q8eOdbfoExL4MgH/LfqVK9Uu1wD4XebOnetu0cfH81v0O3Zwh9WrA+czDwmBFg+pbioWK0ZHE40ebb6fzOcj+vFHopEjrdc6t9piY4n+/neiZcuMHbxeolmzxDZIWm0JCXy5vdmGzpoaoq++krNC+MSWlER0++185a0RVVV8ZbHIJk2rLTWVb33YvNnYoaKCb5np31++Q6NGfAGi2b668nKi996znsFBpDVrxhdi7tpl7FBSQvT223zbidVji4JwXjE9YIC9mug5OUTdusk52eedR7Rtm7jDggVEHTrIcRg+nGj3bnGHOXPkrR6//HKiggJxh5kziVq0kONw7bVEBw6IO3z2GVHjxnIcbrrJ3kbSjz4yL0Nutd15J1FZmbjDxIn8g0QHoePixu3JJ50llKqsDJywSaS9+KK9/VJ+ysv5DMpu/xERRG+9Zb9/Iv5J+Oc/23eIjib68ENnDocOOZsdxsURff65M4fCQv6BYtchKYlvF3HCnj38g9WuQ2oqT87nhB07iDIzjfsRJSyD0CuviA9EMB580N4Jl5VIyucjuvVW8f4ZI5o2TY6D10t03XXiDlFR9jdLnkh1Nd/vJOoQG0v0889yHCoqiIYNE3dITCRaskSOQ2kp34NnJwCtXCnH4fDh4LmEdBACv+YgmyuvFDvhDz8st3+fj2eNFHF4/nm5DtXVRGefLebgdBZ2IhUVRL16iTlMmSLXoaxM/GvyN9/IdTh0iKh1azEHWYHYT0FB8A3OooRVEGrXzt53XTP277d+TaB7dzW5jXft4snSrDj0768mt/HmzfyrjRWHCy6Q3z8R/zSPirLmMGqUGoeFC63nVxozRo3DDz9YD0Djx6tx+PxzHYROaipSmvp5/31rJ1xmVscTef11aw5r1qhzsJLqNiLC3sV4q1hJdRsby9OBqMJKqtvkZD5rUYWVVLdNmqj5YPYT6FqdKGEThDp1Ev/jRaioMJ8NZWerdThyxPzuxJAhah327zfPK6NqBuJnxw7zmYiqGYifdevMA4CqGYifJUvMHR55RK3Djz+qC0Kn3YrpW25Re/y4OOD6642fc+utah1SUoBrr3XXoWlT4Mor3XU480yeE8lNh27dgHPPdddhwAC+6NWIcePUOgwdyhd9qsBp8cOXGGObGGNrGGNfM8ZSJXkF5YILVPfAB/xUdxgyxF2HyEhg0CB3HRITgX793HVo1owHKjcdOnTgAVslERHqXnNOZ0JzAHQnop4AfgfwsHOl4MTFAV27quyBk5UV/LGGDflWBDcdMjKARo3cdejWjS/9d9Ohd28eDN10MHrsj+TgBEdBiIh+IiJ/cs6lAFo7VwpO+/ZAVAh2uzVqBDRpEvixzp3V9w8AbdoAsbHuOnTpEvwx7aAdZCHzmtANAL6XeLyTCMUnr1lffySHmBg+DXfTwagf7XDqODjBdF7BGJsLoHmAhx4lom+PPedRAF4AHxscZxyAcQBwxhln2JKtqbH1a7YIlgD+j+Tg8wVPAB8qB6NE/Nrh1HFwgmkQIiLDS6SMsb8DuBTABcduwwU7ziQAkwCe6F7QEwBPOxAKyst52o1AbN8eGofCwuApJkLlYNSPdtAOsnB6d2w4gIcA/ImIlGdlKS4Gtm1T3QuwalXwGcDu3Tw3kWpyc4M/tnGj2pJFVhxWrVJbqseKg9Fj2iG0Dk5wek3oTQDJAOYwxlYxxiZKcDJk0SLVPQALF57aDrW1vGaXmw4VFTwQuelw4ADw++/uOuTl8URxbjqsWxeaJHlm7wvbBFrBqLo5WTF97rmi6zTF8PnMNy5ecolah+pq88qso0erdSgvN6+Kesstah0OHzavSPrAA2od9u4138P2zDNqHbZuNV8x/X//p9Zh5Uq9Yvo4CxbwVJSqmDMH2LLF+DmzZ6v9WvjNNzwFqhFffKH2E/iTT4DDh42fM3Wq2k/gDz7gMy4jJk9Wm5510iTzr53vvKP24vCECdaeo7KK7FtvqTv2aTcTAng6UCdJxIJRUUHUtav5pw7AN/SpoLSUKCPDmsM116hxOHiQqHlzaw7jxqlx2LvXen36++9X45CXx3MEWXF4+mk1DuvXW68N//rrahxycogiI9XNhE7LIKRq+vnww9ZOtr998IF8h9tvF3P48kv5Dn/7m5jDTz/Jdxg50nr/ERFEixfL7d/nIzr/fOsO0dFEq1fLdaipIerXz7pDfDzRli1yHSorg6dAFiXsglBMjNwX/yefWM8d428JCXJTerz7rlj/AM89ZJbUXoRXXxV3aNyYaMMGeQ7//Ke4Q8uW5gnlRbj3XnGHtm15alZZ3HyzuEPXrkRFRXL693qN04iIEnZBCOCJt2bOFB+ME/nww8DTTSstKUlONru33hIPgv6WliZnJvDCC/b6B3hVB6dpRX0+XhnCrkN6ur2CB/Xxeonuvtu+Q/v2zoNhdTVPlG/XoXt3ovx8Zw6VleZ5jEQJyyDkb+PH82spohw8yCsz2D3Z/hYRwe/SVFSIOxQUEF1xhXOHqCiiJ57gZXRE2b2b6OKLnTvExPBAVlMj7pCX5yzBvL/Fx/Ov6nauGW7c6CzBvL8lJ9vPPb56tZzSP2lpRFOn2nNYvtzatVFRwjoIAbxkzWuvWctwV1BA9Nxz/NPb6cmu39q35zOaI0fMHfLzeaWQhg3lOnTtyr/WWcmyt2MHT4ZlNZ2s1darFy9dYyUob93KLyxbvQBstfXrx79iWwnKGzfy8jixsXIdzjmH6Isv+MzGjDVreKGD6Gi5DhdcwIsQWEkD7PEQXX+99Xp8ogQLQow/Flqys7PJ4/FYei5jYseOjweGDeNpB3r3BtLS+M/9FVg9HuDnn9XeUk1KqnPIzOQVWGtr6yqwLl8O/PIL35uligYN6hx69eKJ0mprgYICvvJ1+XJg/ny1t3UbNeK5l/wVWFNS+O1ufwXWZcv4kguVNG3KHbKyuENSEnfIz+evhaVLgSVL1Dq0bMlz8fgrsCYm8tefvwLr4sVATo5ah/T0OocuXXgV2JoavhUjN5cvRBRdfCoaOhhjuUSUfdLPwy0IaTSa0CArCJ12ixU1Gk14oYOQRqNxFR2ENBqNq+ggpNFoXEUHIY1G4yohSBsfejp04LeFMzN5dQyg7hZ9Tg6wc6d6h86duUOvXvwWPdH/3qLPz1fv0K0bd+jZk98eJ+I77/0OqvPgMNSiB9YiGx70wFokoxQ+RGIvWiIXWViOfihEM6UOkZH878/KArp357fofT6enC43l78eDhxQqoCoKP5a9N+iT0jgywT8t+iXLzfPWOCU6GigT5+6W/Tx8fwW/Y4ddeNw5Ihah6AEWjykuqlYrJiQwPPbrFplfswlS/gmTdkLw5KTie64w9o+qvnzif7yF/vbRYK11FSi++6ztpFx7ly+Wtvq4jSrrTEK6WE8R9txpuETfWA0G8PpUswgoFaqQ7NmfAW52faFmhqib74hGjZM7hgARK1bEz37LNG+fcYO1dVEn31GNHiwfIeMDKIXXzTfT1ZZyVdYn3WW9WOLgnBeMT10KF/9K8r69WK7lI3apZfa27y4YgVfYSzD4eqriQoLxR2WLCHq3FmOw1i8T4eQKvyLv2AwtcVWKQ633UZUUiI+Dt9/zwOH0/4Z4xtgy8vFHb76Ss5K/shIvg+vslLcYdo0ayv5RQnbIPTKK+KDUZ+aGqJ//MP+yY6IIJo40ZlDVRXf/2bXITqaaMoUZw4VFXzJvl2HOBylrzDK0TunDAl0NabbPkRSEtEPPzgbh+JinjnTrkNaGp/lOuHAAaIhQ+w7NG3K9385oaDAfFYkSlgGIbubBAPxzDPiJ5sx/qkhiwceEHeIiuJ7g2Rx663iDrGooJ8hkHzHoHkRQddiivCvJibKyylUXU00apS4fmqq80wCfioq7H1FbNKEaNMmOQ6lpUQDBwbvS5SwC0Iqcgtfd53YCVeRW1gkmRcgP7mbzyf+KfwB/m4r4ARr1Yii/lgi9Guyk7tVVPCUGCIOspO7lZbyHEVW+1eR3O3gweD5zkUJqyDUpYu9tBlmHDpE1KKFtROelWUvZYUZ+/ZZ31k/eLCaNLfbt/OvNlYcLsFMqQHI3zagM8WiwtLTVSX993is3zhQlfT/11+tD5uqpP+zZukgdFKbN098AKzy8cfWTnhOjjqHt9+25iBr2h2If//bvP8oVNMuSLiSG6Q9imdMnxYfLy+TYCDuuMNcNS3N3oVwq/z97+YOLVqo+WD2c/nlOggdb927i//xIlRVmSd5P/tstQ5lZUQNGhg7DB+u1uHgQZ650sjhakxXFoAIoHy0pEjUGD7tppvUjsPmzeaq996r1iE319zhn/9U6/DLL+qC0Gm3YvqWW9QePyYGuOEGdx0SE4G//c1dh4YNgauvNnHAO0odWmEvLsNMYwfF49CxI8/D46ZDnz580WkwGANuukmtw3nnAZ06qTm20zLQzzDG1hyrvvoTY6ylLLFgnH++6h7MX3SngsN557nrEI1qDIT6UrRDMC/oY8nJ/A2q3MFgHFq25IHKTYdOnYBWrdQ7qHrdO50JvUREPYkoE8AsAE84VwpOQgLfDqEaoxd2kyY8S51qsrKCP9auHd8K4qZDd6xDLKrVOyB4AfQ+fYCIEMzljcbB6LE/koMTHJ1CIiqp989EAORMx5j27fleINWkpfG0oIFQNSU9kTPOAOLi3HUw6qcTNofGwaCfU2IctINjHG9gZYw9B2AMgCMAlH5RCfamDGVfoXaorHTPITqazzQC5aGOQwAxBRj1E6pxMOpHOzjHdCbEGJvLGFsXoI0EACJ6lIjSAXwMYLzBccYxxjyMMU9RUZEt2aoqW79mi+og3zT+SA4+X/BE+FWIDYlDNWKCPhaqcQh2HrSDHExnQkQ01OKxpgH4DsCTQY4zCcAkgCe6typYn7w8/qZQfR2gtBTYvz/wY9u2qe3bz759wNGj7jps3Rr8sW1oFxoHtA/ucCqMg3ZwjNO7Yx3q/fNPADY50zGmtFTdQNRn5Uq+EiIQe/fysjmqyQ1+PRabN/OxcNNhNXqhJgTpqHIR/GqokZ9UB4N+tINznM4pXjj21WwNgAsB3CXByRDVdaqs9OG2AxGvVeWmQxXi4IHB4hVZDjg36GOHDwPr1ytXMByHnTt5cjI3HTZsAA4edNfBEYFWMKpuTlZM9+8vvlJTBK+XJ4IyWp06bJhah8pKno7ByOHKK9U6lJbyJG1GDtdjstIV00VoZLp/7K671I7Drl3mSd8ef1ytw4YN5sP10ktqHZYv1yumj7NsmdpqlbNn85SXRsyZA2xS+MXziy94KlgjvvmGpyhVxZQp5l/5PsFoHEAjZQ6TcSOqYHxL5sMP1X41nTjRvErtpElqLw5PmGD+nLff5iljVfHmm+qOfdrNhACeDVHFDvbycl5P3soH9ZAhanawHz5M1KqVNYeRI+X3T0S0fz9R48bWHP6Gj5TMgnYinZJxxNLTb79dzThs2mS+f87fHn5YjcPKlTxnlBWH559X47BgAc+dpWomdFoGIYDohRfEB8GMu+4Se69MmCDfQTS74dSp8h2uvFLM4VtcJj0IXYgfhH5FdmYFr5dvVLbaf0SE82yGJ1JVJZb6NyaGaN06uQ7l5UQdOgTuT5SwC0KRkTxBuSzee0/8vRITQzRnjjyHV18Vd0hIIFq0SJ7DU0+JOzTAYVqBTMeBx9/uw0vCv9a4MdHGjfLGYdw4cfVWrYjy8uT07/XyPEmiDm3b2st1HojqaqLLDD5fRAm7IATw3MqffCI+GCfyxhuBp5tWWlwc0bffOnd4/nn779ukJOfB0OcjeuQR+w5pOEgLITB1CNBqEEl34nXbh2jalKe9cEJVFdENN9j/M9LTeQEFJxw9yiux2HVo145o61ZnDqWlxgFIB6ET2pgxPCuiKHv3mg+01XbLLfYSW+3YwauFOO2fMaK777ZX4WHLFqJzznHuEIkaegTPUiVihH95HbpSXyxz7BAdzdPuVleLj0NuLlGPHs7HIS6O6OWX+WxGlMWLiTp1cu6QmMgvF9i5bjlvHlGbNuZ9iBLWQQjgZVKeeooHFjPy8ogeeognJpcRgPytVSs+o7FSdmfzZqJ77rGeRtVqy8jgFUgOHjR3WL+eV/mIj5fr0AGb6T+4nYqRYvrklehF4zCRYlAp1aFrV14FpbTUfByWLycaO1Z+DbjMTKL33+czGzMWLiT661/l14Dr149fN7RS+mfePLHrgaIEC0KMPxZasrOzyePxWHouY2LHjooCzjmHpx3o3ZvviAfqKrB6PMCSJXwYVRETA5x7LnfIzORpN2pr/7cC6/Ll6voH+GbDQYO4Q69evAJrbS1f7e2v+ql6pW0iynAuFhyvwJqCEngRdbwC6zL0x2pkKnVISak7Fz168AqsXi+vgOvxAEuXql/wmJpady66deNJ62pq6iqwLl7MV8GrpFGjOocuXXhanJoaYPt27rBokfj2D9H3EGMsl4hOWuEadkFIo9GEBllB6LRbrKjRaMILHYQ0Go2r6CCk0WhcRQchjUbjKjoIaTQaV1GflSrEMFZXpykzk9fPAupu0efkAGvXqnWIiOD9Z2fz2+OpqfxOQv1b9Bs2qHWIigL69uUOPXvyW9VEPGPjihU8G8Hvv6t1iEY1+mPZ8Vv0ySiFD5H/c4t+m0HmRBnExgIDBvBb092781v0Ph/PQJCby2/R79ypVAEJCXUO3brxf3u9dbfolyzhSwZUkpQEnHVW3S36+Hh+i37HjjqHffvUOgQl0OIh1U3FYsXUVF6L28py9XXr+M7rhAS5C8MaNyZ69FGinTvNHVasILr5ZqLYWLkOzZvzRZtW9g/5F+lFR8t1aI1d9Dweov1oYvrkhTib/oqpppVWRVubNtYXbfoX6dnduhOsdezItwQVFxv37/MR/fCDvNX79Vu3btYWbXq9RDNmEF10kfVji4JwXjF9+eVEBQXig5KXR3T++XJO9rXXEh04IO6waZPYbm2jdtNN5i/4QKxZQ9SnjwyHWroTr1MZxKN7DrKoG9Y6doiI4Kvh7dRlX7Ag+I5xkRYVxcsyV1WJO8yZQ3Tmmc4dYmOJXnzRXsqbmTOJWrY070OUsAxCERFEkyaJD0Z9fD6if/3L/smOjiaaNs2Zg9frbPNoXJzzjALV1UR33mnfIQkl9BOcbYKrRAzdgPdsHyItjQcSJ5SXO9s82rQpkcfjzKGkxNmsKD3deUqPQ4eILrjAuB9Rwi4IMeb8zV+f118XP9mRkXJ20Pt5+mlxh9hYorlz5Tk88IC4QyJKaTEG2H/XnNBuwdvCv5aayhOAycDr5TNbUYcmTfjMVgbV1TxpnahD69ZE27fLcaioMN5cLUrYBaEnnxQfBDNEc8i88op8h2uuEXN49135DpdcIubwKa6yFWyCNS8iaBB+Ffq12bPljkF1NVFWlvX+GSP67Te5DkePEnXubN0hKsp5KpMTKSkJ/vVQlLAKQr162fu+bcaRI0RnnGHthA8caC9VgxlFReZJ7v3toovk909ElJ9P1KCBNYc/4zOpAcjftqItJaDM0tNvuEHNOKxZY/2i/d13q3FYutT6zvonnlDjMHeuDkIntYULxQfAKp9/bu2Er16tzmGyhSIWjBFt26bO4bXXzB1iUEn70ExJECKAnsLjpk9LSuJ5uVVx333mqo0b28vjZJWbbzZ3SE9X88HsJ9B1MlHCJgj17i3+x4tQU2OeaH7wYLUOR48SNWxo7HDZZWodiovNlzBciynKAhABtA/NKBpVhk+77Ta147Btm/mt+4ceUuuwerX5cD33nFqHhQvVBaHTbsX0uHFqjx8VBdx0k7sO8fHA3//urkODBsDo0SYOvKq3MppjP0bhG2MHxePQti1w4YXGz1Ht0LMnX2gYjIgI4MYb1ToMHMgXWqpAShBijN3PGCPGWGMZxzPivPNU9wAMHnzqOwwa5K5DDKowAEvVO2B+0MdSU/mqeOUOBuOQns4DlZsOXboAzZq56+AEx0GIMZYOYBgA5cVwk5KAjh1V98K3fQSjeXOgZUv1DtkGFZY7duTbMNx06Ik1iEGNegcET35ndJ6kOhiMQ1aWdnCKjJnQawAeBEASjmVI27Z86qmaBg2Cf7K0V7vV6TitWvGvZW46dOgQ/LH22BoaB2wJ7nAqjIN2cIyjtzRj7E8A9hDRagvPHccY8zDGPEVFRbb6izOuCCyV2FjtEBUVPOjHoTIkDrEIXl85VOMQ7DxoBzmY7qJnjM0F0DzAQ48CeASAyWU7DhFNAviVzOzsbFuzpsrQvO4BBK8t/kdy8HqD12GvNKkRL4sqBH/lh2ocjOrMawfnmAYhIhoa6OeMsR4A2gBYzXg2+tYAVjDG+hFRgVTLY+Tl8TeF6q9kR44A+/cHfmxraL6FID8fqKhw18Eo1cdWxSk4jjsg+EXAU2IctINjbL+diWgtETUlogwiygCQD6CPqgAEAGVl6nPgADzfTjAKCoC9e9U7GJXj+f13oKTEXYc16IlqRKt3QPCrrkbnSaqDwTioLpt0ujg44bRbJ/Trr+r7mB/8rvAp4/Dbb+46VCMWSzFAvQOC3xcuLgZWrVKuYDgOu3fzGbqbDhs3Bp+5h8rBEYFWMKpuTlZMZ2aKrtMUQ6+Y5ugV0xy9YpqjV0zXY9UqXi1SFd98A+zZY/yc+fOBNWvUOXzyCXDokPFzZs1S+wn8wQfA0aPGz/kcV6EA6lbJTcI41CDG8DlTpvAZkSomTOBvOSMmTzYfKye8+ab5cyZOBKqr1Tn85z/qjn3azYSAU2MX/dln6130gN5F72+qdtEvWaJ30Z+SQUjVgIvmE3r5ZfkOovmEnGaWDMSIEWIO03G11ABkJ5/Qd9/JHYPqarGUt+GaT+jIEZ1PyPCkf/yx+EAEw0rqihNbZKTztKr1eeopcYeYGJ6XWBb33y/ukIAyWoSzHAcffxuHicK/1qABLx4gA6+X6K9/FVdv0oRo40Y5DtXVRH/6k7hDq1Y8d7oMKiqMU7yKEnZBCODT1HfeER+M+vh8RM8+a/89ExVFNHWqMwevl+jhh+07xMURff21M4fqaqI77rDvkIQS+hHD7B8APMf09Zhs+xCpqc5nI+XlRFc7mNg1bUqUk+PM4cgRoksvte/QujXR2rXOHA4dIhoyxLgfUcIyCPnbqFFE+/aJD0peHtF55zl63xxvo0fbq7axcSPRAEnpmW+4wV61jdWreZ4m5w61NB5vUCkShX95ObKpK9Y5doiI4Hmy7VTb+O03onbtnI9DVBS/XGDnuuVPP1m/LmnUYmKIXnjBXrWNGTOIWrQw70OUsA5CAJ+O33eftbpja9fyW7uy6441asRnNDt2mDvk5vISPbLrjjVrxvNv5+ebOyxdSjRmjPy6Y62wm57Dw1QA8yvsv+EcugbTKAJeqQ4ZGUQvvWTtg2HuXKIrrpBfd6xDB15AwSzzo8/Hc2Q7mf0Ea127Ek2YwHNFG+H18qINF15o/diiBAtCjD8WWrKzs8njCZ6ioT58R4gYffrw9Aa9ewNpafxn/gqsHg+wbp34MUWIiOD9Z2XxfDepqXy7Sf0KrJs2qXWIjOQVWLOyeBXYlBTuUFDAV74uXw5sCb5BXQrRqEZf5ByvwJqCEngRdbwC63L0Qx7aKXWIjQX69ePj0KMHTwfj9fJtMR4Pr0S7S3ESmvh4oH//ugqsiYm8+qm/AuvSpebLQpySmFhXBbZLF14FtqYG2L69zqFAcK+DaOhgjOUS0UkJQcIyCGk0GvXICkKn3WJFjUYTXuggpNFoXEUHIY1G4yo6CGk0GlfRQUij0biKaWbF042oKODcc3llgMxMoGFD/nP/LfqcHGDxYvEr+yLExFRh0KDfkJ3tQa9eq5GaWgwihsLCplixog+WL++HpUsHAFB36y8+/uhxh5491yAlpQREDPv2tTjukJPTT1n/AJCIMgzG/OO36JNRCh8ij9+iX4b+WAm1JTNSUo5g8OD5yMrKRffu65CUVAafLxK7d6cjNzcLS5cOwNq1PZU6pKXxcjn+W/QJCXyZgP8W/aJF6pdsNG5c59ClC182UFMD7NjBHRYuDF2GxpMItHhIdVOxWLFZM6JnnrG2cnr7dr6oMDVV7sKw1q130b///QAVFTUyHYYtW9rR/fe/SMnJR6Q6tGmzjV577S46dCjV1GHDhs50552vU3x8uVSHjthEb+E2OoJk0yevRg+6FRMoBpVSHbp1W0vvvnsjlZUlmI5DTk4WXX/9ZIqKqpbq0Ls30Ycf8o2oZixeTHTttdZ3zFtt/fsTTZtGVFlp7jB/PtFVV1k/tigI5xXTY8fyvS6i7N1rb5Pgya2WbrvtLSopSRIejp070+nCC39w7MCYj+6992UqL48XdtiypR0NGiS2az1Qi0QNPYanqRIxwr+8Hl2oH5Y6doiOrqLnnnuYqqujhMdhxYpM6tVrpWOHuDiiV1+1l+plyRKxnfPBWlIS0cSJ4v0TEf3yC1HbtuZ9iBKWQSg6mmj6dPHBOJE337S/ZD8u7ijNnHmJ42F54YUHHbzgSmju3CGO+vf5GD322NO2HdJwkBbD2Sa4GkTSXXjN9iGaNdtHK1ZkOhqHqqpouvHGd207pKcTbdjg7PVYUSGe0qV+a9+eZ4R0QlmZ+Qe0KGEXhCIj+V4XWUyeLH6yY2IqHb/567fXX79T2CExsZQWLx4gzeHppx8TdmiAw7QSvcQHMEi7Hy8K/1qTJvtp48ZO0sbhllveFnZo3Zp/1ZeB3XQi7drxGb4MzNKJiBJ2Qejf/xYfBDPuvlvshL/99i1W/lyhdsMN7wk5fPzxaOkOf/7zZ0IOMyB/5+VF+F7g6bX0yy+DpY6B1xtBAwcusOwQGUm0fLmc16GfqiqeRdSqQ0wM0fr1ch3Ky/lGXB2ETmj9+6tJrVpezqeyVk74kCFzrfypwq24OIVat95lyWHUqK+UOOzf34QaNy605DAGH1p/lwi0XWhNybB20X78+DeUjMPmzR0oLu6oJYdHHpHwAgzAypU8NYgVhxdeUOOwcGHgyxWihFUQcpo0yogZM6yc8FqpU/8T29Spf7XwyVtDu3a1VuYwYcKtpg5xOEpFaGTtHWKjvQDz62QNGhy2dUPAanvkkWdNHZo3t3b3yS7jx5sPV9u29nIHWWXMmJP7FCVsglD//uJ/vAheL89FY3TChw37kVQOUWVlDDVtWmDocOWVnyt1KC1NNF0+cD1sXEgTaEVoRLGoMHzaXXe9pnQcdu1qTRERxrmOHn/cySvOnI0bzYfrpZfUOixffnKfogQLQqfdiumbb1Z7/MhI4KabzBzeVeoQG1uNsWM/dNUhKakc1177sbED1Do0xkFciS+NHRSPQ3p6PkaMmG3ioFQBnTsDgwYFfzwyErj+erUOffvyxb8qcBSEGGP/ZIztYYytOtZGyBILhtHJkMW555o5qC9/eu65C4I+xlgtBg5UWHzNgkMcKtAXOeodENyhYcOD6NZtg3oHg3HIyADS05UrGL4mu3UDGjVy18EJMrZtvEZEL0s4jikpKUA7tYn4APCMjIzxSeeJtGqVj2bNCpU7ZGUFL/zdufMmJCWVu+rQC6sRBZ96BwR3MPKT6mDQT1ZWSBQM+zkVHJxwWn0da9uWp05VTXIy0CxIYdF27bapFwDQokUBEhICB5pQObRvH3wzUTuEyAEGDqfCOITgQ5E7BH/sVHBwgoy39HjG2BrG2PuMsbRgT2KMjWOMeRhjnqKiIlsdxRhXBJZKsL5iYhTW2rXYV6gcIiNrEREReLYTg9A4GPUTqnEw6idUr0mjfk4FByeYBiHG2FzG2LoAbSSAtwG0A5AJYB+AV4Idh4gmEVE2EWU3adLElmxlpa1fk9pXZWVcCB0C9xUqh5qaKNTWRgZ2QGgcjPoJ1TgY9ROq16RRP6eCgxNMrwkR0VArB2KMvQtglmMjA7ZuBXw+fjdAJYcP88oYgdi8uZPazo+xa1c6KivjXXUw6mczQuRg0M8pMQ6bQ6Jg2M+p4OAEp3fHWtT75+UAlBbTOXpUfd4VgOdXCUZRUVPs3t1auYPHc1JRguNs29YOxcUNXHVYh+6ogvrvAR4Ed1ixog9qa9WXYzEaB6PXilyH4I+dCg5OcHpN6EXG2FrG2BoA5wO4R4KTIfPmqe4B+OUXM4chIXA43+BRZvK4eocaxGAhzlHvgOAOpaUpyM1Vf2vIaBz27g3NTMToNbl5s/q6ZWYOjgi0glF1c7Jiuls38ZWaIlRV8QRpRqtTzzprEakcorKyBEpJKTZ0uOii75U6HDjQ0HTf1FX41Hwpr4O2G60oEjWGT7vxxneVjsOmTR0JqDV0uOceRy85U3JyzIfrySfVOsybd3KfoiBctm0ARD//LD4AVpk61dp7JCcni1QNkZV9W6r3r1nJbxSFatqF1tYGzEZ7BOb7tuLjy6mwsLGycRg//g1Th9RUoiNHnL7yghNo39aJrUULaxkc7TJq1Ml9ihJWQahzZ574STYHD/LNiFbeI336eGxl7zNr+/Y1o7S0g5YcBg36lXw+Jt1h+/YzKTGx1JLDJZhpbcAE23p0sZzydfToj6WPARFP+xoZaTwT87dbbpHyEjyJX3+1PmwPPKDGYWaQUyxKWAUhgOj++8UHwYzrrhN7rzz99GNW/lyhNnLk10IOr79+p9T+vd4IGjJkrpDD+xgrNnAmrRpRwqlev/jiCqnjUFERS927rxFy+PFHWa9ETkmJtTSr/hYRQbRokVyHgweJWrYM3J8oYReEAKJ33hEfiGA8/bT4+4Uxn9SkYvffL55RMDKyhr799jIp/ft8zFZGwVhU0FwMER/AAM2LCLoWU4R/VWaGyerqKOEPA4B/LVu5Us7rsaKCaOhQ8SFs0oTvupdBaSnR2WcH70uUsAxCgPMUBjU1RA89ZP99ExHhdZxhsaoqmm6//T+2HaKiqum//73OkcPRo3E0duz7th3icJS+xOX2BxKgUiTSVfjU9iGSkkro++8vcjQOhw83oBEjZtl2SE3lX6GcUFREdP759oeyaVOiZcucOezbRzTAJGW4KGEbhACiCy4g2rFDfFDWryfq29fR++Z4u/TSGbRnTwvh4VixIpN69lwlxeGqqz61dZF2yZL+1KnTRikOY/AhHUKq8C/+gsHUBtskONTSrbdOsJXobPbs4dSq1W7HDozxO2bl5eKvya++4kHEqUNkJM/2aCfZ2tSpRGlp5n2IEtZBCCBKSCAaN87adHjRIn79Jzra+cmu35KTj9D48W/Q+vVdTIfh118H0dVXT7d84dNqS009RPfe+zL9/nt7w/59PkY//TSURo36yjRpl2hrhCJ6CM9THjIMn+hFBM3CCBqBWWR2G1y0NWu2jx5//CnavbuV4TjU1ETSV1+NomHDfpTaP0DUqpW1WnhVVUSffko0eLDc/gGeoO+FF4gKC40dKiqIpkwxn/3Ub6IEC0KMPxZasrOzyWNx+SWzsSC2fXuedqB3b179EqirwOrx8MqXqunUaROysnKRmbkKqanFqK2NOF6BNSenL/bsUb3qmtC16wZkZeWiV6/VSEkpQW1tBAoKmiM3Nws5OX1RUNDC/DAOYKhFN6w/XoE1BSXwIup4BdYc9EURmip1iIjwoUePtcjKykWPHmuRlFQGrzcK+fmt4fFkw+PJxsGDjZU6REUBPXvWVWBNTOTVT/0VWHNygOJipQqIjuZJyfwVWBMSuMP27dzB4wFKSsSOKRo6GGO5RHTS8vOwDEIajUY9soLQaZVPSKPRhB86CGk0GleRkd5VKS58W9RoNCFEz4Q0Go2r6CCk0WhcRQchjUbjKjoIaTQaV9FBSKPRuIoOQhqNxlV0ENJoNK6ig5BGo3EVHYQ0Go2ruLKBlTFWBGBnCLtsDOBACPvTDtpBO5zMmUR0UvllV4JQqGGMeQLt3tUO2kE7uOsA6K9jGo3GZXQQ0mg0rvJHCUKT3BaAdvCjHTja4Rh/iGtCGo3m1OWPMhPSaDSnKDoIaTQaVwnrIMQYG84Y28wY28oY+4dLDu8zxgoZY+tc6j+dMfYLY2wjY2w9Y+wuFxziGGPLGWOrjzk8FWqHei6RjLGVjLFZLvW/gzG2ljG2ijFmrdqDfIdUxtgXjLFNx14XZ7nhcdwnXK8JMcYiAfwOYBiAfAA5AEYT0YYQewwCUAbgv0TUPZR9H+u/BYAWRLSCMZYMIBfAqFCOA2OMAUgkojLGWDSAhQDuIqKloXKo53IvgGwAKUR0qQv97wCQTUSuLVRkjH0EYAERvccYiwGQQETFbvmE80yoH4CtRJRHRNUApgMYGWoJIvoNwKFQ91uv/31EtOLY/5cC2AigVYgdiIjKjv0z+lgL+acfY6w1gEsAvBfqvk8VGGMpAAYBmAwARFTtZgACwjsItQKwu96/8xHiN9+pBmMsA0BvAMtc6DuSMbYKQCGAOUQUcgcArwN4EECtC337IQA/McZyGWPjXOi/LYAiAB8c+1r6HmMs0QWP44RzEApUNjE8v3tagDGWBOBLAHcTkWCtTecQkY+IMgG0BtCPMRbSr6aMsUsBFBJRbij7DcBAIuoD4GIAtx/7uh5KogD0AfA2EfUGUA7AleulfsI5COUDSK/379YA9rrk4irHrsN8CeBjIvrKTZdjU/9fAQwPcdcDAfzp2DWZ6QCGMMamhtgBRLT32H8LAXwNftkglOQDyK83E/0CPCi5RjgHoRwAHRhjbY5dfLsGwAyXnULOsYvCkwFsJKJXXXJowhhLPfb/8QCGAtgUSgciepiIWhNRBvhrYR4RXRdKB8ZY4rGbAzj2FehCACG9a0pEBQB2M8Y6HfvRBQBCerPmRE754od2ISIvY2w8gB8BRAJ4n4jWh9qDMfYJgPMANGaM5QN4kogmh1BhIIC/AVh77JoMADxCRLND6NACwEfH7lhGAPiMiFy5Re4yzQB8zT8XEAVgGhH94ILHHQA+PvbhnAfgehccjhO2t+g1Gs3pQTh/HdNoNKcBOghpNBpX0UFIo9G4ig5CGo3GVXQQ0mg0rqKDkEajcRUdhDQajav8f6/8P4B+zyI5AAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "\n",
    "def visualize(board):\n",
    "    plt.axes()\n",
    "    rectangle=plt.Rectangle((-0.5,len(board)*-1+0.5),len(board[0]),len(board),fc='blue')\n",
    "    circles=[]\n",
    "    for i,row in enumerate(board):\n",
    "        for j,val in enumerate(row):\n",
    "            color='white' if val==0 else 'red' if val==1 else 'yellow'\n",
    "            circles.append(plt.Circle((j,i*-1),0.4,fc=color))\n",
    "\n",
    "    plt.gca().add_patch(rectangle)\n",
    "    for circle in circles:\n",
    "        plt.gca().add_patch(circle)\n",
    "\n",
    "    plt.axis('scaled')\n",
    "    plt.show()\n",
    "    \n",
    "board = [[0, 0, 0, 0, 0, 0, 0],\n",
    "         [0, 0, 0, 0, 0, 0, 0],\n",
    "         [0, 0, 0, 0, 0, 0, 0],\n",
    "         [0, 0, 0, 1, 0, 0, 0],\n",
    "         [0, 0, 0, 1, 0, 0, 0],\n",
    "         [0,-1,-1, 1,-1, 0, 0]]\n",
    "\n",
    "visualize(board)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Implement helper functions for:\n",
    "\n",
    "* The transition model $result(s, a)$.\n",
    "* The utility function $utility(s)$.\n",
    "* Check for terminal states $terminal(s)$.\n",
    "* A check for available actions in each state $actions(s)$.\n",
    "\n",
    "Make sure that all these functions work with boards of different sizes (number of columns and rows)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Your code/ answer goes here."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Implement an agent that plays randomly. Make sure the agent function receives as the percept the board and returns a valid action. Use an agent function definition with the following signature (arguments):\n",
    "\n",
    "`def random_player(board, player = None): ...`\n",
    "\n",
    "The argument `player` is used for agents that do not store what side they are playing. The value passed on bt yhe environment should be 1 ot -1 for playerred and yellow, respectively.  See [Experiments section for tic-tac-toe](https://nbviewer.org/github/mhahsler/CS7320-AI/blob/master/Games/tictactoe_and_or_tree_search.ipynb#Experiments) for an example."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Your code/ answer goes here."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let two random agents play against each other 1000 times. Look at the [Experiments section for tic-tac-toe](https://nbviewer.org/github/mhahsler/CS7320-AI/blob/master/Games/tictactoe_and_or_tree_search.ipynb#Experiments) to see how the environment uses the agent functions to play against each other.\n",
    "\n",
    "How often does each player win? Is the result expected?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Your code/ answer goes here."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task 3: Minimax Search with Alpha-Beta Pruning [3 points]\n",
    "\n",
    "### Implement the search starting.\n",
    "\n",
    "Implement the search starting from a given board and specifying the player and put it into an agent function.\n",
    "You can use code from the [tic-tac-toe example](https://nbviewer.org/github/mhahsler/CS7320-AI/blob/master/Games/tictactoe_alpha_beta_tree_search.ipynb).\n",
    "\n",
    "__Notes:__ \n",
    "* Make sure that all your agent functions have a signature consistent with the random agent above.\n",
    "* The search space for a $6 \\times 7$ board is large. You can experiment with smaller boards (the smallest is $4 \\times 4$) and/or changing the winning rule to connect 3 instead of 4."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Your code/ answer goes here."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Experiment with some manually created boards (at least 5) to check if the agent spots winning opportunities."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Your code/ answer goes here."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How long does it take to make a move? Start with a smaller board with 4 columns and make the board larger by adding columns."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Your code/ answer goes here."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Move ordering\n",
    "\n",
    "Starting the search with better moves will increase the efficiency of alpha-beta pruning. Describe and implement a simple move ordering strategy. Make a table that shows how the ordering strategies influence the time it takes to make a move?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Your code/ answer goes here."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The first few moves\n",
    "\n",
    "Start with an empty board. This is the worst case scenario for minimax search with alpha-beta pruning since it needs solve all possible games that can be played (minus some pruning) before making the decision. What can you do? "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Your code/ answer goes here."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Playtime\n",
    "\n",
    "Let the Minimax Search agent play a random agent on a small board. Analyze wins, losses and draws."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Your code/ answer goes here."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task 4: Heuristic Alpha-Beta Tree Search [3 points] \n",
    "\n",
    "### Heuristic evaluation function\n",
    "\n",
    "Define and implement a heuristic evaluation function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Your code/ answer goes here."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Cutting off search \n",
    "\n",
    "Modify your Minimax Search with Alpha-Beta Pruning to cut off search at a specified depth and use the heuristic evaluation function. Experiment with different cutoff values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Your code/ answer goes here."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Experiment with the same manually created boards as above to check if the agent spots winning opportunities."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Your code/ answer goes here."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How long does it take to make a move? Start with a smaller board with 4 columns and make the board larger by adding columns."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Your code/ answer goes here."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Playtime\n",
    "\n",
    "Let two heuristic search agents (different cutoff depth, different heuristic evaluation function) compete against each other on a reasonably sized board. Since there is no randomness, you only need to let them play once."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Your code/ answer goes here."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Tournament task [+ 1 to 5 bonus point will be assigned separately]\n",
    "\n",
    "Find another student and let your best agent play against the other student's best player. You are allowed to use any improvements you like as long as you code it yourself. We will set up a class tournament on Canvas. This tournament will continue after the submission deadline."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Graduate student advanced task: Pure Monte Carlo Search and Best First Move [1 point]\n",
    "\n",
    "__Undergraduate students:__ This is a bonus task you can attempt if you like [+1 Bonus point].\n",
    "\n",
    "### Pure Monte Carlo Search\n",
    "\n",
    "Implement Pure Monte Carlo Search (see [tic-tac-toe-example](https://nbviewer.org/github/mhahsler/CS7320-AI/blob/master/Games/tictactoe_pure_monte_carlo_search.ipynb)) and investigate how this search performs on the test boards that you have used above. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Your code/ answer goes here."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Best First Move\n",
    "\n",
    "How would you determine what the best first move for a standard board ($6 \\times 7$) is? You can use Pure Monte Carlo Search or any algorithms that you have implemented above."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Your code/ answer goes here."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}