Negamax_IterativeDeepening.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "source": [
        "# Week 4 - AI Lab\n",
        "\n",
        "Author: Khushee Kapoor\n",
        "\n",
        "Registration Number: 200968052"
      ],
      "metadata": {
        "id": "J_brIjPwMoxj"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "To start, we install easyAI in the environment using pip."
      ],
      "metadata": {
        "id": "Yq0YFvsKMvlT"
      }
    },
    {
      "cell_type": "code",
      "execution_count": 14,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "XN2ckKH11jQm",
        "outputId": "9b5c3bc3-6566-4c50-ce92-21b6878d5965"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Looking in indexes: https://pypi.org/simple, https://us-python.pkg.dev/colab-wheels/public/simple/\n",
            "Requirement already satisfied: easyAI in /usr/local/lib/python3.8/dist-packages (2.0.12)\n",
            "Requirement already satisfied: numpy in /usr/local/lib/python3.8/dist-packages (from easyAI) (1.22.4)\n"
          ]
        }
      ],
      "source": [
        "# installing easyAI\n",
        "!pip install easyAI"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Next, we import the required classes and functions:\n",
        "- TwoPlayerGame: class in the EasyAI library that provides a basic framework for creating two-player games.\n",
        "- Human_Player: class in the EasyAI library that represents a human player. It prompts the user to enter moves from the console (this player always loses :'(\n",
        "- AI_Player: class in the EasyAI library that represents an AI player. It takes a game instance and a search algorithm as input, and uses the algorithm to select the best move (this player always wins :)\n",
        "- solve_with_iterative_deepening: function in the EasyAI library that uses iterative deepening search to find the best move for a given game instance and AI player. It takes as input a game instance, an AI player, and a maximum search depth, and returns the best move.\n",
        "- solve_with_depth_first_search: function in the EasyAI library that uses depth-first search to find the best move for a given game instance and AI player. It takes as input a game instance, an AI player, and a maximum search depth, and returns the best move.\n",
        "- Negamax: class in the EasyAI library that implements the Negamax algorithm for game-playing AI. It takes as input a game instance and a maximum search depth, and returns the best move."
      ],
      "metadata": {
        "id": "q4CDvwItMzYz"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# importing the required classes and functions\n",
        "from easyAI import TwoPlayerGame, Human_Player, AI_Player, solve_with_iterative_deepening, solve_with_depth_first_search\n",
        "from easyAI.AI import Negamax"
      ],
      "metadata": {
        "id": "SA7_FXCh4zZv"
      },
      "execution_count": 15,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Next, we declare the specifications of the game by making a class TicTacToe and defining the following functions:\n",
        "- __ init __: initializes the TicTacToe game with a board of the specified size (default is 3x3). It also sets up the players and their marks (X or O).\n",
        "- possible_moves:  returns a list of all possible moves that can be made on the current board state. Each move is represented as a tuple of (x, y) coordinates.\n",
        "- make_move: makes the specified move on the board for the specified player (X or O).\n",
        "- unmake_move: function undoes the specified move on the board. (used only by AI)\n",
        "- lose: specifies if the current user has lost or not by checking for all possible configurations on the board\n",
        "- is_over: returns True if the game is over (either because someone has won or the game is a draw), or False otherwise.\n",
        "- show: prints the current state of the board to the console.\n",
        "- scoring: calculates and returns the score of the current board state, based on the current player. The score is a value between -100 (loss) and 100 (win)."
      ],
      "metadata": {
        "id": "t_QS5pmoPjUM"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# declaring the specifications of the game\n",
        "class TicTacToe(TwoPlayerGame):\n",
        "    \"\"\"The board positions are numbered as follows:\n",
        "    1 2 3\n",
        "    4 5 6\n",
        "    7 8 9\n",
        "    \"\"\"\n",
        "\n",
        "    def __init__(self, players=None):\n",
        "        self.players = players\n",
        "        self.board = [0 for i in range(9)]\n",
        "        self.current_player = 1\n",
        "\n",
        "    def possible_moves(self):\n",
        "        return [i + 1 for i, e in enumerate(self.board) if e == 0]\n",
        "\n",
        "    def make_move(self, move):\n",
        "        self.board[int(move) - 1] = self.current_player\n",
        "\n",
        "    def unmake_move(self, move):  # optional method (speeds up the AI)\n",
        "        self.board[int(move) - 1] = 0\n",
        "\n",
        "    def lose(self):\n",
        "        \"\"\" Has the opponent \"three in line ?\" \"\"\"\n",
        "        return any(\n",
        "            [\n",
        "                all([(self.board[c - 1] == self.opponent_index) for c in line])\n",
        "                for line in [\n",
        "                    [1, 2, 3],\n",
        "                    [4, 5, 6],\n",
        "                    [7, 8, 9],  # horiz.\n",
        "                    [1, 4, 7],\n",
        "                    [2, 5, 8],\n",
        "                    [3, 6, 9],  # vertical\n",
        "                    [1, 5, 9],\n",
        "                    [3, 5, 7],\n",
        "                ]\n",
        "            ]\n",
        "        )  # diagonal\n",
        "\n",
        "    def is_over(self):\n",
        "        return (self.possible_moves() == []) or self.lose()\n",
        "\n",
        "    def show(self):\n",
        "        print(\n",
        "            \"\\n\"\n",
        "            + \"\\n\".join(\n",
        "                [\n",
        "                    \" \".join([[\".\", \"O\", \"X\"][self.board[3 * j + i]] for i in range(3)])\n",
        "                    for j in range(3)\n",
        "                ]\n",
        "            )\n",
        "        )\n",
        "\n",
        "    def scoring(self):\n",
        "        return -100 if self.lose() else 0"
      ],
      "metadata": {
        "id": "aysCeXbO6Xtr"
      },
      "execution_count": 16,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "The main function defined solves the game as per the algorithm specified:\n",
        "-  Iterative Deepening: it explores the game by using several times the Negamax algorithm, always starting at the initial state of the game, but taking increasing depth (in the list ai_depths) until the score of the initial condition indicates that the first player will certainly win or loose, at which case it stops,\n",
        "- Depth First Search: solves a game using a depth-first search (therefore it cannot be used for games that can have an infinite number of moves). The game is explored until endgames are reached and these endgames are evaluated to see if their are victories or defeats (or draws). Then, a situation in which every move leads to a defeat is labelled as a (certain) defeat, and a situation in which one move leads to a (certain) defeat of the opponent is labelled as a (certain) victory. This way we come back up to the root (initial condition) which receives a label, which is returned.\n",
        "- In negamax, the player whose turn it is to move assigns a value to each possible move based on the outcome of the game assuming optimal play by both players. This is done by recursively exploring the game tree, generating all possible moves and evaluating the resulting positions. The value assigned to each move is the negative of the value assigned by the opponent for their best move, hence the name \"negamax\". By negating the opponent's score, the algorithm takes into account the fact that the opponent is trying to minimize the player's score. The algorithm continues to explore the game tree until it reaches a terminal state, at which point it assigns a score to the position based on whether the player won, lost, or drew the game. The move with the highest score is then chosen as the best move.\n",
        "\n",
        "We use the Negamax algorithm to create a brain for the agent. This way, it can think of all possible solutions upto 9 levels deep and play the move accordingly to maximize its score.\n",
        "\n",
        "We then solve the games using Iterative Deepening and Depth First Search. Solving gives us a glimpse of what could be the potential outcome of a game, how many moves would the game last, and what would be the optimal first move by the first player."
      ],
      "metadata": {
        "id": "PHHA_VjDSpiv"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# solving the game using specified searching approaches\n",
        "def main(algo):\n",
        "  ai = Negamax(9)\n",
        "  if algo == 'id':\n",
        "      result = solve_with_iterative_deepening(game=TicTacToe(players=[AI_Player(ai), Human_Player()]), ai_depths=range(2, 10), win_score=100)\n",
        "  elif algo == 'dfs':\n",
        "      result = solve_with_depth_first_search(game=TicTacToe(players=[AI_Player(ai), Human_Player()]), win_score=100)\n",
        "  else:\n",
        "      print(\"Invalid algorithm.\")\n",
        "  return result"
      ],
      "metadata": {
        "id": "7oWRvq_e8kGQ"
      },
      "execution_count": 17,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Analyzing solution provided by Iterative Deepening."
      ],
      "metadata": {
        "id": "UBhX9zHynUpo"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "import time\n",
        "start = time.time()\n",
        "idres = main('id')\n",
        "end = time.time()\n",
        "print('Result: ', idres)\n",
        "print(str.format('Time Taken: {:.2f}s', end-start))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "MkfT7a1cEHNZ",
        "outputId": "1ba60b8b-9683-4bc0-9cc3-33da862ac695"
      },
      "execution_count": 150,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "d:2, a:0, m:1\n",
            "d:3, a:0, m:1\n",
            "d:4, a:0, m:1\n",
            "d:5, a:0, m:1\n",
            "d:6, a:0, m:1\n",
            "d:7, a:0, m:1\n",
            "d:8, a:0, m:1\n",
            "d:9, a:0, m:1\n",
            "Result:  (0, 9, 1)\n",
            "Time Taken: 0.81s\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "As we can see, there is a possibility of a draw (0), the game would end in 9 moves (5 by first player and 4 by the second), and the optimal first move is 1."
      ],
      "metadata": {
        "id": "PG11G66LnYPK"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Analyzing solution provided by Depth First Search."
      ],
      "metadata": {
        "id": "-s3e7ObdnhWc"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "import time\n",
        "start = time.time()\n",
        "dfsres = main('dfs')\n",
        "end = time.time()\n",
        "print('Result: ', dfsres)\n",
        "print(str.format('Time Taken: {:.2f}s', end-start))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "xNXBb2AHELIJ",
        "outputId": "8079c9c8-eccc-4e7a-d45c-aba985b8b970"
      },
      "execution_count": 152,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Result:  0\n",
            "Time Taken: 2.21s\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "As we can see, this searching technique provides only limited information - that there is a possibility of a draw."
      ],
      "metadata": {
        "id": "QF9Wz7j5nkCq"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Comparison: The time taken is significantly more for DFS in comparison to Iterative Deepening.\n",
        "\n",
        "Some theoretical differences between the two:\n",
        "- Search strategy: Depth-First Search (DFS) is a depth-first search strategy, meaning that it explores as far as possible along each branch before backtracking. Iterative Deepening (ID) is a hybrid search strategy that combines the depth-first search strategy of DFS with the breadth-first search strategy of Breadth-First Search (BFS).\n",
        "\n",
        "- Memory usage: DFS can use a lot of memory, as it stores all visited nodes on the stack. This can lead to stack overflow errors if the search space is too large. ID, on the other hand, only stores the current path being explored, which greatly reduces memory usage.\n",
        "\n",
        "- Completeness: DFS is not guaranteed to find a solution if one exists, especially if the search space is infinite or the solution is at the bottom of a deep branch. ID, however, is complete and will always find a solution if one exists, as it gradually increases the depth of the search until a solution is found.\n",
        "\n",
        "- Time complexity: DFS has a time complexity of O(b^m), where b is the branching factor and m is the maximum depth of the search tree. ID has a time complexity of O(b^d), where d is the depth of the shallowest solution."
      ],
      "metadata": {
        "id": "BkQK-j3mnrJI"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Let's have some fun now - let's break down and analyze how the AI agent is thinking, and not do that :D. In the sense, let's play sub-optimal moves and see how the agent strives to win."
      ],
      "metadata": {
        "id": "NzRXPaEUoppc"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# initializing the game\n",
        "game = TicTacToe(players=[AI_Player(Negamax(9)), Human_Player()])"
      ],
      "metadata": {
        "id": "LJ7eGtP6ajiQ"
      },
      "execution_count": 133,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# asking the AI agent for its move\n",
        "game.get_move()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "gLfPof8HjWPZ",
        "outputId": "500dc291-ec67-412d-c9e4-73cd6c7a13e6"
      },
      "execution_count": 134,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "1"
            ]
          },
          "metadata": {},
          "execution_count": 134
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# haha, playing another move\n",
        "game.play_move(2)\n",
        "game.show()"
      ],
      "metadata": {
        "id": "YgCUxx3JjX-X",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "778ef1c7-85ec-4b13-f2a7-d379cef5d67c"
      },
      "execution_count": 135,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "\n",
            ". O .\n",
            ". . .\n",
            ". . .\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# now, let us play what the AI model intended to do\n",
        "game.get_move()"
      ],
      "metadata": {
        "id": "KnzmL9MJjp3Q",
        "outputId": "dd94d127-ffb3-4adb-d179-fa8ba77ab33e",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "execution_count": 136,
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "\n",
            "Player 2 what do you play ? 1\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "1"
            ]
          },
          "metadata": {},
          "execution_count": 136
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# done\n",
        "game.play_move(1)\n",
        "game.show()"
      ],
      "metadata": {
        "id": "gZUvUidijqoO",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "ad664a88-5135-4ff6-e64b-906ec2ed6a51"
      },
      "execution_count": 137,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "\n",
            "X O .\n",
            ". . .\n",
            ". . .\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# see how it is frantically trying to survive\n",
        "game.get_move()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "pTjYop8Yj_aO",
        "outputId": "8f8a239e-8dd7-4d81-802c-e04f90ca6226"
      },
      "execution_count": 138,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "4"
            ]
          },
          "metadata": {},
          "execution_count": 138
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# oh no, ai agent, let's give you another move\n",
        "game.play_move(3)\n",
        "game.show()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "EvNQVYdMkAgj",
        "outputId": "286f2d46-fd21-453a-e677-8bdfdc7ecd3a"
      },
      "execution_count": 139,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "\n",
            "X O O\n",
            ". . .\n",
            ". . .\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# meanwhile we play your move\n",
        "game.get_move()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "hQ5fwOuYkChR",
        "outputId": "37fc6270-f4be-4bfa-8aea-a202c4b1fd7d"
      },
      "execution_count": 140,
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "\n",
            "Player 2 what do you play ? 4\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "4"
            ]
          },
          "metadata": {},
          "execution_count": 140
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# hahaha\n",
        "game.play_move(4)\n",
        "game.show()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "M7vUw0GAkIJh",
        "outputId": "a8a7846c-9116-4d80-fdd6-2bfee4f099ce"
      },
      "execution_count": 141,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "\n",
            "X O O\n",
            "X . .\n",
            ". . .\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# ah, trying to stop us, eh?\n",
        "game.get_move()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "hFGOju72kKdS",
        "outputId": "48285ac8-94b7-47d6-dca8-870323951536"
      },
      "execution_count": 142,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "7"
            ]
          },
          "metadata": {},
          "execution_count": 142
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# okay, for once, let's grant your wish\n",
        "game.play_move(7)\n",
        "game.show()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "dwuBSQ4vkLJR",
        "outputId": "ad97b1b5-962d-46ef-89c7-f4975182c69d"
      },
      "execution_count": 143,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "\n",
            "X O O\n",
            "X . .\n",
            "O . .\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# but we've got other moves too\n",
        "game.get_move()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "l0aQPUvxkOKZ",
        "outputId": "0f121bee-5f2d-4203-9ee1-409689080429"
      },
      "execution_count": 144,
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "\n",
            "Player 2 what do you play ? 5\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "5"
            ]
          },
          "metadata": {},
          "execution_count": 144
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# aha\n",
        "game.play_move(5)\n",
        "game.show()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "lPVFF-XEk2Pg",
        "outputId": "662b6c75-262c-4b86-bd14-1c21e63712d9"
      },
      "execution_count": 145,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "\n",
            "X O O\n",
            "X X .\n",
            "O . .\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# okay, your turn\n",
        "game.get_move()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "eAGvVzd_k50S",
        "outputId": "9f8e928f-2803-4ef7-c574-cfb3fe96bcf7"
      },
      "execution_count": 146,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "6"
            ]
          },
          "metadata": {},
          "execution_count": 146
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# i don't see how this is going to stop me from winning, so okay your wish\n",
        "game.play_move(6)\n",
        "game.show()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "EY4QhXZ1lpof",
        "outputId": "9c6084e5-d286-49d8-c733-3a48c265f93f"
      },
      "execution_count": 147,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "\n",
            "X O O\n",
            "X X O\n",
            "O . .\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# beating you at your own game\n",
        "game.get_move()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "aaTngCsTlsk7",
        "outputId": "ebb08e33-a30a-4d8d-b837-e996603cf336"
      },
      "execution_count": 148,
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "\n",
            "Player 2 what do you play ? 9\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "9"
            ]
          },
          "metadata": {},
          "execution_count": 148
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# ai can never take over humans\n",
        "game.play_move(9)\n",
        "game.show()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "xg0wXg5El1sf",
        "outputId": "e3dee99f-f921-4a93-c7f4-1619d66a7a0c"
      },
      "execution_count": 149,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "\n",
            "X O O\n",
            "X X O\n",
            "O . X\n"
          ]
        }
      ]
    }
  ]
}