Games/tictactoe_alpha_beta_tree_search.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Adversarial Search: Solving Tic-Tac-Toe with Minimax Search and Alpha-Beta Pruning"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Introduction \n",
    "\n",
    "Multiplayer games can be implemented as:\n",
    "1. Nondeterministic actions: The opponent is seen as part of an environment with nondeterministic actions. Non-determinism is the result of the unknown opponent's moves. \n",
    "2. __Optimal Decisions:__ Minimax search (search complete game tree) and alpha-beta pruning.\n",
    "3. Heuristic Alpha-Beta Tree Search: Cut off tree search and use heuristic to estimate state value. \n",
    "4. Monte Carlo Tree search: Simulate playouts to estimate state value. \n",
    "\n",
    "Here we will implement search for Tic-Tac-Toe (see [rules](https://en.wikipedia.org/wiki/Tic-tac-toe)). The game is a __zero-sum game__: Win by x results in +1, win by o in -1 and a tie has a value of 0. Max plays x and tries to maximize the outcome while Min plays o and tries to minimize the outcome.   \n",
    "\n",
    "We will implement\n",
    "* __minimax search,__\n",
    "* __minimax search with alpha-beta pruning,__ and\n",
    "* __move ordering__. \n",
    "\n",
    "The search time (number if nodes explored) could be further improved by \n",
    "* __heuristic alpha-beta tree search__ (cut off search and use heuristic evaluation function to approximate utility), \n",
    "* __forward pruning__ (prune moves that appear poor), and\n",
    "* __table lookups__ (for openings and end game).\n",
    "\n",
    "The algorithms search the game tree and we could return a conditional plan (or partial plan if cut offs are used), but the implementation here only identifies and returns the optimal next move."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The code for the basic functions used for search are implemented in [tictactoe.py](tictactoe.py)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from tictactoe import empty_board, actions, result, terminal, utility, other, show_board\n",
    "from tictactoe import random_player, play "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Recursive DFS algorithm for Minimax Search\n",
    "\n",
    "See AIMA page 150. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that the minimax search algorithm is very similar to AND-OR search where max does OR and min is represented by AND nodes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "# global variables\n",
    "DEBUG = 1 # 1 ... count nodes, 2 ... debug each node\n",
    "COUNT = 0\n",
    "\n",
    "def minimax_search(board, player = 'x'):\n",
    "    \"\"\"start the search.\"\"\"\n",
    "    global DEBUG, COUNT\n",
    "    COUNT = 0\n",
    "    \n",
    "    value, move = max_value(board, player)\n",
    "    \n",
    "    if DEBUG >= 1: print(f\"Number of nodes searched: {COUNT}\") \n",
    " \n",
    "    return { \"move\": move, \"value\": value}\n",
    "\n",
    "def max_value(state, player):\n",
    "    \"\"\"player's best move.\"\"\"\n",
    "    global DEBUG, COUNT\n",
    "    COUNT += 1\n",
    "    \n",
    "    # return utility of state if it is a terminal state\n",
    "    v = utility(state, player)\n",
    "    if DEBUG >= 2: print(\"max in: \" + str(state) + str([v]) ) \n",
    "    if v is not None: return v, None\n",
    "        \n",
    "    v, move = -math.inf, None\n",
    "\n",
    "    # check all possible actions in the state, return move with the largest value\n",
    "    for a in actions(state):\n",
    "        v2, a2 = min_value(result(state, player, a), player)\n",
    "        if v2 > v:\n",
    "            v, move = v2, a\n",
    "    \n",
    "    if DEBUG >= 2: print(\"max out: \" + str(state) + str([v, move]) ) \n",
    "    return v, move\n",
    "\n",
    "def min_value(state, player):\n",
    "    \"\"\"opponent's best response.\"\"\"\n",
    "    global DEBUG, COUNT\n",
    "    COUNT += 1\n",
    "    \n",
    "    # return utility of state if it is a terminal state\n",
    "    v = utility(state, player)\n",
    "    if DEBUG >= 2: print(\"min in: \" + str(state) + str([v]) ) \n",
    "    if v is not None: return v, None\n",
    "    \n",
    "    v, move = +math.inf, None\n",
    "\n",
    "    # check all possible actions in the state, return move with the smallest value\n",
    "    for a in actions(state):\n",
    "        v2, a2 = max_value(result(state, other(player), a), player)\n",
    "        if v2 < v:\n",
    "            v, move = v2, a\n",
    "    \n",
    "    if DEBUG >= 2: print(\"min out: \" + str(state) + str([v, move]) ) \n",
    "    return v, move"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Some Tests\n",
    "\n",
    "### x is about to win (choose 8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Board:\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAJwAAACcCAYAAACKuMJNAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjguMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy81sbWrAAAACXBIWXMAAAYnAAAGJwFNVNjHAAALpElEQVR4nO3dbWxTZRsH8H8LHXOzxWlH5zJWWRhvDgUG0qCyRQZfxEmADzoJ0fDJmIg8gYRIXKJGYzR7JChGTcDAMpeghgS3wJDNuUDYCMzINLPZIJsvsGwMSYWx1q3X86HPetY5tq69e53Tw/VLFs9Z77v3fTh/e7rT03NZiIggBBOr3hMQdxcJnGBl2sAdPtul9xTiZoZtGMvEgevWewpxM8M2jGXawAljksAJVhI4wWo652A+nw/19fUAgFWrVsHlcnEOr0xvby+amprgdDpRXFys93Ri4vV64fV64ff7UVRUhFmzZrGMy/oK9+OPP6K4uBjr16/H+fPnOYdWatasWSgpKdF7GnGZP38+SktL8eSTT+LSpUts47IGzufzYebMmbDZbBgaGuIcWoyDiHD+/HkUFBSwjckaOIfDAZ/Ph6GhIUyfzno0F2MQEerq6rBs2TLY7Xa2cVn3+tKlS9HQ0AAA8Hg8nEMr5fP50NDQgGvXriEzMxMPP/yw3lOaspaWFvzxxx8YGhqCz+fDggULWMZlDZzD4cCGDRs4h0wIh8OBjRs36j2NuHg8Hl3+p5fTIoKVBE6wksAJVhI4wUoCJ1ipDVx/P5CTA1gsoZ8nngCGhyfvt2WL1ic9HWhvVzotFW7fvo3PP/8cpaWlmDNnDtLS0mC32zF37lw899xzqK6uxnA023q3I9UaGoisViIg9FNePnH7w4e1tgDRZ58pmcaaikYlz0NEdOzYMcrJySEAE/4sWrSImpublY2rchuMQn3giIhef10L0LRpRE1N47fr7CSy27W2Gzcqm4KqnXXw4EGaNm1aRLCcTic9/vjj5PF4yOFwRDyWlpZGJ0+eVDK2BC5a//xDtHKlFqTZs4muX/93m8ce09rk5BD19yubgoqd1draSjabLRwml8tFX331FQ0NDYXbDA4O0v79+yk9PT3c7v7776crV67EPb4EbiouXyZyOLRAbdoU+fju3dpjVitRo9p/XBU7a+XKleEQZWRkUHt7+x3b1tfX0/Tp08Ptt2zZEvf4Eripqqoa//1ZfX3k+7w9e5QPHe/OamlpiThUfvrpp5P2ee2118LtU1JSqKenJ645SOBisXWrFqy0tND7uexs7XceT+jwqli8O2v37t0Rr26Dg4OT9unu7iaLxRLud+DAgbjmYMbAJf483P79wNy5oeWBAaC4GLhyJbTucABffgkY8FKl5ubm8PLatWsxY8aMSfvk5uZiyZIl4z6HCEl84O69NxQqmy20Hgxqj33yCTBnTsKnEIvOzs7w8iOPPBJ1v9FtRz+HCOH5pGHFitDJ3dE2bABeeIFl+Fj89ddf4eXMzMyo+41uO/o5RAhP4H75BaiujvzdmTNATw/L8LHw+/3h5ZSUlKj7jT70jn4OEZL4wA0OAs8/H/rvaH19wNatoT8dDOi+++4LL//9999R9/P5fOM+hwhJfOB27QLa2kLLNhvw5pvaY999B1RUJHwKsRj9tbnLly9H3W/0N6Cmcii+WyQ2cLW1wMcfa+vvvAOUlwMvv6z9bs8eoLU1odOIxbJly8LLZ8+ejarP8PAwzp07F14vLCxUPq9kl7jA9fQAL72krZeUADt3hpYrKoCRL54EAkBZGXDrVsKmEouioqLwcktLCzo6Oibtc/z4cVy7di28vnr16oTMLakl5OxeMEi0dq12ctfpJBr72eLFi0SpqVqbbduUTiHek6Y+n4/sdnv4JG5paemE7f1+PxUUFITbz5s3j4LBYFxzkBO/0aqoCL0/G/HFF8CDD0a2WbwYeP99bf3AAeCbbxIynVjY7Xbs2LEjvH7s2DHs2rVr3GveBgYGUFZWhp9//jn8uzfeeAMWi4VlrklFeYQvXCBKSdFeuV55ZeL2Tz+ttc3IIPrtNyXTUPHqEAgEaMWKFRGfqS5ZsoQ++ugjOnXqFNXV1dF7771HeXl5EW02b96sYAvM+QqnNnA3bxLNn68FqKCA6Pbtifv09hJlZWl9Vq8mGh6Oeyqqdtb169dp1apVk158OTpsfr9fydhmDJzaQ+r27YDXG1pOTQ2d7E1NnbhPZiZw6FDo8nIAaGoC3n1X6bTikZGRgcbGRuzduxfZ2dl3bJefn4+qqiocOXJkSieK7zYWIoOeeY1TyX9/wKn/FE3ecAqICK2trbh48SL6+vpgtVrhcrmwfPlyLFy4UOlYQGK2QW/Gu0zDwCwWCwoLC+X8Whzka4KClQROsJLACVYSOMFKAidYSeAEKwmcYCWBE6wkcIKVBE6wksAJVhI4wepfV4scPttlisKw3f234H4gXe9pxMUM2wAg4ooXuTzJwMywDWPJIVWwksAJVhI4wYo1cN3d3aipqUF1dTWujNwjLkkNDAxg3759uHHjht5TiUlXVxcOHTqEmpoa9PX1sY3Leom52+2G2+3G1atXcfXq1Qm/lGJ0zc3NbCUfE8VmsyEYDCI9ne8vYfZD6oULF1BTU4Pc3FzuoZXp6OjA7Nmzk/rbWW63G2VlZfB4PKx36mQPXGFhIcrKyiJu+pJsfv/9d1y6dAmdnZ1oNeCNeKIxcleAtLQ0BAIBtnFZD6nt7e3o6urC4OAgli9fzjm0Uk899RQAoLGxMeKevsnk119/RUdHB/x+P4qLi9nGZQ3cwoULE/L9Tb1w7ijVFixYoMt7UDktIlhJ4AQrCZxgJYETrCRw4zFxoWG9JTxwSVlJ+YEHgMpKwPr/f54zZ4C33pq4T2UlUFWlrX/4IWCiv8iVSeTN5/SqpEyk6GZ+OhcaNuMNCRMWOD0rKRMp2lk6FxqWwEVJ70rKRAp3lo6FhiVwUdK7kjKR4p2lU6FhCVwUjFBJmSgBO0uHQsNmDJzyv1KPHj0aXs7IyMCLL744aZ8dO3aEr14IBAKora1VPa34JWmhYaNRHjjTVlJO0kLDRqM8cKaupJyEhYaNRnngTF1JOQkLDRuN8sCZtpJykhYaNhrlgTNtJeUkLTRsNMoDZ8pKyklcaNholAfOdJWUk7zQsNEoD5ypKikThd6fjXxR2OkEDh/WCtHdc09kATuvN1TgTtyZ6jPJRqikTKToLP0HH0R+pPXtt+O327cvst3XX8c/Npnzk4aEfJZaXl4e8fHWzp07Iz64H3Hr1i3atGlTRNvKykolc4h7Zxmg0LAELkp6V1IminNnGaTQsARuCvSspEwU587atk0LTmoqUVtbdP3q6ogsFq3v22/HPgeSwE1ZIBCgvXv3UnZ29h2Dlp+fT1VVVUret41mhp1lhm0YK6GXN9hsNmzfvh2vvvoqayVlYVws19NIJWUxQr4mKFhJ4AQrCZxgJYETrCRwgpUETrCSwAlWEjjBSgInWEngBCsJnGAlBXoNzAzbAEiB3qRhhm0YSw6pgpUETrCSwAlWEjjBivUOesFgEN9//z38fj/y8vKStsBtR0cHvF4vbt68CafTiZKSEr2nNGU3btxAXV0dZsyYAbfbjaVLl7KMy/oK5/V6MTAwAKvVipkzZ3IOrVR+fj7Wr1+PrKwsLF68WO/pxKS/vx+PPvoonn32Wfz5559s47IGrr+/Hw899BDWrVtnzLtcTgERobe3Fy6XS++pxCQrKwstLS04ePAgFi1axDYu6yHVbrcjNTUVVmvyv3Xs7u6G2+3Wexox++mnn7Bu3Tq4XC7U1tYiLy+PZVz2Ar0nTpyA1+vFvHnzOIdWrq2tDWvWrNF7GjHLy8vD6dOnYbPZkJubyzYua+BSUlJQWlrKOWTCPPPMM3pPIS5ZWVnYvHkz+7jJf2wTSUUCJ1hJ4AQrCZxgJYETrCRwgpUETrCSwAlWEjjBSgInWEngBCsJnGAlgROsJHCClQROsJLACVYSOMFKAidYSeAEKwmcYCWBE6wkcIKVBE6wksAJVhI4wUoCJ1hJ4AQrCZxgJYETrCRwgpUETrCSwAlWEjjBSgInWEngBCsJnGAlgROsJHCClWkL9Apjklc4wUoCJ1hJ4ASr/wHngomQYG4MtAAAAABJRU5ErkJggg==",
      "text/plain": [
       "<Figure size 192x192 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Number of nodes searched: 190\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "{'move': 2, 'value': 1}"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 14.1 ms, sys: 1.99 ms, total: 16.1 ms\n",
      "Wall time: 5.34 ms\n"
     ]
    }
   ],
   "source": [
    "board = empty_board() \n",
    "board[0] = 'x'\n",
    "board[1] = 'o'\n",
    "board[3] = 'o'\n",
    "board[4] = 'x'\n",
    "\n",
    "print(\"Board:\")\n",
    "show_board(board)\n",
    "\n",
    "print()\n",
    "%time display(minimax_search(board))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Note:** DFS does not pick the the shortest path to a win! Discounting the utility can help.\n",
    "\n",
    "### x can draw if it chooses 7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Board:\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAJwAAACcCAYAAACKuMJNAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjguMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy81sbWrAAAACXBIWXMAAAYnAAAGJwFNVNjHAAAMP0lEQVR4nO3df0xT5xoH8G+BgoG1jt1iCUE6iaAo21R0NLopQfSfOea0yRwjZol/LG7LNm90cb9MzP7Ysh83xoVl12Uuc2EkumQJYhwTkGtcoE4h022sAw1sThgIMx1WWgvP/aO3p9TJD+npc057n09C7I/37fucvF97DqeHvgYiIgjBJEHrAsT/FwmcYBW3gTvU0q11CRGLh224VRwHrkfrEiIWD9twq7gNnNAnCZxgJYETrJI4B3O73WhsbAQArFy5ElarlXN41fT39+PUqVOwWCwoKSnRupwZcblccLlc8Hq9WLNmDebMmcMyLus7XHt7O0pKSrBhwwacPXuWc2hVzZkzB2VlZVqXEZEFCxagvLwcDz/8MC5evMg2Lmvg3G43Zs+eDaPRCL/fzzm0uA0iwtmzZ1FYWMg2JmvgzGYz3G43/H4/kpJY9+biFkSE+vp6LFu2DCaTiW1c1llfunQpmpqaAAB2u51zaFW53W40NTXh6tWryMjIwOLFi7Uu6Y45nU5cvnwZfr8fbrcbCxcuZBmXNXBmsxkbN27kHDIqzGYzNm3apHUZEbHb7Zr8p5fTIoKVBE6wksAJVhI4wUoCJ1ipG7jBQSA7GzAYAj8PPQSMjk7dr7Iy1CctDejoULUsNdy4cQMHDhxAeXk55s2bh9TUVJhMJsyfPx9btmxBTU0NRqezrZz0OB+ktqYmooQEIiDws2fP5O0PHQq1BYj+/W9Vylj7frMqr0NEVFtbS9nZ2QRg0p9FixZRa2urauOqsg06mY8g9QNHRPTqq6GCExOJTp26fbuuLiKTKdR20ybVSlArcAcPHqTExMSwYFksFlq1ahXZ7XYym81hz6WmptI333yjytiq/afRwXwERSdwN28SFReHCp87l2ho6O9tHnww1CY7m2hwULUS1JistrY2MhqNSpisVisdOXKE/H6/0mZkZISqqqooLS1NaXfPPffQlStXIh5ftcDpYD6CohM4IqJLl4jM5tAGbN4c/vzu3aHnEhKImtXbBRKpM1nFxcVKiNLT06mjo2PCto2NjZSUlKS0r6ysjHh8NQ8LtJ6PoOgFjoiouvr2xwONjeHHFa+9pvrQkU6W0+kM21V+9NFHU/Z56aWXlPbJycnU19cXUQ2qBo5I0/kIim7giIi2bg1tSGpq4PghKyv0mN0eeDtXWaSTtXv37rB3t5GRkSn79PT0kMFgUPp98sknEdWgeuCINJuPoOifh6uqAubPD9z2eICSEuDKlcB9sxn44gtAh5cqtba2KrfXrVuHlJSUKfvk5ORgyZIlt30N3dB4PqIfuLvuCmyE0Ri4PzYWeu7DD4F586Jewkx0dXUpt++///5p9xvfdvxr6IbG88HzScOKFYGTieNt3Ag89RTL8DPx559/KrczMjKm3W982/GvoSsazgdP4H78EaipCX/s22+Bvj6W4WfC6/Uqt5OTk6fdb/yud/xr6IqG8xH9wI2MAE8+Gfh3vIEBYOvWwKGqDt19993K7b/++mva/dxu921fQzc0no/oB27XLuDChcBtoxHYuzf03IkTwPvvR72EmRj/Z3OXLl2adr/xfwF1J7tiNlrPR9R+/yUiqqsLP+/zzjuBx7dvDz2WnEx07pzqQ0d6SqGyslI5vVFcXDytPn6/nywWi9Jv7969EdWg+mkRDecjKHqB6+0lysgIbUhZGdHYWOA5j4do8eLQcwsWEA0Pqzp8pJP18ccfh534/eWXX6bsc/To0bA+J0+ejKgGVQOn8XwERSdwY2NE69aFNsBiIbr1s8Xz54lmzQq12bZN1RIinSy3200mk0kJT3l5+aTtvV4vFRYWKu3z8/NpLDihM6Ra4HQwH0HRCdy774a/dR89evt2+/eHt/vyS9VKUGOy9uzZE/aOtXPnzrAP7oOuX79OmzdvDmv7+eefRzy+aoHTwXwEqR+4c+cCxwHBop97bvL2jzwSapueTvTrr6qUocZk+Xw+WrFiRViQlixZQh988AE1NDRQfX09vf3225SbmxvWxuFwqLAFKgVOJ/MRpG7ghocD+/9gwYWFRDduTN6nv58oMzPUZ/VqotHRiEtR691haGiIVq5cGRaoyX4cDgd5vV5Vxo54G3Q0H0HqBm7btlChs2YRXbgwvX719UQGQ6jvm29GXIqaB9w+n4/27dtHWVlZEwYtLy+PqqurIz5uGy/ibdDRfAQZiHR65jVCZf/6Dxr+uUbV1yQitLW14fz58xgYGEBCQgKsViuWL1+OgoICVccCorMNWtPfZRo6ZjAYUFRUhKKiIq1LiVnyZ4KClQROsJLACVYSOMFKAidYSeAEKwmcYCWBE6wkcIKVBE6wksAJVhI4wepvV4scaumOi4Vhewavw/aPNK3LiEg8bAOAsCte5PIkHYuHbbiV7FIFKwmcYCWBE6xYA9fT04O6ujrU1NTgSvA7yWKUx+PB/v37ce3aNa1LmZHu7m589tlnqKurw8DAANu4rJeY22w22Gw29Pb2ore3F1lZWZzDq6q1tZVtycdoMRqNGBsbQ1oa32/C7LvUc+fOoa6uDjk5OdxDq6azsxNz5869o6/x0hubzYaKigrY7XbWb+pkD1xRUREqKipw5swZ7qFV89tvv+HixYvo6upCW1ub1uXMiMFgAACkpqbC5/Oxjcu6S+3o6EB3dzdGRkawfPlyzqFVVVpaCgBobm4O+07fWPLzzz+js7MTXq8XJSUlbOOyBq6goCAqf7+pFc6JUtvChQs1OQaV0yKClQROsJLACVYSOMFKAidYSeCmKSZXhNYj1b74S2dkRWh9kne4KXz66ad4/PHHcfnyZeUxi8WCVatWwW63w2w2K4//9NNPKC0txYkTJ7QoNSZI4CbR3t6OZ555RtlVWq1WHDlyBH19fTh9+jRaWlrQ39+Pqqoq5QNwj8eDLVu2oLe3V8vSdUsCN4nt27fj5s2bAID09HQ0NzfD4XAgMTFRaZOSkoJnn30WtbW1SPrfso9DQ0N4+eWXNalZ7yRwEzhz5gycTqdy/6233pr0o6DS0lI8//zzyv3Dhw/jjz/+iGqNsUgCN4GvvvpKuZ2eno6nn356yj47duxQrsLw+Xw4duxYtMqLWRK4CcTtitAak8BNIG5XhNaYBG4Ccb0itIYkcBOI6xWhNSSBm0DcrgitMQncBOJ2RWiNSeAmsGzZMuV2S0vLtPqMjo6G/XGQrFjzdxK4CaxZE/oSGafTic7Ozin7HD9+HFevXlXur169Oiq1xTIJ3ASeeOIJmEwm5f7OnTsnbe/z+fDKK68o9/Pz88NCKwIkcBMwmUzYsWOHcr+2tha7du267TVvHo8HFRUV+OGHH5TH3njjDeVTBxEiqwlO4vXXX8fx48fx3XffAQDee+89NDQ0YNu2bSgoKMDo6Cja29tx4MCBsF8sHA4HKisrtSpb37S+IC9aZEVofZJd6hSClyXt27dv0i/fycvLQ3V1NQ4fPhzT3zkSbbJLnQaj0YgXX3wRL7zwAuuK0PFIAncHZEXoyMkuVbCSwAlWEjjBSgInWEngBCsJnGAlgROsJHCClQROsJLACVYSOMFKFujVsXjYBkAW6I0Z8bANt5JdqmAlgROsJHCClQROsGK94ndsbAwnT56E1+tFbm5uzC5w29nZCZfLheHhYVgsFpSVlWld0h27du0a6uvrkZKSApvNhqVLl7KMy/oO53K54PF4kJCQgNmzZ3MOraq8vDxs2LABmZmZuO+++7QuZ0YGBwfxwAMP4LHHHsPvv//ONi5r4AYHB3Hvvfdi/fr1Mf/tkESE/v5+WK1WrUuZkczMTDidThw8eBCLFi1iG5d1l2oymTBr1iwkJMT+oWNPTw9sNpvWZczY999/j/Xr18NqteLYsWPIzc1lGZd9gd6vv/4aLpcL+fn5nEOr7sKFC1i7dq3WZcxYbm4uTp8+DaPRiJycHLZxWQOXnJyM8vJyziGj5tFHH9W6hIhkZmbC4XCwjxv7+zYRUyRwgpUETrCSwAlWEjjBSgInWEngBCsJnGAlgROsJHCClQROsJLACVYSOMFKAidYSeAEKwmcYCWBE6wkcIKVBE6wksAJVhI4wUoCJ1hJ4AQrCZxgJYETrCRwgpUETrCSwAlWEjjBSgInWEngBCsJnGAlgROsJHCClQROsJLACVYSOMFKAidYxe0CvUKf5B1OsJLACVYSOMHqv5LF5/1WsPcyAAAAAElFTkSuQmCC",
      "text/plain": [
       "<Figure size 192x192 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Number of nodes searched: 206\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "{'move': 7, 'value': 0}"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 13.3 ms, sys: 5.27 ms, total: 18.6 ms\n",
      "Wall time: 6.14 ms\n"
     ]
    }
   ],
   "source": [
    "board = empty_board() \n",
    "board[0] = 'x'\n",
    "board[1] = 'o'\n",
    "board[2] = 'x'\n",
    "board[4] = 'o'\n",
    "\n",
    "print(\"Board:\")\n",
    "show_board(board)\n",
    "\n",
    "print()\n",
    "%time display(minimax_search(board))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### o is about to win no matter what x does\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Board:\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAJwAAACcCAYAAACKuMJNAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjguMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy81sbWrAAAACXBIWXMAAAYnAAAGJwFNVNjHAAAMSUlEQVR4nO3df0wb5R8H8DcdZQi2GxNWJIwKGfvJdBubNFMHOuSfIS5sf2idi8bMxCyKfLMl02WL08wYla/LdP6YumVDJPFHlkyIogMRXQZmwygabIAFnG4ExrbUwWgtPN8/7kuvRQYtvX7uev28EuJdea7P8+zetsdde58YIYQAY0QMag+ARRcOHCOl28AdO92t9hBCpoc5jKfjwPWoPYSQ6WEO4+k2cEybOHCMFAeOkYql7MzpdKK+vh4AsGbNGlgsFsruFdPX14empiYkJyejoKBA7eFMi8PhgMPhgMvlQn5+PubOnUvSL+kr3E8//YSCggIUFxfjzJkzlF0rau7cuSgsLFR7GCFZuHAhSkpKcM8996Crq4usX9LAOZ1OzJo1C0ajER6Ph7JrNgEhBM6cOYOcnByyPkkDZzab4XQ64fF4EBtL+m7OxhFCoK6uDitXroTJZCLrl3Svr1ixAg0NDQAAm81G2bWinE4nGhoacOnSJaSkpGDp0qVqDyloLS0t+PPPP+HxeOB0OrFo0SKSfkkDZzabsWHDBsouw8JsNqO0tFTtYYTEZrOp8j89nxZhpDhwjBQHjpHiwDFSHDhGKuyBu379Og4dOoSSkhJkZmYiISEBJpMJ8+fPx0MPPYTq6mqMjIyEexgh08s8VCfC6MSJEyI9PV0AmPRnyZIlorm5WdG+11U0KvZcas1DyTloRdgCd/jwYTFjxgy/HZKcnCzuuusuYbPZhNls9vtdQkKC+PrrrxXrX6mdpeY8OHABam1tFUaj0bsTLBaL+PTTT4XH4/G2GR4eFgcPHhSJiYnednPmzBEXLlxQZAxK7Cy158GBC1BeXp73Hz8pKUm0t7ffsG19fb2IjY31tt+8ebMiY1BiZ6k9Dw5cAFpaWvzeYt59990pt3n22We97ePi4kRvb2/I4wh1Z2lhHnoMnOJ/pR4/fty7nJSUhMcee2zKbcrLyxETEwMAcLvdqK2tVXpYQdPLPLRG8cA1Nzd7l++//37MnDlzym0yMjKwfPnyCZ9DLXqZh9YoHrjOzk7v8u233x7wdr5tfZ9DLXqZh9YoHrgrV654l1NSUgLezret73OoRS/z0BrFA+dyubzLcXFxAW/n+5bl+xxq0cs8tEbxwM2ePdu7/Pfffwe8ndPpnPA51KKXeWiN4oHz/brZuXPnAt7O95tDwbyFhYte5qE1igdu5cqV3uXTp08HtM3IyAh+/PFH73pubq7SwwqaXuahNYoHLj8/37vc0tKCjo6OKbf58ssvcenSJe/62rVrlR5W0PQyD81R+kyy0+kUJpPJe8a9pKRk0vYul0vk5OR42y9YsECMjo6GPI5Qz9JrYR58pSEAJpMJ5eXl3vUTJ05gx44dE35WbGhoCHa7Hb/++qv3sd27d3vP1qtJL/PQnHCk2O12i9WrV/tdi1y+fLl48803xcmTJ0VdXZ145ZVXRFZWll+bTZs2KTYGJV4d1J6HHl/hwvZ5uMuXL4s1a9ZM+aFF353kcrkU61+pnaXmPPQYuLB9xDwpKQmNjY3Yv38/0tLSbtguOzsbVVVV+OSTT4I6wUpFL/PQihghwn/bfCEEWltb8csvv6C/vx8GgwEWiwWrVq3C4sWLw9Jn4X+/w8n/5E/dMAjU8wjHHNRGcquHmJgY5ObmRvx5Kb3MQ038NUFGigPHSHHgGCkOHCPFgWOkOHCMFAeOkeLAMVIcOEaKA8dIceAYKQ4cI/WvT4scO92ti8KwPQODsN6SqPYwQqKHOQDw+8QLyceT1KCHj/boYQ7j8VsqI8WBY6Q4cIwUaeB6enpQU1OD6upqXLhwgbJrxQ0NDeHAgQO4evWq2kOZlu7ubhw9ehQ1NTXo7+8n65e0mqDVaoXVasXFixdx8eLFSb+UonXNzc1kJR/DxWg0YnR0FImJdH8Jk7+lnj17FjU1NcjIyKDuWjEdHR2YN29eRH87y2q1wm63w2azkd6pkzxwubm5sNvtfjd9iTTnz59HV1cXOjs70draqvZwpmXsrgAJCQlwu91k/ZK+pba3t6O7uxvDw8NYtWoVZdeKuu+++wAAjY2Nfvf0jSS///47Ojo64HK5UFBQQNYvaeAWL14ctu+hqoFyRylt0aJFqhyD8mkRRooDx0hx4BgpDhwjxYGbyMAAkJ4OxMRIP3ffDQRSfHfzZnmbxESgvT38Y40wXBF6IrfcAlRWAob///OcOgW8+OLk21RWAlVV8vobbwA6+otcMeG8+VzEV4R+/nkhAOlnxgwhmpombtfZKYTJJLctLQ29b6HPGxJyRejJ/POPEHl5cpDmzRPi8uV/t7nzTrlNeroQAwOh9y04cAFTu5KyEArurHPnhDCb5UBt3Oj/+5075d8ZDEI0KhcSDlyA1K6kLITCO6uqSg4VIMR770mP19dLIRt7fNcu5foUHLiAaKGSshBh2FlbtsjBSkiQjufS0uTHbDbp7VVBegwcV4QO1MGDwPz50vLQEFBQAIx9iNRsBj7+GIglvTQdkbgidKBuvlkKldEorY+Oyr97+20gM1OdcUUYrggdjNWrpZO7vjZsAB55RJXhRCKuCB2M334Dqqv9Hzt1CujtVWc8EYgrQgdqeBh4+GHpv776+4EtW6Q/HdiUuCJ0oHbsANrapGWjEdi7V/7dN98AFRXqjCvCcEXoQNTWAm+9Ja/v2wfs2QM89ZT82K5dQIR+v4ESV4SeSm8v8Pjj8nphIbB9u7RcUQEsXSotu92A3Q4MDtKPMYJwRejJCCEdn419UTg5GTh2TPr4EQDcdJP0R0R8vLTucABlZeqMNVIofSZZC5WUhVDoLP1rr/lf0vrii4nbHTjg3+6zz0LvW+jzSkNYrqXu2bPH7/LW9u3b/S7cjxkcHBQbN270a1tZWanIGELeWWfPChEXJ4do27bJ269fL7dNShLijz9C619w4AKmdiVlIULcWdeuCbFwoRygnBwhrl+ffJu+PiFSU+Vt1q4VYmRk+mMQHLigRHRF6CeekIMTHy9EW1tg29XVCRETI2/70kvTH4PgwAXN7XaL/fv3i7S0tBsGLTs7W1RVVSly3OZLDztLD3MYL6wfbzAajSgrK8MzzzxDXhGaaRNXhGak+GuCjBQHjpHiwDFSHDhGigPHSHHgGCkOHCPFgWOkOHCMFAeOkeLAMVJcoFfD9DAHgAv0Rgw9zGE8fktlpDhwjBQHjpHiwDFSpHfQGx0dxbfffguXy4WsrKyILXDb0dEBh8OBa9euITk5GYWFhWoPKWhXr15FXV0dZs6cCavVihUrVpD0S/oK53A4MDQ0BIPBgFmzZlF2rajs7GwUFxcjNTUVy5YtU3s40zIwMIA77rgDDz74IP766y+yfkkDNzAwgNtuuw1FRUXavMtlEIQQ6Ovrg8ViUXso05KamoqWlhYcPnwYS5YsIeuX9C3VZDIhPj4eBkPkHzr29PTAarWqPYxp+/nnn1FUVASLxYLa2lpkZWWR9EteoPerr76Cw+HAggULKLtWXFtbG9atW6f2MKYtKysLP/zwA4xGIzIyMsj6JQ1cXFwcSkpKKLsMmwceeEDtIYQkNTUVmzZtIu838t/bWEThwDFSHDhGigPHSHHg9EyDla05cHqmwcrWHDi9u/deYOdOeX3fPuD77ydu29UFbNsmr5eWAk8+qehwOHDRYO9eIC9PWh4ZkWqDjS8v5fFIt/0fK+aSng68/77iQ+HARYPYWOn2/maztH7+PLB1q3+b3buBsVoZBgPw0UfAnDmKD4UDFy0yM4F33pHXP/8cOHRIWm5oAF59Vf7dc88B+eH5LgUHLprY7VKhkzHl5dLx3KOPyvVfbTbghRfCNgQOXLRRubI1By7aqFzZmgMXjVSsbM2Bi0YqVrbmwEUblStbc+CijcqVrTlw0UQDla05cNFCI5WtOXDRQEOVrTlw0aCiQjo+G3PkCHDrrf5tli3zv7z14YfS5S+FceD0rrVVOi4bs20bUFw8cdunnwbWr5fXt26VLvQriAOnZ4OD0vGY2y2t5+QAr78++TZHjgCpqdLylSvSCWLfqxEh4sDpWVmZdDwGSMdnvsdpN5KSAhw9Kh/fNTUBL7+s2JBIvwjNiH3wgfQTrKIiRV/VfPErHCPFgWOkOHCMFAeOkeLAMVIcOEaKA8dIceAYKQ4cI8WBY6Q4cIwUB46R4sAxUrot0Mu0iV/hGCkOHCPFgWOk/gcEbq4OuI+N9QAAAABJRU5ErkJggg==",
      "text/plain": [
       "<Figure size 192x192 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Number of nodes searched: 33\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "{'move': 2, 'value': -1}"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 1.88 ms, sys: 6.02 ms, total: 7.9 ms\n",
      "Wall time: 2.57 ms\n"
     ]
    }
   ],
   "source": [
    "board = empty_board() \n",
    "board[0] = 'o'\n",
    "board[1] = 'o'\n",
    "board[3] = 'o'\n",
    "board[4] = 'x'\n",
    "board[8] = 'x'\n",
    "\n",
    "print(\"Board:\")\n",
    "show_board(board)\n",
    "\n",
    "print()\n",
    "%time display(minimax_search(board))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Empty board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Board:\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAJwAAACcCAYAAACKuMJNAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjguMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy81sbWrAAAACXBIWXMAAAYnAAAGJwFNVNjHAAAFSUlEQVR4nO3dT0tUexzH8Y/iWBiOi2vOIOSJgUrLKLPFEIRDDa7MIlr5MO4DuYseQFCbnsAECjfrSpCGJeHCDpMwQ38EdUAOXWli8Nzd5V7v3TSOn5PT+7USN9/vYd7Ob5zNryOO41iASWfSC+DnQnCwatvgHr2sJL3CgbXDM+zXxsFVk17hwNrhGfZr2+DwYyI4WBEcrLqcw6Io0tOnTyVJ165dUyaTcY5vmc3NTS0sLKi/v1+FQiHpdZoShqHCMFS9XtfExIQGBgYsc63vcCsrKyoUCpqamtLy8rJzdEsNDAyoWCwmvcaBnDt3TtPT07p+/brW19dtc63BRVGkvr4+pVIpNRoN52j8jziOtby8rNHRUdtMa3DpdFpRFKnRaKiry3qaY584jjU3N6crV66ot7fXNtf6qo+NjWl+fl6SlM/nnaNbKooizc/Pa3t7WydPntSFCxeSXum7LS0t6ePHj2o0GoqiSMPDw5a51uDS6bTu3LnjHHko0um07t69m/QaB5LP5xP5o+drEVgRHKwIDlYEByuCgxXBwYrgYEVwsCI4WBEcrAgOVgQHK4KDFcHBiuBgRXCwIjhYERysCA5WBAcrgoMVwcGK4GBFcLAiOFgRHKwIDlYEByuCgxXBwYrgYEVwsCI4WBEcrAgOVgQHK4KDFcHBiuBg1RHHcfzPXzx6WWmLi2GrtT8V/HIi6TUOpB2eQZJ+/3Xi75//E1y7KP72x78e9Chqh2fYjyMVVgQHK4KDlTW4arWqUqmkx48f6/Pnz87RLbe7u6v79+9rZ2cn6VWaUqlU9PDhQ5VKJW1tbdnmWm8TDIJAQRBoY2NDGxsbGhwcdI5vqcXFRduVj4cllUppb29PJ074/hO2H6mvX79WqVTS0NCQe3TLlMtlnTp1St3d3Umv0rQgCDQzM6N8Pq/FxUXbXHtw4+PjmpmZ0atXr9yjW+bDhw9aX1/X+/fv9ebNm6TXaUpHR4ckqaenR9++fbPNtR6pa2trqlQq+vr1q65eveoc3VI3btyQJD1//lyXL19OdpkmvXv3TuVyWfV6XYVCwTbXGtzIyIhGRkacIw+V84VqteHh4UQ+g/K1CKwIDlYEByuCgxXBwYrgYEVwsCI4WBEcrAgOVgQHK4KDFcHBiuBgRXCwIjhYERysCA5WBAcrgoMVwcGK4GBFcLAiOFgRHKwIDlYEByuCgxXBwYrgYEVwsCI4WBEcrAgOVgQHK4KDFcHBiuBgxQW9P7B2eAaJC3qPjHZ4hv04UmFFcLAiOFgRHKysl7vt7e3p2bNnqtfryuVyR/aC23K5rDAM9eXLF/X396tYLCa90nfb2dnR3Nycjh07piAINDY2ZplrfYcLw1C7u7vq7OxUX1+fc3RLnTlzRlNTU8pms7p48WLS6zSlVqvp0qVLun37tj59+mSbaw2uVqvp9OnTmpyctN5CfBjiONbm5qYymUzSqzQlm81qaWlJDx480Pnz521zrUdqb2+vjh8/rs7Oo//RsVqtKgiCpNdo2tu3bzU5OalMJqMnT54ol8tZ5tov6J2dnVUYhjp79qxzdMutrq7q5s2bSa/RtFwupxcvXiiVSmloaMg21xpcd3e3pqennSMPza1bt5Je4UCy2azu3btnn3v0zzYcKQQHK4KDFcHBiuBgRXCwIjhYERysCA5WBAcrgoMVwcGK4GBFcLAiOFgRHKwIDlYEByuCgxXBwYrgYEVwsCI4WBEcrAgOVgQHK4KDFcHBiuBgRXCwIjhYERysCA5WBAcrgoMVwcGK4GBFcLBq2wt68WPiHQ5WBAcrgoPVX+CrRo0sHKjjAAAAAElFTkSuQmCC",
      "text/plain": [
       "<Figure size 192x192 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Number of nodes searched: 549946\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "{'move': 0, 'value': 0}"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 13.1 s, sys: 165 ms, total: 13.3 s\n",
      "Wall time: 13 s\n"
     ]
    }
   ],
   "source": [
    "board = empty_board() \n",
    "\n",
    "print(\"Board:\")\n",
    "show_board(board)\n",
    "\n",
    "\n",
    "print()\n",
    "%time display(minimax_search(board))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Note:__ Starting with an empty board searched the complete game tree and takes a while. The number of nodes above is the actual size of the complete game tree. A table with know 'openings' (e.g., place x in a corner, o chooses the center, etc.) would be helpful to speed things up."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Recursive DFS algorithm for Minimax Search with Alpha-Beta Pruning\n",
    "\n",
    "See AIMA page 154. \n",
    "\n",
    "Adds alpha-beta pruning to minimax search. Alpha and beta are used to maintain bounds on the minimax value of a node in the form `[alpha, beta]`. alpha means that the value is at least that high and beta means that the actual value is at most that high. Subtrees below a node that are worse than the currently known bound do not need to be further explored and can be pruned. Max uses alpha and Min uses beta for pruning.\n",
    "\n",
    "The implementation is for player 'x' returns a the optimal next move."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# global variables\n",
    "DEBUG = 1 # 1 ... count nodes, 2 ... debug each node\n",
    "COUNT = 0\n",
    "\n",
    "def alpha_beta_search(board, player = 'x'):\n",
    "    \"\"\"start the search.\"\"\"\n",
    "    global DEBUG, COUNT\n",
    "    COUNT = 0\n",
    "    \n",
    "    value, move = max_value_ab(board, player, -math.inf, +math.inf)\n",
    "    \n",
    "    if DEBUG >= 1: print(f\"Number of nodes searched: {COUNT}\") \n",
    "    \n",
    "    return { \"move\": move, \"value\": value }\n",
    "\n",
    "def max_value_ab(state, player, alpha, beta):\n",
    "    \"\"\"player's best move.\"\"\"\n",
    "    global DEBUG, COUNT\n",
    "    COUNT += 1\n",
    "       \n",
    "    # return utility of state is a terminal state\n",
    "    v = utility(state, player)\n",
    "    if DEBUG >= 2: print(f\"max: {state} [alpha,beta]=[{alpha},{beta}] v={v}\")\n",
    "    if v is not None: \n",
    "        if DEBUG >= 2: print(f\"     found terminal state. backtracking.\")\n",
    "        return v, None\n",
    "        \n",
    "    v, move = -math.inf, None\n",
    "\n",
    "    # check all possible actions in the state, update alpha and return move with the largest value\n",
    "    for a in actions(state):\n",
    "        v2, a2 = min_value_ab(result(state, player, a), player, alpha, beta)\n",
    "        if DEBUG >= 2: print(f\"max: {state} (backtracked) [alpha,beta]=[{alpha},{beta}] v={v2}\")\n",
    "        \n",
    "        if v2 > v:\n",
    "            v, move = v2, a\n",
    "            alpha = max(alpha, v)\n",
    "        if v >= beta:\n",
    "            if DEBUG >= 2: print(f\"     v>=beta ({v}>={beta}): pruning remaining subtree (actions). backtracking.\")\n",
    "            return v, move\n",
    "    \n",
    "    return v, move\n",
    "\n",
    "def min_value_ab(state, player, alpha, beta):\n",
    "    \"\"\"opponent's best response.\"\"\"\n",
    "    global DEBUG, COUNT\n",
    "    COUNT += 1\n",
    "    \n",
    "    # return utility of state is a terminal state\n",
    "    v = utility(state, player)\n",
    "    if DEBUG >= 2: print(f\"min: {state} [alpha,beta]=[{alpha},{beta}] v={v}\")\n",
    "    if v is not None: \n",
    "        if DEBUG >= 2: print(f\"     found terminal state. backtacking.\")\n",
    "        return v, None\n",
    "    \n",
    "    v, move = +math.inf, None\n",
    "\n",
    "    # check all possible actions in the state, update beta and return move with the smallest value\n",
    "    for a in actions(state):\n",
    "        v2, a2 = max_value_ab(result(state, other(player), a), player, alpha, beta)\n",
    "        if DEBUG >= 2: print(f\"min: {state} (backtracked) [alpha,beta]=[{alpha},{beta}] v={v2}\")\n",
    "        \n",
    "        if v2 < v:\n",
    "            v, move = v2, a\n",
    "            beta = min(beta, v)\n",
    "        if v <= alpha: \n",
    "            if DEBUG >= 2: print(f\"     v<=alpha ({v}<={alpha}): pruning remaining subtree (actions). backtracking.\")\n",
    "            return v, move\n",
    "    \n",
    "    return v, move"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Some Tests\n",
    "\n",
    "### x is about to win (play 8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Board:\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAJwAAACcCAYAAACKuMJNAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjguMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy81sbWrAAAACXBIWXMAAAYnAAAGJwFNVNjHAAALpElEQVR4nO3dbWxTZRsH8H8LHXOzxWlH5zJWWRhvDgUG0qCyRQZfxEmADzoJ0fDJmIg8gYRIXKJGYzR7JChGTcDAMpeghgS3wJDNuUDYCMzINLPZIJsvsGwMSYWx1q3X86HPetY5tq69e53Tw/VLFs9Z77v3fTh/e7rT03NZiIggBBOr3hMQdxcJnGBl2sAdPtul9xTiZoZtGMvEgevWewpxM8M2jGXawAljksAJVhI4wWo652A+nw/19fUAgFWrVsHlcnEOr0xvby+amprgdDpRXFys93Ri4vV64fV64ff7UVRUhFmzZrGMy/oK9+OPP6K4uBjr16/H+fPnOYdWatasWSgpKdF7GnGZP38+SktL8eSTT+LSpUts47IGzufzYebMmbDZbBgaGuIcWoyDiHD+/HkUFBSwjckaOIfDAZ/Ph6GhIUyfzno0F2MQEerq6rBs2TLY7Xa2cVn3+tKlS9HQ0AAA8Hg8nEMr5fP50NDQgGvXriEzMxMPP/yw3lOaspaWFvzxxx8YGhqCz+fDggULWMZlDZzD4cCGDRs4h0wIh8OBjRs36j2NuHg8Hl3+p5fTIoKVBE6wksAJVhI4wUoCJ1ipDVx/P5CTA1gsoZ8nngCGhyfvt2WL1ic9HWhvVzotFW7fvo3PP/8cpaWlmDNnDtLS0mC32zF37lw899xzqK6uxnA023q3I9UaGoisViIg9FNePnH7w4e1tgDRZ58pmcaaikYlz0NEdOzYMcrJySEAE/4sWrSImpublY2rchuMQn3giIhef10L0LRpRE1N47fr7CSy27W2Gzcqm4KqnXXw4EGaNm1aRLCcTic9/vjj5PF4yOFwRDyWlpZGJ0+eVDK2BC5a//xDtHKlFqTZs4muX/93m8ce09rk5BD19yubgoqd1draSjabLRwml8tFX331FQ0NDYXbDA4O0v79+yk9PT3c7v7776crV67EPb4EbiouXyZyOLRAbdoU+fju3dpjVitRo9p/XBU7a+XKleEQZWRkUHt7+x3b1tfX0/Tp08Ptt2zZEvf4Eripqqoa//1ZfX3k+7w9e5QPHe/OamlpiThUfvrpp5P2ee2118LtU1JSqKenJ645SOBisXWrFqy0tND7uexs7XceT+jwqli8O2v37t0Rr26Dg4OT9unu7iaLxRLud+DAgbjmYMbAJf483P79wNy5oeWBAaC4GLhyJbTucABffgkY8FKl5ubm8PLatWsxY8aMSfvk5uZiyZIl4z6HCEl84O69NxQqmy20Hgxqj33yCTBnTsKnEIvOzs7w8iOPPBJ1v9FtRz+HCOH5pGHFitDJ3dE2bABeeIFl+Fj89ddf4eXMzMyo+41uO/o5RAhP4H75BaiujvzdmTNATw/L8LHw+/3h5ZSUlKj7jT70jn4OEZL4wA0OAs8/H/rvaH19wNatoT8dDOi+++4LL//9999R9/P5fOM+hwhJfOB27QLa2kLLNhvw5pvaY999B1RUJHwKsRj9tbnLly9H3W/0N6Cmcii+WyQ2cLW1wMcfa+vvvAOUlwMvv6z9bs8eoLU1odOIxbJly8LLZ8+ejarP8PAwzp07F14vLCxUPq9kl7jA9fQAL72krZeUADt3hpYrKoCRL54EAkBZGXDrVsKmEouioqLwcktLCzo6Oibtc/z4cVy7di28vnr16oTMLakl5OxeMEi0dq12ctfpJBr72eLFi0SpqVqbbduUTiHek6Y+n4/sdnv4JG5paemE7f1+PxUUFITbz5s3j4LBYFxzkBO/0aqoCL0/G/HFF8CDD0a2WbwYeP99bf3AAeCbbxIynVjY7Xbs2LEjvH7s2DHs2rVr3GveBgYGUFZWhp9//jn8uzfeeAMWi4VlrklFeYQvXCBKSdFeuV55ZeL2Tz+ttc3IIPrtNyXTUPHqEAgEaMWKFRGfqS5ZsoQ++ugjOnXqFNXV1dF7771HeXl5EW02b96sYAvM+QqnNnA3bxLNn68FqKCA6Pbtifv09hJlZWl9Vq8mGh6Oeyqqdtb169dp1apVk158OTpsfr9fydhmDJzaQ+r27YDXG1pOTQ2d7E1NnbhPZiZw6FDo8nIAaGoC3n1X6bTikZGRgcbGRuzduxfZ2dl3bJefn4+qqiocOXJkSieK7zYWIoOeeY1TyX9/wKn/FE3ecAqICK2trbh48SL6+vpgtVrhcrmwfPlyLFy4UOlYQGK2QW/Gu0zDwCwWCwoLC+X8Whzka4KClQROsJLACVYSOMFKAidYSeAEKwmcYCWBE6wkcIKVBE6wksAJVhI4wepfV4scPttlisKw3f234H4gXe9pxMUM2wAg4ooXuTzJwMywDWPJIVWwksAJVhI4wYo1cN3d3aipqUF1dTWujNwjLkkNDAxg3759uHHjht5TiUlXVxcOHTqEmpoa9PX1sY3Leom52+2G2+3G1atXcfXq1Qm/lGJ0zc3NbCUfE8VmsyEYDCI9ne8vYfZD6oULF1BTU4Pc3FzuoZXp6OjA7Nmzk/rbWW63G2VlZfB4PKx36mQPXGFhIcrKyiJu+pJsfv/9d1y6dAmdnZ1oNeCNeKIxcleAtLQ0BAIBtnFZD6nt7e3o6urC4OAgli9fzjm0Uk899RQAoLGxMeKevsnk119/RUdHB/x+P4qLi9nGZQ3cwoULE/L9Tb1w7ijVFixYoMt7UDktIlhJ4AQrCZxgJYETrCRw4zFxoWG9JTxwSVlJ+YEHgMpKwPr/f54zZ4C33pq4T2UlUFWlrX/4IWCiv8iVSeTN5/SqpEyk6GZ+OhcaNuMNCRMWOD0rKRMp2lk6FxqWwEVJ70rKRAp3lo6FhiVwUdK7kjKR4p2lU6FhCVwUjFBJmSgBO0uHQsNmDJzyv1KPHj0aXs7IyMCLL744aZ8dO3aEr14IBAKora1VPa34JWmhYaNRHjjTVlJO0kLDRqM8cKaupJyEhYaNRnngTF1JOQkLDRuN8sCZtpJykhYaNhrlgTNtJeUkLTRsNMoDZ8pKyklcaNholAfOdJWUk7zQsNEoD5ypKikThd6fjXxR2OkEDh/WCtHdc09kATuvN1TgTtyZ6jPJRqikTKToLP0HH0R+pPXtt+O327cvst3XX8c/Npnzk4aEfJZaXl4e8fHWzp07Iz64H3Hr1i3atGlTRNvKykolc4h7Zxmg0LAELkp6V1IminNnGaTQsARuCvSspEwU587atk0LTmoqUVtbdP3q6ogsFq3v22/HPgeSwE1ZIBCgvXv3UnZ29h2Dlp+fT1VVVUret41mhp1lhm0YK6GXN9hsNmzfvh2vvvoqayVlYVws19NIJWUxQr4mKFhJ4AQrCZxgJYETrCRwgpUETrCSwAlWEjjBSgInWEngBCsJnGAlBXoNzAzbAEiB3qRhhm0YSw6pgpUETrCSwAlWEjjBivUOesFgEN9//z38fj/y8vKStsBtR0cHvF4vbt68CafTiZKSEr2nNGU3btxAXV0dZsyYAbfbjaVLl7KMy/oK5/V6MTAwAKvVipkzZ3IOrVR+fj7Wr1+PrKwsLF68WO/pxKS/vx+PPvoonn32Wfz5559s47IGrr+/Hw899BDWrVtnzLtcTgERobe3Fy6XS++pxCQrKwstLS04ePAgFi1axDYu6yHVbrcjNTUVVmvyv3Xs7u6G2+3Wexox++mnn7Bu3Tq4XC7U1tYiLy+PZVz2Ar0nTpyA1+vFvHnzOIdWrq2tDWvWrNF7GjHLy8vD6dOnYbPZkJubyzYua+BSUlJQWlrKOWTCPPPMM3pPIS5ZWVnYvHkz+7jJf2wTSUUCJ1hJ4AQrCZxgJYETrCRwgpUETrCSwAlWEjjBSgInWEngBCsJnGAlgROsJHCClQROsJLACVYSOMFKAidYSeAEKwmcYCWBE6wkcIKVBE6wksAJVhI4wUoCJ1hJ4AQrCZxgJYETrCRwgpUETrCSwAlWEjjBSgInWEngBCsJnGAlgROsJHCClWkL9Apjklc4wUoCJ1hJ4ASr/wHngomQYG4MtAAAAABJRU5ErkJggg==",
      "text/plain": [
       "<Figure size 192x192 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "max: ['x', 'o', ' ', 'o', 'x', ' ', ' ', ' ', ' '] [alpha,beta]=[-inf,inf] v=None\n",
      "min: ['x', 'o', 'x', 'o', 'x', ' ', ' ', ' ', ' '] [alpha,beta]=[-inf,inf] v=None\n",
      "max: ['x', 'o', 'x', 'o', 'x', 'o', ' ', ' ', ' '] [alpha,beta]=[-inf,inf] v=None\n",
      "min: ['x', 'o', 'x', 'o', 'x', 'o', 'x', ' ', ' '] [alpha,beta]=[-inf,inf] v=1\n",
      "     found terminal state. backtacking.\n",
      "max: ['x', 'o', 'x', 'o', 'x', 'o', ' ', ' ', ' '] (backtracked) [alpha,beta]=[-inf,inf] v=1\n",
      "min: ['x', 'o', 'x', 'o', 'x', 'o', ' ', 'x', ' '] [alpha,beta]=[1,inf] v=None\n",
      "max: ['x', 'o', 'x', 'o', 'x', 'o', 'o', 'x', ' '] [alpha,beta]=[1,inf] v=None\n",
      "min: ['x', 'o', 'x', 'o', 'x', 'o', 'o', 'x', 'x'] [alpha,beta]=[1,inf] v=1\n",
      "     found terminal state. backtacking.\n",
      "max: ['x', 'o', 'x', 'o', 'x', 'o', 'o', 'x', ' '] (backtracked) [alpha,beta]=[1,inf] v=1\n",
      "min: ['x', 'o', 'x', 'o', 'x', 'o', ' ', 'x', ' '] (backtracked) [alpha,beta]=[1,inf] v=1\n",
      "     v<=alpha (1<=1): pruning remaining subtree (actions). backtracking.\n",
      "max: ['x', 'o', 'x', 'o', 'x', 'o', ' ', ' ', ' '] (backtracked) [alpha,beta]=[1,inf] v=1\n",
      "min: ['x', 'o', 'x', 'o', 'x', 'o', ' ', ' ', 'x'] [alpha,beta]=[1,inf] v=1\n",
      "     found terminal state. backtacking.\n",
      "max: ['x', 'o', 'x', 'o', 'x', 'o', ' ', ' ', ' '] (backtracked) [alpha,beta]=[1,inf] v=1\n",
      "min: ['x', 'o', 'x', 'o', 'x', ' ', ' ', ' ', ' '] (backtracked) [alpha,beta]=[-inf,inf] v=1\n",
      "max: ['x', 'o', 'x', 'o', 'x', ' ', 'o', ' ', ' '] [alpha,beta]=[-inf,1] v=None\n",
      "min: ['x', 'o', 'x', 'o', 'x', 'x', 'o', ' ', ' '] [alpha,beta]=[-inf,1] v=None\n",
      "max: ['x', 'o', 'x', 'o', 'x', 'x', 'o', 'o', ' '] [alpha,beta]=[-inf,1] v=None\n",
      "min: ['x', 'o', 'x', 'o', 'x', 'x', 'o', 'o', 'x'] [alpha,beta]=[-inf,1] v=1\n",
      "     found terminal state. backtacking.\n",
      "max: ['x', 'o', 'x', 'o', 'x', 'x', 'o', 'o', ' '] (backtracked) [alpha,beta]=[-inf,1] v=1\n",
      "     v>=beta (1>=1): pruning remaining subtree (actions). backtracking.\n",
      "min: ['x', 'o', 'x', 'o', 'x', 'x', 'o', ' ', ' '] (backtracked) [alpha,beta]=[-inf,1] v=1\n",
      "max: ['x', 'o', 'x', 'o', 'x', 'x', 'o', ' ', 'o'] [alpha,beta]=[-inf,1] v=None\n",
      "min: ['x', 'o', 'x', 'o', 'x', 'x', 'o', 'x', 'o'] [alpha,beta]=[-inf,1] v=0\n",
      "     found terminal state. backtacking.\n",
      "max: ['x', 'o', 'x', 'o', 'x', 'x', 'o', ' ', 'o'] (backtracked) [alpha,beta]=[-inf,1] v=0\n",
      "min: ['x', 'o', 'x', 'o', 'x', 'x', 'o', ' ', ' '] (backtracked) [alpha,beta]=[-inf,1] v=0\n",
      "max: ['x', 'o', 'x', 'o', 'x', ' ', 'o', ' ', ' '] (backtracked) [alpha,beta]=[-inf,1] v=0\n",
      "min: ['x', 'o', 'x', 'o', 'x', ' ', 'o', 'x', ' '] [alpha,beta]=[0,1] v=None\n",
      "max: ['x', 'o', 'x', 'o', 'x', 'o', 'o', 'x', ' '] [alpha,beta]=[0,1] v=None\n",
      "min: ['x', 'o', 'x', 'o', 'x', 'o', 'o', 'x', 'x'] [alpha,beta]=[0,1] v=1\n",
      "     found terminal state. backtacking.\n",
      "max: ['x', 'o', 'x', 'o', 'x', 'o', 'o', 'x', ' '] (backtracked) [alpha,beta]=[0,1] v=1\n",
      "     v>=beta (1>=1): pruning remaining subtree (actions). backtracking.\n",
      "min: ['x', 'o', 'x', 'o', 'x', ' ', 'o', 'x', ' '] (backtracked) [alpha,beta]=[0,1] v=1\n",
      "max: ['x', 'o', 'x', 'o', 'x', ' ', 'o', 'x', 'o'] [alpha,beta]=[0,1] v=None\n",
      "min: ['x', 'o', 'x', 'o', 'x', 'x', 'o', 'x', 'o'] [alpha,beta]=[0,1] v=0\n",
      "     found terminal state. backtacking.\n",
      "max: ['x', 'o', 'x', 'o', 'x', ' ', 'o', 'x', 'o'] (backtracked) [alpha,beta]=[0,1] v=0\n",
      "min: ['x', 'o', 'x', 'o', 'x', ' ', 'o', 'x', ' '] (backtracked) [alpha,beta]=[0,1] v=0\n",
      "     v<=alpha (0<=0): pruning remaining subtree (actions). backtracking.\n",
      "max: ['x', 'o', 'x', 'o', 'x', ' ', 'o', ' ', ' '] (backtracked) [alpha,beta]=[0,1] v=0\n",
      "min: ['x', 'o', 'x', 'o', 'x', ' ', 'o', ' ', 'x'] [alpha,beta]=[0,1] v=1\n",
      "     found terminal state. backtacking.\n",
      "max: ['x', 'o', 'x', 'o', 'x', ' ', 'o', ' ', ' '] (backtracked) [alpha,beta]=[0,1] v=1\n",
      "     v>=beta (1>=1): pruning remaining subtree (actions). backtracking.\n",
      "min: ['x', 'o', 'x', 'o', 'x', ' ', ' ', ' ', ' '] (backtracked) [alpha,beta]=[-inf,1] v=1\n",
      "max: ['x', 'o', 'x', 'o', 'x', ' ', ' ', 'o', ' '] [alpha,beta]=[-inf,1] v=None\n",
      "min: ['x', 'o', 'x', 'o', 'x', 'x', ' ', 'o', ' '] [alpha,beta]=[-inf,1] v=None\n",
      "max: ['x', 'o', 'x', 'o', 'x', 'x', 'o', 'o', ' '] [alpha,beta]=[-inf,1] v=None\n",
      "min: ['x', 'o', 'x', 'o', 'x', 'x', 'o', 'o', 'x'] [alpha,beta]=[-inf,1] v=1\n",
      "     found terminal state. backtacking.\n",
      "max: ['x', 'o', 'x', 'o', 'x', 'x', 'o', 'o', ' '] (backtracked) [alpha,beta]=[-inf,1] v=1\n",
      "     v>=beta (1>=1): pruning remaining subtree (actions). backtracking.\n",
      "min: ['x', 'o', 'x', 'o', 'x', 'x', ' ', 'o', ' '] (backtracked) [alpha,beta]=[-inf,1] v=1\n",
      "max: ['x', 'o', 'x', 'o', 'x', 'x', ' ', 'o', 'o'] [alpha,beta]=[-inf,1] v=None\n",
      "min: ['x', 'o', 'x', 'o', 'x', 'x', 'x', 'o', 'o'] [alpha,beta]=[-inf,1] v=1\n",
      "     found terminal state. backtacking.\n",
      "max: ['x', 'o', 'x', 'o', 'x', 'x', ' ', 'o', 'o'] (backtracked) [alpha,beta]=[-inf,1] v=1\n",
      "     v>=beta (1>=1): pruning remaining subtree (actions). backtracking.\n",
      "min: ['x', 'o', 'x', 'o', 'x', 'x', ' ', 'o', ' '] (backtracked) [alpha,beta]=[-inf,1] v=1\n",
      "max: ['x', 'o', 'x', 'o', 'x', ' ', ' ', 'o', ' '] (backtracked) [alpha,beta]=[-inf,1] v=1\n",
      "     v>=beta (1>=1): pruning remaining subtree (actions). backtracking.\n",
      "min: ['x', 'o', 'x', 'o', 'x', ' ', ' ', ' ', ' '] (backtracked) [alpha,beta]=[-inf,1] v=1\n",
      "max: ['x', 'o', 'x', 'o', 'x', ' ', ' ', ' ', 'o'] [alpha,beta]=[-inf,1] v=None\n",
      "min: ['x', 'o', 'x', 'o', 'x', 'x', ' ', ' ', 'o'] [alpha,beta]=[-inf,1] v=None\n",
      "max: ['x', 'o', 'x', 'o', 'x', 'x', 'o', ' ', 'o'] [alpha,beta]=[-inf,1] v=None\n",
      "min: ['x', 'o', 'x', 'o', 'x', 'x', 'o', 'x', 'o'] [alpha,beta]=[-inf,1] v=0\n",
      "     found terminal state. backtacking.\n",
      "max: ['x', 'o', 'x', 'o', 'x', 'x', 'o', ' ', 'o'] (backtracked) [alpha,beta]=[-inf,1] v=0\n",
      "min: ['x', 'o', 'x', 'o', 'x', 'x', ' ', ' ', 'o'] (backtracked) [alpha,beta]=[-inf,1] v=0\n",
      "max: ['x', 'o', 'x', 'o', 'x', 'x', ' ', 'o', 'o'] [alpha,beta]=[-inf,0] v=None\n",
      "min: ['x', 'o', 'x', 'o', 'x', 'x', 'x', 'o', 'o'] [alpha,beta]=[-inf,0] v=1\n",
      "     found terminal state. backtacking.\n",
      "max: ['x', 'o', 'x', 'o', 'x', 'x', ' ', 'o', 'o'] (backtracked) [alpha,beta]=[-inf,0] v=1\n",
      "     v>=beta (1>=0): pruning remaining subtree (actions). backtracking.\n",
      "min: ['x', 'o', 'x', 'o', 'x', 'x', ' ', ' ', 'o'] (backtracked) [alpha,beta]=[-inf,0] v=1\n",
      "max: ['x', 'o', 'x', 'o', 'x', ' ', ' ', ' ', 'o'] (backtracked) [alpha,beta]=[-inf,1] v=0\n",
      "min: ['x', 'o', 'x', 'o', 'x', ' ', 'x', ' ', 'o'] [alpha,beta]=[0,1] v=1\n",
      "     found terminal state. backtacking.\n",
      "max: ['x', 'o', 'x', 'o', 'x', ' ', ' ', ' ', 'o'] (backtracked) [alpha,beta]=[0,1] v=1\n",
      "     v>=beta (1>=1): pruning remaining subtree (actions). backtracking.\n",
      "min: ['x', 'o', 'x', 'o', 'x', ' ', ' ', ' ', ' '] (backtracked) [alpha,beta]=[-inf,1] v=1\n",
      "max: ['x', 'o', ' ', 'o', 'x', ' ', ' ', ' ', ' '] (backtracked) [alpha,beta]=[-inf,inf] v=1\n",
      "min: ['x', 'o', ' ', 'o', 'x', 'x', ' ', ' ', ' '] [alpha,beta]=[1,inf] v=None\n",
      "max: ['x', 'o', 'o', 'o', 'x', 'x', ' ', ' ', ' '] [alpha,beta]=[1,inf] v=None\n",
      "min: ['x', 'o', 'o', 'o', 'x', 'x', 'x', ' ', ' '] [alpha,beta]=[1,inf] v=None\n",
      "max: ['x', 'o', 'o', 'o', 'x', 'x', 'x', 'o', ' '] [alpha,beta]=[1,inf] v=None\n",
      "min: ['x', 'o', 'o', 'o', 'x', 'x', 'x', 'o', 'x'] [alpha,beta]=[1,inf] v=1\n",
      "     found terminal state. backtacking.\n",
      "max: ['x', 'o', 'o', 'o', 'x', 'x', 'x', 'o', ' '] (backtracked) [alpha,beta]=[1,inf] v=1\n",
      "min: ['x', 'o', 'o', 'o', 'x', 'x', 'x', ' ', ' '] (backtracked) [alpha,beta]=[1,inf] v=1\n",
      "     v<=alpha (1<=1): pruning remaining subtree (actions). backtracking.\n",
      "max: ['x', 'o', 'o', 'o', 'x', 'x', ' ', ' ', ' '] (backtracked) [alpha,beta]=[1,inf] v=1\n",
      "min: ['x', 'o', 'o', 'o', 'x', 'x', ' ', 'x', ' '] [alpha,beta]=[1,inf] v=None\n",
      "max: ['x', 'o', 'o', 'o', 'x', 'x', 'o', 'x', ' '] [alpha,beta]=[1,inf] v=None\n",
      "min: ['x', 'o', 'o', 'o', 'x', 'x', 'o', 'x', 'x'] [alpha,beta]=[1,inf] v=1\n",
      "     found terminal state. backtacking.\n",
      "max: ['x', 'o', 'o', 'o', 'x', 'x', 'o', 'x', ' '] (backtracked) [alpha,beta]=[1,inf] v=1\n",
      "min: ['x', 'o', 'o', 'o', 'x', 'x', ' ', 'x', ' '] (backtracked) [alpha,beta]=[1,inf] v=1\n",
      "     v<=alpha (1<=1): pruning remaining subtree (actions). backtracking.\n",
      "max: ['x', 'o', 'o', 'o', 'x', 'x', ' ', ' ', ' '] (backtracked) [alpha,beta]=[1,inf] v=1\n",
      "min: ['x', 'o', 'o', 'o', 'x', 'x', ' ', ' ', 'x'] [alpha,beta]=[1,inf] v=1\n",
      "     found terminal state. backtacking.\n",
      "max: ['x', 'o', 'o', 'o', 'x', 'x', ' ', ' ', ' '] (backtracked) [alpha,beta]=[1,inf] v=1\n",
      "min: ['x', 'o', ' ', 'o', 'x', 'x', ' ', ' ', ' '] (backtracked) [alpha,beta]=[1,inf] v=1\n",
      "     v<=alpha (1<=1): pruning remaining subtree (actions). backtracking.\n",
      "max: ['x', 'o', ' ', 'o', 'x', ' ', ' ', ' ', ' '] (backtracked) [alpha,beta]=[1,inf] v=1\n",
      "min: ['x', 'o', ' ', 'o', 'x', ' ', 'x', ' ', ' '] [alpha,beta]=[1,inf] v=None\n",
      "max: ['x', 'o', 'o', 'o', 'x', ' ', 'x', ' ', ' '] [alpha,beta]=[1,inf] v=None\n",
      "min: ['x', 'o', 'o', 'o', 'x', 'x', 'x', ' ', ' '] [alpha,beta]=[1,inf] v=None\n",
      "max: ['x', 'o', 'o', 'o', 'x', 'x', 'x', 'o', ' '] [alpha,beta]=[1,inf] v=None\n",
      "min: ['x', 'o', 'o', 'o', 'x', 'x', 'x', 'o', 'x'] [alpha,beta]=[1,inf] v=1\n",
      "     found terminal state. backtacking.\n",
      "max: ['x', 'o', 'o', 'o', 'x', 'x', 'x', 'o', ' '] (backtracked) [alpha,beta]=[1,inf] v=1\n",
      "min: ['x', 'o', 'o', 'o', 'x', 'x', 'x', ' ', ' '] (backtracked) [alpha,beta]=[1,inf] v=1\n",
      "     v<=alpha (1<=1): pruning remaining subtree (actions). backtracking.\n",
      "max: ['x', 'o', 'o', 'o', 'x', ' ', 'x', ' ', ' '] (backtracked) [alpha,beta]=[1,inf] v=1\n",
      "min: ['x', 'o', 'o', 'o', 'x', ' ', 'x', 'x', ' '] [alpha,beta]=[1,inf] v=None\n",
      "max: ['x', 'o', 'o', 'o', 'x', 'o', 'x', 'x', ' '] [alpha,beta]=[1,inf] v=None\n",
      "min: ['x', 'o', 'o', 'o', 'x', 'o', 'x', 'x', 'x'] [alpha,beta]=[1,inf] v=1\n",
      "     found terminal state. backtacking.\n",
      "max: ['x', 'o', 'o', 'o', 'x', 'o', 'x', 'x', ' '] (backtracked) [alpha,beta]=[1,inf] v=1\n",
      "min: ['x', 'o', 'o', 'o', 'x', ' ', 'x', 'x', ' '] (backtracked) [alpha,beta]=[1,inf] v=1\n",
      "     v<=alpha (1<=1): pruning remaining subtree (actions). backtracking.\n",
      "max: ['x', 'o', 'o', 'o', 'x', ' ', 'x', ' ', ' '] (backtracked) [alpha,beta]=[1,inf] v=1\n",
      "min: ['x', 'o', 'o', 'o', 'x', ' ', 'x', ' ', 'x'] [alpha,beta]=[1,inf] v=1\n",
      "     found terminal state. backtacking.\n",
      "max: ['x', 'o', 'o', 'o', 'x', ' ', 'x', ' ', ' '] (backtracked) [alpha,beta]=[1,inf] v=1\n",
      "min: ['x', 'o', ' ', 'o', 'x', ' ', 'x', ' ', ' '] (backtracked) [alpha,beta]=[1,inf] v=1\n",
      "     v<=alpha (1<=1): pruning remaining subtree (actions). backtracking.\n",
      "max: ['x', 'o', ' ', 'o', 'x', ' ', ' ', ' ', ' '] (backtracked) [alpha,beta]=[1,inf] v=1\n",
      "min: ['x', 'o', ' ', 'o', 'x', ' ', ' ', 'x', ' '] [alpha,beta]=[1,inf] v=None\n",
      "max: ['x', 'o', 'o', 'o', 'x', ' ', ' ', 'x', ' '] [alpha,beta]=[1,inf] v=None\n",
      "min: ['x', 'o', 'o', 'o', 'x', 'x', ' ', 'x', ' '] [alpha,beta]=[1,inf] v=None\n",
      "max: ['x', 'o', 'o', 'o', 'x', 'x', 'o', 'x', ' '] [alpha,beta]=[1,inf] v=None\n",
      "min: ['x', 'o', 'o', 'o', 'x', 'x', 'o', 'x', 'x'] [alpha,beta]=[1,inf] v=1\n",
      "     found terminal state. backtacking.\n",
      "max: ['x', 'o', 'o', 'o', 'x', 'x', 'o', 'x', ' '] (backtracked) [alpha,beta]=[1,inf] v=1\n",
      "min: ['x', 'o', 'o', 'o', 'x', 'x', ' ', 'x', ' '] (backtracked) [alpha,beta]=[1,inf] v=1\n",
      "     v<=alpha (1<=1): pruning remaining subtree (actions). backtracking.\n",
      "max: ['x', 'o', 'o', 'o', 'x', ' ', ' ', 'x', ' '] (backtracked) [alpha,beta]=[1,inf] v=1\n",
      "min: ['x', 'o', 'o', 'o', 'x', ' ', 'x', 'x', ' '] [alpha,beta]=[1,inf] v=None\n",
      "max: ['x', 'o', 'o', 'o', 'x', 'o', 'x', 'x', ' '] [alpha,beta]=[1,inf] v=None\n",
      "min: ['x', 'o', 'o', 'o', 'x', 'o', 'x', 'x', 'x'] [alpha,beta]=[1,inf] v=1\n",
      "     found terminal state. backtacking.\n",
      "max: ['x', 'o', 'o', 'o', 'x', 'o', 'x', 'x', ' '] (backtracked) [alpha,beta]=[1,inf] v=1\n",
      "min: ['x', 'o', 'o', 'o', 'x', ' ', 'x', 'x', ' '] (backtracked) [alpha,beta]=[1,inf] v=1\n",
      "     v<=alpha (1<=1): pruning remaining subtree (actions). backtracking.\n",
      "max: ['x', 'o', 'o', 'o', 'x', ' ', ' ', 'x', ' '] (backtracked) [alpha,beta]=[1,inf] v=1\n",
      "min: ['x', 'o', 'o', 'o', 'x', ' ', ' ', 'x', 'x'] [alpha,beta]=[1,inf] v=1\n",
      "     found terminal state. backtacking.\n",
      "max: ['x', 'o', 'o', 'o', 'x', ' ', ' ', 'x', ' '] (backtracked) [alpha,beta]=[1,inf] v=1\n",
      "min: ['x', 'o', ' ', 'o', 'x', ' ', ' ', 'x', ' '] (backtracked) [alpha,beta]=[1,inf] v=1\n",
      "     v<=alpha (1<=1): pruning remaining subtree (actions). backtracking.\n",
      "max: ['x', 'o', ' ', 'o', 'x', ' ', ' ', ' ', ' '] (backtracked) [alpha,beta]=[1,inf] v=1\n",
      "min: ['x', 'o', ' ', 'o', 'x', ' ', ' ', ' ', 'x'] [alpha,beta]=[1,inf] v=1\n",
      "     found terminal state. backtacking.\n",
      "max: ['x', 'o', ' ', 'o', 'x', ' ', ' ', ' ', ' '] (backtracked) [alpha,beta]=[1,inf] v=1\n",
      "Number of nodes searched: 61\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "{'move': 2, 'value': 1}"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 7.28 ms, sys: 8.41 ms, total: 15.7 ms\n",
      "Wall time: 5.2 ms\n"
     ]
    }
   ],
   "source": [
    "DEBUG = 2 # show more debugging info\n",
    "\n",
    "board = empty_board() \n",
    "board[0] = 'x'\n",
    "board[1] = 'o'\n",
    "board[3] = 'o'\n",
    "board[4] = 'x'\n",
    "\n",
    "print(\"Board:\")\n",
    "show_board(board)\n",
    "\n",
    "print()\n",
    "%time display(alpha_beta_search(board))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The code does not pick the the shortest path to a win! Discounting could help.\n",
    "\n",
    "### x can draw if it chooses 7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Board:\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAJwAAACcCAYAAACKuMJNAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjguMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy81sbWrAAAACXBIWXMAAAYnAAAGJwFNVNjHAAAMP0lEQVR4nO3df0xT5xoH8G+BgoG1jt1iCUE6iaAo21R0NLopQfSfOea0yRwjZol/LG7LNm90cb9MzP7Ysh83xoVl12Uuc2EkumQJYhwTkGtcoE4h022sAw1sThgIMx1WWgvP/aO3p9TJD+npc057n09C7I/37fucvF97DqeHvgYiIgjBJEHrAsT/FwmcYBW3gTvU0q11CRGLh224VRwHrkfrEiIWD9twq7gNnNAnCZxgJYETrJI4B3O73WhsbAQArFy5ElarlXN41fT39+PUqVOwWCwoKSnRupwZcblccLlc8Hq9WLNmDebMmcMyLus7XHt7O0pKSrBhwwacPXuWc2hVzZkzB2VlZVqXEZEFCxagvLwcDz/8MC5evMg2Lmvg3G43Zs+eDaPRCL/fzzm0uA0iwtmzZ1FYWMg2JmvgzGYz3G43/H4/kpJY9+biFkSE+vp6LFu2DCaTiW1c1llfunQpmpqaAAB2u51zaFW53W40NTXh6tWryMjIwOLFi7Uu6Y45nU5cvnwZfr8fbrcbCxcuZBmXNXBmsxkbN27kHDIqzGYzNm3apHUZEbHb7Zr8p5fTIoKVBE6wksAJVhI4wUoCJ1ipG7jBQSA7GzAYAj8PPQSMjk7dr7Iy1CctDejoULUsNdy4cQMHDhxAeXk55s2bh9TUVJhMJsyfPx9btmxBTU0NRqezrZz0OB+ktqYmooQEIiDws2fP5O0PHQq1BYj+/W9Vylj7frMqr0NEVFtbS9nZ2QRg0p9FixZRa2urauOqsg06mY8g9QNHRPTqq6GCExOJTp26fbuuLiKTKdR20ybVSlArcAcPHqTExMSwYFksFlq1ahXZ7XYym81hz6WmptI333yjytiq/afRwXwERSdwN28SFReHCp87l2ho6O9tHnww1CY7m2hwULUS1JistrY2MhqNSpisVisdOXKE/H6/0mZkZISqqqooLS1NaXfPPffQlStXIh5ftcDpYD6CohM4IqJLl4jM5tAGbN4c/vzu3aHnEhKImtXbBRKpM1nFxcVKiNLT06mjo2PCto2NjZSUlKS0r6ysjHh8NQ8LtJ6PoOgFjoiouvr2xwONjeHHFa+9pvrQkU6W0+kM21V+9NFHU/Z56aWXlPbJycnU19cXUQ2qBo5I0/kIim7giIi2bg1tSGpq4PghKyv0mN0eeDtXWaSTtXv37rB3t5GRkSn79PT0kMFgUPp98sknEdWgeuCINJuPoOifh6uqAubPD9z2eICSEuDKlcB9sxn44gtAh5cqtba2KrfXrVuHlJSUKfvk5ORgyZIlt30N3dB4PqIfuLvuCmyE0Ri4PzYWeu7DD4F586Jewkx0dXUpt++///5p9xvfdvxr6IbG88HzScOKFYGTieNt3Ag89RTL8DPx559/KrczMjKm3W982/GvoSsazgdP4H78EaipCX/s22+Bvj6W4WfC6/Uqt5OTk6fdb/yud/xr6IqG8xH9wI2MAE8+Gfh3vIEBYOvWwKGqDt19993K7b/++mva/dxu921fQzc0no/oB27XLuDChcBtoxHYuzf03IkTwPvvR72EmRj/Z3OXLl2adr/xfwF1J7tiNlrPR9R+/yUiqqsLP+/zzjuBx7dvDz2WnEx07pzqQ0d6SqGyslI5vVFcXDytPn6/nywWi9Jv7969EdWg+mkRDecjKHqB6+0lysgIbUhZGdHYWOA5j4do8eLQcwsWEA0Pqzp8pJP18ccfh534/eWXX6bsc/To0bA+J0+ejKgGVQOn8XwERSdwY2NE69aFNsBiIbr1s8Xz54lmzQq12bZN1RIinSy3200mk0kJT3l5+aTtvV4vFRYWKu3z8/NpLDihM6Ra4HQwH0HRCdy774a/dR89evt2+/eHt/vyS9VKUGOy9uzZE/aOtXPnzrAP7oOuX79OmzdvDmv7+eefRzy+aoHTwXwEqR+4c+cCxwHBop97bvL2jzwSapueTvTrr6qUocZk+Xw+WrFiRViQlixZQh988AE1NDRQfX09vf3225SbmxvWxuFwqLAFKgVOJ/MRpG7ghocD+/9gwYWFRDduTN6nv58oMzPUZ/VqotHRiEtR691haGiIVq5cGRaoyX4cDgd5vV5Vxo54G3Q0H0HqBm7btlChs2YRXbgwvX719UQGQ6jvm29GXIqaB9w+n4/27dtHWVlZEwYtLy+PqqurIz5uGy/ibdDRfAQZiHR65jVCZf/6Dxr+uUbV1yQitLW14fz58xgYGEBCQgKsViuWL1+OgoICVccCorMNWtPfZRo6ZjAYUFRUhKKiIq1LiVnyZ4KClQROsJLACVYSOMFKAidYSeAEKwmcYCWBE6wkcIKVBE6wksAJVhI4wepvV4scaumOi4Vhewavw/aPNK3LiEg8bAOAsCte5PIkHYuHbbiV7FIFKwmcYCWBE6xYA9fT04O6ujrU1NTgSvA7yWKUx+PB/v37ce3aNa1LmZHu7m589tlnqKurw8DAANu4rJeY22w22Gw29Pb2ore3F1lZWZzDq6q1tZVtycdoMRqNGBsbQ1oa32/C7LvUc+fOoa6uDjk5OdxDq6azsxNz5869o6/x0hubzYaKigrY7XbWb+pkD1xRUREqKipw5swZ7qFV89tvv+HixYvo6upCW1ub1uXMiMFgAACkpqbC5/Oxjcu6S+3o6EB3dzdGRkawfPlyzqFVVVpaCgBobm4O+07fWPLzzz+js7MTXq8XJSUlbOOyBq6goCAqf7+pFc6JUtvChQs1OQaV0yKClQROsJLACVYSOMFKAidYSeCmKSZXhNYj1b74S2dkRWh9kne4KXz66ad4/PHHcfnyZeUxi8WCVatWwW63w2w2K4//9NNPKC0txYkTJ7QoNSZI4CbR3t6OZ555RtlVWq1WHDlyBH19fTh9+jRaWlrQ39+Pqqoq5QNwj8eDLVu2oLe3V8vSdUsCN4nt27fj5s2bAID09HQ0NzfD4XAgMTFRaZOSkoJnn30WtbW1SPrfso9DQ0N4+eWXNalZ7yRwEzhz5gycTqdy/6233pr0o6DS0lI8//zzyv3Dhw/jjz/+iGqNsUgCN4GvvvpKuZ2eno6nn356yj47duxQrsLw+Xw4duxYtMqLWRK4CcTtitAak8BNIG5XhNaYBG4Ccb0itIYkcBOI6xWhNSSBm0DcrgitMQncBOJ2RWiNSeAmsGzZMuV2S0vLtPqMjo6G/XGQrFjzdxK4CaxZE/oSGafTic7Ozin7HD9+HFevXlXur169Oiq1xTIJ3ASeeOIJmEwm5f7OnTsnbe/z+fDKK68o9/Pz88NCKwIkcBMwmUzYsWOHcr+2tha7du267TVvHo8HFRUV+OGHH5TH3njjDeVTBxEiqwlO4vXXX8fx48fx3XffAQDee+89NDQ0YNu2bSgoKMDo6Cja29tx4MCBsF8sHA4HKisrtSpb37S+IC9aZEVofZJd6hSClyXt27dv0i/fycvLQ3V1NQ4fPhzT3zkSbbJLnQaj0YgXX3wRL7zwAuuK0PFIAncHZEXoyMkuVbCSwAlWEjjBSgInWEngBCsJnGAlgROsJHCClQROsJLACVYSOMFKFujVsXjYBkAW6I0Z8bANt5JdqmAlgROsJHCClQROsGK94ndsbAwnT56E1+tFbm5uzC5w29nZCZfLheHhYVgsFpSVlWld0h27du0a6uvrkZKSApvNhqVLl7KMy/oO53K54PF4kJCQgNmzZ3MOraq8vDxs2LABmZmZuO+++7QuZ0YGBwfxwAMP4LHHHsPvv//ONi5r4AYHB3Hvvfdi/fr1Mf/tkESE/v5+WK1WrUuZkczMTDidThw8eBCLFi1iG5d1l2oymTBr1iwkJMT+oWNPTw9sNpvWZczY999/j/Xr18NqteLYsWPIzc1lGZd9gd6vv/4aLpcL+fn5nEOr7sKFC1i7dq3WZcxYbm4uTp8+DaPRiJycHLZxWQOXnJyM8vJyziGj5tFHH9W6hIhkZmbC4XCwjxv7+zYRUyRwgpUETrCSwAlWEjjBSgInWEngBCsJnGAlgROsJHCClQROsJLACVYSOMFKAidYSeAEKwmcYCWBE6wkcIKVBE6wksAJVhI4wUoCJ1hJ4AQrCZxgJYETrCRwgpUETrCSwAlWEjjBSgInWEngBCsJnGAlgROsJHCClQROsJLACVYSOMFKAidYxe0CvUKf5B1OsJLACVYSOMHqv5LF5/1WsPcyAAAAAElFTkSuQmCC",
      "text/plain": [
       "<Figure size 192x192 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Number of nodes searched: 101\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "{'move': 7, 'value': 0}"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 18.5 ms, sys: 0 ns, total: 18.5 ms\n",
      "Wall time: 6.11 ms\n"
     ]
    }
   ],
   "source": [
    "DEBUG = 1\n",
    "\n",
    "board = empty_board() \n",
    "board[0] = 'x'\n",
    "board[1] = 'o'\n",
    "board[2] = 'x'\n",
    "board[4] = 'o'\n",
    "\n",
    "print(\"Board:\")\n",
    "show_board(board)\n",
    "\n",
    "print()\n",
    "%time display(alpha_beta_search(board))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### o is about to win no matter what x does\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Board:\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAJwAAACcCAYAAACKuMJNAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjguMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy81sbWrAAAACXBIWXMAAAYnAAAGJwFNVNjHAAAMSUlEQVR4nO3df0wb5R8H8DcdZQi2GxNWJIwKGfvJdBubNFMHOuSfIS5sf2idi8bMxCyKfLMl02WL08wYla/LdP6YumVDJPFHlkyIogMRXQZmwygabIAFnG4ExrbUwWgtPN8/7kuvRQYtvX7uev28EuJdea7P8+zetsdde58YIYQAY0QMag+ARRcOHCOl28AdO92t9hBCpoc5jKfjwPWoPYSQ6WEO4+k2cEybOHCMFAeOkYql7MzpdKK+vh4AsGbNGlgsFsruFdPX14empiYkJyejoKBA7eFMi8PhgMPhgMvlQn5+PubOnUvSL+kr3E8//YSCggIUFxfjzJkzlF0rau7cuSgsLFR7GCFZuHAhSkpKcM8996Crq4usX9LAOZ1OzJo1C0ajER6Ph7JrNgEhBM6cOYOcnByyPkkDZzab4XQ64fF4EBtL+m7OxhFCoK6uDitXroTJZCLrl3Svr1ixAg0NDQAAm81G2bWinE4nGhoacOnSJaSkpGDp0qVqDyloLS0t+PPPP+HxeOB0OrFo0SKSfkkDZzabsWHDBsouw8JsNqO0tFTtYYTEZrOp8j89nxZhpDhwjBQHjpHiwDFSHDhGKuyBu379Og4dOoSSkhJkZmYiISEBJpMJ8+fPx0MPPYTq6mqMjIyEexgh08s8VCfC6MSJEyI9PV0AmPRnyZIlorm5WdG+11U0KvZcas1DyTloRdgCd/jwYTFjxgy/HZKcnCzuuusuYbPZhNls9vtdQkKC+PrrrxXrX6mdpeY8OHABam1tFUaj0bsTLBaL+PTTT4XH4/G2GR4eFgcPHhSJiYnednPmzBEXLlxQZAxK7Cy158GBC1BeXp73Hz8pKUm0t7ffsG19fb2IjY31tt+8ebMiY1BiZ6k9Dw5cAFpaWvzeYt59990pt3n22We97ePi4kRvb2/I4wh1Z2lhHnoMnOJ/pR4/fty7nJSUhMcee2zKbcrLyxETEwMAcLvdqK2tVXpYQdPLPLRG8cA1Nzd7l++//37MnDlzym0yMjKwfPnyCZ9DLXqZh9YoHrjOzk7v8u233x7wdr5tfZ9DLXqZh9YoHrgrV654l1NSUgLezret73OoRS/z0BrFA+dyubzLcXFxAW/n+5bl+xxq0cs8tEbxwM2ePdu7/Pfffwe8ndPpnPA51KKXeWiN4oHz/brZuXPnAt7O95tDwbyFhYte5qE1igdu5cqV3uXTp08HtM3IyAh+/PFH73pubq7SwwqaXuahNYoHLj8/37vc0tKCjo6OKbf58ssvcenSJe/62rVrlR5W0PQyD81R+kyy0+kUJpPJe8a9pKRk0vYul0vk5OR42y9YsECMjo6GPI5Qz9JrYR58pSEAJpMJ5eXl3vUTJ05gx44dE35WbGhoCHa7Hb/++qv3sd27d3vP1qtJL/PQnHCk2O12i9WrV/tdi1y+fLl48803xcmTJ0VdXZ145ZVXRFZWll+bTZs2KTYGJV4d1J6HHl/hwvZ5uMuXL4s1a9ZM+aFF353kcrkU61+pnaXmPPQYuLB9xDwpKQmNjY3Yv38/0tLSbtguOzsbVVVV+OSTT4I6wUpFL/PQihghwn/bfCEEWltb8csvv6C/vx8GgwEWiwWrVq3C4sWLw9Jn4X+/w8n/5E/dMAjU8wjHHNRGcquHmJgY5ObmRvx5Kb3MQ038NUFGigPHSHHgGCkOHCPFgWOkOHCMFAeOkeLAMVIcOEaKA8dIceAYKQ4cI/WvT4scO92ti8KwPQODsN6SqPYwQqKHOQDw+8QLyceT1KCHj/boYQ7j8VsqI8WBY6Q4cIwUaeB6enpQU1OD6upqXLhwgbJrxQ0NDeHAgQO4evWq2kOZlu7ubhw9ehQ1NTXo7+8n65e0mqDVaoXVasXFixdx8eLFSb+UonXNzc1kJR/DxWg0YnR0FImJdH8Jk7+lnj17FjU1NcjIyKDuWjEdHR2YN29eRH87y2q1wm63w2azkd6pkzxwubm5sNvtfjd9iTTnz59HV1cXOjs70draqvZwpmXsrgAJCQlwu91k/ZK+pba3t6O7uxvDw8NYtWoVZdeKuu+++wAAjY2Nfvf0jSS///47Ojo64HK5UFBQQNYvaeAWL14ctu+hqoFyRylt0aJFqhyD8mkRRooDx0hx4BgpDhwjxYGbyMAAkJ4OxMRIP3ffDQRSfHfzZnmbxESgvT38Y40wXBF6IrfcAlRWAob///OcOgW8+OLk21RWAlVV8vobbwA6+otcMeG8+VzEV4R+/nkhAOlnxgwhmpombtfZKYTJJLctLQ29b6HPGxJyRejJ/POPEHl5cpDmzRPi8uV/t7nzTrlNeroQAwOh9y04cAFTu5KyEArurHPnhDCb5UBt3Oj/+5075d8ZDEI0KhcSDlyA1K6kLITCO6uqSg4VIMR770mP19dLIRt7fNcu5foUHLiAaKGSshBh2FlbtsjBSkiQjufS0uTHbDbp7VVBegwcV4QO1MGDwPz50vLQEFBQAIx9iNRsBj7+GIglvTQdkbgidKBuvlkKldEorY+Oyr97+20gM1OdcUUYrggdjNWrpZO7vjZsAB55RJXhRCKuCB2M334Dqqv9Hzt1CujtVWc8EYgrQgdqeBh4+GHpv776+4EtW6Q/HdiUuCJ0oHbsANrapGWjEdi7V/7dN98AFRXqjCvCcEXoQNTWAm+9Ja/v2wfs2QM89ZT82K5dQIR+v4ESV4SeSm8v8Pjj8nphIbB9u7RcUQEsXSotu92A3Q4MDtKPMYJwRejJCCEdn419UTg5GTh2TPr4EQDcdJP0R0R8vLTucABlZeqMNVIofSZZC5WUhVDoLP1rr/lf0vrii4nbHTjg3+6zz0LvW+jzSkNYrqXu2bPH7/LW9u3b/S7cjxkcHBQbN270a1tZWanIGELeWWfPChEXJ4do27bJ269fL7dNShLijz9C619w4AKmdiVlIULcWdeuCbFwoRygnBwhrl+ffJu+PiFSU+Vt1q4VYmRk+mMQHLigRHRF6CeekIMTHy9EW1tg29XVCRETI2/70kvTH4PgwAXN7XaL/fv3i7S0tBsGLTs7W1RVVSly3OZLDztLD3MYL6wfbzAajSgrK8MzzzxDXhGaaRNXhGak+GuCjBQHjpHiwDFSHDhGigPHSHHgGCkOHCPFgWOkOHCMFAeOkeLAMVJcoFfD9DAHgAv0Rgw9zGE8fktlpDhwjBQHjpHiwDFSpHfQGx0dxbfffguXy4WsrKyILXDb0dEBh8OBa9euITk5GYWFhWoPKWhXr15FXV0dZs6cCavVihUrVpD0S/oK53A4MDQ0BIPBgFmzZlF2rajs7GwUFxcjNTUVy5YtU3s40zIwMIA77rgDDz74IP766y+yfkkDNzAwgNtuuw1FRUXavMtlEIQQ6Ovrg8ViUXso05KamoqWlhYcPnwYS5YsIeuX9C3VZDIhPj4eBkPkHzr29PTAarWqPYxp+/nnn1FUVASLxYLa2lpkZWWR9EteoPerr76Cw+HAggULKLtWXFtbG9atW6f2MKYtKysLP/zwA4xGIzIyMsj6JQ1cXFwcSkpKKLsMmwceeEDtIYQkNTUVmzZtIu838t/bWEThwDFSHDhGigPHSHHg9EyDla05cHqmwcrWHDi9u/deYOdOeX3fPuD77ydu29UFbNsmr5eWAk8+qehwOHDRYO9eIC9PWh4ZkWqDjS8v5fFIt/0fK+aSng68/77iQ+HARYPYWOn2/maztH7+PLB1q3+b3buBsVoZBgPw0UfAnDmKD4UDFy0yM4F33pHXP/8cOHRIWm5oAF59Vf7dc88B+eH5LgUHLprY7VKhkzHl5dLx3KOPyvVfbTbghRfCNgQOXLRRubI1By7aqFzZmgMXjVSsbM2Bi0YqVrbmwEUblStbc+CijcqVrTlw0UQDla05cNFCI5WtOXDRQEOVrTlw0aCiQjo+G3PkCHDrrf5tli3zv7z14YfS5S+FceD0rrVVOi4bs20bUFw8cdunnwbWr5fXt26VLvQriAOnZ4OD0vGY2y2t5+QAr78++TZHjgCpqdLylSvSCWLfqxEh4sDpWVmZdDwGSMdnvsdpN5KSAhw9Kh/fNTUBL7+s2JBIvwjNiH3wgfQTrKIiRV/VfPErHCPFgWOkOHCMFAeOkeLAMVIcOEaKA8dIceAYKQ4cI8WBY6Q4cIwUB46R4sAxUrot0Mu0iV/hGCkOHCPFgWOk/gcEbq4OuI+N9QAAAABJRU5ErkJggg==",
      "text/plain": [
       "<Figure size 192x192 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Number of nodes searched: 15\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "{'move': 2, 'value': -1}"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 8.66 ms, sys: 1.28 ms, total: 9.94 ms\n",
      "Wall time: 3.27 ms\n"
     ]
    }
   ],
   "source": [
    "board = empty_board() \n",
    "board[0] = 'o'\n",
    "board[1] = 'o'\n",
    "board[3] = 'o'\n",
    "board[4] = 'x'\n",
    "board[8] = 'x'\n",
    "\n",
    "print(\"Board:\")\n",
    "show_board(board)\n",
    "\n",
    "print()\n",
    "%time display(alpha_beta_search(board))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Empty board: Only a draw an be guaranteed"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Board:\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAJwAAACcCAYAAACKuMJNAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjguMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy81sbWrAAAACXBIWXMAAAYnAAAGJwFNVNjHAAAFSUlEQVR4nO3dT0tUexzH8Y/iWBiOi2vOIOSJgUrLKLPFEIRDDa7MIlr5MO4DuYseQFCbnsAECjfrSpCGJeHCDpMwQ38EdUAOXWli8Nzd5V7v3TSOn5PT+7USN9/vYd7Ob5zNryOO41iASWfSC+DnQnCwatvgHr2sJL3CgbXDM+zXxsFVk17hwNrhGfZr2+DwYyI4WBEcrLqcw6Io0tOnTyVJ165dUyaTcY5vmc3NTS0sLKi/v1+FQiHpdZoShqHCMFS9XtfExIQGBgYsc63vcCsrKyoUCpqamtLy8rJzdEsNDAyoWCwmvcaBnDt3TtPT07p+/brW19dtc63BRVGkvr4+pVIpNRoN52j8jziOtby8rNHRUdtMa3DpdFpRFKnRaKiry3qaY584jjU3N6crV66ot7fXNtf6qo+NjWl+fl6SlM/nnaNbKooizc/Pa3t7WydPntSFCxeSXum7LS0t6ePHj2o0GoqiSMPDw5a51uDS6bTu3LnjHHko0um07t69m/QaB5LP5xP5o+drEVgRHKwIDlYEByuCgxXBwYrgYEVwsCI4WBEcrAgOVgQHK4KDFcHBiuBgRXCwIjhYERysCA5WBAcrgoMVwcGK4GBFcLAiOFgRHKwIDlYEByuCgxXBwYrgYEVwsCI4WBEcrAgOVgQHK4KDFcHBiuBg1RHHcfzPXzx6WWmLi2GrtT8V/HIi6TUOpB2eQZJ+/3Xi75//E1y7KP72x78e9Chqh2fYjyMVVgQHK4KDlTW4arWqUqmkx48f6/Pnz87RLbe7u6v79+9rZ2cn6VWaUqlU9PDhQ5VKJW1tbdnmWm8TDIJAQRBoY2NDGxsbGhwcdI5vqcXFRduVj4cllUppb29PJ074/hO2H6mvX79WqVTS0NCQe3TLlMtlnTp1St3d3Umv0rQgCDQzM6N8Pq/FxUXbXHtw4+PjmpmZ0atXr9yjW+bDhw9aX1/X+/fv9ebNm6TXaUpHR4ckqaenR9++fbPNtR6pa2trqlQq+vr1q65eveoc3VI3btyQJD1//lyXL19OdpkmvXv3TuVyWfV6XYVCwTbXGtzIyIhGRkacIw+V84VqteHh4UQ+g/K1CKwIDlYEByuCgxXBwYrgYEVwsCI4WBEcrAgOVgQHK4KDFcHBiuBgRXCwIjhYERysCA5WBAcrgoMVwcGK4GBFcLAiOFgRHKwIDlYEByuCgxXBwYrgYEVwsCI4WBEcrAgOVgQHK4KDFcHBiuBgxQW9P7B2eAaJC3qPjHZ4hv04UmFFcLAiOFgRHKysl7vt7e3p2bNnqtfryuVyR/aC23K5rDAM9eXLF/X396tYLCa90nfb2dnR3Nycjh07piAINDY2ZplrfYcLw1C7u7vq7OxUX1+fc3RLnTlzRlNTU8pms7p48WLS6zSlVqvp0qVLun37tj59+mSbaw2uVqvp9OnTmpyctN5CfBjiONbm5qYymUzSqzQlm81qaWlJDx480Pnz521zrUdqb2+vjh8/rs7Oo//RsVqtKgiCpNdo2tu3bzU5OalMJqMnT54ol8tZ5tov6J2dnVUYhjp79qxzdMutrq7q5s2bSa/RtFwupxcvXiiVSmloaMg21xpcd3e3pqennSMPza1bt5Je4UCy2azu3btnn3v0zzYcKQQHK4KDFcHBiuBgRXCwIjhYERysCA5WBAcrgoMVwcGK4GBFcLAiOFgRHKwIDlYEByuCgxXBwYrgYEVwsCI4WBEcrAgOVgQHK4KDFcHBiuBgRXCwIjhYERysCA5WBAcrgoMVwcGK4GBFcLBq2wt68WPiHQ5WBAcrgoPVX+CrRo0sHKjjAAAAAElFTkSuQmCC",
      "text/plain": [
       "<Figure size 192x192 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Number of nodes searched: 18297\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "{'move': 0, 'value': 0}"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 720 ms, sys: 188 ms, total: 908 ms\n",
      "Wall time: 660 ms\n"
     ]
    }
   ],
   "source": [
    "board = empty_board() \n",
    "\n",
    "print(\"Board:\")\n",
    "show_board(board)\n",
    "\n",
    "\n",
    "print()\n",
    "%time display(alpha_beta_search(board))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Note:** Alpha-Beta search expands fewer nodes and is **much faster** than minimax search. \n",
    "\n",
    "## Move ordering\n",
    "\n",
    "Smart move reordering can make alpha-beta pruning more effective. I think the center `[4]` and corners `[0, 2, 6, 8]` are good. I implement move reordering in the `actions()`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAJwAAACcCAYAAACKuMJNAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjguMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy81sbWrAAAACXBIWXMAAAYnAAAGJwFNVNjHAAAFSUlEQVR4nO3dT0tUexzH8Y/iWBiOi2vOIOSJgUrLKLPFEIRDDa7MIlr5MO4DuYseQFCbnsAECjfrSpCGJeHCDpMwQ38EdUAOXWli8Nzd5V7v3TSOn5PT+7USN9/vYd7Ob5zNryOO41iASWfSC+DnQnCwatvgHr2sJL3CgbXDM+zXxsFVk17hwNrhGfZr2+DwYyI4WBEcrLqcw6Io0tOnTyVJ165dUyaTcY5vmc3NTS0sLKi/v1+FQiHpdZoShqHCMFS9XtfExIQGBgYsc63vcCsrKyoUCpqamtLy8rJzdEsNDAyoWCwmvcaBnDt3TtPT07p+/brW19dtc63BRVGkvr4+pVIpNRoN52j8jziOtby8rNHRUdtMa3DpdFpRFKnRaKiry3qaY584jjU3N6crV66ot7fXNtf6qo+NjWl+fl6SlM/nnaNbKooizc/Pa3t7WydPntSFCxeSXum7LS0t6ePHj2o0GoqiSMPDw5a51uDS6bTu3LnjHHko0um07t69m/QaB5LP5xP5o+drEVgRHKwIDlYEByuCgxXBwYrgYEVwsCI4WBEcrAgOVgQHK4KDFcHBiuBgRXCwIjhYERysCA5WBAcrgoMVwcGK4GBFcLAiOFgRHKwIDlYEByuCgxXBwYrgYEVwsCI4WBEcrAgOVgQHK4KDFcHBiuBg1RHHcfzPXzx6WWmLi2GrtT8V/HIi6TUOpB2eQZJ+/3Xi75//E1y7KP72x78e9Chqh2fYjyMVVgQHK4KDlTW4arWqUqmkx48f6/Pnz87RLbe7u6v79+9rZ2cn6VWaUqlU9PDhQ5VKJW1tbdnmWm8TDIJAQRBoY2NDGxsbGhwcdI5vqcXFRduVj4cllUppb29PJ074/hO2H6mvX79WqVTS0NCQe3TLlMtlnTp1St3d3Umv0rQgCDQzM6N8Pq/FxUXbXHtw4+PjmpmZ0atXr9yjW+bDhw9aX1/X+/fv9ebNm6TXaUpHR4ckqaenR9++fbPNtR6pa2trqlQq+vr1q65eveoc3VI3btyQJD1//lyXL19OdpkmvXv3TuVyWfV6XYVCwTbXGtzIyIhGRkacIw+V84VqteHh4UQ+g/K1CKwIDlYEByuCgxXBwYrgYEVwsCI4WBEcrAgOVgQHK4KDFcHBiuBgRXCwIjhYERysCA5WBAcrgoMVwcGK4GBFcLAiOFgRHKwIDlYEByuCgxXBwYrgYEVwsCI4WBEcrAgOVgQHK4KDFcHBiuBgxQW9P7B2eAaJC3qPjHZ4hv04UmFFcLAiOFgRHKysl7vt7e3p2bNnqtfryuVyR/aC23K5rDAM9eXLF/X396tYLCa90nfb2dnR3Nycjh07piAINDY2ZplrfYcLw1C7u7vq7OxUX1+fc3RLnTlzRlNTU8pms7p48WLS6zSlVqvp0qVLun37tj59+mSbaw2uVqvp9OnTmpyctN5CfBjiONbm5qYymUzSqzQlm81qaWlJDx480Pnz521zrUdqb2+vjh8/rs7Oo//RsVqtKgiCpNdo2tu3bzU5OalMJqMnT54ol8tZ5tov6J2dnVUYhjp79qxzdMutrq7q5s2bSa/RtFwupxcvXiiVSmloaMg21xpcd3e3pqennSMPza1bt5Je4UCy2azu3btnn3v0zzYcKQQHK4KDFcHBiuBgRXCwIjhYERysCA5WBAcrgoMVwcGK4GBFcLAiOFgRHKwIDlYEByuCgxXBwYrgYEVwsCI4WBEcrAgOVgQHK4KDFcHBiuBgRXCwIjhYERysCA5WBAcrgoMVwcGK4GBFcLBq2wt68WPiHQ5WBAcrgoPVX+CrRo0sHKjjAAAAAElFTkSuQmCC",
      "text/plain": [
       "<Figure size 192x192 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[4, 8, 6, 2, 0, 7, 5, 3, 1]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "def actions(board):\n",
    "    \"\"\"return possible actions as a vector ot indices\"\"\"\n",
    "    actions = np.where(np.array(board) == ' ')[0].tolist()\n",
    "\n",
    "    priority = [1,0,1,\n",
    "                0,2,0,\n",
    "                1,0,1]\n",
    "    priority = [priority[i] for i in actions]\n",
    "    \n",
    "    actions =[a for _,a in sorted(zip(priority,actions), reverse=True)]\n",
    "    \n",
    "    return actions\n",
    "\n",
    "board = empty_board()   \n",
    "show_board(board)\n",
    "actions(board)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Empty board: Only a draw an be guaranteed"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Board:\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAJwAAACcCAYAAACKuMJNAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjguMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy81sbWrAAAACXBIWXMAAAYnAAAGJwFNVNjHAAAFSUlEQVR4nO3dT0tUexzH8Y/iWBiOi2vOIOSJgUrLKLPFEIRDDa7MIlr5MO4DuYseQFCbnsAECjfrSpCGJeHCDpMwQ38EdUAOXWli8Nzd5V7v3TSOn5PT+7USN9/vYd7Ob5zNryOO41iASWfSC+DnQnCwatvgHr2sJL3CgbXDM+zXxsFVk17hwNrhGfZr2+DwYyI4WBEcrLqcw6Io0tOnTyVJ165dUyaTcY5vmc3NTS0sLKi/v1+FQiHpdZoShqHCMFS9XtfExIQGBgYsc63vcCsrKyoUCpqamtLy8rJzdEsNDAyoWCwmvcaBnDt3TtPT07p+/brW19dtc63BRVGkvr4+pVIpNRoN52j8jziOtby8rNHRUdtMa3DpdFpRFKnRaKiry3qaY584jjU3N6crV66ot7fXNtf6qo+NjWl+fl6SlM/nnaNbKooizc/Pa3t7WydPntSFCxeSXum7LS0t6ePHj2o0GoqiSMPDw5a51uDS6bTu3LnjHHko0um07t69m/QaB5LP5xP5o+drEVgRHKwIDlYEByuCgxXBwYrgYEVwsCI4WBEcrAgOVgQHK4KDFcHBiuBgRXCwIjhYERysCA5WBAcrgoMVwcGK4GBFcLAiOFgRHKwIDlYEByuCgxXBwYrgYEVwsCI4WBEcrAgOVgQHK4KDFcHBiuBg1RHHcfzPXzx6WWmLi2GrtT8V/HIi6TUOpB2eQZJ+/3Xi75//E1y7KP72x78e9Chqh2fYjyMVVgQHK4KDlTW4arWqUqmkx48f6/Pnz87RLbe7u6v79+9rZ2cn6VWaUqlU9PDhQ5VKJW1tbdnmWm8TDIJAQRBoY2NDGxsbGhwcdI5vqcXFRduVj4cllUppb29PJ074/hO2H6mvX79WqVTS0NCQe3TLlMtlnTp1St3d3Umv0rQgCDQzM6N8Pq/FxUXbXHtw4+PjmpmZ0atXr9yjW+bDhw9aX1/X+/fv9ebNm6TXaUpHR4ckqaenR9++fbPNtR6pa2trqlQq+vr1q65eveoc3VI3btyQJD1//lyXL19OdpkmvXv3TuVyWfV6XYVCwTbXGtzIyIhGRkacIw+V84VqteHh4UQ+g/K1CKwIDlYEByuCgxXBwYrgYEVwsCI4WBEcrAgOVgQHK4KDFcHBiuBgRXCwIjhYERysCA5WBAcrgoMVwcGK4GBFcLAiOFgRHKwIDlYEByuCgxXBwYrgYEVwsCI4WBEcrAgOVgQHK4KDFcHBiuBgxQW9P7B2eAaJC3qPjHZ4hv04UmFFcLAiOFgRHKysl7vt7e3p2bNnqtfryuVyR/aC23K5rDAM9eXLF/X396tYLCa90nfb2dnR3Nycjh07piAINDY2ZplrfYcLw1C7u7vq7OxUX1+fc3RLnTlzRlNTU8pms7p48WLS6zSlVqvp0qVLun37tj59+mSbaw2uVqvp9OnTmpyctN5CfBjiONbm5qYymUzSqzQlm81qaWlJDx480Pnz521zrUdqb2+vjh8/rs7Oo//RsVqtKgiCpNdo2tu3bzU5OalMJqMnT54ol8tZ5tov6J2dnVUYhjp79qxzdMutrq7q5s2bSa/RtFwupxcvXiiVSmloaMg21xpcd3e3pqennSMPza1bt5Je4UCy2azu3btnn3v0zzYcKQQHK4KDFcHBiuBgRXCwIjhYERysCA5WBAcrgoMVwcGK4GBFcLAiOFgRHKwIDlYEByuCgxXBwYrgYEVwsCI4WBEcrAgOVgQHK4KDFcHBiuBgRXCwIjhYERysCA5WBAcrgoMVwcGK4GBFcLBq2wt68WPiHQ5WBAcrgoPVX+CrRo0sHKjjAAAAAElFTkSuQmCC",
      "text/plain": [
       "<Figure size 192x192 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Number of nodes searched: 7275\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "{'move': 4, 'value': 0}"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 259 ms, sys: 196 ms, total: 455 ms\n",
      "Wall time: 202 ms\n"
     ]
    }
   ],
   "source": [
    "board = empty_board() \n",
    "\n",
    "print(\"Board:\")\n",
    "show_board(board)\n",
    "\n",
    "\n",
    "print()\n",
    "%time display(alpha_beta_search(board))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Note:__ Compare to the number of nodes searched without move reordering (right above)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Experiments\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Minimax with Alpha-Beta Pruning vs. Random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "alpha-beta vs. random:\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "{'x': 100, 'o': 0, 'd': 0}"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 15.5 s, sys: 1.96 ms, total: 15.5 s\n",
      "Wall time: 15.5 s\n",
      "\n",
      "random vs. alpha-beta\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "{'x': 0, 'o': 84, 'd': 16}"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 5.16 s, sys: 7.74 ms, total: 5.16 s\n",
      "Wall time: 5.17 s\n"
     ]
    }
   ],
   "source": [
    "DEBUG = 0\n",
    "\n",
    "def alpha_beta_player(board, player = 'x'):\n",
    "    return alpha_beta_search(board, player)[\"move\"]\n",
    "\n",
    "print(\"alpha-beta vs. random:\")\n",
    "%time display(play(alpha_beta_player, random_player))\n",
    "\n",
    "print()\n",
    "print(\"random vs. alpha-beta\")\n",
    "%time display(play(random_player, alpha_beta_player))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Note on runtime:** Compared to AND-OR Search, Minimax search is slower, because AND-OR Search terminates once it finds the first subtree that has only goal nodes, buy Minimax search traverses the whole tree (minus what is pruned if alpha-beta pruning is used). \n",
    "\n",
    "Also, I was lazy and recreate the search tree every time the agent is asked for a move. The agent could create the tree with the Minimax values once and then use it to decide on actions. A problem could be that the tree may be too large to store. "
   ]
  }
 ],
 "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.10.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}