2_isolation_player.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "# Game-playing Agent\n",
    "\n",
    "Notebook version of the project [Build a Game-playing Agent](https://github.com/udacity/AIND-Isolation) from [Udacity's Artificial Intelligence Nanodegree](https://www.udacity.com/course/artificial-intelligence-nanodegree--nd889) <br>\n",
    "\n",
    "\n",
    "**Goal**: Implement an effective adversarial search agent to play the game **Isolation**\n",
    "\n",
    "Isolation is a deterministic, two-player game of perfect information in which the players alternate turns moving a single piece from one cell to another on a board.  Whenever either player occupies a cell, that cell becomes blocked for the remainder of the game.  The first player with no remaining legal moves loses, and the opponent is declared the winner.\n",
    "\n",
    "This project uses a version of Isolation where each agent is restricted to L-shaped movements (like a knight in chess) on a rectangular grid (like a chess or checkerboard).  The agents can move to any open cell on the board that is 2-rows and 1-column or 2-columns and 1-row away from their current position on the board. Movements are blocked at the edges of the board (the board does not wrap around), however, the player can \"jump\" blocked or occupied spaces (just like a knight in chess).\n",
    "\n",
    "Additionally, agents will have a fixed time limit each turn to search for the best move and respond.  If the time limit expires during a player's turn, that player forfeits the match, and the opponent wins.\n",
    "\n",
    "These rules are implemented in the `isolation.Board` class provided in the repository. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The final evaluation will estimate the strength rating of student-agent with iterative deepening and\n",
    "a custom heuristic evaluation function against fixed-depth minimax and\n",
    "alpha-beta search agents by running a round-robin tournament for the student\n",
    "agent. The student agent plays a fixed number of \"fair\" matches against each test\n",
    "agent. The matches are fair because the board is initialized randomly for both\n",
    "players, and the players play each match twice -- switching the player order\n",
    "between games. This helps to correct for imbalances in the game due to both\n",
    "starting position and initiative.\n",
    "\n",
    "For example, if the random moves chosen for initialization are (5, 2) and\n",
    "(1, 3), then the first match will place agent A at (5, 2) as player 1 and\n",
    "agent B at (1, 3) as player 2 then play to conclusion; the agents swap\n",
    "initiative in the second match with agent B at (5, 2) as player 1 and agent A at\n",
    "(1, 3) as player 2."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sample players\n",
    "\n",
    "Collection of player classes for comparison with the custom agent and example heuristic functions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from random import randint\n",
    "\n",
    "\n",
    "def null_score(game, player):\n",
    "    \"\"\"This heuristic presumes no knowledge for non-terminal states, and returns the same\n",
    "    uninformative value for all other states. \"\"\"\n",
    "\n",
    "    if game.is_loser(player):\n",
    "        return float(\"-inf\")\n",
    "    if game.is_winner(player):\n",
    "        return float(\"inf\")\n",
    "    return 0.\n",
    "\n",
    "\n",
    "def open_move_score(game, player):\n",
    "    \"\"\"The basic evaluation function dthat outputs a score equal to the number of moves open\n",
    "    for your computer player on the board. \"\"\"\n",
    "\n",
    "    if game.is_loser(player):\n",
    "        return float(\"-inf\")\n",
    "    if game.is_winner(player):\n",
    "        return float(\"inf\")\n",
    "    return float(len(game.get_legal_moves(player)))\n",
    "\n",
    "\n",
    "def improved_score(game, player):\n",
    "    \"\"\"The \"Improved\" evaluation function that outputs a score equal to the difference in the \n",
    "    number of moves available to the two players. \"\"\"\n",
    "\n",
    "    if game.is_loser(player):\n",
    "        return float(\"-inf\")\n",
    "    if game.is_winner(player):\n",
    "        return float(\"inf\")\n",
    "    own_moves = len(game.get_legal_moves(player))\n",
    "    opp_moves = len(game.get_legal_moves(game.get_opponent(player)))\n",
    "    return float(own_moves - opp_moves)\n",
    "\n",
    "\n",
    "class RandomPlayer():\n",
    "    \"\"\"Player that chooses a move randomly.\"\"\"\n",
    "\n",
    "    def get_move(self, game, legal_moves, time_left):\n",
    "        \"\"\"Randomly select a move from the available legal moves.\"\"\"\n",
    "\n",
    "        if not legal_moves:\n",
    "            return (-1, -1)\n",
    "        return legal_moves[randint(0, len(legal_moves) - 1)]\n",
    "\n",
    "\n",
    "class GreedyPlayer():\n",
    "    \"\"\"Player that chooses next move to maximize heuristic score. This is  equivalent to a\n",
    "    minimax search agent with a search depth of one.  \"\"\"\n",
    "\n",
    "    def __init__(self, score_fn=open_move_score):\n",
    "        self.score = score_fn\n",
    "\n",
    "    def get_move(self, game, legal_moves, time_left):\n",
    "\n",
    "        if not legal_moves:\n",
    "            return (-1, -1)\n",
    "        _, move = max([(self.score(game.forecast_move(m), self), m) for m in legal_moves])\n",
    "        return move\n",
    "\n",
    "\n",
    "class HumanPlayer():\n",
    "    \"\"\"Player that chooses a move according to user's input.\"\"\"\n",
    "\n",
    "    def get_move(self, game, legal_moves, time_left):\n",
    "        \"\"\"\n",
    "        Select a move from the available legal moves based on user input at the\n",
    "        terminal.  If testing with this player, remember to disable move timeout in\n",
    "        the call to `Board.play()`. \"\"\"\n",
    "\n",
    "        if not legal_moves:\n",
    "            return (-1, -1)\n",
    "\n",
    "        print(('\\t'.join(['[%d] %s' % (i, str(move)) for i, move in enumerate(legal_moves)])))\n",
    "\n",
    "        valid_choice = False\n",
    "        while not valid_choice:\n",
    "            try:\n",
    "                index = int(input('Select move index:'))\n",
    "                valid_choice = 0 <= index < len(legal_moves)\n",
    "\n",
    "                if not valid_choice:\n",
    "                    print('Illegal move! Try again.')\n",
    "\n",
    "            except ValueError:\n",
    "                print('Invalid index! Try again.')\n",
    "\n",
    "        return legal_moves[index]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Custom heuristic score: Lock, mobility, and moves with a tuned linear function\n",
    "\n",
    "\n",
    "Zero-sum function based on player’s mobility (moves / blank_spaces ), also predicting if one player can lock the other in its next ply:\n",
    "\n",
    "- Predict if the player is about to win or lose when the adversary has no move available for its next play: +inf, -inf <br> This case is  not detected by game.is_winner() or game.is_loser() due their inactive/active player condition.\n",
    "\n",
    "- Predict if a player can reach the unique move available to the adversary, thus winning the game: +inf, inf\n",
    "\n",
    "- The usual scenario is valued as: `score = A * own_mobility + B * opp_mobility + C * own_moves + D * opp_moves`. Mobility is defined as the ratio between the available move of the player and the total available cells of the board. Thus the value of looking for more legal moves will be increased when the game is about to end due to lack of empty cells. After a few tournaments, the selected parameters were tuned to: `A = 10, B = -10, C = 1, D = 0`\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def custom_score(game, player):\n",
    "    \"\"\"Calculate the heuristic value of a game state from the point of view\n",
    "    of the given player.\n",
    "\n",
    "    Parameters\n",
    "    ----------\n",
    "    game : `isolation.Board`\n",
    "        An instance of `isolation.Board` encoding the current state of the\n",
    "        game (e.g., player locations and blocked cells).\n",
    "\n",
    "    player : object\n",
    "        A player instance in the current game (i.e., an object corresponding to\n",
    "        one of the player objects `game.__player_1__` or `game.__player_2__`.)\n",
    "\n",
    "    Returns\n",
    "    -------\n",
    "    float\n",
    "        The heuristic value of the current game state to the specified player.\n",
    "    \"\"\"\n",
    "\n",
    "    if game.is_loser(player):\n",
    "        return float(\"-inf\")\n",
    "    if game.is_winner(player):\n",
    "        return float(\"inf\")\n",
    "\n",
    "    own_moves_list = game.get_legal_moves(player)\n",
    "    own_moves = len(own_moves_list)\n",
    "\n",
    "    opp_moves_list = (game.get_legal_moves(game.get_opponent(player)))\n",
    "    opp_moves = len(opp_moves_list)\n",
    "\n",
    "    # game.is_loser() game.is_winner depends on the active player.\n",
    "    # These cases can occur. e.g.: Opponent has no moves while Own is active\n",
    "    if opp_moves == 0:\n",
    "        return float(\"inf\")\n",
    "    if own_moves == 0:\n",
    "        return float(\"-inf\")\n",
    "    # Thus we can predict 1 ply more\n",
    "\n",
    "    # This easy killing move  can also be predicted:\n",
    "    # Lock the opponent if, in your turn, you can get to its unique move\n",
    "    if (player == game.active_player and opp_moves == 1\n",
    "            and opp_moves_list[0] in own_moves_list):\n",
    "        return float(\"inf\")\n",
    "    # opposite case\n",
    "    if (player != game.active_player and own_moves == 1\n",
    "            and own_moves_list[0] in opp_moves_list):\n",
    "        return float(\"-inf\")\n",
    "\n",
    "    # heuristic values for the rest of the cases\n",
    "    blank_spaces = game.width * game.height - game.move_count\n",
    "    own_mobility = own_moves / blank_spaces\n",
    "    opp_mobility = opp_moves / blank_spaces\n",
    "\n",
    "    score = 10 * (own_mobility - opp_mobility) + own_moves\n",
    "\n",
    "    return float(score)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Custom Player\n",
    "\n",
    "Game-playing agent that chooses a move using your evaluation function and a depth-limited minimax algorithm with alpha-beta pruning; also making sure it properly uses minimax and alpha-beta to return a good move before the search time limit expires.\n",
    "    \n",
    "\n",
    "- `CustomPlayer.minimax()`:   implement minimax search\n",
    "- `CustomPlayer.alphabeta()`: implement minimax search with alpha-beta pruning\n",
    "- `CustomPlayer.get_move()`:  implement fixed-depth and iterative deepening search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class CustomPlayer:\n",
    "    \"\"\"\n",
    "    Parameters\n",
    "    ----------\n",
    "    search_depth : int (optional)\n",
    "        A strictly positive integer (i.e., 1, 2, 3,...) for the number of\n",
    "        layers in the game tree to explore for fixed-depth search. (i.e., a\n",
    "        depth of one (1) would only explore the immediate sucessors of the\n",
    "        current state.)\n",
    "\n",
    "    score_fn : callable (optional)\n",
    "        A function to use for heuristic evaluation of game states.\n",
    "\n",
    "    iterative : boolean (optional)\n",
    "        Flag indicating whether to perform fixed-depth search (False) or\n",
    "        iterative deepening search (True).\n",
    "\n",
    "    method : {'minimax', 'alphabeta'} (optional)\n",
    "        The name of the search method to use in get_move().\n",
    "\n",
    "    timeout : float (optional)\n",
    "        Time remaining (in milliseconds) when search is aborted. Should be a\n",
    "        positive value large enough to allow the function to return before the\n",
    "        timer expires.\n",
    "    \"\"\"\n",
    "\n",
    "    def __init__(self,\n",
    "                 search_depth=3,\n",
    "                 score_fn=custom_score,\n",
    "                 iterative=True,\n",
    "                 method='minimax',\n",
    "                 timeout=10.):\n",
    "        self.search_depth = search_depth\n",
    "        self.iterative = iterative\n",
    "        self.score = score_fn\n",
    "        self.method = method\n",
    "        self.time_left = None\n",
    "        self.TIMER_THRESHOLD = timeout\n",
    "\n",
    "    def get_move(self, game, legal_moves, time_left):\n",
    "        \"\"\"Search for the best move from the available legal moves and return a\n",
    "        result before the time limit expires.\n",
    "\n",
    "        Parameters\n",
    "        ----------\n",
    "        game : `isolation.Board`\n",
    "            An instance of `isolation.Board` encoding the current state of the\n",
    "            game (e.g., player locations and blocked cells).\n",
    "\n",
    "        legal_moves : list<(int, int)>\n",
    "            A list containing legal moves. Moves are encoded as tuples of pairs\n",
    "            of ints defining the next (row, col) for the agent to occupy.\n",
    "\n",
    "        time_left : callable\n",
    "            A function that returns the number of milliseconds left in the\n",
    "            current turn. Returning with any less than 0 ms remaining forfeits\n",
    "            the game.\n",
    "\n",
    "        Returns\n",
    "        -------\n",
    "        (int, int)\n",
    "            Board coordinates corresponding to a legal move; may return\n",
    "            (-1, -1) if there are no available legal moves.\n",
    "        \"\"\"\n",
    "\n",
    "        self.time_left = time_left\n",
    "\n",
    "        move = None\n",
    "\n",
    "        if not legal_moves:\n",
    "            return -1, -1\n",
    "\n",
    "        try:\n",
    "\n",
    "            if self.iterative:  # Iterative search\n",
    "                depth = 1\n",
    "\n",
    "                # Get the best move found (higher value) evaluating each level\n",
    "                # (from top to bottom) before searching in the next level.\n",
    "                # Timeout or an optimal state found (e.g. win) returns\n",
    "                while True:\n",
    "                    if self.method == 'minimax':\n",
    "                        score, move = self.minimax(game, depth)\n",
    "                    elif self.method == 'alphabeta':\n",
    "                        score, move = self.alphabeta(game, depth)\n",
    "                    depth += 1\n",
    "                    # No need to wait for Timeout if an optimal move is reached\n",
    "                    if score == float('inf'):\n",
    "                        return move\n",
    "            else:  # Depth-first search\n",
    "                if self.method == 'minimax':\n",
    "                    _, move = self.minimax(game, self.search_depth)\n",
    "                elif self.method == 'alphabeta':\n",
    "                    _, move = self.alphabeta(game, self.search_depth)\n",
    "\n",
    "        except Timeout:\n",
    "            pass\n",
    "\n",
    "        # Return the best move from the last completed search iteration\n",
    "        return move\n",
    "\n",
    "    def minimax(self, game, depth, maximizing_player=True):\n",
    "        \"\"\"Implement the minimax search algorithm as described in the lectures.\n",
    "\n",
    "        Parameters\n",
    "        ----------\n",
    "        game : isolation.Board\n",
    "            An instance of the Isolation game `Board` class representing the\n",
    "            current game state\n",
    "\n",
    "        depth : int\n",
    "            Depth is an integer representing the maximum number of plies to\n",
    "            search in the game tree before aborting\n",
    "\n",
    "        maximizing_player : bool\n",
    "            Flag indicating whether the current search depth corresponds to a\n",
    "            maximizing layer (True) or a minimizing layer (False)\n",
    "\n",
    "        Returns\n",
    "        -------\n",
    "        float\n",
    "            The score for the current search branch\n",
    "\n",
    "        tuple(int, int)\n",
    "            The best move for the current branch; (-1, -1) for no legal moves\n",
    "\n",
    "        \"\"\"\n",
    "        if self.time_left() < self.TIMER_THRESHOLD:\n",
    "            raise Timeout()\n",
    "\n",
    "        legal_moves = game.get_legal_moves()\n",
    "        move = (-1, -1)\n",
    "\n",
    "        # If no more moves -> Terminal state: return its score with move (-1,-1)\n",
    "        if not legal_moves:\n",
    "            return self.score(game, self), move\n",
    "\n",
    "        # depth 0 evaluates and returns directly the value for the current state\n",
    "        # The current location here is the move to return\n",
    "        #  (it won't be evaualted again since depth = 0)\n",
    "        if depth == 0:\n",
    "            score = self.score(game, self)\n",
    "            move = game.get_player_location(self)\n",
    "            return score, move\n",
    "\n",
    "        depth -= 1  # Each recursive call to minimax will have one less depth\n",
    "\n",
    "        if maximizing_player:\n",
    "            # MAX-VALUE node: Get the maximum value from the MIN-VALUE nodes of\n",
    "            #  its next level\n",
    "            score, move = max([(self.minimax(game.forecast_move(m), depth, False)[0], m)\n",
    "                               for m in legal_moves])\n",
    "        else:\n",
    "            # MIN-VALUE node: Get the minimum value from the MAX-VALUE nodes of\n",
    "            #  its next level\n",
    "            score, move = min([(self.minimax(game.forecast_move(m), depth, True)[0], m)\n",
    "                               for m in legal_moves])\n",
    "        return score, move\n",
    "\n",
    "    def alphabeta(self,\n",
    "                  game,\n",
    "                  depth,\n",
    "                  alpha=float(\"-inf\"),\n",
    "                  beta=float(\"inf\"),\n",
    "                  maximizing_player=True):\n",
    "        \"\"\"Implement minimax search with alpha-beta pruning as described in the\n",
    "        lectures.\n",
    "\n",
    "        Parameters\n",
    "        ----------\n",
    "        game : isolation.Board\n",
    "            An instance of the Isolation game `Board` class representing the\n",
    "            current game state\n",
    "\n",
    "        depth : int\n",
    "            Depth is an integer representing the maximum number of plies to\n",
    "            search in the game tree before aborting\n",
    "\n",
    "        alpha : float\n",
    "            Alpha limits the lower bound of search on minimizing layers\n",
    "\n",
    "        beta : float\n",
    "            Beta limits the upper bound of search on maximizing layers\n",
    "\n",
    "        maximizing_player : bool\n",
    "            Flag indicating whether the current search depth corresponds to a\n",
    "            maximizing layer (True) or a minimizing layer (False)\n",
    "\n",
    "        Returns\n",
    "        -------\n",
    "        float\n",
    "            The score for the current search branch\n",
    "\n",
    "        tuple(int, int)\n",
    "            The best move for the current branch; (-1, -1) for no legal moves\n",
    "        \"\"\"\n",
    "        if self.time_left() < self.TIMER_THRESHOLD:\n",
    "            raise Timeout()\n",
    "\n",
    "        legal_moves = game.get_legal_moves()\n",
    "        move = (-1, -1)\n",
    "        score = None\n",
    "\n",
    "        # If no more moves -> Terminal state: return its score with move (-1,-1)\n",
    "        if not legal_moves:\n",
    "            return self.score(game, self), move\n",
    "\n",
    "        # depth 0 evaluates and returns directly the value for the current state\n",
    "        # The current location here is the move to return\n",
    "        #  (it won't be evaluated  again since depth = 0)\n",
    "        if depth == 0:\n",
    "            score = self.score(game, self)\n",
    "            move = game.get_player_location(self)  # Todo\n",
    "            return score, move\n",
    "\n",
    "        depth -= 1  # Each recursive call to alphabeta will have one less depth\n",
    "\n",
    "        # A dict with key=move and value=score is used for pruning the branches\n",
    "        scores = {}\n",
    "        if maximizing_player:  # MAX-VALUE node\n",
    "            for m in legal_moves:\n",
    "                # evaluate the next level of m (minimizing player)\n",
    "                #  and return its scores dictionary\n",
    "                scores[m], _ = self.alphabeta(game.forecast_move(m), depth, alpha, beta, False)\n",
    "                # get the max value of the resulted scores dictionary for the\n",
    "                #  current level(maximizing player)\n",
    "                move = max(scores, key=scores.get)\n",
    "                score = scores[move]\n",
    "\n",
    "                # Prune the next branches (for the next m's) if the value\n",
    "                #  obtained so far is larger than beta\n",
    "                #  (best choice for MIN in the higher level).\n",
    "                if score >= beta:\n",
    "                    return score, move\n",
    "\n",
    "                # Update alpha (best choice for MAX) for the next evaluation\n",
    "                #  (minimizing player)\n",
    "                alpha = max(alpha, score)\n",
    "\n",
    "        else:\n",
    "            for m in legal_moves:  # MIN-VALUE node\n",
    "                # evaluate the next level of m (maximizing player) and return\n",
    "                #  its scores dictionary\n",
    "                scores[m], _ = self.alphabeta(game.forecast_move(m), depth, alpha, beta, True)\n",
    "                # get the min value of the resulted scores dictionary for the\n",
    "                #  current level(minimizing player)\n",
    "                move = min(scores, key=scores.get)\n",
    "                score = scores[move]\n",
    "\n",
    "                # Prune the next branches (for the next m's) if the value\n",
    "                #  obtained so far is smaller than alpha\n",
    "                #  (best choice for MAX in the higher level).\n",
    "                if score <= alpha:\n",
    "                    return score, move\n",
    "\n",
    "                # Update beta (best choice for MIN) for the next evaluation\n",
    "                #  (maximazing player)\n",
    "                beta = min(beta, score)\n",
    "\n",
    "        return score, move"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Game setup"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import itertools\n",
    "import random\n",
    "import warnings\n",
    "\n",
    "from collections import namedtuple\n",
    "\n",
    "from isolation import Board\n",
    "\n",
    "NUM_MATCHES = 5  # number of matches against each opponent\n",
    "TIME_LIMIT = 30  # number of milliseconds before timeout\n",
    "\n",
    "TIMEOUT_WARNING = \"One or more agents lost a match this round due to \" + \\\n",
    "                  \"timeout. The get_move() function must return before \" + \\\n",
    "                  \"time_left() reaches 0 ms. You will need to leave some \" + \\\n",
    "                  \"time for the function to return, and may need to \" + \\\n",
    "                  \"increase this margin to avoid timeouts during  \" + \\\n",
    "                  \"tournament play.\"\n",
    "\n",
    "Agent = namedtuple(\"Agent\", [\"player\", \"name\"])\n",
    "\n",
    "\n",
    "class Timeout(Exception):\n",
    "    \"\"\"Subclass base exception for code clarity.\"\"\"\n",
    "    pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Play a \"fair\" set of matches between two agents by playing two games between the players, forcing each agent to play from randomly selected positions. This should control for differences in outcome resulting from advantage due to starting position on the board."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def play_match(player1, player2):\n",
    "\n",
    "    num_wins = {player1: 0, player2: 0}\n",
    "    num_timeouts = {player1: 0, player2: 0}\n",
    "    num_invalid_moves = {player1: 0, player2: 0}\n",
    "    games = [Board(player1, player2), Board(player2, player1)]\n",
    "\n",
    "    # initialize both games with a random move and response\n",
    "    for _ in range(2):\n",
    "        move = random.choice(games[0].get_legal_moves())\n",
    "        games[0].apply_move(move)\n",
    "        games[1].apply_move(move)\n",
    "\n",
    "    # play both games and tally the results\n",
    "    for game in games:\n",
    "        winner, _, termination = game.play(time_limit=TIME_LIMIT)\n",
    "\n",
    "        if player1 == winner:\n",
    "            num_wins[player1] += 1\n",
    "\n",
    "            if termination == \"timeout\":\n",
    "                num_timeouts[player2] += 1\n",
    "            else:\n",
    "                num_invalid_moves[player2] += 1\n",
    "\n",
    "        elif player2 == winner:\n",
    "\n",
    "            num_wins[player2] += 1\n",
    "\n",
    "            if termination == \"timeout\":\n",
    "                num_timeouts[player1] += 1\n",
    "            else:\n",
    "                num_invalid_moves[player1] += 1\n",
    "\n",
    "    if sum(num_timeouts.values()) != 0:\n",
    "        warnings.warn(TIMEOUT_WARNING)\n",
    "\n",
    "    return num_wins[player1], num_wins[player2]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " Play one round (i.e., a single match between each pair of opponents)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def play_round(agents, num_matches):\n",
    "\n",
    "    agent_1 = agents[-1]\n",
    "    wins = 0.\n",
    "    total = 0.\n",
    "\n",
    "    print(\"\\nPlaying Matches:\")\n",
    "    print(\"----------\")\n",
    "\n",
    "    for idx, agent_2 in enumerate(agents[:-1]):\n",
    "\n",
    "        counts = {agent_1.player: 0., agent_2.player: 0.}\n",
    "        names = [agent_1.name, agent_2.name]\n",
    "        print(\"  Match {}: {!s:^11} vs {!s:^11}\".format(idx + 1, *names), end=' ')\n",
    "\n",
    "        # Each player takes a turn going first\n",
    "        for p1, p2 in itertools.permutations((agent_1.player, agent_2.player)):\n",
    "            for _ in range(num_matches):\n",
    "                score_1, score_2 = play_match(p1, p2)\n",
    "                counts[p1] += score_1\n",
    "                counts[p2] += score_2\n",
    "                total += score_1 + score_2\n",
    "\n",
    "        wins += counts[agent_1.player]\n",
    "\n",
    "        print(\"\\tResult: {} to {}\".format(\n",
    "            int(counts[agent_1.player]), int(counts[agent_2.player])))\n",
    "\n",
    "    return 100. * wins / total"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Evaluation\n",
    "\n",
    "\n",
    "This section evaluates the performance of the custom heuristic function by\n",
    "comparing the strength of an agent using iterative deepening (ID) search with\n",
    "alpha-beta pruning against the strength rating of agents using other heuristic\n",
    "functions.  The `ID_Improved` agent provides a baseline by measuring the\n",
    "performance of a basic agent using Iterative Deepening and the \"improved\"\n",
    "heuristic (from lecture) on your hardware.  The `Student` agent then measures\n",
    "the performance of Iterative Deepening and the custom heuristic against the\n",
    "same opponents.\n",
    "\n",
    "\n",
    "The performance of time-limited iterative deepening search is hardware dependent (faster hardware is expected to search deeper than slower hardware in the same amount of time).  The script controls for these effects by also measuring the baseline performance of an agent called \"ID_Improved\" that uess Iterative Deepening and the improved_score heuristic from the above sample players.  \n",
    "\n",
    "The tournament opponents are listed below: \n",
    "\n",
    "- Random: An agent that randomly chooses a move each turn.\n",
    "- MM_Null: CustomPlayer agent using fixed-depth minimax search and the null_score heuristic\n",
    "- MM_Open: CustomPlayer agent using fixed-depth minimax search and the open_move_score heuristic\n",
    "- MM_Improved: CustomPlayer agent using fixed-depth minimax search and the improved_score heuristic\n",
    "- AB_Null: CustomPlayer agent using fixed-depth alpha-beta search and the null_score heuristic\n",
    "- AB_Open: CustomPlayer agent using fixed-depth alpha-beta search and the open_move_score heuristic\n",
    "- AB_Improved: CustomPlayer agent using fixed-depth alpha-beta search and the improved_score heuristic\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "*************************\n",
      " Evaluating: ID_Improved \n",
      "*************************\n",
      "\n",
      "Playing Matches:\n",
      "----------\n",
      "  Match 1: ID_Improved vs   Random    \tResult: 19 to 1\n",
      "  Match 2: ID_Improved vs   MM_Null   \tResult: 19 to 1\n",
      "  Match 3: ID_Improved vs   MM_Open   \tResult: 12 to 8\n",
      "  Match 4: ID_Improved vs MM_Improved \tResult: 12 to 8\n",
      "  Match 5: ID_Improved vs   AB_Null   \tResult: 14 to 6\n",
      "  Match 6: ID_Improved vs   AB_Open   \tResult: 19 to 1\n",
      "  Match 7: ID_Improved vs AB_Improved \tResult: 20 to 0\n",
      "\n",
      "\n",
      "Results:\n",
      "----------\n",
      "ID_Improved         82.14%\n",
      "\n",
      "*************************\n",
      "   Evaluating: Student   \n",
      "*************************\n",
      "\n",
      "Playing Matches:\n",
      "----------\n",
      "  Match 1:   Student   vs   Random    \tResult: 20 to 0\n",
      "  Match 2:   Student   vs   MM_Null   \tResult: 19 to 1\n",
      "  Match 3:   Student   vs   MM_Open   \tResult: 18 to 2\n",
      "  Match 4:   Student   vs MM_Improved \tResult: 15 to 5\n",
      "  Match 5:   Student   vs   AB_Null   \tResult: 15 to 5\n",
      "  Match 6:   Student   vs   AB_Open   \tResult: 20 to 0\n",
      "  Match 7:   Student   vs AB_Improved \tResult: 20 to 0\n",
      "\n",
      "\n",
      "Results:\n",
      "----------\n",
      "Student             90.71%\n"
     ]
    }
   ],
   "source": [
    "HEURISTICS = [(\"Null\", null_score), (\"Open\", open_move_score), (\"Improved\", improved_score)]\n",
    "AB_ARGS = {\"search_depth\": 5, \"method\": 'alphabeta', \"iterative\": False}\n",
    "MM_ARGS = {\"search_depth\": 3, \"method\": 'minimax', \"iterative\": False}\n",
    "CUSTOM_ARGS = {\"method\": 'alphabeta', 'iterative': True}\n",
    "\n",
    "# Create a collection of CPU agents\n",
    "mm_agents = [\n",
    "    Agent(CustomPlayer(score_fn=h, **MM_ARGS), \"MM_\" + name) for name, h in HEURISTICS\n",
    "]\n",
    "ab_agents = [\n",
    "    Agent(CustomPlayer(score_fn=h, **AB_ARGS), \"AB_\" + name) for name, h in HEURISTICS\n",
    "]\n",
    "random_agents = [Agent(RandomPlayer(), \"Random\")]\n",
    "\n",
    "# ID_Improved agent is used for comparison to the performance of the\n",
    "# submitted agent for calibration on the performance across different\n",
    "# systems; i.e., the performance of the student agent is considered\n",
    "# relative to the performance of the ID_Improved agent to account for\n",
    "# faster or slower computers.\n",
    "test_agents = [\n",
    "    Agent(CustomPlayer(score_fn=improved_score, **CUSTOM_ARGS), \"ID_Improved\"),\n",
    "    Agent(CustomPlayer(score_fn=custom_score, **CUSTOM_ARGS), \"Student\")\n",
    "]\n",
    "\n",
    "for agentUT in test_agents:\n",
    "    print(\"\")\n",
    "    print(\"*************************\")\n",
    "    print(\"{:^25}\".format(\"Evaluating: \" + agentUT.name))\n",
    "    print(\"*************************\")\n",
    "\n",
    "    agents = random_agents + mm_agents + ab_agents + [agentUT]\n",
    "    win_ratio = play_round(agents, NUM_MATCHES)\n",
    "\n",
    "    print(\"\\n\\nResults:\")\n",
    "    print(\"----------\")\n",
    "    print(\"{!s:<15}{:>10.2f}%\".format(agentUT.name, win_ratio))"
   ]
  }
 ],
 "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.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}