Local_Search/Maze_Example_LocalSearch.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Apply Simple Hill Climbing to a Maze Problem"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 133,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "%config InlineBackend.figure_format = 'retina'\n",
    "\n",
    "import numpy as np\n",
    "import maze_helper as mh\n",
    "\n",
    "f = open(\"L_maze.txt\", \"r\")\n",
    "\n",
    "maze_str = f.read()\n",
    "maze = mh.parse_maze(maze_str)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 134,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Directions are checked in the order ['N', 'E', 'S', 'W']\n"
     ]
    }
   ],
   "source": [
    "DIR2POS = {\n",
    "    'N' : (-1, 0),\n",
    "    'E' : ( 0, 1),\n",
    "    'S' : ( 1, 0),\n",
    "    'W' : ( 0,-1)\n",
    "}\n",
    "\n",
    "ORDER = None\n",
    "RANDOMIZATION = None\n",
    "DIRS = None \n",
    "\n",
    "# The order matters if RANDOMIZATION = False\n",
    "# Note that: DFS works takes elements from the frontier in reverse order!\n",
    "def set_order(order = \"NESW\", random = False, verbose = True):\n",
    "    global RANDOMIZATION, DIR2POS, ORDER, DIRS\n",
    "    \n",
    "    RANDOMIZATION = random\n",
    "    ORDER = [pos for pos in order]\n",
    "    DIRS = [DIR2POS[dir] for dir in ORDER]\n",
    "    \n",
    "    if verbose:\n",
    "        if RANDOMIZATION:\n",
    "            print(\"Directions are checked at every step in random order.\")\n",
    "        else:\n",
    "            print(f\"Directions are checked in the order {ORDER}\")\n",
    "        \n",
    "set_order(\"NESW\", verbose = True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 135,
   "metadata": {},
   "outputs": [],
   "source": [
    "def expand(maze, pos):\n",
    "    \"\"\"find available directions as a list of lists with elements [dir, (pos)].\"\"\"\n",
    "    global RANDOMIZATION, DIRS, ORDER\n",
    "       \n",
    "    available = [[dir, pos] for dir, pos in zip(ORDER, np.add(pos, DIRS)) if mh.look(maze, pos) != \"X\"]\n",
    "    if RANDOMIZATION: np.random.shuffle(available)\n",
    "        \n",
    "    return available"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Hill Climbing\n",
    "\n",
    "We use Manhattan distance to the goal as the objective function (minimization)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 136,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n"
     ]
    }
   ],
   "source": [
    "# Manhattan distance h(n)\n",
    "def manhattan(pos1, pos2):\n",
    "    \"\"\"returns the Manhattan distance between two positions\"\"\"\n",
    "    return(np.sum(np.abs(np.subtract(pos1, pos2))))\n",
    "    \n",
    "print(manhattan([0,0], [1,1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 137,
   "metadata": {},
   "outputs": [],
   "source": [
    "def local_search(maze, vis = False, animation = False, verbose = False):\n",
    "    if animation:\n",
    "        maze_anim = []\n",
    "    else:\n",
    "        maze_anim = None\n",
    "    \n",
    "    # Local search starts here\n",
    "    start_pos = mh.find_pos(maze, \"S\")\n",
    "    goal_pos = mh.find_pos(maze, \"G\")\n",
    "\n",
    "    current = start_pos\n",
    "    current_obj = manhattan(current, goal_pos)\n",
    "\n",
    "    while True:\n",
    "        # find best neighbor\n",
    "        neighbors = [n[1] for n in expand(maze, current)]\n",
    "        obj = [manhattan(n, goal_pos) for n in neighbors]\n",
    "        best_obj = min(obj)\n",
    "        best_neighbor = neighbors[obj.index(best_obj)]\n",
    "\n",
    "        if verbose:\n",
    "            print(\"Current state:\", current, \"with obj\", current_obj)\n",
    "            print(\"Evaluating neighbors:\\t\", neighbors)\n",
    "            print(\"Obj:\\t\\t\\t\", obj)\n",
    "\n",
    "\n",
    "        # move there if it is an improvement or stop\n",
    "        if best_obj < current_obj:\n",
    "            current = best_neighbor\n",
    "            current_obj = best_obj\n",
    "            if verbose:\n",
    "                print(\"Moving to:\", current, \"\\n\")\n",
    "        else:\n",
    "            if verbose:\n",
    "                print(\"No better state in the neighborhood! Stopping.\\n\")\n",
    "            break\n",
    "\n",
    "        if animation:\n",
    "            maze2 = maze.copy()\n",
    "            maze2[current[0], current[1]] = \"P\"\n",
    "            maze_anim.append(maze2)\n",
    "\n",
    "\n",
    "    return { \"solution\" : current, \"path\" : None, \"reached\" : None, \"maze_anim\" : maze_anim }"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 138,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Current state: (np.int64(9), np.int64(5)) with obj 14\n",
      "Evaluating neighbors:\t [array([8, 5]), array([9, 6]), array([10, 5]), array([9, 4])]\n",
      "Obj:\t\t\t [np.int64(13), np.int64(13), np.int64(15), np.int64(15)]\n",
      "Moving to: [8 5] \n",
      "\n",
      "Current state: [8 5] with obj 13\n",
      "Evaluating neighbors:\t [array([7, 5]), array([8, 6]), array([9, 5]), array([8, 4])]\n",
      "Obj:\t\t\t [np.int64(12), np.int64(12), np.int64(14), np.int64(14)]\n",
      "Moving to: [7 5] \n",
      "\n",
      "Current state: [7 5] with obj 12\n",
      "Evaluating neighbors:\t [array([6, 5]), array([7, 6]), array([8, 5]), array([7, 4])]\n",
      "Obj:\t\t\t [np.int64(11), np.int64(11), np.int64(13), np.int64(13)]\n",
      "Moving to: [6 5] \n",
      "\n",
      "Current state: [6 5] with obj 11\n",
      "Evaluating neighbors:\t [array([5, 5]), array([6, 6]), array([7, 5]), array([6, 4])]\n",
      "Obj:\t\t\t [np.int64(10), np.int64(10), np.int64(12), np.int64(12)]\n",
      "Moving to: [5 5] \n",
      "\n",
      "Current state: [5 5] with obj 10\n",
      "Evaluating neighbors:\t [array([5, 6]), array([6, 5]), array([5, 4])]\n",
      "Obj:\t\t\t [np.int64(9), np.int64(11), np.int64(11)]\n",
      "Moving to: [5 6] \n",
      "\n",
      "Current state: [5 6] with obj 9\n",
      "Evaluating neighbors:\t [array([5, 7]), array([6, 6]), array([5, 5])]\n",
      "Obj:\t\t\t [np.int64(8), np.int64(10), np.int64(10)]\n",
      "Moving to: [5 7] \n",
      "\n",
      "Current state: [5 7] with obj 8\n",
      "Evaluating neighbors:\t [array([5, 8]), array([6, 7]), array([5, 6])]\n",
      "Obj:\t\t\t [np.int64(7), np.int64(9), np.int64(9)]\n",
      "Moving to: [5 8] \n",
      "\n",
      "Current state: [5 8] with obj 7\n",
      "Evaluating neighbors:\t [array([5, 9]), array([6, 8]), array([5, 7])]\n",
      "Obj:\t\t\t [np.int64(6), np.int64(8), np.int64(8)]\n",
      "Moving to: [5 9] \n",
      "\n",
      "Current state: [5 9] with obj 6\n",
      "Evaluating neighbors:\t [array([6, 9]), array([5, 8])]\n",
      "Obj:\t\t\t [np.int64(7), np.int64(7)]\n",
      "No better state in the neighborhood! Stopping.\n",
      "\n",
      "CPU times: user 3.74 ms, sys: 0 ns, total: 3.74 ms\n",
      "Wall time: 3.64 ms\n",
      "No solution found.\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<video width=\"640\" height=\"480\" controls autoplay>\n",
       "  <source type=\"video/mp4\" src=\"data:video/mp4;base64,AAAAIGZ0eXBNNFYgAAACAE00ViBpc29taXNvMmF2YzEAAAAIZnJlZQAAE2ptZGF0AAACrgYF//+q\n",
       "3EXpvebZSLeWLNgg2SPu73gyNjQgLSBjb3JlIDE2NCByMzEwOCAzMWUxOWY5IC0gSC4yNjQvTVBF\n",
       "Ry00IEFWQyBjb2RlYyAtIENvcHlsZWZ0IDIwMDMtMjAyMyAtIGh0dHA6Ly93d3cudmlkZW9sYW4u\n",
       "b3JnL3gyNjQuaHRtbCAtIG9wdGlvbnM6IGNhYmFjPTEgcmVmPTMgZGVibG9jaz0xOjA6MCBhbmFs\n",
       "eXNlPTB4MzoweDExMyBtZT1oZXggc3VibWU9NyBwc3k9MSBwc3lfcmQ9MS4wMDowLjAwIG1peGVk\n",
       "X3JlZj0xIG1lX3JhbmdlPTE2IGNocm9tYV9tZT0xIHRyZWxsaXM9MSA4eDhkY3Q9MSBjcW09MCBk\n",
       "ZWFkem9uZT0yMSwxMSBmYXN0X3Bza2lwPTEgY2hyb21hX3FwX29mZnNldD0tMiB0aHJlYWRzPTE1\n",
       "IGxvb2thaGVhZF90aHJlYWRzPTIgc2xpY2VkX3RocmVhZHM9MCBucj0wIGRlY2ltYXRlPTEgaW50\n",
       "ZXJsYWNlZD0wIGJsdXJheV9jb21wYXQ9MCBjb25zdHJhaW5lZF9pbnRyYT0wIGJmcmFtZXM9MyBi\n",
       "X3B5cmFtaWQ9MiBiX2FkYXB0PTEgYl9iaWFzPTAgZGlyZWN0PTEgd2VpZ2h0Yj0xIG9wZW5fZ29w\n",
       "PTAgd2VpZ2h0cD0yIGtleWludD0yNTAga2V5aW50X21pbj01IHNjZW5lY3V0PTQwIGludHJhX3Jl\n",
       "ZnJlc2g9MCByY19sb29rYWhlYWQ9NDAgcmM9Y3JmIG1idHJlZT0xIGNyZj0yMy4wIHFjb21wPTAu\n",
       "NjAgcXBtaW49MCBxcG1heD02OSBxcHN0ZXA9NCBpcF9yYXRpbz0xLjQwIGFxPTE6MS4wMACAAAAL\n",
       "dGWIhAAR//73iB8yy2n5OtdyEeetLq0fUO5GcV6kvf4gAAADAAADAABlQN8pUH95cNzgAAAE8ADA\n",
       "TP/gzT/xAG2yaPJV7523B99UBaG/sH/n+m+D6DJbBZ2240iNua+I6HIwT1AR3EX+RB/kczDy0oX5\n",
       "lw/B38dk7IwDOSoWdgAsckLRsj/rvJHbOX30xn7a6AinVHEz9sWLwlwMs6WlP8+v/g5wYev9ZGXW\n",
       "UTTju1aTc4fZKYiod8pUohS1VyBtFLNxM68pLF5uweGtTvuC3HmsTU5VcDV2m79dAbhLk6CFtedp\n",
       "quZVwBubKbePZSW+4El9Lfr5/gDz75xGmI6WfBXfgfEs2xoJPAAqdRprNdtvDWXMDFrN4D00sGlM\n",
       "+TPQEhgo0HwAL7lNk6yImI3594B0gO7iUWikeELFVjSGYxGYYFkIx9EMDY2O750m8jyNo1zDF5vN\n",
       "TVfzSlAEqpESMIfJaoofWvyR0XO6WWourCsOTl0W0S2Q/1v/NLcFIqpt34i7Mx+bR6X/Gw4L/ZE5\n",
       "9Clis2YIQpPA27n3XvJJ/H2PmSo4IDLYitIBPd7bfOnsvgAP3PAI7dkJ0amL/ioRuzAPlgnaUicn\n",
       "MZ6teN4ELSwFNUQyIjOysOsMLXQckx+VH/7InVdAEDWcratq7aAfDsKqkI6zBwBsFb9pRpWd58Pr\n",
       "d6xwioeExRgFDkJAketm5b/pd80jPbB2rn1VzK02Eawms6v3e7rPhRlsrGeEXy9D40tMWll6p6i7\n",
       "fP3ZmKE6BTyMMXfE28pWmcR/gTU+JzNCvO39i0e+t9wzg2rJ/D4uerZ/bHa4TarUdQ7DxjSba+0o\n",
       "IC5BvTv/mbfdyF8wA/gukfOXTUiYy+AB7liC5vo1Nr41B+4fEQT66jOY/HibvmgDf2qPxFqvsWRV\n",
       "dxb2SyYhbC+4/uL9BxK+oRP/rx9r5yvo0jQOp+xYkvhilR3pEq3l4ctFEy/AFMqeVf/kznvXZrIP\n",
       "IvyUVBPuDuAry0/+ddpX2LVdnvYD+7or9HnbYAOOC8hNY4palWatXLE0lkzS2h8Mq3RvnAAcqAtH\n",
       "1+J4DLgSZQioB/PJeI+FqgsJ4LMGPQluHluexaKSUqB+qxEgPCWDg6mwYyGImMAWFGPgtkKDcpsy\n",
       "jkS0fWGf1omTydAKtTZyZV1wIQZgarUa615Ot93ltu0jAj6S/6+Yp/IDs+T8nrLCSSRwVQCIu+f6\n",
       "qOf+ICIDDbCJIAR30TJBONP/H3P/xo8ILlBmtUYh2sTA08EJNK54FN3HNJZvbdUMW/iPMgGbgcz+\n",
       "fZ3R5QbXBSU4PKOmeGOFe0CPB1J9NxI7kxiHNJm8hO53AAkj0es/V1Sk+fRwal9RA8N0ROZTPcO8\n",
       "fiPxgjZQCUnWfyxq+vEiJdb5dX0/2d21ridWnermuklnB8AR44xbMXuWUFAI4mYrraS8xxQk9X6O\n",
       "kfrHGhaJG4eaNch8WmiBBp3r9IqRPp8+VFdxp+aMYKocnD9dAdoGklTNmejCB9/u3ivEs0EPsdzB\n",
       "7W2LWdTXw/HdjFt9apTVYSJ4BtpJVeil+2tMbCRDxHAC2u8eP55conB2f0MrBjEUuXHq2LzA9gjZ\n",
       "fEdz5xTyVGXVxYmuMHiqJ8NJsaZDFiufSsUjQ4IY44UvkzLXnP4SF4YMIGo/kmUouVmAaKE/41Un\n",
       "pxFH0kz+i2Dsqt+v9pQAy6lVxRUYPZ9Ffmr9CEik15OZqXNx8xgmg2/6/Ob6pEkuSbcwXVVZjW+V\n",
       "QoMCIbs6HrcjuG4CeWp4FrJB0SHBl+DJ621uvtTQiN+c3v/RgT+2CpfGb0OTnFMGOBKGEuas0Tu4\n",
       "ylfF0kHFScJE2dmhFfomPDKr5N99xpxsMya2agZMs+9KnXv7Ap0COL8NXyT1DnYHk2OMtRHM/uLJ\n",
       "BAcsnqWRqU6cxdJ3zqWVela464Z3Rb80NX/vSMeAjjOWgf/k3kyVO3+oNJWfgEUjTMx47kgzyiuF\n",
       "XQm8SGQFYyh5iG6rRx1nXmfpcIVWAR25F7nhJXbpcfpUFg939XbXBO1EQb2BsjT3F1cU03K6m5ze\n",
       "28ZJdKwEuHOB14B3mfkA28yL/MaVL4uuUdZ72hfv46sof7a+zf5c+hRJTHd23NMZOqWx3kfRFlaT\n",
       "IHqzyAAbE/7z1E03ZGgEKzgw1kjXzAZN+KVGA88xSaQeiPPUIGPgyO1FJaM1Lg/9/2BJxqw8PKil\n",
       "krhSCIRCDZMyywK96tT4VATsP91L9MLWxf3Wn1H2JuIF5SRvVH03mBVKEKr/hmZVGSqgBA3yERYd\n",
       "5jrtyePbGxoU5xg+l7VXG/9CrQF3j67rI8ylDmWarSy+TuK/gElxJtSCuP02gW8aXVerUbTr0AAA\n",
       "gp37K+8VKqXP5XmOwnIUlqbx2cY02PbHpa7ppC6C9LU/tjFpUw/hlSJoZAccWEZmTr1JbHQg8HTj\n",
       "mZ7Uh4BzOcQ0Yu8OIcnaoiXaBXwdOXGBh3HCLHScdNCsubUJ57RP/kP//8NBrJziEkQKGQ8TGWt7\n",
       "xiFXiov25WXO3a8EO3sDBF80QsYt4cHpwDdlU0cT4xBXZbfgi0P6e52F9Afq0uc6e+g/CfWvsGvM\n",
       "kO64gcqOCbxBrHdDwlTZkHC6PBW5U1nErkDsguvFp85rgzYDnzZF+W8AbqcVfPTwn4gfXEQwfKvY\n",
       "49dRx/moxOzq43A72FwuJkCEYVLmeRM/0i3P/YYHHd3uobbeXoRnmCRABlj/5uMbBqANLvn6/pE0\n",
       "bX5mzgDB5+VopjPz/s52O91q+AXwAALyPTaJe91D+QqXDcjzS/fCPwZgH2HfFOoekuAS+L9NnRjD\n",
       "pZAzR5gkI529ImZlkfeVDdVYwlqCKDGlaSLG4EWkiKjlwknB2sGiFdh0YgVgX+8Z7w6eJmmH3jgs\n",
       "CrqFI7NCoyj/HTN9dtkM8bGdWkiT85nmp+S46p9fWnqpL8Xn2ZoNE6NK+Wsoj+/wHX8etqXOF6iL\n",
       "XUXWsSm/oUvd8hphDrscaHNR8V3zCH+azQpjiTacQajHmDNzIdANM9D/A1HRZgDBrTLNtvE69DZ+\n",
       "TSXmsvxbIaFCmtuSgRrLYzj19TUxn9l838wQHfq0LbRQVtC5ELXdMQ3NuTDFNSDucoGSN8unQp/y\n",
       "wBaNaIZrQbjQYmqPXynLhpkWDkKLvhuzu3G6LHVkYeBgTwuFVOLjFBntLQnh9MGZUzkPQTnekUHE\n",
       "9yL6dotJRENCOnWSmW3RVscAOa4fiVhQFu05fdccne5+E9Fj+sIBDbINxnDOYO5rYEw1944LZuIA\n",
       "KtxIfFO84SyKBT5fs6k0uuchwUsPr5p16ldpv5okchAc4JANlK+reQ6dyZhFa9iEeWH6nAHeWOVm\n",
       "o3DRkfOjC3YFAQScVd8GMieDxZuCb/O/2RqKwIhlvVYmgwE7jwJUz9p6EO5Y5cs8RUj16is3eGGv\n",
       "k9aiZQmbJRe7dG8PSkSRWbVpEFnky8wHGOGEo/m1HF/Ylrz+Hb2zyToejjKSSxC91Khc0DhlW4W3\n",
       "vsDuT0qkq3x8O3DpghAImXKuol5Ih3IE9fa6eoPc+axmyXrNNScHyoLJ4yoFsexSunXf3p6Kjko2\n",
       "mCVviyZqvFaQbZZGRP+2f2Hq2rMQpKNsuS4Nb1P5fU91h7WbLukvlka5eX4jndZJ0Vv3x0bZHzbt\n",
       "AfPmqrJDIPeJXp37mQ/qOjwJxu1/SW3oCc+Rtijq0mJLAXNT8OQNjS/FqAncpq/Vct4pbkSdFsQk\n",
       "+7nF6yAO4zv5kpqi2lc3Q7Yfix+/WJfY6iA4TraAnGOvlX+TgAKaSwIqE5SNxnLnssRV6aXUdCQ1\n",
       "E/anYMa4QI9eg4ChK5ZAxtAMGhFNtjOMfMd7D/Tx3NY/v01ACNms/njvkkvbxGyzsfKDI1F4y2Vj\n",
       "ElETSjNUVJpbX2HTcFUADmNOtzb+1AAABa0AAAFcQZohbEEf/rUqgAAEQeDDzACsI4GE0gy6a/1X\n",
       "Ac/+8+xYuQ5HAaSkCBkq88SZYcamvb6RSRdGZ2VidmtUHZzHbP3NQ8gjF3dLmY0fhZ5KJ6X8wzUv\n",
       "PPB1u7QK6D/OcDK0Dx2TlbDbyU2NYNTlSD1edUXxp/Ep4eGOpL56bp3pBtmK49Mhl4qlFwxYIw9E\n",
       "dk9n5M8MOeT1++qtTpRKJyuWeRgno7SDm15Gm6IYLk9JxFX2dOdUFf/KYGkyr3tWHdVsF7363YdM\n",
       "gnNT/KGWWSotrs7/C9a8OloqkkqbsB/8j9PmqXfktSGzckEqA6X2rPM3/83d33CgvI9U9oQTcTk/\n",
       "9LxOOyzmmDVQzqs/hmmNEv1emf2qWtpKsqZAqqvwr5rAI/eb8kT5MBTH3y4Q1TcGeD8/FAkaRtLJ\n",
       "ZhdOvxmy6wptgep/Y9vovPf8f/NXo5d9Jg5lHXtjaoxWW9NgAAAA4UGaQjwhkymEEP/+qlUAAAhE\n",
       "/d0lCIndP8I6IAAE62paSZLQPcEfjD8vhhe3kxbZaaakyMtzjuwf8ky7zdw6ctctw81zAlwdKFct\n",
       "4xupy3E+16kNifDk02hRYk0TPLf416a8S4ENaNkpEuXn41ut3bo0CZN2L/xz09/Hc+t3htmuGa//\n",
       "CvK3cQzcLx+a0jzgeaZ5jhQt4gP8+RUBc4DHagcSPe65/8tH+AHBvLIVDjsr3z9v5th9Zc4l3Uym\n",
       "Ebe9L5neaEyPDmZkGIa69z8M1EMlUPooUh9sOjHQdZ2g+4gDAwAAAKNBmmVJ4Q8mUwII//61KoAA\n",
       "AD1bcJhZOObgAJfYf/3PFIim3N4IDvcfBAeonG/yeJ8JSEvZ4fCtDofOq1U60aPq16OmjNmuVL2U\n",
       "GX5hsDLyMXSBCETC6UUHBy7n8Ni17Za1PaQxeJIbRF5I+9px42ecbLaG0SAcqtm6HkW/HM9CJOM8\n",
       "VTGXJ+bSpYVqTUnrocLx7CyB6RRsKuM3P4anhGVHZAN6AAAAxUGeg0URPBD/AAAFHIza5Kgamnou\n",
       "3dIAObBH/yEBZugBte2S2y0SssCjB7WcbyJXIbZ3lMziPJD+6VX/DFnj3Kp7dha8SB/0ksxT+nK9\n",
       "EGzL8+EE92mrUU+U1B4SvIDucWV+qN0zSJp2fvcq0MoaT/ThtZaV8BA3xnZveKEETqmIQZruCjbB\n",
       "gZd2XEA6blrAJuvCLT7xEJ3G2R4U5rqyhWTwmkITh+oDo51noF5O5hfuNcoucTnRdLfsV2aAVchm\n",
       "dV4rQLaBAAAAWwGepGpD/wAAAwC6E59lFzAB+GCgAB/zAC3xDP742kC/MQEdyhX7fn/O/xnTHLal\n",
       "iO0sDIpPtp1QtEJC+nUTLGCqHpZck/foxB2140CrL9QdYDGkVwImFA4AVsEAAACTQZqmSahBaJlM\n",
       "CCH//qpVAAADAHoYWUHRmi2igAdmt/+Eb4O9Xa3pen/dqGNdLuHg3cmaWV8qFYNV/XP0XGv8Pg7w\n",
       "0n5Bh5s5197Etmr+nxY5zFVqG1yMQUoIMJwaa2j9zJQ9vDdxWtfHu569vHlo6nX5JoKiZFJYzEYz\n",
       "6N8J+BF/qzdrjyjUGVESEhHFSLxLGNyxAAAAiUGax0nhClJlMCH//qmWAAADAcdqZXWLEtf+Q/ya\n",
       "nnV/4iABdQJfyKx9bqtuZnzbAm53kRpD4haYxzKF5neuYSTjZBgJU/lYw07iCqB35BjOOLRw4Bj6\n",
       "FR4v7RXct0QVGj1lMVAewHYpjJ15f1k51Mbd7gwdC1Z1cdl4LoEbBhnp4JECIEBCnyDZAAADcm1v\n",
       "b3YAAABsbXZoZAAAAAAAAAAAAAAAAAAAA+gAAAZAAAEAAAEAAAAAAAAAAAAAAAABAAAAAAAAAAAA\n",
       "AAAAAAAAAQAAAAAAAAAAAAAAAAAAQAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAIAAAKc\n",
       "dHJhawAAAFx0a2hkAAAAAwAAAAAAAAAAAAAAAQAAAAAAAAZAAAAAAAAAAAAAAAAAAAAAAAABAAAA\n",
       "AAAAAAAAAAAAAAAAAQAAAAAAAAAAAAAAAAAAQAAAAAKAAAAB4AAAAAAAJGVkdHMAAAAcZWxzdAAA\n",
       "AAAAAAABAAAGQAAAEAAAAQAAAAACFG1kaWEAAAAgbWRoZAAAAAAAAAAAAAAAAAAAKAAAAEAAVcQA\n",
       "AAAAAC1oZGxyAAAAAAAAAAB2aWRlAAAAAAAAAAAAAAAAVmlkZW9IYW5kbGVyAAAAAb9taW5mAAAA\n",
       "FHZtaGQAAAABAAAAAAAAAAAAAAAkZGluZgAAABxkcmVmAAAAAAAAAAEAAAAMdXJsIAAAAAEAAAF/\n",
       "c3RibAAAALdzdHNkAAAAAAAAAAEAAACnYXZjMQAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAKAAeAA\n",
       "SAAAAEgAAAAAAAAAAQAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABj//wAAADVhdmND\n",
       "AWQAFv/hABhnZAAWrNlAoD2hAAADAAEAAAMACg8WLZYBAAZo6+PLIsD9+PgAAAAAHHV1aWRraEDy\n",
       "XyRPxbo5pRvPAyPzAAAAAAAAABhzdHRzAAAAAAAAAAEAAAAIAAAIAAAAABRzdHNzAAAAAAAAAAEA\n",
       "AAABAAAAMGN0dHMAAAAAAAAABAAAAAMAABAAAAAAAQAAIAAAAAACAAAIAAAAAAIAABAAAAAAHHN0\n",
       "c2MAAAAAAAAAAQAAAAEAAAAIAAAAAQAAADRzdHN6AAAAAAAAAAAAAAAIAAAOKgAAAWAAAADlAAAA\n",
       "pwAAAMkAAABfAAAAlwAAAI0AAAAUc3RjbwAAAAAAAAABAAAAMAAAAGJ1ZHRhAAAAWm1ldGEAAAAA\n",
       "AAAAIWhkbHIAAAAAAAAAAG1kaXJhcHBsAAAAAAAAAAAAAAAALWlsc3QAAAAlqXRvbwAAAB1kYXRh\n",
       "AAAAAQAAAABMYXZmNjAuMTYuMTAw\n",
       "\">\n",
       "  Your browser does not support the video tag.\n",
       "</video>"
      ],
      "text/plain": [
       "<matplotlib.animation.FuncAnimation at 0x7e40a401ecf0>"
      ]
     },
     "execution_count": 138,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time result = local_search(maze, animation = True, verbose = True)\n",
    "result[\"solution\"]\n",
    "\n",
    "mh.animate_maze(result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Note:** Simple hill climbing is greedy. It gets stuck in local optima!"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": ".venv_AI",
   "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.12.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}