games.ipynb

       "minimax_viz_canvas_object.line(400, 403, 400, 578);\n",
       "minimax_viz_canvas_object.stroke(0, 200, 0);\n",
       "minimax_viz_canvas_object.strokeWidth(1);\n",
       "minimax_viz_canvas_object.line(400, 403, 430, 578);\n",
       "minimax_viz_canvas_object.stroke(0, 200, 0);\n",
       "minimax_viz_canvas_object.strokeWidth(1);\n",
       "minimax_viz_canvas_object.line(489, 403, 459, 578);\n",
       "minimax_viz_canvas_object.stroke(0, 200, 0);\n",
       "minimax_viz_canvas_object.strokeWidth(1);\n",
       "minimax_viz_canvas_object.line(489, 403, 489, 578);\n",
       "minimax_viz_canvas_object.stroke(0, 200, 0);\n",
       "minimax_viz_canvas_object.strokeWidth(1);\n",
       "minimax_viz_canvas_object.line(489, 403, 519, 578);\n",
       "minimax_viz_canvas_object.stroke(0, 200, 0);\n",
       "minimax_viz_canvas_object.strokeWidth(1);\n",
       "minimax_viz_canvas_object.line(578, 403, 548, 578);\n",
       "minimax_viz_canvas_object.stroke(0, 200, 0);\n",
       "minimax_viz_canvas_object.strokeWidth(1);\n",
       "minimax_viz_canvas_object.line(578, 403, 578, 578);\n",
       "minimax_viz_canvas_object.stroke(0, 200, 0);\n",
       "minimax_viz_canvas_object.strokeWidth(1);\n",
       "minimax_viz_canvas_object.line(578, 403, 607, 578);\n",
       "minimax_viz_canvas_object.stroke(0, 200, 0);\n",
       "minimax_viz_canvas_object.strokeWidth(1);\n",
       "minimax_viz_canvas_object.line(667, 403, 637, 578);\n",
       "minimax_viz_canvas_object.stroke(0, 200, 0);\n",
       "minimax_viz_canvas_object.strokeWidth(1);\n",
       "minimax_viz_canvas_object.line(667, 403, 667, 578);\n",
       "minimax_viz_canvas_object.stroke(0, 200, 0);\n",
       "minimax_viz_canvas_object.strokeWidth(1);\n",
       "minimax_viz_canvas_object.line(667, 403, 696, 578);\n",
       "minimax_viz_canvas_object.stroke(0, 200, 0);\n",
       "minimax_viz_canvas_object.strokeWidth(1);\n",
       "minimax_viz_canvas_object.line(756, 403, 726, 578);\n",
       "minimax_viz_canvas_object.stroke(0, 200, 0);\n",
       "minimax_viz_canvas_object.strokeWidth(1);\n",
       "minimax_viz_canvas_object.line(756, 403, 756, 578);\n",
       "minimax_viz_canvas_object.stroke(0, 200, 0);\n",
       "minimax_viz_canvas_object.strokeWidth(1);\n",
       "minimax_viz_canvas_object.line(756, 403, 785, 578);\n",
       "</script>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "minimax_viz = Canvas_minimax('minimax_viz', [randint(1, 50) for i in range(27)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# ALPHA-BETA\n",
    "\n",
    "## Overview\n",
    "\n",
    "While *Minimax* is great for computing a move, it can get tricky when the number of games states gets bigger. The algorithm needs to search all the leaves of the tree, which increase exponentially to its depth.\n",
    "\n",
    "For Tic-Tac-Toe, where the depth of the tree is 9 (after the 9th move, the game ends), we can have at most 9! terminal states (at most because not all terminal nodes are at the last level of the tree; some are higher up because the game ended before the 9th move). This isn't so bad, but for more complex problems like chess, we have over $10^{40}$ terminal nodes. Unfortunately we have not found a way to cut the exponent away, but we nevertheless have found ways to alleviate the workload.\n",
    "\n",
    "Here we examine *pruning* the game tree, which means removing parts of it that we do not need to examine. The particular type of pruning is called *alpha-beta*, and the search in whole is called *alpha-beta search*.\n",
    "\n",
    "To showcase what parts of the tree we don't need to search, we will take a look at the example `Fig52Game`.\n",
    "\n",
    "In the example game, we need to find the best move for player MAX at state A, which is the maximum value of MIN's possible moves at successor states.\n",
    "\n",
    "`MAX(A) = MAX( MIN(B), MIN(C), MIN(D) )`\n",
    "\n",
    "`MIN(B)` is the minimum of 3, 12, 8 which is 3. So the above formula becomes:\n",
    "\n",
    "`MAX(A) = MAX( 3, MIN(C), MIN(D) )`\n",
    "\n",
    "Next move we will check is c1, which leads to a terminal state with utility of 2. Before we continue searching under state C, let's pop back into our formula with the new value:\n",
    "\n",
    "`MAX(A) = MAX( 3, MIN(2, c2, .... cN), MIN(D) )`\n",
    "\n",
    "We do not know how many moves state C allows, but we know that the first one results in a value of 2. Do we need to keep searching under C? The answer is no. The value MIN will pick on C will at most be 2. Since MAX already has the option to pick something greater than that, 3 from B, he does not need to keep searching under C.\n",
    "\n",
    "In *alpha-beta* we make use of two additional parameters for each state/node, *a* and *b*, that describe bounds on the possible moves. The parameter *a* denotes the best choice (highest value) for MAX along that path, while *b* denotes the best choice (lowest value) for MIN. As we go along we update *a* and *b* and prune a node branch when the value of the node is worse than the value of *a* and *b* for MAX and MIN respectively.\n",
    "\n",
    "In the above example, after the search under state B, MAX had an *a* value of 3. So, when searching node C we found a value less than that, 2, we stopped searching under C."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implementation\n",
    "\n",
    "Like *minimax*, we again make use of functions `max_value` and `min_value`, but this time we utilise the *a* and *b* values, updating them and stopping the recursive call if we end up on nodes with values worse than *a* and *b* (for MAX and MIN). The algorithm finds the maximum value and returns the move that results in it.\n",
    "\n",
    "The implementation:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%psource alphabeta_search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example\n",
    "\n",
    "We will play the Fig52 Game with the *alpha-beta* search algorithm. It is the turn of MAX to play at state A."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a1\n"
     ]
    }
   ],
   "source": [
    "print(alphabeta_search('A', fig52))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The optimal move for MAX is a1, for the reasons given above. MIN will pick move b1 for B resulting in a value of 3, updating the *a* value of MAX to 3. Then, when we find under C a node of value 2, we will stop searching under that sub-tree since it is less than *a*. From D we have a value of 2. So, the best move for MAX is the one resulting in a value of 3, which is a1.\n",
    "\n",
    "Below we see the best moves for MIN starting from B, C and D respectively. Note that the algorithm in these cases works the same way as *minimax*, since all the nodes below the aforementioned states are terminal."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "b1\n",
      "c1\n",
      "d3\n"
     ]
    }
   ],
   "source": [
    "print(alphabeta_search('B', fig52))\n",
    "print(alphabeta_search('C', fig52))\n",
    "print(alphabeta_search('D', fig52))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Visualization\n",
    "\n",
    "Below you will find the visualization of the alpha-beta algorithm for a simple game. Click on the cell after you run the command to move the game along. You can input your own values via a list of 27 integers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from notebook import Canvas_alphabeta\n",
    "from random import randint"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "\n",
       "<script type=\"text/javascript\" src=\"./js/canvas.js\"></script>\n",
       "<div>\n",
       "<canvas id=\"alphabeta_viz\" width=\"800\" height=\"600\" style=\"background:rgba(158, 167, 184, 0.2);\" onclick='click_callback(this, event, \"alphabeta_viz\")'></canvas>\n",
       "</div>\n",
       "\n",
       "<script> var alphabeta_viz_canvas_object = new Canvas(\"alphabeta_viz\");</script>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<script>\n",
       "alphabeta_viz_canvas_object.font(\"12px Arial\");\n",
       "alphabeta_viz_canvas_object.clear();\n",
       "alphabeta_viz_canvas_object.stroke(0, 0, 0);\n",
       "alphabeta_viz_canvas_object.strokeWidth(1);\n",
       "alphabeta_viz_canvas_object.fill(200, 200, 200);\n",
       "alphabeta_viz_canvas_object.rect(390, 23, 20, 15);\n",
       "alphabeta_viz_canvas_object.line(390, 23, 410, 23);\n",
       "alphabeta_viz_canvas_object.line(390, 23, 390, 38);\n",
       "alphabeta_viz_canvas_object.line(410, 38, 410, 23);\n",
       "alphabeta_viz_canvas_object.line(410, 38, 390, 38);\n",
       "alphabeta_viz_canvas_object.fill(0, 0, 0);\n",
       "alphabeta_viz_canvas_object.fill(200, 200, 200);\n",
       "alphabeta_viz_canvas_object.rect(123, 208, 20, 15);\n",
       "alphabeta_viz_canvas_object.line(123, 208, 143, 208);\n",
       "alphabeta_viz_canvas_object.line(123, 208, 123, 222);\n",
       "alphabeta_viz_canvas_object.line(143, 222, 143, 208);\n",
       "alphabeta_viz_canvas_object.line(143, 222, 123, 222);\n",
       "alphabeta_viz_canvas_object.fill(0, 0, 0);\n",
       "alphabeta_viz_canvas_object.fill(200, 200, 200);\n",
       "alphabeta_viz_canvas_object.rect(390, 208, 20, 15);\n",
       "alphabeta_viz_canvas_object.line(390, 208, 410, 208);\n",
       "alphabeta_viz_canvas_object.line(390, 208, 390, 222);\n",
       "alphabeta_viz_canvas_object.line(410, 222, 410, 208);\n",
       "alphabeta_viz_canvas_object.line(410, 222, 390, 222);\n",
       "alphabeta_viz_canvas_object.fill(0, 0, 0);\n",
       "alphabeta_viz_canvas_object.fill(200, 200, 200);\n",
       "alphabeta_viz_canvas_object.rect(657, 208, 20, 15);\n",
       "alphabeta_viz_canvas_object.line(657, 208, 677, 208);\n",
       "alphabeta_viz_canvas_object.line(657, 208, 657, 222);\n",
       "alphabeta_viz_canvas_object.line(677, 222, 677, 208);\n",
       "alphabeta_viz_canvas_object.line(677, 222, 657, 222);\n",
       "alphabeta_viz_canvas_object.fill(0, 0, 0);\n",
       "alphabeta_viz_canvas_object.fill(200, 200, 200);\n",
       "alphabeta_viz_canvas_object.rect(34, 392, 20, 15);\n",
       "alphabeta_viz_canvas_object.line(34, 392, 54, 392);\n",
       "alphabeta_viz_canvas_object.line(34, 392, 34, 408);\n",
       "alphabeta_viz_canvas_object.line(54, 408, 54, 392);\n",
       "alphabeta_viz_canvas_object.line(54, 408, 34, 408);\n",
       "alphabeta_viz_canvas_object.fill(0, 0, 0);\n",
       "alphabeta_viz_canvas_object.fill(200, 200, 200);\n",
       "alphabeta_viz_canvas_object.rect(123, 392, 20, 15);\n",
       "alphabeta_viz_canvas_object.line(123, 392, 143, 392);\n",
       "alphabeta_viz_canvas_object.line(123, 392, 123, 408);\n",
       "alphabeta_viz_canvas_object.line(143, 408, 143, 392);\n",
       "alphabeta_viz_canvas_object.line(143, 408, 123, 408);\n",
       "alphabeta_viz_canvas_object.fill(0, 0, 0);\n",
       "alphabeta_viz_canvas_object.fill(200, 200, 200);\n",
       "alphabeta_viz_canvas_object.rect(212, 392, 20, 15);\n",
       "alphabeta_viz_canvas_object.line(212, 392, 232, 392);\n",
       "alphabeta_viz_canvas_object.line(212, 392, 212, 408);\n",
       "alphabeta_viz_canvas_object.line(232, 408, 232, 392);\n",
       "alphabeta_viz_canvas_object.line(232, 408, 212, 408);\n",
       "alphabeta_viz_canvas_object.fill(0, 0, 0);\n",
       "alphabeta_viz_canvas_object.fill(200, 200, 200);\n",
       "alphabeta_viz_canvas_object.rect(301, 392, 20, 15);\n",
       "alphabeta_viz_canvas_object.line(301, 392, 321, 392);\n",
       "alphabeta_viz_canvas_object.line(301, 392, 301, 408);\n",
       "alphabeta_viz_canvas_object.line(321, 408, 321, 392);\n",
       "alphabeta_viz_canvas_object.line(321, 408, 301, 408);\n",
       "alphabeta_viz_canvas_object.fill(0, 0, 0);\n",
       "alphabeta_viz_canvas_object.fill(200, 200, 200);\n",
       "alphabeta_viz_canvas_object.rect(390, 392, 20, 15);\n",
       "alphabeta_viz_canvas_object.line(390, 392, 410, 392);\n",
       "alphabeta_viz_canvas_object.line(390, 392, 390, 408);\n",
       "alphabeta_viz_canvas_object.line(410, 408, 410, 392);\n",
       "alphabeta_viz_canvas_object.line(410, 408, 390, 408);\n",
       "alphabeta_viz_canvas_object.fill(0, 0, 0);\n",
       "alphabeta_viz_canvas_object.fill(200, 200, 200);\n",
       "alphabeta_viz_canvas_object.rect(479, 392, 20, 15);\n",
       "alphabeta_viz_canvas_object.line(479, 392, 499, 392);\n",
       "alphabeta_viz_canvas_object.line(479, 392, 479, 408);\n",
       "alphabeta_viz_canvas_object.line(499, 408, 499, 392);\n",
       "alphabeta_viz_canvas_object.line(499, 408, 479, 408);\n",
       "alphabeta_viz_canvas_object.fill(0, 0, 0);\n",
       "alphabeta_viz_canvas_object.fill(200, 200, 200);\n",
       "alphabeta_viz_canvas_object.rect(568, 392, 20, 15);\n",
       "alphabeta_viz_canvas_object.line(568, 392, 588, 392);\n",
       "alphabeta_viz_canvas_object.line(568, 392, 568, 408);\n",
       "alphabeta_viz_canvas_object.line(588, 408, 588, 392);\n",
       "alphabeta_viz_canvas_object.line(588, 408, 568, 408);\n",
       "alphabeta_viz_canvas_object.fill(0, 0, 0);\n",
       "alphabeta_viz_canvas_object.fill(200, 200, 200);\n",
       "alphabeta_viz_canvas_object.rect(657, 392, 20, 15);\n",
       "alphabeta_viz_canvas_object.line(657, 392, 677, 392);\n",
       "alphabeta_viz_canvas_object.line(657, 392, 657, 408);\n",
       "alphabeta_viz_canvas_object.line(677, 408, 677, 392);\n",
       "alphabeta_viz_canvas_object.line(677, 408, 657, 408);\n",
       "alphabeta_viz_canvas_object.fill(0, 0, 0);\n",
       "alphabeta_viz_canvas_object.fill(200, 200, 200);\n",
       "alphabeta_viz_canvas_object.rect(746, 392, 20, 15);\n",
       "alphabeta_viz_canvas_object.line(746, 392, 766, 392);\n",
       "alphabeta_viz_canvas_object.line(746, 392, 746, 408);\n",
       "alphabeta_viz_canvas_object.line(766, 408, 766, 392);\n",
       "alphabeta_viz_canvas_object.line(766, 408, 746, 408);\n",
       "alphabeta_viz_canvas_object.fill(0, 0, 0);\n",
       "alphabeta_viz_canvas_object.fill(255, 255, 255);\n",
       "alphabeta_viz_canvas_object.rect(5, 578, 20, 15);\n",
       "alphabeta_viz_canvas_object.line(5, 578, 25, 578);\n",
       "alphabeta_viz_canvas_object.line(5, 578, 5, 592);\n",
       "alphabeta_viz_canvas_object.line(25, 592, 25, 578);\n",
       "alphabeta_viz_canvas_object.line(25, 592, 5, 592);\n",
       "alphabeta_viz_canvas_object.fill(0, 0, 0);\n",
       "alphabeta_viz_canvas_object.fill_text(\"50\", 7, 591);\n",
       "alphabeta_viz_canvas_object.fill(255, 255, 255);\n",
       "alphabeta_viz_canvas_object.rect(34, 578, 20, 15);\n",
       "alphabeta_viz_canvas_object.line(34, 578, 54, 578);\n",
       "alphabeta_viz_canvas_object.line(34, 578, 34, 592);\n",
       "alphabeta_viz_canvas_object.line(54, 592, 54, 578);\n",
       "alphabeta_viz_canvas_object.line(54, 592, 34, 592);\n",
       "alphabeta_viz_canvas_object.fill(0, 0, 0);\n",
       "alphabeta_viz_canvas_object.fill_text(\"5\", 36, 591);\n",
       "alphabeta_viz_canvas_object.fill(255, 255, 255);\n",
       "alphabeta_viz_canvas_object.rect(64, 578, 20, 15);\n",
       "alphabeta_viz_canvas_object.line(64, 578, 84, 578);\n",
       "alphabeta_viz_canvas_object.line(64, 578, 64, 592);\n",
       "alphabeta_viz_canvas_object.line(84, 592, 84, 578);\n",
       "alphabeta_viz_canvas_object.line(84, 592, 64, 592);\n",
       "alphabeta_viz_canvas_object.fill(0, 0, 0);\n",
       "alphabeta_viz_canvas_object.fill_text(\"1\", 66, 591);\n",
       "alphabeta_viz_canvas_object.fill(255, 255, 255);\n",
       "alphabeta_viz_canvas_object.rect(94, 578, 20, 15);\n",
       "alphabeta_viz_canvas_object.line(94, 578, 114, 578);\n",
       "alphabeta_viz_canvas_object.line(94, 578, 94, 592);\n",
       "alphabeta_viz_canvas_object.line(114, 592, 114, 578);\n",
       "alphabeta_viz_canvas_object.line(114, 592, 94, 592);\n",
       "alphabeta_viz_canvas_object.fill(0, 0, 0);\n",
       "alphabeta_viz_canvas_object.fill_text(\"30\", 96, 591);\n",
       "alphabeta_viz_canvas_object.fill(255, 255, 255);\n",
       "alphabeta_viz_canvas_object.rect(123, 578, 20, 15);\n",
       "alphabeta_viz_canvas_object.line(123, 578, 143, 578);\n",
       "alphabeta_viz_canvas_object.line(123, 578, 123, 592);\n",
       "alphabeta_viz_canvas_object.line(143, 592, 143, 578);\n",
       "alphabeta_viz_canvas_object.line(143, 592, 123, 592);\n",
       "alphabeta_viz_canvas_object.fill(0, 0, 0);\n",
       "alphabeta_viz_canvas_object.fill_text(\"20\", 125, 591);\n",
       "alphabeta_viz_canvas_object.fill(255, 255, 255);\n",
       "alphabeta_viz_canvas_object.rect(153, 578, 20, 15);\n",
       "alphabeta_viz_canvas_object.line(153, 578, 173, 578);\n",
       "alphabeta_viz_canvas_object.line(153, 578, 153, 592);\n",
       "alphabeta_viz_canvas_object.line(173, 592, 173, 578);\n",
       "alphabeta_viz_canvas_object.line(173, 592, 153, 592);\n",
       "alphabeta_viz_canvas_object.fill(0, 0, 0);\n",
       "alphabeta_viz_canvas_object.fill_text(\"48\", 155, 591);\n",
       "alphabeta_viz_canvas_object.fill(255, 255, 255);\n",
       "alphabeta_viz_canvas_object.rect(183, 578, 20, 15);\n",
       "alphabeta_viz_canvas_object.line(183, 578, 203, 578);\n",
       "alphabeta_viz_canvas_object.line(183, 578, 183, 592);\n",
       "alphabeta_viz_canvas_object.line(203, 592, 203, 578);\n",
       "alphabeta_viz_canvas_object.line(203, 592, 183, 592);\n",
       "alphabeta_viz_canvas_object.fill(0, 0, 0);\n",
       "alphabeta_viz_canvas_object.fill_text(\"11\", 185, 591);\n",
       "alphabeta_viz_canvas_object.fill(255, 255, 255);\n",
       "alphabeta_viz_canvas_object.rect(212, 578, 20, 15);\n",
       "alphabeta_viz_canvas_object.line(212, 578, 232, 578);\n",
       "alphabeta_viz_canvas_object.line(212, 578, 212, 592);\n",
       "alphabeta_viz_canvas_object.line(232, 592, 232, 578);\n",
       "alphabeta_viz_canvas_object.line(232, 592, 212, 592);\n",
       "alphabeta_viz_canvas_object.fill(0, 0, 0);\n",
       "alphabeta_viz_canvas_object.fill_text(\"37\", 214, 591);\n",
       "alphabeta_viz_canvas_object.fill(255, 255, 255);\n",
       "alphabeta_viz_canvas_object.rect(242, 578, 20, 15);\n",
       "alphabeta_viz_canvas_object.line(242, 578, 262, 578);\n",
       "alphabeta_viz_canvas_object.line(242, 578, 242, 592);\n",
       "alphabeta_viz_canvas_object.line(262, 592, 262, 578);\n",
       "alphabeta_viz_canvas_object.line(262, 592, 242, 592);\n",
       "alphabeta_viz_canvas_object.fill(0, 0, 0);\n",
       "alphabeta_viz_canvas_object.fill_text(\"19\", 244, 591);\n",
       "alphabeta_viz_canvas_object.fill(255, 255, 255);\n",
       "alphabeta_viz_canvas_object.rect(271, 578, 20, 15);\n",
       "alphabeta_viz_canvas_object.line(271, 578, 291, 578);\n",
       "alphabeta_viz_canvas_object.line(271, 578, 271, 592);\n",
       "alphabeta_viz_canvas_object.line(291, 592, 291, 578);\n",
       "alphabeta_viz_canvas_object.line(291, 592, 271, 592);\n",
       "alphabeta_viz_canvas_object.fill(0, 0, 0);\n",
       "alphabeta_viz_canvas_object.fill_text(\"47\", 273, 591);\n",
       "alphabeta_viz_canvas_object.fill(255, 255, 255);\n",
       "alphabeta_viz_canvas_object.rect(301, 578, 20, 15);\n",
       "alphabeta_viz_canvas_object.line(301, 578, 321, 578);\n",
       "alphabeta_viz_canvas_object.line(301, 578, 301, 592);\n",
       "alphabeta_viz_canvas_object.line(321, 592, 321, 578);\n",
       "alphabeta_viz_canvas_object.line(321, 592, 301, 592);\n",
       "alphabeta_viz_canvas_object.fill(0, 0, 0);\n",
       "alphabeta_viz_canvas_object.fill_text(\"25\", 303, 591);\n",
       "alphabeta_viz_canvas_object.fill(255, 255, 255);\n",
       "alphabeta_viz_canvas_object.rect(331, 578, 20, 15);\n",
       "alphabeta_viz_canvas_object.line(331, 578, 351, 578);\n",
       "alphabeta_viz_canvas_object.line(331, 578, 331, 592);\n",
       "alphabeta_viz_canvas_object.line(351, 592, 351, 578);\n",
       "alphabeta_viz_canvas_object.line(351, 592, 331, 592);\n",
       "alphabeta_viz_canvas_object.fill(0, 0, 0);\n",
       "alphabeta_viz_canvas_object.fill_text(\"34\", 333, 591);\n",
       "alphabeta_viz_canvas_object.fill(255, 255, 255);\n",
       "alphabeta_viz_canvas_object.rect(360, 578, 20, 15);\n",
       "alphabeta_viz_canvas_object.line(360, 578, 380, 578);\n",
       "alphabeta_viz_canvas_object.line(360, 578, 360, 592);\n",
       "alphabeta_viz_canvas_object.line(380, 592, 380, 578);\n",
       "alphabeta_viz_canvas_object.line(380, 592, 360, 592);\n",
       "alphabeta_viz_canvas_object.fill(0, 0, 0);\n",
       "alphabeta_viz_canvas_object.fill_text(\"35\", 362, 591);\n",
       "alphabeta_viz_canvas_object.fill(255, 255, 255);\n",
       "alphabeta_viz_canvas_object.rect(390, 578, 20, 15);\n",
       "alphabeta_viz_canvas_object.line(390, 578, 410, 578);\n",
       "alphabeta_viz_canvas_object.line(390, 578, 390, 592);\n",
       "alphabeta_viz_canvas_object.line(410, 592, 410, 578);\n",
       "alphabeta_viz_canvas_object.line(410, 592, 390, 592);\n",
       "alphabeta_viz_canvas_object.fill(0, 0, 0);\n",
       "alphabeta_viz_canvas_object.fill_text(\"3\", 392, 591);\n",
       "alphabeta_viz_canvas_object.fill(255, 255, 255);\n",
       "alphabeta_viz_canvas_object.rect(420, 578, 20, 15);\n",
       "alphabeta_viz_canvas_object.line(420, 578, 440, 578);\n",
       "alphabeta_viz_canvas_object.line(420, 578, 420, 592);\n",
       "alphabeta_viz_canvas_object.line(440, 592, 440, 578);\n",
       "alphabeta_viz_canvas_object.line(440, 592, 420, 592);\n",
       "alphabeta_viz_canvas_object.fill(0, 0, 0);\n",
       "alphabeta_viz_canvas_object.fill_text(\"28\", 422, 591);\n",
       "alphabeta_viz_canvas_object.fill(255, 255, 255);\n",
       "alphabeta_viz_canvas_object.rect(449, 578, 20, 15);\n",
       "alphabeta_viz_canvas_object.line(449, 578, 469, 578);\n",
       "alphabeta_viz_canvas_object.line(449, 578, 449, 592);\n",
       "alphabeta_viz_canvas_object.line(469, 592, 469, 578);\n",
       "alphabeta_viz_canvas_object.line(469, 592, 449, 592);\n",
       "alphabeta_viz_canvas_object.fill(0, 0, 0);\n",
       "alphabeta_viz_canvas_object.fill_text(\"9\", 451, 591);\n",
       "alphabeta_viz_canvas_object.fill(255, 255, 255);\n",
       "alphabeta_viz_canvas_object.rect(479, 578, 20, 15);\n",
       "alphabeta_viz_canvas_object.line(479, 578, 499, 578);\n",
       "alphabeta_viz_canvas_object.line(479, 578, 479, 592);\n",
       "alphabeta_viz_canvas_object.line(499, 592, 499, 578);\n",
       "alphabeta_viz_canvas_object.line(499, 592, 479, 592);\n",
       "alphabeta_viz_canvas_object.fill(0, 0, 0);\n",
       "alphabeta_viz_canvas_object.fill_text(\"24\", 481, 591);\n",
       "alphabeta_viz_canvas_object.fill(255, 255, 255);\n",
       "alphabeta_viz_canvas_object.rect(509, 578, 20, 15);\n",
       "alphabeta_viz_canvas_object.line(509, 578, 529, 578);\n",
       "alphabeta_viz_canvas_object.line(509, 578, 509, 592);\n",
       "alphabeta_viz_canvas_object.line(529, 592, 529, 578);\n",
       "alphabeta_viz_canvas_object.line(529, 592, 509, 592);\n",
       "alphabeta_viz_canvas_object.fill(0, 0, 0);\n",
       "alphabeta_viz_canvas_object.fill_text(\"1\", 511, 591);\n",
       "alphabeta_viz_canvas_object.fill(255, 255, 255);\n",
       "alphabeta_viz_canvas_object.rect(538, 578, 20, 15);\n",
       "alphabeta_viz_canvas_object.line(538, 578, 558, 578);\n",
       "alphabeta_viz_canvas_object.line(538, 578, 538, 592);\n",
       "alphabeta_viz_canvas_object.line(558, 592, 558, 578);\n",
       "alphabeta_viz_canvas_object.line(558, 592, 538, 592);\n",
       "alphabeta_viz_canvas_object.fill(0, 0, 0);\n",
       "alphabeta_viz_canvas_object.fill_text(\"21\", 540, 591);\n",
       "alphabeta_viz_canvas_object.fill(255, 255, 255);\n",
       "alphabeta_viz_canvas_object.rect(568, 578, 20, 15);\n",
       "alphabeta_viz_canvas_object.line(568, 578, 588, 578);\n",
       "alphabeta_viz_canvas_object.line(568, 578, 568, 592);\n",
       "alphabeta_viz_canvas_object.line(588, 592, 588, 578);\n",
       "alphabeta_viz_canvas_object.line(588, 592, 568, 592);\n",
       "alphabeta_viz_canvas_object.fill(0, 0, 0);\n",
       "alphabeta_viz_canvas_object.fill_text(\"9\", 570, 591);\n",
       "alphabeta_viz_canvas_object.fill(255, 255, 255);\n",
       "alphabeta_viz_canvas_object.rect(597, 578, 20, 15);\n",
       "alphabeta_viz_canvas_object.line(597, 578, 617, 578);\n",
       "alphabeta_viz_canvas_object.line(597, 578, 597, 592);\n",
       "alphabeta_viz_canvas_object.line(617, 592, 617, 578);\n",
       "alphabeta_viz_canvas_object.line(617, 592, 597, 592);\n",
       "alphabeta_viz_canvas_object.fill(0, 0, 0);\n",
       "alphabeta_viz_canvas_object.fill_text(\"45\", 599, 591);\n",
       "alphabeta_viz_canvas_object.fill(255, 255, 255);\n",
       "alphabeta_viz_canvas_object.rect(627, 578, 20, 15);\n",
       "alphabeta_viz_canvas_object.line(627, 578, 647, 578);\n",
       "alphabeta_viz_canvas_object.line(627, 578, 627, 592);\n",
       "alphabeta_viz_canvas_object.line(647, 592, 647, 578);\n",
       "alphabeta_viz_canvas_object.line(647, 592, 627, 592);\n",
       "alphabeta_viz_canvas_object.fill(0, 0, 0);\n",
       "alphabeta_viz_canvas_object.fill_text(\"33\", 629, 591);\n",
       "alphabeta_viz_canvas_object.fill(255, 255, 255);\n",
       "alphabeta_viz_canvas_object.rect(657, 578, 20, 15);\n",
       "alphabeta_viz_canvas_object.line(657, 578, 677, 578);\n",
       "alphabeta_viz_canvas_object.line(657, 578, 657, 592);\n",
       "alphabeta_viz_canvas_object.line(677, 592, 677, 578);\n",
       "alphabeta_viz_canvas_object.line(677, 592, 657, 592);\n",
       "alphabeta_viz_canvas_object.fill(0, 0, 0);\n",
       "alphabeta_viz_canvas_object.fill_text(\"38\", 659, 591);\n",
       "alphabeta_viz_canvas_object.fill(255, 255, 255);\n",
       "alphabeta_viz_canvas_object.rect(686, 578, 20, 15);\n",
       "alphabeta_viz_canvas_object.line(686, 578, 706, 578);\n",
       "alphabeta_viz_canvas_object.line(686, 578, 686, 592);\n",
       "alphabeta_viz_canvas_object.line(706, 592, 706, 578);\n",
       "alphabeta_viz_canvas_object.line(706, 592, 686, 592);\n",
       "alphabeta_viz_canvas_object.fill(0, 0, 0);\n",
       "alphabeta_viz_canvas_object.fill_text(\"27\", 688, 591);\n",
       "alphabeta_viz_canvas_object.fill(255, 255, 255);\n",
       "alphabeta_viz_canvas_object.rect(716, 578, 20, 15);\n",
       "alphabeta_viz_canvas_object.line(716, 578, 736, 578);\n",
       "alphabeta_viz_canvas_object.line(716, 578, 716, 592);\n",
       "alphabeta_viz_canvas_object.line(736, 592, 736, 578);\n",
       "alphabeta_viz_canvas_object.line(736, 592, 716, 592);\n",
       "alphabeta_viz_canvas_object.fill(0, 0, 0);\n",
       "alphabeta_viz_canvas_object.fill_text(\"33\", 718, 591);\n",
       "alphabeta_viz_canvas_object.fill(255, 255, 255);\n",
       "alphabeta_viz_canvas_object.rect(746, 578, 20, 15);\n",
       "alphabeta_viz_canvas_object.line(746, 578, 766, 578);\n",
       "alphabeta_viz_canvas_object.line(746, 578, 746, 592);\n",
       "alphabeta_viz_canvas_object.line(766, 592, 766, 578);\n",
       "alphabeta_viz_canvas_object.line(766, 592, 746, 592);\n",
       "alphabeta_viz_canvas_object.fill(0, 0, 0);\n",
       "alphabeta_viz_canvas_object.fill_text(\"22\", 748, 591);\n",
       "alphabeta_viz_canvas_object.fill(255, 255, 255);\n",
       "alphabeta_viz_canvas_object.rect(775, 578, 20, 15);\n",
       "alphabeta_viz_canvas_object.line(775, 578, 795, 578);\n",
       "alphabeta_viz_canvas_object.line(775, 578, 775, 592);\n",
       "alphabeta_viz_canvas_object.line(795, 592, 795, 578);\n",
       "alphabeta_viz_canvas_object.line(795, 592, 775, 592);\n",
       "alphabeta_viz_canvas_object.fill(0, 0, 0);\n",
       "alphabeta_viz_canvas_object.fill_text(\"24\", 777, 591);\n",
       "alphabeta_viz_canvas_object.stroke(0, 200, 0);\n",
       "alphabeta_viz_canvas_object.strokeWidth(1);\n",
       "alphabeta_viz_canvas_object.line(400, 38, 133, 208);\n",
       "alphabeta_viz_canvas_object.stroke(0, 200, 0);\n",
       "alphabeta_viz_canvas_object.strokeWidth(1);\n",
       "alphabeta_viz_canvas_object.line(400, 38, 400, 208);\n",
       "alphabeta_viz_canvas_object.stroke(0, 200, 0);\n",
       "alphabeta_viz_canvas_object.strokeWidth(1);\n",
       "alphabeta_viz_canvas_object.line(400, 38, 667, 208);\n",
       "alphabeta_viz_canvas_object.stroke(200, 0, 0);\n",
       "alphabeta_viz_canvas_object.strokeWidth(1);\n",
       "alphabeta_viz_canvas_object.line(133, 222, 44, 392);\n",
       "alphabeta_viz_canvas_object.stroke(200, 0, 0);\n",
       "alphabeta_viz_canvas_object.strokeWidth(1);\n",
       "alphabeta_viz_canvas_object.line(133, 222, 133, 392);\n",
       "alphabeta_viz_canvas_object.stroke(200, 0, 0);\n",
       "alphabeta_viz_canvas_object.strokeWidth(1);\n",
       "alphabeta_viz_canvas_object.line(133, 222, 222, 392);\n",
       "alphabeta_viz_canvas_object.stroke(200, 0, 0);\n",
       "alphabeta_viz_canvas_object.strokeWidth(1);\n",
       "alphabeta_viz_canvas_object.line(400, 222, 311, 392);\n",
       "alphabeta_viz_canvas_object.stroke(200, 0, 0);\n",
       "alphabeta_viz_canvas_object.strokeWidth(1);\n",
       "alphabeta_viz_canvas_object.line(400, 222, 400, 392);\n",
       "alphabeta_viz_canvas_object.stroke(200, 0, 0);\n",
       "alphabeta_viz_canvas_object.strokeWidth(1);\n",
       "alphabeta_viz_canvas_object.line(400, 222, 489, 392);\n",
       "alphabeta_viz_canvas_object.stroke(200, 0, 0);\n",
       "alphabeta_viz_canvas_object.strokeWidth(1);\n",
       "alphabeta_viz_canvas_object.line(667, 222, 578, 392);\n",
       "alphabeta_viz_canvas_object.stroke(200, 0, 0);\n",
       "alphabeta_viz_canvas_object.strokeWidth(1);\n",
       "alphabeta_viz_canvas_object.line(667, 222, 667, 392);\n",
       "alphabeta_viz_canvas_object.stroke(200, 0, 0);\n",
       "alphabeta_viz_canvas_object.strokeWidth(1);\n",
       "alphabeta_viz_canvas_object.line(667, 222, 756, 392);\n",
       "alphabeta_viz_canvas_object.stroke(0, 200, 0);\n",
       "alphabeta_viz_canvas_object.strokeWidth(1);\n",
       "alphabeta_viz_canvas_object.line(44, 408, 15, 578);\n",
       "alphabeta_viz_canvas_object.stroke(0, 200, 0);\n",
       "alphabeta_viz_canvas_object.strokeWidth(1);\n",
       "alphabeta_viz_canvas_object.line(44, 408, 44, 578);\n",
       "alphabeta_viz_canvas_object.stroke(0, 200, 0);\n",
       "alphabeta_viz_canvas_object.strokeWidth(1);\n",
       "alphabeta_viz_canvas_object.line(44, 408, 74, 578);\n",
       "alphabeta_viz_canvas_object.stroke(0, 200, 0);\n",
       "alphabeta_viz_canvas_object.strokeWidth(1);\n",
       "alphabeta_viz_canvas_object.line(133, 408, 104, 578);\n",
       "alphabeta_viz_canvas_object.stroke(0, 200, 0);\n",
       "alphabeta_viz_canvas_object.strokeWidth(1);\n",
       "alphabeta_viz_canvas_object.line(133, 408, 133, 578);\n",
       "alphabeta_viz_canvas_object.stroke(0, 200, 0);\n",
       "alphabeta_viz_canvas_object.strokeWidth(1);\n",
       "alphabeta_viz_canvas_object.line(133, 408, 163, 578);\n",
       "alphabeta_viz_canvas_object.stroke(0, 200, 0);\n",
       "alphabeta_viz_canvas_object.strokeWidth(1);\n",
       "alphabeta_viz_canvas_object.line(222, 408, 193, 578);\n",
       "alphabeta_viz_canvas_object.stroke(0, 200, 0);\n",
       "alphabeta_viz_canvas_object.strokeWidth(1);\n",
       "alphabeta_viz_canvas_object.line(222, 408, 222, 578);\n",
       "alphabeta_viz_canvas_object.stroke(0, 200, 0);\n",
       "alphabeta_viz_canvas_object.strokeWidth(1);\n",
       "alphabeta_viz_canvas_object.line(222, 408, 252, 578);\n",
       "alphabeta_viz_canvas_object.stroke(0, 200, 0);\n",
       "alphabeta_viz_canvas_object.strokeWidth(1);\n",
       "alphabeta_viz_canvas_object.line(311, 408, 281, 578);\n",
       "alphabeta_viz_canvas_object.stroke(0, 200, 0);\n",
       "alphabeta_viz_canvas_object.strokeWidth(1);\n",
       "alphabeta_viz_canvas_object.line(311, 408, 311, 578);\n",
       "alphabeta_viz_canvas_object.stroke(0, 200, 0);\n",
       "alphabeta_viz_canvas_object.strokeWidth(1);\n",
       "alphabeta_viz_canvas_object.line(311, 408, 341, 578);\n",
       "alphabeta_viz_canvas_object.stroke(0, 200, 0);\n",
       "alphabeta_viz_canvas_object.strokeWidth(1);\n",
       "alphabeta_viz_canvas_object.line(400, 408, 370, 578);\n",
       "alphabeta_viz_canvas_object.stroke(0, 200, 0);\n",
       "alphabeta_viz_canvas_object.strokeWidth(1);\n",
       "alphabeta_viz_canvas_object.line(400, 408, 400, 578);\n",
       "alphabeta_viz_canvas_object.stroke(0, 200, 0);\n",
       "alphabeta_viz_canvas_object.strokeWidth(1);\n",
       "alphabeta_viz_canvas_object.line(400, 408, 430, 578);\n",
       "alphabeta_viz_canvas_object.stroke(0, 200, 0);\n",
       "alphabeta_viz_canvas_object.strokeWidth(1);\n",
       "alphabeta_viz_canvas_object.line(489, 408, 459, 578);\n",
       "alphabeta_viz_canvas_object.stroke(0, 200, 0);\n",
       "alphabeta_viz_canvas_object.strokeWidth(1);\n",
       "alphabeta_viz_canvas_object.line(489, 408, 489, 578);\n",
       "alphabeta_viz_canvas_object.stroke(0, 200, 0);\n",
       "alphabeta_viz_canvas_object.strokeWidth(1);\n",
       "alphabeta_viz_canvas_object.line(489, 408, 519, 578);\n",
       "alphabeta_viz_canvas_object.stroke(0, 200, 0);\n",
       "alphabeta_viz_canvas_object.strokeWidth(1);\n",
       "alphabeta_viz_canvas_object.line(578, 408, 548, 578);\n",
       "alphabeta_viz_canvas_object.stroke(0, 200, 0);\n",
       "alphabeta_viz_canvas_object.strokeWidth(1);\n",
       "alphabeta_viz_canvas_object.line(578, 408, 578, 578);\n",
       "alphabeta_viz_canvas_object.stroke(0, 200, 0);\n",
       "alphabeta_viz_canvas_object.strokeWidth(1);\n",
       "alphabeta_viz_canvas_object.line(578, 408, 607, 578);\n",
       "alphabeta_viz_canvas_object.stroke(0, 200, 0);\n",
       "alphabeta_viz_canvas_object.strokeWidth(1);\n",
       "alphabeta_viz_canvas_object.line(667, 408, 637, 578);\n",
       "alphabeta_viz_canvas_object.stroke(0, 200, 0);\n",
       "alphabeta_viz_canvas_object.strokeWidth(1);\n",
       "alphabeta_viz_canvas_object.line(667, 408, 667, 578);\n",
       "alphabeta_viz_canvas_object.stroke(0, 200, 0);\n",
       "alphabeta_viz_canvas_object.strokeWidth(1);\n",
       "alphabeta_viz_canvas_object.line(667, 408, 696, 578);\n",
       "alphabeta_viz_canvas_object.stroke(0, 200, 0);\n",
       "alphabeta_viz_canvas_object.strokeWidth(1);\n",
       "alphabeta_viz_canvas_object.line(756, 408, 726, 578);\n",
       "alphabeta_viz_canvas_object.stroke(0, 200, 0);\n",
       "alphabeta_viz_canvas_object.strokeWidth(1);\n",
       "alphabeta_viz_canvas_object.line(756, 408, 756, 578);\n",
       "alphabeta_viz_canvas_object.stroke(0, 200, 0);\n",
       "alphabeta_viz_canvas_object.strokeWidth(1);\n",
       "alphabeta_viz_canvas_object.line(756, 408, 785, 578);\n",
       "</script>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "alphabeta_viz = Canvas_alphabeta('alphabeta_viz', [randint(1, 50) for i in range(27)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# PLAYERS\n",
    "\n",
    "So, we have finished the implementation of the `TicTacToe` and `Fig52Game` classes. What these classes do is defining the rules of the games. We need more to create an AI that can actually play games. This is where `random_player` and `alphabeta_player` come in.\n",
    "\n",
    "## query_player\n",
    "The `query_player` function allows you, a human opponent, to play the game. This function requires a `display` method to be implemented in your game class, so that successive game states can be displayed on the terminal, making it easier for you to visualize the game and play accordingly.\n",
    "\n",
    "## random_player\n",
    "The `random_player` is a function that plays random moves in the game. That's it. There isn't much more to this guy. \n",
    "\n",
    "## alphabeta_player\n",
    "The `alphabeta_player`, on the other hand, calls the `alphabeta_search` function, which returns the best move in the current game state. Thus, the `alphabeta_player` always plays the best move given a game state, assuming that the game tree is small enough to search entirely.\n",
    "\n",
    "## play_game\n",
    "The `play_game` function will be the one that will actually be used to play the game. You pass as arguments to it an instance of the game you want to play and the players you want in this game. Use it to play AI vs AI, AI vs human, or even human vs human matches!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# LET'S PLAY SOME GAMES!\n",
    "\n",
    "## Game52\n",
    "\n",
    "Let's start by experimenting with the `Fig52Game` first. For that we'll create an instance of the subclass Fig52Game inherited from the class Game:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "game52 = Fig52Game()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First we try out our `random_player(game, state)`. Given a game state it will give us a random move every time:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a1\n",
      "a3\n"
     ]
    }
   ],
   "source": [
    "print(random_player(game52, 'A'))\n",
    "print(random_player(game52, 'A'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `alphabeta_player(game, state)` will always give us the best move possible, for the relevant player (MAX or MIN):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a1\n",
      "b1\n",
      "c1\n"
     ]
    }
   ],
   "source": [
    "print( alphabeta_player(game52, 'A') )\n",
    "print( alphabeta_player(game52, 'B') )\n",
    "print( alphabeta_player(game52, 'C') )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What the `alphabeta_player` does is, it simply calls the method `alphabeta_full_search`. They both are essentially the same. In the module, both `alphabeta_full_search` and `minimax_decision` have been implemented. They both do the same job and return the same thing, which is, the best move in the current state. It's just that `alphabeta_full_search` is more efficient with regards to time because it prunes the search tree and hence, explores lesser number of states."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'a1'"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "minimax_decision('A', game52)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'a1'"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "alphabeta_search('A', game52)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Demonstrating the play_game function on the game52:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "B1\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "game52.play_game(alphabeta_player, alphabeta_player)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "B2\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "game52.play_game(alphabeta_player, random_player)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "current state:\n",
      "A\n",
      "available moves: ['a1', 'a2', 'a3']\n",
      "\n",
      "Your move? a1\n",
      "B1\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "game52.play_game(query_player, alphabeta_player)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "current state:\n",
      "B\n",
      "available moves: ['b1', 'b2', 'b3']\n",
      "\n",
      "Your move? b1\n",
      "B1\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "game52.play_game(alphabeta_player, query_player)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that if you are the first player then alphabeta_player plays as MIN, and if you are the second player then alphabeta_player plays as MAX. This happens because that's the way the game is defined in the class Fig52Game. Having a look at the code of this class should make it clear."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## TicTacToe\n",
    "\n",
    "Now let's play `TicTacToe`. First we initialize the game by creating an instance of the subclass TicTacToe inherited from the class Game:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "ttt = TicTacToe()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can print a state using the display method:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      ". . . \n",
      ". . . \n",
      ". . . \n"
     ]
    }
   ],
   "source": [
    "ttt.display(ttt.initial)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Hmm, so that's the initial state of the game; no X's and no O's.\n",
    "\n",
    "Let us create a new game state by ourselves to experiment:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "my_state = GameState(\n",
    "    to_move = 'X',\n",
    "    utility = '0',\n",
    "    board = {(1,1): 'X', (1,2): 'O', (1,3): 'X',\n",