Lab7_TicTacToe_MinimaxAlgorithm.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h1>Lab 7: Tic-Tac-Toe Game using MiniMax Algorithm</h1>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<b>What is Minimax?</b>\n",
    "\n",
    "\n",
    "Minimax is a artifical intelligence applied in two player games, such as tic-tac-toe, checkers, chess and go. This games are known as zero-sum games, because in a mathematical representation: one player wins (+1) and other player loses (-1) or both of anyone not to win (0).\n",
    "\n",
    "\n",
    "Minimax is a type of adversarial search algorithm for generating and exploring game trees. It is mostly used to solve zero-sum games where one side’s gain is equivalent to other side’s loss, so adding all gains and subtracting all losses end up being zero.\n",
    "\n",
    "\n",
    "Adversarial search differs from conventional searching algorithms by adding opponents into the mix. Minimax algorithm keeps playing the turns of both player and the opponent optimally to figure out the best possible move.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<b>How does it works?</b>\n",
    "\n",
    "The algorithm search, recursively, the best move that leads the Max player to win or not lose (draw). It consider the current state of the game and the available moves at that state, then for each valid move it plays (alternating min and max) until it finds a terminal state (win, draw or lose).\n",
    "\n",
    "Minimax is a kind of backtracking algorithm that is used in decision making and game theory to find the optimal move for a player, assuming that your opponent also plays optimally. It is widely used in two player turn-based games such as Tic-Tac-Toe, Backgammon, Mancala, Chess, etc.\n",
    "\n",
    "In Minimax the two players are called maximizer and minimizer. The maximizer tries to get the highest score possible while the minimizer tries to do the opposite and get the lowest score possible.\n",
    "\n",
    "Every board state has a value associated with it. In a given state if the maximizer has upper hand then, the score of the board will tend to be some positive value. If the minimizer has the upper hand in that board state then it will tend to be some negative value. The values of the board are calculated by some heuristics which are unique for every type of game.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from math import inf as infinity"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "game_state = [[' ',' ',' '],\n",
    "              [' ',' ',' '],\n",
    "              [' ',' ',' ']]\n",
    "players = ['X','O']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def play_move(state, player, block_num):\n",
    "    if state[int((block_num-1)/3)][(block_num-1)%3] == ' ':\n",
    "        state[int((block_num-1)/3)][(block_num-1)%3] = player\n",
    "    else:\n",
    "        block_num = int(input(\"Block is not empty, ya blockhead! Choose again: \"))\n",
    "        play_move(state, player, block_num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def copy_game_state(state):\n",
    "    new_state = [[' ',' ',' '],[' ',' ',' '],[' ',' ',' ']]\n",
    "    for i in range(3):\n",
    "        for j in range(3):\n",
    "            new_state[i][j] = state[i][j]\n",
    "    return new_state"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def check_current_state(game_state):\n",
    "    # Check if draw\n",
    "    draw_flag = 0\n",
    "    for i in range(3):\n",
    "        for j in range(3):\n",
    "            if game_state[i][j] == ' ':\n",
    "                draw_flag = 1\n",
    "    if draw_flag is 0:\n",
    "        return None, \"Draw\"\n",
    "    \n",
    "    # Check horizontals\n",
    "    if (game_state[0][0] == game_state[0][1] and game_state[0][1] == game_state[0][2] and game_state[0][0] != ' '):\n",
    "        return game_state[0][0], \"Done\"\n",
    "    if (game_state[1][0] == game_state[1][1] and game_state[1][1] == game_state[1][2] and game_state[1][0] != ' '):\n",
    "        return game_state[1][0], \"Done\"\n",
    "    if (game_state[2][0] == game_state[2][1] and game_state[2][1] == game_state[2][2] and game_state[2][0] != ' '):\n",
    "        return game_state[2][0], \"Done\"\n",
    "    \n",
    "    # Check verticals\n",
    "    if (game_state[0][0] == game_state[1][0] and game_state[1][0] == game_state[2][0] and game_state[0][0] != ' '):\n",
    "        return game_state[0][0], \"Done\"\n",
    "    if (game_state[0][1] == game_state[1][1] and game_state[1][1] == game_state[2][1] and game_state[0][1] != ' '):\n",
    "        return game_state[0][1], \"Done\"\n",
    "    if (game_state[0][2] == game_state[1][2] and game_state[1][2] == game_state[2][2] and game_state[0][2] != ' '):\n",
    "        return game_state[0][2], \"Done\"\n",
    "    \n",
    "    # Check diagonals\n",
    "    if (game_state[0][0] == game_state[1][1] and game_state[1][1] == game_state[2][2] and game_state[0][0] != ' '):\n",
    "        return game_state[1][1], \"Done\"\n",
    "    if (game_state[2][0] == game_state[1][1] and game_state[1][1] == game_state[0][2] and game_state[2][0] != ' '):\n",
    "        return game_state[1][1], \"Done\"\n",
    "    \n",
    "    return None, \"Not Done\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_board(game_state):\n",
    "    print('----------------')\n",
    "    print('| ' + str(game_state[0][0]) + ' || ' + str(game_state[0][1]) + ' || ' + str(game_state[0][2]) + ' |')\n",
    "    print('----------------')\n",
    "    print('| ' + str(game_state[1][0]) + ' || ' + str(game_state[1][1]) + ' || ' + str(game_state[1][2]) + ' |')\n",
    "    print('----------------')\n",
    "    print('| ' + str(game_state[2][0]) + ' || ' + str(game_state[2][1]) + ' || ' + str(game_state[2][2]) + ' |')\n",
    "    print('----------------')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def getBestMove(state, player):\n",
    "    '''\n",
    "    Minimax Algorithm\n",
    "    '''\n",
    "    winner_loser , done = check_current_state(state)\n",
    "    if done == \"Done\" and winner_loser == 'O': # If AI won\n",
    "        return 1\n",
    "    elif done == \"Done\" and winner_loser == 'X': # If Human won\n",
    "        return -1\n",
    "    elif done == \"Draw\":    # Draw condition\n",
    "        return 0\n",
    "        \n",
    "    moves = []\n",
    "    empty_cells = []\n",
    "    for i in range(3):\n",
    "        for j in range(3):\n",
    "            if state[i][j] is ' ':\n",
    "                empty_cells.append(i*3 + (j+1))\n",
    "    \n",
    "    for empty_cell in empty_cells:\n",
    "        move = {}\n",
    "        move['index'] = empty_cell\n",
    "        new_state = copy_game_state(state)\n",
    "        play_move(new_state, player, empty_cell)\n",
    "        \n",
    "        if player == 'O':    # If AI\n",
    "            result = getBestMove(new_state, 'X')    # make more depth tree for human\n",
    "            move['score'] = result\n",
    "        else:\n",
    "            result = getBestMove(new_state, 'O')    # make more depth tree for AI\n",
    "            move['score'] = result\n",
    "        \n",
    "        moves.append(move)\n",
    "\n",
    "    # Find best move\n",
    "    best_move = None\n",
    "    if player == 'O':   # If AI player\n",
    "        best = -infinity\n",
    "        for move in moves:\n",
    "            if move['score'] > best:\n",
    "                best = move['score']\n",
    "                best_move = move['index']\n",
    "    else:\n",
    "        best = infinity\n",
    "        for move in moves:\n",
    "            if move['score'] < best:\n",
    "                best = move['score']\n",
    "                best_move = move['index']\n",
    "                \n",
    "    return best_move"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "New Game!\n",
      "----------------\n",
      "|   ||   ||   |\n",
      "----------------\n",
      "|   ||   ||   |\n",
      "----------------\n",
      "|   ||   ||   |\n",
      "----------------\n",
      "Choose which player goes first - X (You - the petty human) or O(The mighty AI): X\n",
      "Oye Human, your turn! Choose where to place (1 to 9): 1\n",
      "----------------\n",
      "| X ||   ||   |\n",
      "----------------\n",
      "|   ||   ||   |\n",
      "----------------\n",
      "|   ||   ||   |\n",
      "----------------\n",
      "AI plays move: 2\n",
      "----------------\n",
      "| X || O ||   |\n",
      "----------------\n",
      "|   ||   ||   |\n",
      "----------------\n",
      "|   ||   ||   |\n",
      "----------------\n",
      "Oye Human, your turn! Choose where to place (1 to 9): 7\n",
      "----------------\n",
      "| X || O ||   |\n",
      "----------------\n",
      "|   ||   ||   |\n",
      "----------------\n",
      "| X ||   ||   |\n",
      "----------------\n",
      "AI plays move: 4\n",
      "----------------\n",
      "| X || O ||   |\n",
      "----------------\n",
      "| O ||   ||   |\n",
      "----------------\n",
      "| X ||   ||   |\n",
      "----------------\n",
      "Oye Human, your turn! Choose where to place (1 to 9): 9\n",
      "----------------\n",
      "| X || O ||   |\n",
      "----------------\n",
      "| O ||   ||   |\n",
      "----------------\n",
      "| X ||   || X |\n",
      "----------------\n",
      "AI plays move: 5\n",
      "----------------\n",
      "| X || O ||   |\n",
      "----------------\n",
      "| O || O ||   |\n",
      "----------------\n",
      "| X ||   || X |\n",
      "----------------\n",
      "Oye Human, your turn! Choose where to place (1 to 9): 8\n",
      "----------------\n",
      "| X || O ||   |\n",
      "----------------\n",
      "| O || O ||   |\n",
      "----------------\n",
      "| X || X || X |\n",
      "----------------\n",
      "X won!\n",
      "Wanna try again?(Y/N) : N\n",
      "GG!\n"
     ]
    }
   ],
   "source": [
    "# PLaying\n",
    "play_again = 'Y'\n",
    "while play_again == 'Y' or play_again == 'y':\n",
    "    game_state = [[' ',' ',' '],\n",
    "              [' ',' ',' '],\n",
    "              [' ',' ',' ']]\n",
    "    current_state = \"Not Done\"\n",
    "    print(\"\\nNew Game!\")\n",
    "    print_board(game_state)\n",
    "    player_choice = input(\"Choose which player goes first - X (You - the petty human) or O(The mighty AI): \")\n",
    "    winner = None\n",
    "    \n",
    "    if player_choice == 'X' or player_choice == 'x':\n",
    "        current_player_idx = 0\n",
    "    else:\n",
    "        current_player_idx = 1\n",
    "        \n",
    "    while current_state == \"Not Done\":\n",
    "        if current_player_idx == 0: # Human's turn\n",
    "            block_choice = int(input(\"Oye Human, your turn! Choose where to place (1 to 9): \"))\n",
    "            play_move(game_state ,players[current_player_idx], block_choice)\n",
    "        else:   # AI's turn\n",
    "            block_choice = getBestMove(game_state, players[current_player_idx])\n",
    "            play_move(game_state ,players[current_player_idx], block_choice)\n",
    "            print(\"AI plays move: \" + str(block_choice))\n",
    "        print_board(game_state)\n",
    "        winner, current_state = check_current_state(game_state)\n",
    "        if winner is not None:\n",
    "            print(str(winner) + \" won!\")\n",
    "        else:\n",
    "            current_player_idx = (current_player_idx + 1)%2\n",
    "        \n",
    "        if current_state is \"Draw\":\n",
    "            print(\"Draw!\")\n",
    "            \n",
    "    play_again = input('Wanna try again?(Y/N) : ')\n",
    "    if play_again == 'N':\n",
    "        print('GG!')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}