AI - Lab 07 - TicTacToe_Minimax.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "AI - Lab 07 - TicTacToe_Minimax.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "authorship_tag": "ABX9TyPymvyyYbxHilETuqed3hdU",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/svishakan/Artificial-Intelligence/blob/master/AI%20-%20Lab%2007%20-%20TicTacToe_Minimax.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "EIlBHPMMJe2G"
      },
      "source": [
        "# AI - Lab 07 - TicTacToe Game Playing Agent using Minimax Algorithm\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "gvKRd_FmJrUS"
      },
      "source": [
        "#### 13 October 2020"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "zZ2gy7uSMF-2"
      },
      "source": [
        "import time"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cRBL9rjpe3Hp"
      },
      "source": [
        "## Minimax Algorithm"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cAB_KuCqer-i"
      },
      "source": [
        "<hr>\n",
        "The Minimax algorithm relies on systematic searching, or more accurately said - on <br>brute force</br> and a simple evaluation function. Let's assume that every time during deciding the next move we search through a whole tree, all the way down to leaves. Effectively we would look into all the possible outcomes and every time we would be able to determine the best possible move.\n",
        "\n",
        "However, for non-trivial games, that practice is inapplicable. Even searching to a certain depth sometimes takes an unacceptable amount of time. Therefore, Minimax applies search to a fairly low tree depth aided with appropriate heuristics, and a well designed, yet simple evaluation function.\n",
        "\n",
        "With this approach we lose the certainty in finding the best possible move, but the majority of cases the decision that Minimax makes is much better than any human's.\n",
        "<hr>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "bJg_7iVAJ4b7"
      },
      "source": [
        "class TicTacToe_Minimax:\n",
        "    \"\"\"Class to implement the TicTacToe game using the Minimax algorithm. \"\"\"\n",
        "\n",
        "    def __init__(self):\n",
        "        \"\"\"Initialize with an empty board and X to start the game. \"\"\"\n",
        "\n",
        "        self.board = [['-', '-', '-'],\n",
        "                      ['-', '-', '-'],\n",
        "                      ['-', '-', '-']]\n",
        "\n",
        "        self.turn = 'X'\n",
        "        self.moves_checked = 0\n",
        "\n",
        "    \n",
        "    def __str__(self):\n",
        "        \"\"\"Returns a string format of the current board.\"\"\"\n",
        "\n",
        "        board_str = \"-------------\\n| \"\n",
        "\n",
        "        for i in range(0, 3):\n",
        "            for j in range(0, 3):\n",
        "                board_str += self.board[i][j] + \" | \"\n",
        "            board_str += \"\\n-------------\\n| \"\n",
        "        board_str = board_str[:-2:]\n",
        "        board_str += \"\\n\"\n",
        "\n",
        "        return board_str\n",
        "\n",
        "\n",
        "    def is_valid(self, x, y):\n",
        "        \"\"\"Checks if the move made is valid. \"\"\"\n",
        "\n",
        "        if x < 0 or x > 2 or y < 0 or y > 2:    #Row and Col <= 2\n",
        "            return False\n",
        "        elif self.board[x][y] != '-':           #Position not empty\n",
        "            return False\n",
        "        else:                                   #Valid\n",
        "            return True\n",
        "\n",
        "\n",
        "    def is_end(self):\n",
        "        \"\"\"Checks if the game has ended by win/draw. \"\"\"\n",
        "\n",
        "        board = self.board\n",
        "\n",
        "        win_combinations = [[board[0][0], board[0][1], board[0][2]],    #Horizontal wins\n",
        "                            [board[1][0], board[1][1], board[1][2]],\n",
        "                            [board[2][0], board[2][1], board[2][2]],\n",
        "\n",
        "                            [board[0][0], board[1][0], board[2][0]],    #Vertical wins\n",
        "                            [board[0][1], board[1][1], board[2][1]],\n",
        "                            [board[0][2], board[1][2], board[2][2]],\n",
        "\n",
        "                            [board[0][0], board[1][1], board[2][2]],    #Diagonal win\n",
        "                            [board[0][2], board[1][1], board[2][0]]]    #Anti-Diagonal win\n",
        "        \n",
        "        #Has X won?\n",
        "        if ['X', 'X', 'X'] in win_combinations:\n",
        "            return 'X'\n",
        "        \n",
        "        #Has O won?\n",
        "        if ['O', 'O', 'O'] in win_combinations:\n",
        "            return 'O'\n",
        "\n",
        "        #Is board full?\n",
        "        for i in range(0, 3):\n",
        "            for j in range(0, 3):\n",
        "                if self.board[i][j] == '-':\n",
        "                    return False        #Board is not full\n",
        "\n",
        "        return True                     #Board is full\n",
        "\n",
        "    \n",
        "    def max(self):\n",
        "        \"\"\"Player O tries to maximize its own score and minimize Player X's score. \"\"\"\n",
        "        \n",
        "        max_value = -2  #Possible values: -1 - Loss, 0 - Tie, 1 - Win\n",
        "\n",
        "        x, y = None, None\n",
        "\n",
        "        result = self.is_end()\n",
        "\n",
        "        if result == 'X':       #Loss for O\n",
        "            return (-1, 0, 0)\n",
        "\n",
        "        elif result == 'O':     #Win for O\n",
        "            return (1, 0, 0)\n",
        "\n",
        "        elif result == True:    #Tie\n",
        "            return (0, 0, 0)\n",
        "\n",
        "        #Find best move by trial and error basis\n",
        "        for i in range(0, 3):\n",
        "            for j in range(0, 3):\n",
        "                if self.board[i][j] == '-':\n",
        "                    self.moves_checked += 1     #For understanding efficiency\n",
        "\n",
        "                    #Player O makes a move & calls min()\n",
        "                    self.board[i][j] = 'O'\n",
        "                    m, min_i, min_j = self.min() #Player X makes a move\n",
        "\n",
        "                    #Finding value if needed\n",
        "                    if m > max_value:\n",
        "                        max_value = m\n",
        "                        x = i\n",
        "                        y = j\n",
        "\n",
        "                    #Set grid value back to empty\n",
        "                    self.board[i][j] = '-'\n",
        "        \n",
        "        return max_value, x, y\n",
        "\n",
        "\n",
        "    def min(self):\n",
        "        \"\"\"Player X tries to maximize its score and minimize Player O's score. \"\"\"\n",
        "\n",
        "        min_value = 2   #-1 - Win, 0 - Tie, 1 - Loss\n",
        "\n",
        "        x, y = None, None\n",
        "\n",
        "        result = self.is_end()\n",
        "\n",
        "        if result == 'X':       #Loss for O thus Win for X\n",
        "            return (-1, 0, 0)\n",
        "\n",
        "        elif result == 'O':     #Loss for X thus Win for X\n",
        "            return (1, 0, 0)\n",
        "\n",
        "        elif result == '-':     #Tie\n",
        "            return (0, 0, 0)\n",
        "\n",
        "        #Find best move by trial & error basis\n",
        "        for i in range(0, 3):\n",
        "            for j in range(0, 3):\n",
        "                if self.board[i][j] == '-':\n",
        "                    self.moves_checked += 1     #For understanding efficiency\n",
        "\n",
        "                    #Player X makes a move & calls max()\n",
        "                    self.board[i][j] = 'X'\n",
        "                    m, max_i, max_j = self.max() #Player O makes a move\n",
        "\n",
        "                    if m < min_value:\n",
        "                        min_value = m\n",
        "                        x = i\n",
        "                        y = j\n",
        "                    \n",
        "                    #Set grid value back to empty\n",
        "                    self.board[i][j] = '-'\n",
        "\n",
        "        return min_value, x, y\n",
        "\n",
        "\n",
        "    def play_game(self):\n",
        "        \"\"\"Play a game of Tic-Tac-Toe using the Minimax algorithm. \"\"\"\n",
        "\n",
        "        while True:\n",
        "            print(self)\n",
        "            self.result = self.is_end()\n",
        "\n",
        "            #If game ended\n",
        "            if self.result == True:\n",
        "                if self.result == 'X':\n",
        "                    print(\"The winner is X!\")\n",
        "                \n",
        "                elif self.result == 'O':\n",
        "                    print(\"The winner is O!\")\n",
        "                \n",
        "                else:\n",
        "                    print(\"It is a tie!\")\n",
        "\n",
        "                self.__init__()\n",
        "                return\n",
        "\n",
        "            #If Player X's turn\n",
        "            if self.turn == 'X':\n",
        "                while True:\n",
        "                    self.moves_checked = 0  #To understand computational efficiency of this move\n",
        "                    start = time.time()\n",
        "                    m, x, y = self.min()    #Player O makes a move\n",
        "                    end = time.time()\n",
        "\n",
        "                    print(\"Evaluation Time\\t\\t: {0}s\".format(round(end - start, 2)))\n",
        "                    print(\"Recommnded move for you\\t: X = {0}, Y = {1}\".format(x, y))\n",
        "                    print(\"Moves checked\\t\\t: {0}\\n\".format(self.moves_checked))\n",
        "\n",
        "                    x = int(input(\"Enter the X co-ordinate of your move: \"))\n",
        "                    y = int(input(\"Enter the Y co-ordinate of your move: \"))\n",
        "\n",
        "                    if self.is_valid(x, y):\n",
        "                        self.board[x][y] = 'X'\n",
        "                        self.turn = 'O'\n",
        "                        break\n",
        "                    \n",
        "                    else:\n",
        "                        print(\"Invalid move. Try again.\")\n",
        "            \n",
        "            #If Player O's turn\n",
        "            else:\n",
        "                self.moves_checked = 0\n",
        "                start = time.time()\n",
        "                m, x, y = self.max()\n",
        "                end = time.time()\n",
        "\n",
        "                print(\"Evaluation Time\\t\\t: {0}s\".format(round(end - start, 2)))\n",
        "                print(\"Moves checked\\t\\t: {0}\\n\".format(self.moves_checked))\n",
        "\n",
        "                self.board[x][y] = 'O'\n",
        "                self.turn = 'X'\n",
        "                    "
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "-iDSl5zfHvh7",
        "outputId": "ef5adc2d-704c-4fe2-d8ad-760f7ee79614",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        }
      },
      "source": [
        "if __name__ == \"__main__\":\n",
        "    game = TicTacToe_Minimax()\n",
        "    game.play_game()"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "-------------\n",
            "| - | - | - | \n",
            "-------------\n",
            "| - | - | - | \n",
            "-------------\n",
            "| - | - | - | \n",
            "-------------\n",
            "\n",
            "\n",
            "Evaluation Time\t\t: 2.05s\n",
            "Recommnded move for you\t: X = 0, Y = 0\n",
            "Moves checked\t\t: 549945\n",
            "\n",
            "Enter the X co-ordinate of your move: 0\n",
            "Enter the Y co-ordinate of your move: 0\n",
            "-------------\n",
            "| X | - | - | \n",
            "-------------\n",
            "| - | - | - | \n",
            "-------------\n",
            "| - | - | - | \n",
            "-------------\n",
            "\n",
            "\n",
            "Evaluation Time\t\t: 0.24s\n",
            "Moves checked\t\t: 59704\n",
            "\n",
            "-------------\n",
            "| X | - | - | \n",
            "-------------\n",
            "| - | O | - | \n",
            "-------------\n",
            "| - | - | - | \n",
            "-------------\n",
            "\n",
            "\n",
            "Evaluation Time\t\t: 0.03s\n",
            "Recommnded move for you\t: X = 0, Y = 1\n",
            "Moves checked\t\t: 7331\n",
            "\n",
            "Enter the X co-ordinate of your move: 0\n",
            "Enter the Y co-ordinate of your move: 1\n",
            "-------------\n",
            "| X | X | - | \n",
            "-------------\n",
            "| - | O | - | \n",
            "-------------\n",
            "| - | - | - | \n",
            "-------------\n",
            "\n",
            "\n",
            "Evaluation Time\t\t: 0.01s\n",
            "Moves checked\t\t: 934\n",
            "\n",
            "-------------\n",
            "| X | X | O | \n",
            "-------------\n",
            "| - | O | - | \n",
            "-------------\n",
            "| - | - | - | \n",
            "-------------\n",
            "\n",
            "\n",
            "Evaluation Time\t\t: 0.0s\n",
            "Recommnded move for you\t: X = 2, Y = 0\n",
            "Moves checked\t\t: 197\n",
            "\n",
            "Enter the X co-ordinate of your move: 2\n",
            "Enter the Y co-ordinate of your move: 0\n",
            "-------------\n",
            "| X | X | O | \n",
            "-------------\n",
            "| - | O | - | \n",
            "-------------\n",
            "| X | - | - | \n",
            "-------------\n",
            "\n",
            "\n",
            "Evaluation Time\t\t: 0.0s\n",
            "Moves checked\t\t: 46\n",
            "\n",
            "-------------\n",
            "| X | X | O | \n",
            "-------------\n",
            "| O | O | - | \n",
            "-------------\n",
            "| X | - | - | \n",
            "-------------\n",
            "\n",
            "\n",
            "Evaluation Time\t\t: 0.0s\n",
            "Recommnded move for you\t: X = 1, Y = 2\n",
            "Moves checked\t\t: 13\n",
            "\n",
            "Enter the X co-ordinate of your move: 1\n",
            "Enter the Y co-ordinate of your move: 2\n",
            "-------------\n",
            "| X | X | O | \n",
            "-------------\n",
            "| O | O | X | \n",
            "-------------\n",
            "| X | - | - | \n",
            "-------------\n",
            "\n",
            "\n",
            "Evaluation Time\t\t: 0.0s\n",
            "Moves checked\t\t: 4\n",
            "\n",
            "-------------\n",
            "| X | X | O | \n",
            "-------------\n",
            "| O | O | X | \n",
            "-------------\n",
            "| X | O | - | \n",
            "-------------\n",
            "\n",
            "\n",
            "Evaluation Time\t\t: 0.0s\n",
            "Recommnded move for you\t: X = 2, Y = 2\n",
            "Moves checked\t\t: 1\n",
            "\n",
            "Enter the X co-ordinate of your move: 2\n",
            "Enter the Y co-ordinate of your move: 2\n",
            "-------------\n",
            "| X | X | O | \n",
            "-------------\n",
            "| O | O | X | \n",
            "-------------\n",
            "| X | O | X | \n",
            "-------------\n",
            "\n",
            "\n",
            "It is a tie!\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "VI9-9SqYWHMu"
      },
      "source": [
        "---\n",
        "## Alpha - Beta Pruning"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "B4L1KTMwfE1G"
      },
      "source": [
        "<hr>\n",
        "Alpha–Beta (𝛼−𝛽) algorithm was discovered independently by a few researches in mid 1900s. Alpha–Beta is actually an <b>improved Minimax</b> using a <b>heuristic</b>. It stops evaluating a move when it makes sure that it's worse than previously examined move. Such moves need not to be evaluated further.\n",
        "\n",
        "When added to a simple minimax algorithm, it gives the same output, but cuts off certain branches that can't possibly affect the final decision - dramatically improving the performance.\n",
        "\n",
        "The main concept is to maintain two values through whole search:\n",
        "\n",
        "<ul>\n",
        "<li>Alpha : Best already explored option for player Max\n",
        "<li>Beta  : Best already explored option for player Min\n",
        "</ul>\n",
        "\n",
        "Initially, alpha is negative infinity and beta is positive infinity, i.e. the worst possible scores for both players.\n",
        "<hr>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "oDqATxAbWFMF"
      },
      "source": [
        "class TicTacToe_Alpha_Beta(TicTacToe_Minimax):\n",
        "    \"\"\"Subclassing the TicTacToe class which implements TicTacToe with \n",
        "    the minimax algorithm to include Alpha-Beta Pruning. \"\"\"\n",
        "    \n",
        "    def max(self, alpha, beta):\n",
        "        \"\"\"Player O tries to maximize its own score and minimize Player X's score. \"\"\"\n",
        "        \n",
        "        max_value = -2  #Possible values: -1 - Loss, 0 - Tie, 1 - Win\n",
        "\n",
        "        x, y = None, None\n",
        "\n",
        "        result = self.is_end()\n",
        "\n",
        "        if result == 'X':       #Loss for O\n",
        "            return (-1, 0, 0)\n",
        "\n",
        "        elif result == 'O':     #Win for O\n",
        "            return (1, 0, 0)\n",
        "\n",
        "        elif result == True:    #Tie\n",
        "            return (0, 0, 0)\n",
        "\n",
        "        #Find best move by trial and error basis\n",
        "        for i in range(0, 3):\n",
        "            for j in range(0, 3):\n",
        "                if self.board[i][j] == '-':\n",
        "                    self.moves_checked += 1     #For understanding efficiency\n",
        "\n",
        "                    #Player O makes a move & calls min()\n",
        "                    self.board[i][j] = 'O'\n",
        "                    m, min_i, min_j = self.min(alpha, beta) #Player X makes a move\n",
        "\n",
        "                    #Finding value if needed\n",
        "                    if m > max_value:\n",
        "                        max_value = m\n",
        "                        x = i\n",
        "                        y = j\n",
        "\n",
        "                    #Set grid value back to empty\n",
        "                    self.board[i][j] = '-'\n",
        "\n",
        "                    #Alpha - Beta Pruning (only extra code)\n",
        "                    if max_value >= beta:\n",
        "                        return max_value, x, y\n",
        "                    \n",
        "                    if max_value > alpha:\n",
        "                        alpha = max_value\n",
        "        \n",
        "        return max_value, x, y\n",
        "\n",
        "\n",
        "    def min(self, alpha, beta):\n",
        "        \"\"\"Player X tries to maximize its score and minimize Player O's score. \"\"\"\n",
        "\n",
        "        min_value = 2   #-1 - Win, 0 - Tie, 1 - Loss\n",
        "\n",
        "        x, y = None, None\n",
        "\n",
        "        result = self.is_end()\n",
        "\n",
        "        if result == 'X':       #Loss for O thus Win for X\n",
        "            return (-1, 0, 0)\n",
        "\n",
        "        elif result == 'O':     #Loss for X thus Win for X\n",
        "            return (1, 0, 0)\n",
        "\n",
        "        elif result == '-':     #Tie\n",
        "            return (0, 0, 0)\n",
        "        \n",
        "        #Find best move by trial & error basis\n",
        "        for i in range(0, 3):\n",
        "            for j in range(0, 3):\n",
        "                if self.board[i][j] == '-':\n",
        "                    self.moves_checked += 1     #For understanding efficiency\n",
        "\n",
        "                    #Player X makes a move & calls max()\n",
        "                    self.board[i][j] = 'X'\n",
        "                    m, max_i, max_j = self.max(alpha, beta) #Player O makes a move\n",
        "\n",
        "                    if m < min_value:\n",
        "                        min_value = m\n",
        "                        x = i\n",
        "                        y = j\n",
        "                    \n",
        "                    #Set grid value back to empty\n",
        "                    self.board[i][j] = '-'\n",
        "\n",
        "                    #Alpha-Beta Pruning (only extra code)\n",
        "                    if min_value <= alpha:\n",
        "                        return min_value, x, y\n",
        "                    \n",
        "                    if min_value < beta:\n",
        "                        beta = min_value\n",
        "\n",
        "        return min_value, x, y\n",
        "\n",
        "\n",
        "    def play_game(self):\n",
        "        \"\"\"Play a game of Tic-Tac-Toe using the Minimax algorithm\n",
        "           with alpha-beta pruning. \"\"\"\n",
        "\n",
        "        while True:\n",
        "            print(self)\n",
        "            self.result = self.is_end()\n",
        "\n",
        "            #If game ended\n",
        "            if self.result == True:\n",
        "                if self.result == 'X':\n",
        "                    print(\"The winner is X!\")\n",
        "                \n",
        "                elif self.result == 'O':\n",
        "                    print(\"The winner is O!\")\n",
        "                \n",
        "                else:\n",
        "                    print(\"It is a tie!\")\n",
        "\n",
        "                self.__init__()\n",
        "                return\n",
        "\n",
        "            #If Player X's turn\n",
        "            if self.turn == 'X':\n",
        "                while True:\n",
        "                    self.moves_checked = 0    #To understand computational efficiency of this move\n",
        "                    start = time.time()\n",
        "                    m, x, y = self.min(-2, 2) #Player O makes a move\n",
        "                    end = time.time()\n",
        "\n",
        "                    print(\"Evaluation Time\\t\\t: {0}s\".format(round(end - start, 2)))\n",
        "                    print(\"Recommnded move for you\\t: X = {0}, Y = {1}\".format(x, y))\n",
        "                    print(\"Moves checked\\t\\t: {0}\\n\".format(self.moves_checked))\n",
        "\n",
        "                    x = int(input(\"Enter the X co-ordinate of your move: \"))\n",
        "                    y = int(input(\"Enter the Y co-ordinate of your move: \"))\n",
        "\n",
        "                    if self.is_valid(x, y):\n",
        "                        self.board[x][y] = 'X'\n",
        "                        self.turn = 'O'\n",
        "                        break\n",
        "                    \n",
        "                    else:\n",
        "                        print(\"Invalid move. Try again.\")\n",
        "            \n",
        "            #If Player O's turn\n",
        "            else:\n",
        "                self.moves_checked = 0\n",
        "                start = time.time()\n",
        "                m, x, y = self.max(-2, 2)\n",
        "                end = time.time()\n",
        "\n",
        "                print(\"Evaluation Time\\t\\t: {0}s\".format(round(end - start, 2)))\n",
        "                print(\"Moves checked\\t\\t: {0}\\n\".format(self.moves_checked))\n",
        "\n",
        "                self.board[x][y] = 'O'\n",
        "                self.turn = 'X'"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "i9bwA7eYYUS9",
        "outputId": "180bbb70-a2a5-46b7-dd68-be38f0a20d17",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        }
      },
      "source": [
        "efficient_game = TicTacToe_Alpha_Beta()\n",
        "efficient_game.play_game()"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "-------------\n",
            "| - | - | - | \n",
            "-------------\n",
            "| - | - | - | \n",
            "-------------\n",
            "| - | - | - | \n",
            "-------------\n",
            "\n",
            "\n",
            "Evaluation Time\t\t: 0.08s\n",
            "Recommnded move for you\t: X = 0, Y = 0\n",
            "Moves checked\t\t: 18296\n",
            "\n",
            "Enter the X co-ordinate of your move: 0\n",
            "Enter the Y co-ordinate of your move: 0\n",
            "-------------\n",
            "| X | - | - | \n",
            "-------------\n",
            "| - | - | - | \n",
            "-------------\n",
            "| - | - | - | \n",
            "-------------\n",
            "\n",
            "\n",
            "Evaluation Time\t\t: 0.01s\n",
            "Moves checked\t\t: 2337\n",
            "\n",
            "-------------\n",
            "| X | - | - | \n",
            "-------------\n",
            "| - | O | - | \n",
            "-------------\n",
            "| - | - | - | \n",
            "-------------\n",
            "\n",
            "\n",
            "Evaluation Time\t\t: 0.0s\n",
            "Recommnded move for you\t: X = 0, Y = 1\n",
            "Moves checked\t\t: 843\n",
            "\n",
            "Enter the X co-ordinate of your move: 0\n",
            "Enter the Y co-ordinate of your move: 1\n",
            "-------------\n",
            "| X | X | - | \n",
            "-------------\n",
            "| - | O | - | \n",
            "-------------\n",
            "| - | - | - | \n",
            "-------------\n",
            "\n",
            "\n",
            "Evaluation Time\t\t: 0.0s\n",
            "Moves checked\t\t: 74\n",
            "\n",
            "-------------\n",
            "| X | X | O | \n",
            "-------------\n",
            "| - | O | - | \n",
            "-------------\n",
            "| - | - | - | \n",
            "-------------\n",
            "\n",
            "\n",
            "Evaluation Time\t\t: 0.0s\n",
            "Recommnded move for you\t: X = 2, Y = 0\n",
            "Moves checked\t\t: 63\n",
            "\n",
            "Enter the X co-ordinate of your move: 2\n",
            "Enter the Y co-ordinate of your move: 0\n",
            "-------------\n",
            "| X | X | O | \n",
            "-------------\n",
            "| - | O | - | \n",
            "-------------\n",
            "| X | - | - | \n",
            "-------------\n",
            "\n",
            "\n",
            "Evaluation Time\t\t: 0.0s\n",
            "Moves checked\t\t: 16\n",
            "\n",
            "-------------\n",
            "| X | X | O | \n",
            "-------------\n",
            "| O | O | - | \n",
            "-------------\n",
            "| X | - | - | \n",
            "-------------\n",
            "\n",
            "\n",
            "Evaluation Time\t\t: 0.0s\n",
            "Recommnded move for you\t: X = 1, Y = 2\n",
            "Moves checked\t\t: 9\n",
            "\n",
            "Enter the X co-ordinate of your move: 1\n",
            "Enter the Y co-ordinate of your move: 2\n",
            "-------------\n",
            "| X | X | O | \n",
            "-------------\n",
            "| O | O | X | \n",
            "-------------\n",
            "| X | - | - | \n",
            "-------------\n",
            "\n",
            "\n",
            "Evaluation Time\t\t: 0.0s\n",
            "Moves checked\t\t: 4\n",
            "\n",
            "-------------\n",
            "| X | X | O | \n",
            "-------------\n",
            "| O | O | X | \n",
            "-------------\n",
            "| X | O | - | \n",
            "-------------\n",
            "\n",
            "\n",
            "Evaluation Time\t\t: 0.0s\n",
            "Recommnded move for you\t: X = 2, Y = 2\n",
            "Moves checked\t\t: 1\n",
            "\n",
            "Enter the X co-ordinate of your move: 2\n",
            "Enter the Y co-ordinate of your move: 2\n",
            "-------------\n",
            "| X | X | O | \n",
            "-------------\n",
            "| O | O | X | \n",
            "-------------\n",
            "| X | O | X | \n",
            "-------------\n",
            "\n",
            "\n",
            "It is a tie!\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}