intro_to_game_ai_and_reinforcement_learning/03-n-step-lookahead.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "896fa7b3",
   "metadata": {
    "papermill": {
     "duration": 0.012582,
     "end_time": "2021-08-27T03:00:13.682206",
     "exception": false,
     "start_time": "2021-08-27T03:00:13.669624",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "**This notebook is an exercise in the [Intro to Game AI and Reinforcement Learning](https://www.kaggle.com/learn/intro-to-game-ai-and-reinforcement-learning) course.  You can reference the tutorial at [this link](https://www.kaggle.com/alexisbcook/n-step-lookahead).**\n",
    "\n",
    "---\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b07c32be",
   "metadata": {
    "papermill": {
     "duration": 0.011123,
     "end_time": "2021-08-27T03:00:13.705199",
     "exception": false,
     "start_time": "2021-08-27T03:00:13.694076",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "# Introduction\n",
    "\n",
    "In the tutorial, you learned how to build a reasonably intelligent agent with the minimax algorithm.  In this exercise, you will check your understanding and submit your own agent to the competition."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "1d766a55",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2021-08-27T03:00:13.736937Z",
     "iopub.status.busy": "2021-08-27T03:00:13.736032Z",
     "iopub.status.idle": "2021-08-27T03:00:13.863032Z",
     "shell.execute_reply": "2021-08-27T03:00:13.862392Z",
     "shell.execute_reply.started": "2021-08-27T00:08:07.622854Z"
    },
    "papermill": {
     "duration": 0.14657,
     "end_time": "2021-08-27T03:00:13.863200",
     "exception": false,
     "start_time": "2021-08-27T03:00:13.716630",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "from learntools.core import binder\n",
    "binder.bind(globals())\n",
    "from learntools.game_ai.ex3 import *"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ee9d035e",
   "metadata": {
    "papermill": {
     "duration": 0.01116,
     "end_time": "2021-08-27T03:00:13.885884",
     "exception": false,
     "start_time": "2021-08-27T03:00:13.874724",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "### 1) A closer look\n",
    "\n",
    "The heuristic from the tutorial looks at all groups of four adjacent grid locations on the same row, column, or diagonal and assigns points for each occurrence of the following patterns:\n",
    "\n",
    "<center>\n",
    "<img src=\"https://i.imgur.com/3NvBEGL.png\" width=70%><br/>\n",
    "</center>\n",
    "\n",
    "Is it really necessary to use so many numbers to define the heuristic?  Consider simplifying it, as in the image below.\n",
    "\n",
    "<center>\n",
    "<img src=\"https://i.imgur.com/grViegG.png\" width=70%><br/>\n",
    "</center>\n",
    "\n",
    "How would each heuristic score the potential moves in the example below (where, in this case, the agent looks only one step ahead)?  Which heuristic would lead to the agent selecting the better move?\n",
    "\n",
    "<center>\n",
    "<img src=\"https://i.imgur.com/LWPLy7N.png\" width=100%><br/>\n",
    "</center>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "80d17e4d",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2021-08-27T03:00:13.916563Z",
     "iopub.status.busy": "2021-08-27T03:00:13.915952Z",
     "iopub.status.idle": "2021-08-27T03:00:13.918995Z",
     "shell.execute_reply": "2021-08-27T03:00:13.918408Z",
     "shell.execute_reply.started": "2021-08-27T00:09:43.686110Z"
    },
    "papermill": {
     "duration": 0.021146,
     "end_time": "2021-08-27T03:00:13.919133",
     "exception": false,
     "start_time": "2021-08-27T03:00:13.897987",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "#q_1.hint()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "8af2d959",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2021-08-27T03:00:13.950547Z",
     "iopub.status.busy": "2021-08-27T03:00:13.949573Z",
     "iopub.status.idle": "2021-08-27T03:00:13.956137Z",
     "shell.execute_reply": "2021-08-27T03:00:13.955543Z",
     "shell.execute_reply.started": "2021-08-27T00:10:05.414287Z"
    },
    "papermill": {
     "duration": 0.025025,
     "end_time": "2021-08-27T03:00:13.956268",
     "exception": false,
     "start_time": "2021-08-27T03:00:13.931243",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "application/javascript": [
       "parent.postMessage({\"jupyterEvent\": \"custom.exercise_interaction\", \"data\": {\"outcomeType\": 1, \"valueTowardsCompletion\": 0.2, \"interactionType\": 1, \"questionType\": 4, \"questionId\": \"1_WorseHeuristic\", \"learnToolsVersion\": \"0.3.4\", \"failureMessage\": \"\", \"exceptionClass\": \"\", \"trace\": \"\"}}, \"*\")"
      ],
      "text/plain": [
       "<IPython.core.display.Javascript object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/markdown": [
       "<span style=\"color:#33cc33\">Correct:</span> \n",
       "\n",
       "The first heuristic is guaranteed to select column 2 to block the opponent from winning.  The second heuristic selects either column 2 or column 3 (where it selects each with 50% probability). Thus, for this game board, the first heuristic is better. In general, we can expect that the first heuristic is a better heuristic, since we cannot trust the second heuristic to block the opponent from winning."
      ],
      "text/plain": [
       "Correct: \n",
       "\n",
       "The first heuristic is guaranteed to select column 2 to block the opponent from winning.  The second heuristic selects either column 2 or column 3 (where it selects each with 50% probability). Thus, for this game board, the first heuristic is better. In general, we can expect that the first heuristic is a better heuristic, since we cannot trust the second heuristic to block the opponent from winning."
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Check your answer (Run this code cell to receive credit!)\n",
    "#q_1.solution()\n",
    "q_1.check()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "962cb871",
   "metadata": {
    "papermill": {
     "duration": 0.011902,
     "end_time": "2021-08-27T03:00:13.980992",
     "exception": false,
     "start_time": "2021-08-27T03:00:13.969090",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "### 2) Count the leaves\n",
    "\n",
    "In the tutorial, we worked with a small game tree.\n",
    "\n",
    "<center>\n",
    "<img src=\"https://i.imgur.com/BrRe7Bu.png\" width=90%><br/>\n",
    "</center>\n",
    "\n",
    "The game tree above has 8 leaf nodes that appear at the bottom of the tree.  By definition, \"leaf nodes\" in a game tree are nodes that don't have nodes below them.\n",
    "\n",
    "In the ConnectX competition, the game trees will be much larger!  \n",
    "\n",
    "To see this, consider a minimax agent that is trying to plan its first move, where all columns in the game board are  empty.  Say the agent builds a game tree of depth 3.  How many leaf nodes are in the game tree?  \n",
    "\n",
    "Use your answer to fill in the blank below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "d1dafee2",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2021-08-27T03:00:14.011207Z",
     "iopub.status.busy": "2021-08-27T03:00:14.010456Z",
     "iopub.status.idle": "2021-08-27T03:00:14.016951Z",
     "shell.execute_reply": "2021-08-27T03:00:14.017407Z",
     "shell.execute_reply.started": "2021-08-27T00:15:28.510014Z"
    },
    "papermill": {
     "duration": 0.024259,
     "end_time": "2021-08-27T03:00:14.017562",
     "exception": false,
     "start_time": "2021-08-27T03:00:13.993303",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "application/javascript": [
       "parent.postMessage({\"jupyterEvent\": \"custom.exercise_interaction\", \"data\": {\"outcomeType\": 1, \"valueTowardsCompletion\": 0.2, \"interactionType\": 1, \"questionType\": 1, \"questionId\": \"2_NumLeaves\", \"learnToolsVersion\": \"0.3.4\", \"failureMessage\": \"\", \"exceptionClass\": \"\", \"trace\": \"\"}}, \"*\")"
      ],
      "text/plain": [
       "<IPython.core.display.Javascript object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/markdown": [
       "<span style=\"color:#33cc33\">Correct</span>"
      ],
      "text/plain": [
       "Correct"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Fill in the blank\n",
    "num_leaves = 7 ** 3\n",
    "\n",
    "# Check your answer\n",
    "q_2.check()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "07ee3433",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2021-08-27T03:00:14.048212Z",
     "iopub.status.busy": "2021-08-27T03:00:14.047418Z",
     "iopub.status.idle": "2021-08-27T03:00:14.050808Z",
     "shell.execute_reply": "2021-08-27T03:00:14.050291Z",
     "shell.execute_reply.started": "2021-08-27T00:15:32.242062Z"
    },
    "papermill": {
     "duration": 0.020075,
     "end_time": "2021-08-27T03:00:14.050946",
     "exception": false,
     "start_time": "2021-08-27T03:00:14.030871",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Lines below will give you a hint or solution code\n",
    "#q_2.hint()\n",
    "#q_2.solution()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9a11e42a",
   "metadata": {
    "papermill": {
     "duration": 0.012744,
     "end_time": "2021-08-27T03:00:14.076971",
     "exception": false,
     "start_time": "2021-08-27T03:00:14.064227",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "### 3) Which move will the agent select?\n",
    "\n",
    "In this question, you'll check your understanding of the minimax algorithm.  Remember that with this algorithm, \n",
    "> The agent chooses moves to get a score that is as high as possible, and it assumes the opponent will counteract this by choosing moves to force the score to be as low as possible.\n",
    "\n",
    "Consider the toy example below of a game tree that the agent will use to select its next move.  \n",
    "<center>\n",
    "<img src=\"https://i.imgur.com/QlfWGM9.png\" width=80%><br/>\n",
    "</center>\n",
    "\n",
    "Which move will the agent select?  Use your answer to set the value of the `selected_move` variable below.  Your answer should be one of `1`, `2`, or `3`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "a18949f1",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2021-08-27T03:00:14.108740Z",
     "iopub.status.busy": "2021-08-27T03:00:14.108153Z",
     "iopub.status.idle": "2021-08-27T03:00:14.114257Z",
     "shell.execute_reply": "2021-08-27T03:00:14.113746Z",
     "shell.execute_reply.started": "2021-08-27T00:17:42.897942Z"
    },
    "papermill": {
     "duration": 0.023343,
     "end_time": "2021-08-27T03:00:14.114389",
     "exception": false,
     "start_time": "2021-08-27T03:00:14.091046",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "application/javascript": [
       "parent.postMessage({\"jupyterEvent\": \"custom.exercise_interaction\", \"data\": {\"outcomeType\": 1, \"valueTowardsCompletion\": 0.2, \"interactionType\": 1, \"questionType\": 2, \"questionId\": \"3_WhichMove\", \"learnToolsVersion\": \"0.3.4\", \"failureMessage\": \"\", \"exceptionClass\": \"\", \"trace\": \"\"}}, \"*\")"
      ],
      "text/plain": [
       "<IPython.core.display.Javascript object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/markdown": [
       "<span style=\"color:#33cc33\">Correct</span>"
      ],
      "text/plain": [
       "Correct"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Fill in the blank\n",
    "selected_move = 3\n",
    "\n",
    "# Check your answer\n",
    "q_3.check()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "97b07361",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2021-08-27T03:00:14.147040Z",
     "iopub.status.busy": "2021-08-27T03:00:14.146373Z",
     "iopub.status.idle": "2021-08-27T03:00:14.148890Z",
     "shell.execute_reply": "2021-08-27T03:00:14.148347Z",
     "shell.execute_reply.started": "2021-08-27T00:17:45.671787Z"
    },
    "papermill": {
     "duration": 0.020695,
     "end_time": "2021-08-27T03:00:14.149029",
     "exception": false,
     "start_time": "2021-08-27T03:00:14.128334",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Lines below will give you a hint or solution code\n",
    "#q_3.hint()\n",
    "#q_3.solution()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c58c74d7",
   "metadata": {
    "papermill": {
     "duration": 0.013946,
     "end_time": "2021-08-27T03:00:14.176929",
     "exception": false,
     "start_time": "2021-08-27T03:00:14.162983",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "### 4) Examine the assumptions\n",
    "\n",
    "The minimax agent assumes that its opponent plays optimally (with respect to the heuristic, and using a game tree of limited depth).  But this is almost never the case, in practice: it's far more likely for the agent to encounter a suboptimal (that is: worse than optimal) opponent.  \n",
    "\n",
    "Say the minimax agent encounters a suboptimal opponent. Should we expect the minimax agent to still play the game well, despite the contradiction with its assumptions?  If so, why?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "484da66c",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2021-08-27T03:00:14.208886Z",
     "iopub.status.busy": "2021-08-27T03:00:14.208187Z",
     "iopub.status.idle": "2021-08-27T03:00:14.212489Z",
     "shell.execute_reply": "2021-08-27T03:00:14.211995Z",
     "shell.execute_reply.started": "2021-08-27T00:19:07.442748Z"
    },
    "papermill": {
     "duration": 0.021228,
     "end_time": "2021-08-27T03:00:14.212620",
     "exception": false,
     "start_time": "2021-08-27T03:00:14.191392",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "#q_4.hint()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "479851cf",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2021-08-27T03:00:14.246849Z",
     "iopub.status.busy": "2021-08-27T03:00:14.245961Z",
     "iopub.status.idle": "2021-08-27T03:00:14.251809Z",
     "shell.execute_reply": "2021-08-27T03:00:14.251142Z",
     "shell.execute_reply.started": "2021-08-27T00:22:18.278468Z"
    },
    "papermill": {
     "duration": 0.024666,
     "end_time": "2021-08-27T03:00:14.251947",
     "exception": false,
     "start_time": "2021-08-27T03:00:14.227281",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "application/javascript": [
       "parent.postMessage({\"jupyterEvent\": \"custom.exercise_interaction\", \"data\": {\"outcomeType\": 1, \"valueTowardsCompletion\": 0.2, \"interactionType\": 1, \"questionType\": 4, \"questionId\": \"4_Assumptions\", \"learnToolsVersion\": \"0.3.4\", \"failureMessage\": \"\", \"exceptionClass\": \"\", \"trace\": \"\"}}, \"*\")"
      ],
      "text/plain": [
       "<IPython.core.display.Javascript object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/markdown": [
       "<span style=\"color:#33cc33\">Correct:</span> \n",
       "\n",
       "We can still expect the minimax agent to perform well. On a high level, assuming an optimal opponent simply overestimates the opponent, but does not break the algorithm.  The effect of overestimating the opponent is merely that the minimax agent will take longer to win, than if it had a more accurate understanding of its opponent.  For instance, the minimax agent is highly unlikely to select the same column three times in its first three moves (since it assumes an optimal opponent that will certainly block the winning play in the next move), but this is not a bad initial strategy for playing against an agent that selects columns completely at random."
      ],
      "text/plain": [
       "Correct: \n",
       "\n",
       "We can still expect the minimax agent to perform well. On a high level, assuming an optimal opponent simply overestimates the opponent, but does not break the algorithm.  The effect of overestimating the opponent is merely that the minimax agent will take longer to win, than if it had a more accurate understanding of its opponent.  For instance, the minimax agent is highly unlikely to select the same column three times in its first three moves (since it assumes an optimal opponent that will certainly block the winning play in the next move), but this is not a bad initial strategy for playing against an agent that selects columns completely at random."
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Check your answer (Run this code cell to receive credit!)\n",
    "#q_4.solution()\n",
    "q_4.check()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fa82347d",
   "metadata": {
    "papermill": {
     "duration": 0.014319,
     "end_time": "2021-08-27T03:00:14.281194",
     "exception": false,
     "start_time": "2021-08-27T03:00:14.266875",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "### 5) Submit to the competition\n",
    "\n",
    "Now, it's time to submit an agent to the competition!  Use the next code cell to define an agent.  (You can see an example of how to write a valid agent in **[this notebook](https://www.kaggle.com/alexisbcook/create-a-connectx-agent)**.)\n",
    "\n",
    "If you decide to use the minimax code from the tutorial, you might like to add [**alpha-beta pruning**](https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning) to decrease the computation time (i.e., get the minimax algorithm to run much faster!).  In this case, \"alpha\" and \"beta\" to refer to two values that are maintained while the algorithm is running, that help to identify early stopping conditions.  \n",
    "\n",
    "Without alpha-beta pruning, minimax evaluates each leaf node.  With alpha-beta pruning, minimax only evaluates nodes that could provide information that affects the agent's choice of action.  Put another way, it identifies nodes that could not possibly affect the final result and avoids evaluating them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "acb3b689",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2021-08-27T03:00:14.319735Z",
     "iopub.status.busy": "2021-08-27T03:00:14.319026Z",
     "iopub.status.idle": "2021-08-27T03:00:14.337488Z",
     "shell.execute_reply": "2021-08-27T03:00:14.337993Z",
     "shell.execute_reply.started": "2021-08-27T02:45:58.550734Z"
    },
    "papermill": {
     "duration": 0.042247,
     "end_time": "2021-08-27T03:00:14.338172",
     "exception": false,
     "start_time": "2021-08-27T03:00:14.295925",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "def my_agent(obs, config):\n",
    "    # Your code here: Amend the agent!\n",
    "    import random\n",
    "    import numpy as np\n",
    "    \n",
    "    # How deep to make the game tree: higher values take longer to run!\n",
    "    N_STEPS = 4\n",
    "\n",
    "    # Gets board at next step if agent drops piece in selected column\n",
    "    def drop_piece(grid, col, mark, config):\n",
    "        next_grid = grid.copy()\n",
    "        for row in range(config.rows-1, -1, -1):\n",
    "            if next_grid[row][col] == 0:\n",
    "                break\n",
    "        next_grid[row][col] = mark\n",
    "        return next_grid\n",
    "\n",
    "    # Helper function for get_heuristic: checks if window satisfies heuristic conditions\n",
    "    def check_window(window, num_discs, piece, config):\n",
    "        return (window.count(piece) == num_discs and window.count(0) == config.inarow-num_discs)\n",
    "\n",
    "    # Helper function for get_heuristic: counts number of windows satisfying specified heuristic conditions\n",
    "    def count_windows(grid, num_discs, piece, config):\n",
    "        num_windows = 0\n",
    "        # horizontal\n",
    "        for row in range(config.rows):\n",
    "            for col in range(config.columns-(config.inarow-1)):\n",
    "                window = list(grid[row, col:col+config.inarow])\n",
    "                if check_window(window, num_discs, piece, config):\n",
    "                    num_windows += 1\n",
    "        # vertical\n",
    "        for row in range(config.rows-(config.inarow-1)):\n",
    "            for col in range(config.columns):\n",
    "                window = list(grid[row:row+config.inarow, col])\n",
    "                if check_window(window, num_discs, piece, config):\n",
    "                    num_windows += 1\n",
    "        # positive diagonal\n",
    "        for row in range(config.rows-(config.inarow-1)):\n",
    "            for col in range(config.columns-(config.inarow-1)):\n",
    "                window = list(grid[range(row, row+config.inarow), range(col, col+config.inarow)])\n",
    "                if check_window(window, num_discs, piece, config):\n",
    "                    num_windows += 1\n",
    "        # negative diagonal\n",
    "        for row in range(config.inarow-1, config.rows):\n",
    "            for col in range(config.columns-(config.inarow-1)):\n",
    "                window = list(grid[range(row, row-config.inarow, -1), range(col, col+config.inarow)])\n",
    "                if check_window(window, num_discs, piece, config):\n",
    "                    num_windows += 1\n",
    "        return num_windows\n",
    "    \n",
    "    # Helper function for minimax: calculates value of heuristic for grid\n",
    "    def get_heuristic(grid, mark, config):\n",
    "        num_threes = count_windows(grid, 3, mark, config)\n",
    "        num_fours = count_windows(grid, 4, mark, config)\n",
    "        num_threes_opp = count_windows(grid, 3, mark%2+1, config)\n",
    "        num_fours_opp = count_windows(grid, 4, mark%2+1, config)\n",
    "        score = num_threes - 1e2*num_threes_opp - 1e4*num_fours_opp + 1e6*num_fours\n",
    "        return score   \n",
    "    \n",
    "    # Uses minimax to calculate value of dropping piece in selected column\n",
    "    def score_move(grid, col, mark, config, nsteps):\n",
    "        next_grid = drop_piece(grid, col, mark, config)\n",
    "        score = minimax(next_grid, nsteps-1, False, -np.Inf, np.Inf, mark, config)\n",
    "        return score\n",
    "\n",
    "    # Helper function for minimax: checks if agent or opponent has four in a row in the window\n",
    "    def is_terminal_window(window, config):\n",
    "        return window.count(1) == config.inarow or window.count(2) == config.inarow\n",
    "\n",
    "    # Helper function for minimax: checks if game has ended\n",
    "    def is_terminal_node(grid, config):\n",
    "        # Check for draw \n",
    "        if list(grid[0, :]).count(0) == 0:\n",
    "            return True\n",
    "        # Check for win: horizontal, vertical, or diagonal\n",
    "        # horizontal \n",
    "        for row in range(config.rows):\n",
    "            for col in range(config.columns-(config.inarow-1)):\n",
    "                window = list(grid[row, col:col+config.inarow])\n",
    "                if is_terminal_window(window, config):\n",
    "                    return True\n",
    "        # vertical\n",
    "        for row in range(config.rows-(config.inarow-1)):\n",
    "            for col in range(config.columns):\n",
    "                window = list(grid[row:row+config.inarow, col])\n",
    "                if is_terminal_window(window, config):\n",
    "                    return True\n",
    "        # positive diagonal\n",
    "        for row in range(config.rows-(config.inarow-1)):\n",
    "            for col in range(config.columns-(config.inarow-1)):\n",
    "                window = list(grid[range(row, row+config.inarow), range(col, col+config.inarow)])\n",
    "                if is_terminal_window(window, config):\n",
    "                    return True\n",
    "        # negative diagonal\n",
    "        for row in range(config.inarow-1, config.rows):\n",
    "            for col in range(config.columns-(config.inarow-1)):\n",
    "                window = list(grid[range(row, row-config.inarow, -1), range(col, col+config.inarow)])\n",
    "                if is_terminal_window(window, config):\n",
    "                    return True\n",
    "        return False\n",
    "\n",
    "    # Minimax implementation\n",
    "    def minimax(node, depth, maximizingPlayer, alpha, beta, mark, config):\n",
    "        #is_terminal = is_terminal_node(node, config)\n",
    "        #if depth == 0 or is_terminal:\n",
    "        if depth == 0 or is_terminal_node(node, config):\n",
    "            return get_heuristic(node, mark, config)\n",
    "        valid_moves = [c for c in range(config.columns) if node[0][c] == 0]\n",
    "        if maximizingPlayer:\n",
    "            value = -np.Inf\n",
    "            for col in valid_moves:\n",
    "                child = drop_piece(node, col, mark, config)\n",
    "                value = max(value, minimax(child, depth-1, False, alpha, beta, mark, config))\n",
    "                alpha = max(value, alpha)\n",
    "                if alpha >= beta:\n",
    "                    break\n",
    "            return value\n",
    "        else:\n",
    "            value = np.Inf\n",
    "            for col in valid_moves:\n",
    "                child = drop_piece(node, col, mark%2+1, config)\n",
    "                value = min(value, minimax(child, depth-1, True, alpha, beta, mark, config))\n",
    "                beta = min(value, beta)\n",
    "                if alpha >= beta:\n",
    "                    break\n",
    "            return value\n",
    "        \n",
    "        \n",
    "    # Get list of valid moves\n",
    "    valid_moves = [col for col in range(config.columns) if obs.board[col] == 0]\n",
    "    # Convert the board to a 2D grid\n",
    "    grid = np.asarray(obs.board).reshape(config.rows, config.columns)\n",
    "    # Use the heuristic to assign a score to each possible board in the next step\n",
    "    scores = dict(zip(valid_moves, [score_move(grid, col, obs.mark, config, N_STEPS) for col in valid_moves]))\n",
    "    # Get a list of columns (moves) that maximize the heuristic\n",
    "    max_cols = [key for key in scores.keys() if scores[key] == max(scores.values())]\n",
    "    # Select at random from the maximizing columns\n",
    "    return random.choice(max_cols)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "7b918967",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2021-08-27T03:00:14.372468Z",
     "iopub.status.busy": "2021-08-27T03:00:14.371859Z",
     "iopub.status.idle": "2021-08-27T03:00:14.377810Z",
     "shell.execute_reply": "2021-08-27T03:00:14.377223Z",
     "shell.execute_reply.started": "2021-08-27T00:45:49.634478Z"
    },
    "papermill": {
     "duration": 0.025286,
     "end_time": "2021-08-27T03:00:14.377941",
     "exception": false,
     "start_time": "2021-08-27T03:00:14.352655",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "application/javascript": [
       "parent.postMessage({\"jupyterEvent\": \"custom.exercise_interaction\", \"data\": {\"outcomeType\": 1, \"valueTowardsCompletion\": 0.2, \"interactionType\": 1, \"questionType\": 2, \"questionId\": \"5_JustSubmitEx3\", \"learnToolsVersion\": \"0.3.4\", \"failureMessage\": \"\", \"exceptionClass\": \"\", \"trace\": \"\"}}, \"*\")"
      ],
      "text/plain": [
       "<IPython.core.display.Javascript object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/markdown": [
       "<span style=\"color:#33cc33\">Thank you for creating an agent!</span>"
      ],
      "text/plain": [
       "Thank you for creating an agent!"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Run this code cell to get credit for creating an agent\n",
    "q_5.check()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "8762ba82",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2021-08-27T03:00:14.412626Z",
     "iopub.status.busy": "2021-08-27T03:00:14.412045Z",
     "iopub.status.idle": "2021-08-27T03:00:14.426040Z",
     "shell.execute_reply": "2021-08-27T03:00:14.426912Z"
    },
    "papermill": {
     "duration": 0.033097,
     "end_time": "2021-08-27T03:00:14.427189",
     "exception": false,
     "start_time": "2021-08-27T03:00:14.394092",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<function my_agent at 0x7f02df4acef0> written to submission.py\n"
     ]
    }
   ],
   "source": [
    "import inspect\n",
    "import os\n",
    "\n",
    "def write_agent_to_file(function, file):\n",
    "    with open(file, \"a\" if os.path.exists(file) else \"w\") as f:\n",
    "        f.write(inspect.getsource(function))\n",
    "        print(function, \"written to\", file)\n",
    "\n",
    "write_agent_to_file(my_agent, \"submission.py\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a93d480b",
   "metadata": {
    "papermill": {
     "duration": 0.015428,
     "end_time": "2021-08-27T03:00:14.459410",
     "exception": false,
     "start_time": "2021-08-27T03:00:14.443982",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "Then, follow these steps to submit your agent to the competition:\n",
    "1. Begin by clicking on the blue **Save Version** button in the top right corner of the window.  This will generate a pop-up window.  \n",
    "2. Ensure that the **Save and Run All** option is selected, and then click on the blue **Save** button.\n",
    "3. This generates a window in the bottom left corner of the notebook.  After it has finished running, click on the number to the right of the **Save Version** button.  This pulls up a list of versions on the right of the screen.  Click on the ellipsis **(...)** to the right of the most recent version, and select **Open in Viewer**.  This brings you into view mode of the same page. You will need to scroll down to get back to these instructions.\n",
    "4. Click on the **Output** tab on the right of the screen.  Then, click on the file you would like to submit, and click on the blue **Submit** button to submit your results to the leaderboard.\n",
    "\n",
    "You have now successfully submitted to the competition!\n",
    "\n",
    "If you want to keep working to improve your performance, select the blue **Edit** button in the top right of the screen. Then you can change your code and repeat the process. There's a lot of room to improve, and you will climb up the leaderboard as you work.\n",
    "\n",
    "\n",
    "Go to **\"My Submissions\"** to view your score and episodes being played.\n",
    "\n",
    "# Keep going\n",
    "\n",
    "Move on to learn how to **[use deep reinforcement learning](https://www.kaggle.com/alexisbcook/deep-reinforcement-learning)** to develop an agent without a heuristic!"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bb43618e",
   "metadata": {
    "papermill": {
     "duration": 0.015613,
     "end_time": "2021-08-27T03:00:14.490824",
     "exception": false,
     "start_time": "2021-08-27T03:00:14.475211",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "---\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "*Have questions or comments? Visit the [Learn Discussion forum](https://www.kaggle.com/learn-forum/161477) to chat with other Learners.*"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.7.10"
  },
  "papermill": {
   "default_parameters": {},
   "duration": 8.809537,
   "end_time": "2021-08-27T03:00:15.115133",
   "environment_variables": {},
   "exception": null,
   "input_path": "__notebook__.ipynb",
   "output_path": "__notebook__.ipynb",
   "parameters": {},
   "start_time": "2021-08-27T03:00:06.305596",
   "version": "2.3.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}