tic_tac_toe.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Importing required moduless\n",
    "import numpy as np \n",
    "import pandas as pd \n",
    "import pprint,random\n",
    "\n",
    "from scipy.ndimage.interpolation import shift\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "from keras.models import Sequential\n",
    "from keras.layers import Dense,Dropout\n",
    "from keras.optimizers import SGD"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Creating a Tic Tac Toe Game\n",
    "In order for a program to learn how to play Tic-Tac-Toe, we first need to create the Tic-Tac-Toe game\n",
    "\n",
    "Below, we create a simple tic tac toe game using Numpy\n",
    "\n",
    "Below are the details of the Numpy Tic Tac Toe Game:\n",
    "\n",
    "* The game board is a 3 * 3 numpy array\n",
    "* The below is the denotation used:\n",
    "    * 2: placeholder/empty cell\n",
    "    * 0: 'O'\n",
    "    * 1: 'X'\n",
    "* By default, the array is filled with the number 2 as placeholder\n",
    "* The number 0 denotes an 'O' and the number 1 denotes an 'X'\n",
    "* Players take turns in choosing the coordinates of the numpy array where they will place 0 or 1 respectively\n",
    "* The player who succeeds in placing three of their marks in a horizontal, vertical, or diagonal row wins the game\n",
    "* For simplicity, the program always plays with the mark 1 and the opponent plays with 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class tic_tac_toe_game(object):\n",
    "    def __init__(self):\n",
    "        self.board=np.full((3,3),2)\n",
    "\n",
    "    def toss(self):\n",
    "        \"\"\"Function to simulate a toss and decide which player goes first\n",
    "\n",
    "        Args:\n",
    "\n",
    "        Returns:\n",
    "        Returns 1 if player assigned mark 1 has won, or 0 if his opponent won\n",
    "\n",
    "        \"\"\"\n",
    "        turn=np.random.randint(0,2,size=1)\n",
    "        if turn.mean()==0:\n",
    "            self.turn_monitor=0\n",
    "        elif turn.mean()==1:\n",
    "            self.turn_monitor=1\n",
    "        return self.turn_monitor\n",
    "\n",
    "    def move(self,player,coord):\n",
    "        \"\"\"Function to perform the action of placing a mark on the tic tac toe board\n",
    "        After performing the action, this function flips the value of the turn_monitor to \n",
    "        the next player\n",
    "\n",
    "        Args:\n",
    "        player: 1 if player who is assigned the mark 1 is performing the action, \n",
    "        0 if his opponent is performing the action\n",
    "        coord: The coordinate where the 1 or 0 is to be placed on the \n",
    "        tic-tac-toe board (numpy array)\n",
    "\n",
    "        Returns:\n",
    "        game_status(): Calls the game status function and returns its value\n",
    "        board: Returns the new board state after making the move\n",
    "\n",
    "        \"\"\"\n",
    "        if self.board[coord]!=2 or self.game_status()!=\"In Progress\" or self.turn_monitor!=player:\n",
    "            raise ValueError(\"Invalid move\")\n",
    "        self.board[coord]=player\n",
    "        self.turn_monitor=1-player\n",
    "        return self.game_status(),self.board\n",
    "\n",
    "\n",
    "    def game_status(self):\n",
    "        \"\"\"Function to check the current status of the game, \n",
    "        whether the game has been won, drawn or is in progress\n",
    "\n",
    "        Args:\n",
    "\n",
    "        Returns:\n",
    "        \"Won\" if the game has been won, \"Drawn\" if the \n",
    "        game has been drawn, or \"In Progress\", if the game is still in progress\n",
    "\n",
    "        \"\"\"\n",
    "        #check for a win along rows\n",
    "        for i in range(self.board.shape[0]):\n",
    "            if 2 not in self.board[i,:] and len(set(self.board[i,:]))==1:\n",
    "                return \"Won\"\n",
    "        #check for a win along columns\n",
    "        for j in range(self.board.shape[1]):\n",
    "            if 2 not in self.board[:,j] and len(set(self.board[:,j]))==1:\n",
    "                return \"Won\"\n",
    "        # check for a win along diagonals\n",
    "        if 2 not in np.diag(self.board) and len(set(np.diag(self.board)))==1:\n",
    "            return \"Won\"\n",
    "        if 2 not in np.diag(np.fliplr(self.board)) and len(set(np.diag(np.fliplr(self.board))))==1:\n",
    "            return \"Won\"\n",
    "        # check for a Draw\n",
    "        if not 2 in self.board:\n",
    "            return \"Drawn\"\n",
    "        else:\n",
    "            return \"In Progress\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Testing the Tic Tac Toe game\n",
    "\n",
    "To simply test the tic-tac-toe game created above, let us play a dummy game. We make the moves for both the players."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# create an object of the class tick_tac_toe_game\n",
    "game=tic_tac_toe_game()\n",
    "# toss to decide which player goes first\n",
    "game.toss()\n",
    "print(\"Player \",game.turn_monitor,\" has won the toss\")\n",
    "# make the first move\n",
    "print(\"Initial board state \\n\",game.board)\n",
    "print(\"Let first player place their mark on 0,0\")\n",
    "game_status,board=game.move(game.turn_monitor,(0,0))\n",
    "print(\"New Board State: \\n\",board)\n",
    "print(\"Let second player place their mark on 0,1\")\n",
    "game_status,board=game.move(game.turn_monitor,(0,1))\n",
    "print(\"New Board State: \\n\",board)\n",
    "print(\"Let first player place their mark on 1,1\")\n",
    "game_status,board=game.move(game.turn_monitor,(1,1))\n",
    "print(\"New Board State: \\n\",board)\n",
    "print(\"Let second player place their mark on 0,2\")\n",
    "game_status,board=game.move(game.turn_monitor,(0,2))\n",
    "print(\"New Board State: \\n\",board)\n",
    "print(\"Let first player place their mark on 2,2\")\n",
    "game_status,board=game.move(game.turn_monitor,(2,2))\n",
    "print(\"New Board State: \\n\",board)\n",
    "print(\"Player \",1-game.turn_monitor,\" Has \",game_status)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Creating the Legal Moves Generator\n",
    "\n",
    "The legal moves genator accepts the board state and player as input, and provides the set of all possible legal moves as output.\n",
    "\n",
    "Basically, for a given board state and player, it tells us where all the player can place his mark legally (the player can only place the mark where there is no opponent's mark)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def legal_moves_generator(current_board_state,turn_monitor):\n",
    "    \"\"\"Function that returns the set of all possible legal moves and resulting board states, \n",
    "    for a given input board state and player\n",
    "\n",
    "    Args:\n",
    "    current_board_state: The current board state\n",
    "    turn_monitor: 1 if it's the player who places the mark 1's turn to play, 0 if its his opponent's turn\n",
    "\n",
    "    Returns:\n",
    "    legal_moves_dict: A dictionary of a list of possible next coordinate-resulting board state pairs\n",
    "    The resulting board state is flattened to 1 d array\n",
    "\n",
    "    \"\"\"\n",
    "    legal_moves_dict={}\n",
    "    for i in range(current_board_state.shape[0]):\n",
    "        for j in range(current_board_state.shape[1]):\n",
    "            if current_board_state[i,j]==2:\n",
    "                board_state_copy=current_board_state.copy()\n",
    "                board_state_copy[i,j]=turn_monitor\n",
    "                legal_moves_dict[(i,j)]=board_state_copy.flatten()\n",
    "    return legal_moves_dict"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Testing the Legal Moves Generator\n",
    "\n",
    "Let us test the above created Legal Moves Generator.\n",
    "\n",
    "We start a dummy game, and do the toss. We then pass the current board state and toss winner to the Legal Moves Generator. It returns the dictionary of legal moves that it returns the dictionary is of the form \"possible next legal move coordinate\":\"flattened resulting board state\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "game=tic_tac_toe_game()\n",
    "game.toss()\n",
    "print(\"Player \",game.turn_monitor,\" has won the toss\")\n",
    "print(\"Current board state \\n\",game.board)\n",
    "legal_moves_dict=legal_moves_generator(game.board,game.turn_monitor)\n",
    "print(\"Dictionary of Possible Next Legal Moves:\")\n",
    "pprint.pprint(legal_moves_dict)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can observe above that the Legal Moves Generator returns a dictionary with all the possible legal coordinates and their resulting flattened numpy board states"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Creating the Evaluator (Neural Network Model)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As defined previously, the Evaluator function maps board states to scores.\n",
    "\n",
    "It is expected that after training, the Evaluator learns to assign higher scores to board states that are favourable to the program.\n",
    "In our kernel, we use a neural network as an Evaluator Function.\n",
    "\n",
    "Below, we create the neural network. The weights of the neural network are intialized randomly.\n",
    "The neural network takes the flattened tic-tac-toe board numpy array as input and outputs a score."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "model = Sequential()\n",
    "model.add(Dense(18, input_dim=9,kernel_initializer='normal', activation='relu'))\n",
    "model.add(Dropout(0.1))\n",
    "model.add(Dense(9, kernel_initializer='normal',activation='relu'))\n",
    "model.add(Dropout(0.1))\n",
    "model.add(Dense(1,kernel_initializer='normal'))\n",
    "\n",
    "learning_rate = 0.001\n",
    "momentum = 0.8\n",
    "\n",
    "sgd = SGD(lr=learning_rate, momentum=momentum,nesterov=False)\n",
    "model.compile(loss='mean_squared_error', optimizer=sgd)\n",
    "model.summary()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Creating the Program Move Selector\n",
    "\n",
    "The Program Move Selector selects the next move for a player given the current board state using the following approach:\n",
    "* Use the Legal Moves Generator to get all the possible next legal board states.\n",
    "* Use the Evaluator (model) to score each possible next board state.\n",
    "* The next board state that is assigned the highest score is selected as the next board state.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def move_selector(model,current_board_state,turn_monitor):\n",
    "    \"\"\"Function that selects the next move to make from a set of possible legal moves\n",
    "\n",
    "    Args:\n",
    "    model: The Evaluator function to use to evaluate each possible next board state\n",
    "    turn_monitor: 1 if it's the player who places the mark 1's turn to play, 0 if its his opponent's turn\n",
    "\n",
    "    Returns:\n",
    "    selected_move: The numpy array coordinates where the player should place thier mark\n",
    "    new_board_state: The flattened new board state resulting from performing above selected move\n",
    "    score: The score that was assigned to the above selected_move by the Evaluator (model)\n",
    "\n",
    "    \"\"\"\n",
    "    tracker={}\n",
    "    legal_moves_dict=legal_moves_generator(current_board_state,turn_monitor)\n",
    "    for legal_move_coord in legal_moves_dict:\n",
    "        score=model.predict(legal_moves_dict[legal_move_coord].reshape(1,9))\n",
    "        tracker[legal_move_coord]=score\n",
    "    selected_move=max(tracker, key=tracker.get)\n",
    "    new_board_state=legal_moves_dict[selected_move]\n",
    "    score=tracker[selected_move]\n",
    "    return selected_move,new_board_state,score"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Testing the Program Move Selector\n",
    "\n",
    "Let us play a dummy game and use the above created Program Move Selector function to select the next move"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# new game\n",
    "game=tic_tac_toe_game()\n",
    "# toss\n",
    "game.toss()\n",
    "# choose the first move\n",
    "print(\"Player assigned mark 1\",game.turn_monitor,\" won the toss\")\n",
    "print(\"Initial board state:\")\n",
    "print(game.board)\n",
    "selected_move,new_board_state,score=move_selector(model,game.board,game.turn_monitor)\n",
    "print(\"Selected move: \",selected_move)\n",
    "print(\"Resulting new board state: \",new_board_state)\n",
    "print(\"Score assigned to above board state by Evaluator(model): \", score)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Please note that since the Evaluator (model) has not yet been trained and has been assigned random weights, hence the score above is a random number"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Creating the opponent (The Opponent Move Selector)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For our program to self learn, it needs to play several games of tic-tac-toe.\n",
    "\n",
    "But with who will it play with?\n",
    "\n",
    "The program learns by playing games against a coded opponent.\n",
    "\n",
    "The opponent is coded to do the following:\n",
    "\n",
    "1. If playing in \"Easy\" mode:\n",
    "\n",
    "    * When it is your turn, use the Legal Moves Generator to get all possible legal next moves\n",
    "    * Pick a legal move at random\n",
    "    * Repeat above until the end of the game\n",
    "\n",
    "2. If playing in \"Hard\" mode:\n",
    "\n",
    "    * When it is your turn, use the Legal Moves Generator to get all possible legal next moves\n",
    "    * Of the above legal moves, if any legal move makes you win (along row/column/diagonal), pick that legal move\n",
    "    * Else, if any legal move prevents your opponent (program) from winning when it is one move away from a win, pick that move\n",
    "    * Else, if any legal move leads to a row/diagonal/column having two 0's and no 1's (program's mark) , pick that legal move\n",
    "    * If none of the above conditions exist, pick a legal move at random\n",
    "\n",
    "The Program is trained by repeatedly playing games against the above opponent and updating the weights of the model at the end of each game.\n",
    "\n",
    "Each game is played at either \"Easy\" or \"Hard\" mode, which is picked at random at the start of each game.\n",
    "\n",
    "The \"Easy\" mode helps the Program explore the tic-tac-toe space. The \"Hard\" mode helps the Program learn how to play with a real opponent."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def row_winning_move_check(current_board_state,legal_moves_dict,turn_monitor):\n",
    "    \"\"\"Function to scan rowwise and identify coordinate amongst the legal coordinates that will\n",
    "    result in a winning board state\n",
    "\n",
    "    Args:\n",
    "    legal_moves_dict: Dictionary of legal next moves\n",
    "    turn_monitor: whose turn it is to move\n",
    "    \n",
    "    Returns:\n",
    "    selected_move: The coordinates of numpy array where placing the 0 will lead to win for the opponent\n",
    "    \"\"\" \n",
    "    legal_move_coords =  list(legal_moves_dict.keys())\n",
    "    random.shuffle(legal_move_coords)\n",
    "    for legal_move_coord in legal_move_coords:\n",
    "        current_board_state_copy=current_board_state.copy()\n",
    "        current_board_state_copy[legal_move_coord]=turn_monitor\n",
    "        #check for a win along rows\n",
    "        for i in range(current_board_state_copy.shape[0]):\n",
    "            if 2 not in current_board_state_copy[i,:] and len(set(current_board_state_copy[i,:]))==1:\n",
    "                selected_move=legal_move_coord\n",
    "                return selected_move\n",
    "            \n",
    "def column_winning_move_check(current_board_state,legal_moves_dict,turn_monitor):\n",
    "    \"\"\"Function to scan column wise and identify coordinate amongst the legal coordinates that will\n",
    "    result in a winning board state\n",
    "\n",
    "    Args:\n",
    "    legal_moves_dict: Dictionary of legal next moves\n",
    "    turn_monitor: whose turn it is to move\n",
    "\n",
    "    Returns:\n",
    "    selected_move: The coordinates of numpy array where placing the 0 will lead to win for the opponent\n",
    "    \"\"\" \n",
    "    legal_move_coords =  list(legal_moves_dict.keys())\n",
    "    random.shuffle(legal_move_coords)\n",
    "    for legal_move_coord in legal_move_coords:\n",
    "        current_board_state_copy=current_board_state.copy()\n",
    "        current_board_state_copy[legal_move_coord]=turn_monitor\n",
    "        for j in range(current_board_state_copy.shape[1]):\n",
    "                    if 2 not in current_board_state_copy[:,j] and len(set(current_board_state_copy[:,j]))==1:\n",
    "                        selected_move=legal_move_coord\n",
    "                        return selected_move\n",
    "\n",
    "def diag1_winning_move_check(current_board_state,legal_moves_dict,turn_monitor):\n",
    "    \"\"\"Function to scan diagonal and identify coordinate amongst the legal coordinates that will\n",
    "    result in a winning board state\n",
    "\n",
    "    Args:\n",
    "    legal_moves_dict: Dictionary of legal next moves\n",
    "    turn_monitor: whose turn it is to move\n",
    "\n",
    "    Returns:\n",
    "    selected_move: The coordinates of numpy array where placing the 0 will lead to win for the opponent\n",
    "\n",
    "    \"\"\" \n",
    "    legal_move_coords =  list(legal_moves_dict.keys())\n",
    "    random.shuffle(legal_move_coords)\n",
    "    for legal_move_coord in legal_move_coords:\n",
    "        current_board_state_copy=current_board_state.copy()\n",
    "        current_board_state_copy[legal_move_coord]=turn_monitor\n",
    "        if 2 not in np.diag(current_board_state_copy) and len(set(np.diag(current_board_state_copy)))==1:\n",
    "            selected_move=legal_move_coord\n",
    "            return selected_move\n",
    "            \n",
    "def diag2_winning_move_check(current_board_state,legal_moves_dict,turn_monitor):\n",
    "    \"\"\"Function to scan second diagonal and identify coordinate amongst the legal coordinates that will\n",
    "    result in a winning board state\n",
    "\n",
    "    Args:\n",
    "    legal_moves_dict: Dictionary of legal next moves\n",
    "    turn_monitor: whose turn it is to move\n",
    "\n",
    "    Returns:\n",
    "    selected_move: The coordinates of numpy array where placing the 0 will lead to win for the opponent\n",
    "\n",
    "    \"\"\" \n",
    "    legal_move_coords =  list(legal_moves_dict.keys())\n",
    "    random.shuffle(legal_move_coords)\n",
    "    for legal_move_coord in legal_move_coords:\n",
    "        current_board_state_copy=current_board_state.copy()\n",
    "        current_board_state_copy[legal_move_coord]=turn_monitor\n",
    "        if 2 not in np.diag(np.fliplr(current_board_state_copy)) and len(set(np.diag(np.fliplr(current_board_state_copy))))==1:\n",
    "            selected_move=legal_move_coord\n",
    "            return selected_move\n",
    "            \n",
    "#------------#\n",
    "\n",
    "def row_block_move_check(current_board_state,legal_moves_dict,turn_monitor):\n",
    "    \"\"\"Function to scan rowwise and identify coordinate amongst the legal coordinates \n",
    "    that will prevent the program \n",
    "    from winning\n",
    "\n",
    "    Args:\n",
    "    legal_moves_dict: Dictionary of legal next moves\n",
    "    turn_monitor: whose turn it is to move\n",
    "    \n",
    "    Returns:\n",
    "    selected_move: The coordinates of numpy array where placing the 0 will block 1 from winning\n",
    "\n",
    "    \"\"\" \n",
    "    legal_move_coords =  list(legal_moves_dict.keys())\n",
    "    random.shuffle(legal_move_coords)\n",
    "    for legal_move_coord in legal_move_coords:\n",
    "        current_board_state_copy=current_board_state.copy()\n",
    "        current_board_state_copy[legal_move_coord]=turn_monitor\n",
    "        for i in range(current_board_state_copy.shape[0]):\n",
    "            if 2 not in current_board_state_copy[i,:] and (current_board_state_copy[i,:]==1).sum()==2:\n",
    "                if not (2 not in current_board_state[i,:] and (current_board_state[i,:]==1).sum()==2):\n",
    "                    selected_move=legal_move_coord\n",
    "                    return selected_move\n",
    "            \n",
    "def column_block_move_check(current_board_state,legal_moves_dict,turn_monitor):\n",
    "    \"\"\"Function to scan column wise and identify coordinate amongst the legal coordinates that will prevent 1 \n",
    "    from winning\n",
    "\n",
    "    Args:\n",
    "    legal_moves_dict: Dictionary of legal next moves\n",
    "    turn_monitor: whose turn it is to move\n",
    "    \n",
    "    Returns:\n",
    "    selected_move: The coordinates of numpy array where placing the 0 will block 1 from winning\n",
    "\n",
    "    \"\"\" \n",
    "    legal_move_coords =  list(legal_moves_dict.keys())\n",
    "    random.shuffle(legal_move_coords)\n",
    "    for legal_move_coord in legal_move_coords:\n",
    "        current_board_state_copy=current_board_state.copy()\n",
    "        current_board_state_copy[legal_move_coord]=turn_monitor\n",
    "        \n",
    "        for j in range(current_board_state_copy.shape[1]):\n",
    "                    if 2 not in current_board_state_copy[:,j] and (current_board_state_copy[:,j]==1).sum()==2:\n",
    "                        if not (2 not in current_board_state[:,j] and (current_board_state[:,j]==1).sum()==2):\n",
    "                            selected_move=legal_move_coord\n",
    "                            return selected_move\n",
    "\n",
    "def diag1_block_move_check(current_board_state,legal_moves_dict,turn_monitor):\n",
    "    \"\"\"Function to scan diagonal 1 and identify coordinate amongst the legal coordinates that will prevent 1 \n",
    "    from winning\n",
    "\n",
    "    Args:\n",
    "    legal_moves_dict: Dictionary of legal next moves\n",
    "    turn_monitor: whose turn it is to move\n",
    "    \n",
    "    Returns:\n",
    "    selected_move: The coordinates of numpy array where placing the 0 will block 1 from winning\n",
    "\n",
    "    \"\"\" \n",
    "    legal_move_coords =  list(legal_moves_dict.keys())\n",
    "    random.shuffle(legal_move_coords)\n",
    "    for legal_move_coord in legal_move_coords:\n",
    "        current_board_state_copy=current_board_state.copy()\n",
    "        current_board_state_copy[legal_move_coord]=turn_monitor    \n",
    "        if 2 not in np.diag(current_board_state_copy) and (np.diag(current_board_state_copy)==1).sum()==2:\n",
    "                if not (2 not in np.diag(current_board_state) and (np.diag(current_board_state)==1).sum()==2):\n",
    "                    selected_move=legal_move_coord\n",
    "                    return selected_move\n",
    "            \n",
    "def diag2_block_move_check(current_board_state,legal_moves_dict,turn_monitor):\n",
    "    \"\"\"Function to scan second diagonal wise and identify coordinate amongst the legal coordinates that will\n",
    "    result in a column having only 0s\n",
    "\n",
    "    Args:\n",
    "    legal_moves_dict: Dictionary of legal next moves\n",
    "    turn_monitor: whose turn it is to move\n",
    "    \n",
    "    Returns:\n",
    "    selected_move: The coordinates of numpy array where placing the 0 will lead to two 0s being there (and no 1s)\n",
    "\n",
    "    \"\"\" \n",
    "    legal_move_coords =  list(legal_moves_dict.keys())\n",
    "    random.shuffle(legal_move_coords)\n",
    "    for legal_move_coord in legal_move_coords:\n",
    "        current_board_state_copy=current_board_state.copy()\n",
    "        current_board_state_copy[legal_move_coord]=turn_monitor\n",
    "        if 2 not in np.diag(np.fliplr(current_board_state_copy)) and (np.diag(np.fliplr(current_board_state_copy))==1).sum()==2:\n",
    "            if not (2 not in np.diag(np.fliplr(current_board_state)) and (np.diag(np.fliplr(current_board_state))==1).sum()==2):\n",
    "                selected_move=legal_move_coord\n",
    "                return selected_move\n",
    "\n",
    "#---------------#\n",
    "def row_second_move_check(current_board_state,legal_moves_dict,turn_monitor):\n",
    "    \"\"\"Function to scan rowwise and identify coordinate amongst the legal coordinates that will\n",
    "    result in a row having two 0s and no 1s\n",
    "\n",
    "    Args:\n",
    "    legal_moves_dict: Dictionary of legal next moves\n",
    "    turn_monitor: whose turn it is to move\n",
    "    \n",
    "    Returns:\n",
    "    selected_move: The coordinates of numpy array where placing the 0 will lead to two 0s being there (and no 1s)\n",
    "\n",
    "    \"\"\" \n",
    "    legal_move_coords =  list(legal_moves_dict.keys())\n",
    "    random.shuffle(legal_move_coords)\n",
    "    for legal_move_coord in legal_move_coords:\n",
    "        current_board_state_copy=current_board_state.copy()\n",
    "        current_board_state_copy[legal_move_coord]=turn_monitor\n",
    "        \n",
    "        for i in range(current_board_state_copy.shape[0]):\n",
    "            if 1 not in current_board_state_copy[i,:] and (current_board_state_copy[i,:]==0).sum()==2:\n",
    "                if not (1 not in current_board_state[i,:] and (current_board_state[i,:]==0).sum()==2):\n",
    "                    selected_move=legal_move_coord\n",
    "                    return selected_move\n",
    "            \n",
    "def column_second_move_check(current_board_state,legal_moves_dict,turn_monitor):\n",
    "    \"\"\"Function to scan column wise and identify coordinate amongst the legal coordinates that will\n",
    "    result in a column having two 0s and no 1s\n",
    "\n",
    "    Args:\n",
    "    legal_moves_dict: Dictionary of legal next moves\n",
    "    turn_monitor: whose turn it is to move\n",
    "    \n",
    "    Returns:\n",
    "    selected_move: The coordinates of numpy array where placing the 0 will lead to two 0s being there (and no 1s)\n",
    "\n",
    "    \"\"\" \n",
    "    legal_move_coords =  list(legal_moves_dict.keys())\n",
    "    random.shuffle(legal_move_coords)\n",
    "    for legal_move_coord in legal_move_coords:\n",
    "        current_board_state_copy=current_board_state.copy()\n",
    "        current_board_state_copy[legal_move_coord]=turn_monitor\n",
    "        \n",
    "        for j in range(current_board_state_copy.shape[1]):\n",
    "                    if 1 not in current_board_state_copy[:,j] and (current_board_state_copy[:,j]==0).sum()==2:\n",
    "                        if not (1 not in current_board_state[:,j] and (current_board_state[:,j]==0).sum()==2):\n",
    "                            selected_move=legal_move_coord\n",
    "                            return selected_move\n",
    "\n",
    "def diag1_second_move_check(current_board_state,legal_moves_dict,turn_monitor):\n",
    "    \"\"\"Function to scan diagonal wise and identify coordinate amongst the legal coordinates that will\n",
    "    result in a column having two 0s and no 1s\n",
    "\n",
    "    Args:\n",
    "    legal_moves_dict: Dictionary of legal next moves\n",
    "    turn_monitor: whose turn it is to move\n",
    "    \n",
    "    Returns:\n",
    "    selected_move: The coordinates of numpy array where placing the 0 will lead to two 0s being there (and no 1s)\n",
    "\n",
    "    \"\"\" \n",
    "    legal_move_coords =  list(legal_moves_dict.keys())\n",
    "    random.shuffle(legal_move_coords)\n",
    "    for legal_move_coord in legal_move_coords:\n",
    "        current_board_state_copy=current_board_state.copy()\n",
    "        current_board_state_copy[legal_move_coord]=turn_monitor\n",
    "        if 1 not in np.diag(current_board_state_copy) and (np.diag(current_board_state_copy)==0).sum()==2:\n",
    "            if not (1 not in np.diag(current_board_state) and (np.diag(current_board_state)==0).sum()==2):\n",
    "                selected_move=legal_move_coord\n",
    "                return selected_move\n",
    "            \n",
    "def diag2_second_move_check(current_board_state,legal_moves_dict,turn_monitor):\n",
    "    \"\"\"Function to scan second diagonal wise and identify coordinate amongst \n",
    "    the legal coordinates that will result in a column having two 0s and no 1s\n",
    "\n",
    "    Args:\n",
    "    legal_moves_dict: Dictionary of legal next moves\n",
    "    turn_monitor: whose turn it is to move\n",
    "    \n",
    "    Returns:\n",
    "    selected_move: The coordinates of numpy array where opponent places their mark\n",
    "\n",
    "    \"\"\" \n",
    "    legal_move_coords =  list(legal_moves_dict.keys())\n",
    "    random.shuffle(legal_move_coords)\n",
    "    for legal_move_coord in legal_move_coords:\n",
    "        current_board_state_copy=current_board_state.copy()\n",
    "        current_board_state_copy[legal_move_coord]=turn_monitor\n",
    "        if 1 not in np.diag(np.fliplr(current_board_state_copy)) and (np.diag(np.fliplr(current_board_state_copy))==0).sum()==2:\n",
    "            if not (1 not in np.diag(np.fliplr(current_board_state)) and (np.diag(np.fliplr(current_board_state))==0).sum()==2):\n",
    "                selected_move=legal_move_coord\n",
    "                return selected_move\n",
    "    \n",
    "def opponent_move_selector(current_board_state,turn_monitor,mode):\n",
    "    \"\"\"Function that picks a legal move for the opponent\n",
    "\n",
    "    Args:\n",
    "    current_board_state: Current board state\n",
    "    turn_monitor: whose turn it is to move\n",
    "    mode: whether hard or easy mode\n",
    "\n",
    "    Returns:\n",
    "    selected_move: The coordinates of numpy array where placing the 0 will lead to two 0s being there (and no 1s)\n",
    "\n",
    "    \"\"\" \n",
    "    legal_moves_dict=legal_moves_generator(current_board_state,turn_monitor)\n",
    "    \n",
    "    winning_move_checks=[row_winning_move_check,column_winning_move_check,diag1_winning_move_check,diag2_winning_move_check]\n",
    "    block_move_checks=[row_block_move_check,column_block_move_check,diag1_block_move_check,diag2_block_move_check]\n",
    "    second_move_checks=[row_second_move_check,column_second_move_check,diag1_second_move_check,diag2_second_move_check]\n",
    "\n",
    "    if mode==\"Hard\":\n",
    "        random.shuffle(winning_move_checks)\n",
    "        random.shuffle(block_move_checks)\n",
    "        random.shuffle(second_move_checks)        \n",
    "        \n",
    "        for fn in winning_move_checks:\n",
    "            if fn(current_board_state,legal_moves_dict,turn_monitor):\n",
    "                return fn(current_board_state,legal_moves_dict,turn_monitor)\n",
    "            \n",
    "        for fn in block_move_checks:\n",
    "            if fn(current_board_state,legal_moves_dict,turn_monitor):\n",
    "                return fn(current_board_state,legal_moves_dict,turn_monitor)\n",
    "            \n",
    "        for fn in second_move_checks:\n",
    "            if fn(current_board_state,legal_moves_dict,turn_monitor):\n",
    "                return fn(current_board_state,legal_moves_dict,turn_monitor)\n",
    "            \n",
    "        selected_move=random.choice(list(legal_moves_dict.keys()))\n",
    "        return selected_move\n",
    "    \n",
    "    elif mode==\"Easy\":\n",
    "        legal_moves_dict=legal_moves_generator(current_board_state,turn_monitor)\n",
    "        selected_move=random.choice(list(legal_moves_dict.keys()))\n",
    "        return selected_move"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Training the Program\n",
    "\n",
    "Training the progam is essentially training the Evaluator(model) to assign higher scores to board states favourable to the program, and lower scores to board states unfavourable to the program.\n",
    "\n",
    "The progam is expected to learn by playing games against the Opponent.\n",
    "\n",
    "The Evaluator (model) is trained in the following way:\n",
    "\n",
    "* At first the weights of the model are randomly assigned\n",
    "* Using this model, the Move Selector function selects the next move to make for the program\n",
    "* The program and the opponent make thier moves until the game ends\n",
    "* After the game is completed, the scores are corrected as follows:\n",
    "    * If the game was Won by the program, assign the score 1 to the final board state, or assign -1 if lost or 0 if drawn\n",
    "    * Shift the remaining scores so that they become the scores of the previous board states\n",
    "    * Update the weights of the model using the board state and corrected score\n",
    "* The above process is repeated over 100s of thousands of games\n",
    "* It is expected that eventually, the Evaluator (model) learns to assign higher scores to more favourable board states and lower scores to less favourable board states"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def train(model,mode,print_progress=False):\n",
    "    \"\"\"Function trains the Evaluator (model) by playing a game against an opponent \n",
    "    playing random moves, and updates the weights of the model after the game\n",
    "    \n",
    "    Note that the model weights are updated using SGD with a batch size of 1\n",
    "\n",
    "    Args:\n",
    "    model: The Evaluator function being trained\n",
    "\n",
    "    Returns:\n",
    "    model: The model updated using SGD\n",
    "    y: The corrected scores\n",
    "\n",
    "    \"\"\" \n",
    "    # start the game\n",
    "    if print_progress==True:\n",
    "        print(\"___________________________________________________________________\")\n",
    "        print(\"Starting a new game\")\n",
    "    game=tic_tac_toe_game()\n",
    "    game.toss()\n",
    "    scores_list=[]\n",
    "    corrected_scores_list=[]\n",
    "    new_board_states_list=[]\n",
    "    \n",
    "    while(1):\n",
    "        if game.game_status()==\"In Progress\" and game.turn_monitor==1:\n",
    "            # If its the program's turn, use the Move Selector function to select the next move\n",
    "            selected_move,new_board_state,score=move_selector(model,game.board,game.turn_monitor)\n",
    "            scores_list.append(score[0][0])\n",
    "            new_board_states_list.append(new_board_state)\n",
    "            # Make the next move\n",
    "            game_status,board=game.move(game.turn_monitor,selected_move)\n",
    "            if print_progress==True:\n",
    "                print(\"Program's Move\")\n",
    "                print(board)\n",
    "                print(\"\\n\")\n",
    "        elif game.game_status()==\"In Progress\" and game.turn_monitor==0:\n",
    "            selected_move=opponent_move_selector(game.board,game.turn_monitor,mode=mode)\n",
    "        \n",
    "            # Make the next move\n",
    "            game_status,board=game.move(game.turn_monitor,selected_move)\n",
    "            if print_progress==True:\n",
    "                print(\"Opponent's Move\")\n",
    "                print(board)\n",
    "                print(\"\\n\")\n",
    "        else:\n",
    "            break\n",
    "\n",
    "    \n",
    "    # Correct the scores, assigning 1/0/-1 to the winning/drawn/losing final board state, \n",
    "    # and assigning the other previous board states the score of their next board state\n",
    "    new_board_states_list=tuple(new_board_states_list)\n",
    "    new_board_states_list=np.vstack(new_board_states_list)\n",
    "    if game_status==\"Won\" and (1-game.turn_monitor)==1: \n",
    "        corrected_scores_list=shift(scores_list,-1,cval=1.0)\n",
    "        result=\"Won\"\n",
    "    if game_status==\"Won\" and (1-game.turn_monitor)!=1:\n",
    "        corrected_scores_list=shift(scores_list,-1,cval=-1.0)\n",
    "        result=\"Lost\"\n",
    "    if game_status==\"Drawn\":\n",
    "        corrected_scores_list=shift(scores_list,-1,cval=0.0)\n",
    "        result=\"Drawn\"\n",
    "    if print_progress==True:\n",
    "        print(\"Program has \",result)\n",
    "        print(\"\\n Correcting the Scores and Updating the model weights:\")\n",
    "        print(\"___________________________________________________________________\\n\")\n",
    "        \n",
    "    x=new_board_states_list\n",
    "    y=corrected_scores_list\n",
    "    \n",
    "    def unison_shuffled_copies(a, b):\n",
    "        assert len(a) == len(b)\n",
    "        p = np.random.permutation(len(a))\n",
    "        return a[p], b[p]\n",
    "    \n",
    "    # shuffle x and y in unison\n",
    "    x,y=unison_shuffled_copies(x,y)\n",
    "    x=x.reshape(-1,9) \n",
    "    \n",
    "    # update the weights of the model, one record at a time\n",
    "    model.fit(x,y,epochs=1,batch_size=1,verbose=0)\n",
    "    return model,y,result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### A sample single training game\n",
    "\n",
    "Note that the program will always play the mark '1' and the opponent will always play mark '0'.\n",
    "\n",
    "below, we run a single iteration of training, or in other words, a single game of tic-tac-toe between the program and opponent."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "updated_model,y,result=train(model,mode=\"Hard\",print_progress=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Training by playing a large number of games\n",
    "\n",
    "We play 200,000 games of tic-tac-toe between the program and the opponent. We record the result of each game and plot the distribution of wins/losses/draws by the program over fixed intervals of games"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "game_counter=1\n",
    "data_for_graph=pd.DataFrame()\n",
    "\n",
    "mode_list=[\"Easy\",\"Hard\"]\n",
    "\n",
    "while(game_counter<=200000):\n",
    "    mode_selected=np.random.choice(mode_list, 1, p=[0.5,0.5])\n",
    "    model,y,result=train(model,mode=mode_selected[0],print_progress=False)\n",
    "    # data_for_graph=data_for_graph.append({\"game_counter\":game_counter,\"result\":result},ignore_index=True)\n",
    "    if game_counter % 10000 == 0:\n",
    "        print(\"Game#: \",game_counter)\n",
    "        print(\"Mode: \",mode_selected[0])\n",
    "    game_counter+=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "model.save('model/ttt.h5')  # creates a HDF5 file 'ttt.h5'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Play Against AI\n",
    "Below you can play against AI agent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def play_with_model(model):\n",
    "    # Start a new game\n",
    "    game = tic_tac_toe_game()\n",
    "    game.toss()\n",
    "    current_player = \"Human\" if game.turn_monitor == 0 else \"Model\"\n",
    "\n",
    "    print(f\"{current_player} won the toss\")\n",
    "\n",
    "    # Game loop\n",
    "    while game.game_status() == \"In Progress\":\n",
    "        print(\"Current board state:\")\n",
    "        print(game.board)\n",
    "        \n",
    "        if game.turn_monitor == 0:  # Human's turn\n",
    "            valid_move = False\n",
    "            while not valid_move:\n",
    "                try:\n",
    "                    move_row = int(input(\"Enter the row where you want to place your mark (0, 1, 2): \"))\n",
    "                    move_col = int(input(\"Enter the column where you want to place your mark (0, 1, 2): \"))\n",
    "                    game_status, board = game.move(0, (move_row, move_col))\n",
    "                    valid_move = True\n",
    "                except ValueError as e:\n",
    "                    print(e)\n",
    "                    print(\"Try again.\")\n",
    "        else:  # Model's turn\n",
    "            selected_move, new_board_state, score = move_selector(model, game.board, game.turn_monitor)\n",
    "            game_status, board = game.move(1, selected_move)\n",
    "            print(f\"Model places at {selected_move}\")\n",
    "\n",
    "    print(f\"Game Over! Status: {game_status}\")\n",
    "    print(\"Final board state:\")\n",
    "    print(game.board)\n",
    "\n",
    "model = load_model('ttt.h5')\n",
    "play_with_model(model)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Convert to ONNX"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "! pip install onnx\n",
    "! pip install keras2onnx\n",
    "! pip install tensorflow\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from tensorflow.python.keras.models import load_model\n",
    "import os\n",
    "os.environ['TF_KERAS'] = '1'\n",
    "import onnxmltools\n",
    "\n",
    "\n",
    "model = load_model('model/ttt.h5')\n",
    "onnx_model = onnxmltools.convert_keras(model) \n",
    "\n",
    "onnxmltools.utils.save_model(onnx_model, 'model/ttt.onnx')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import onnx\n",
    "\n",
    "# Load the ONNX model and check the model structure\n",
    "onnx_model = onnx.load('model/ttt.onnx')\n",
    "onnx.checker.check_model(onnx_model)\n",
    "\n",
    "# You can print the ONNX model's graph to inspect its structure\n",
    "print(onnx_model.graph)"
   ]
  },
  {
   "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.10.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}