Notebooks/TicTacToe MCTS.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Tic Tac Toe MCTS.ipynb",
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "3RLUwr5J65A0"
      },
      "source": [
        "#MCTS Tic Tac Toe"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "MykLo6xP65A1"
      },
      "source": [
        "from copy import deepcopy\n",
        "from math import log, sqrt\n",
        "from random import choice as rndchoice\n",
        "import time\n",
        "import random\n",
        "import numpy as np\n",
        "import matplotlib.pyplot as plt"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "w5AqKqL965A6"
      },
      "source": [
        "class TTT:\n",
        "    def __init__(self):\n",
        "        \n",
        "        self.board = list('_' * 9)\n",
        "        self.result = 0\n",
        "        self.player = 1\n",
        "\n",
        "    def render(self):\n",
        "        disp_board = [f' {self.board[i]} ' if self.board[i] != '_' else f'({str(i)})' for i in range(9)]\n",
        "        for i in range(3):\n",
        "            print(' '.join(disp_board[3 * i:3 * (i + 1)]))\n",
        "        print('----------------------------------------------------------')\n",
        "\n",
        "    def checkresult(self):\n",
        "        winning_cases = [(0, 1, 2), (3, 4, 5), (6, 7, 8),\n",
        "                         (0, 3, 6), (1, 4, 7), (2, 5, 8),\n",
        "                         (0, 4, 8), (2, 4, 6)]\n",
        "\n",
        "        for wc in winning_cases:\n",
        "            if self.board[wc[0]] != '_' and \\\n",
        "                    self.board[wc[0]] == self.board[wc[1]] and \\\n",
        "                    self.board[wc[1]] == self.board[wc[2]]:\n",
        "                if self.board[wc[0]] == 'X':\n",
        "                    self.result = 1\n",
        "                else:\n",
        "                    self.result = 2\n",
        "        if '_' not in self.board:\n",
        "            self.result = 3\n",
        "\n",
        "    def checkresult_with_returns(self, s=None):\n",
        "        s = self.board if s is None else s\n",
        "\n",
        "        winning_cases = [(0, 1, 2), (3, 4, 5), (6, 7, 8),\n",
        "                         (0, 3, 6), (1, 4, 7), (2, 5, 8),\n",
        "                         (0, 4, 8), (2, 4, 6)]\n",
        "        for wc in winning_cases:\n",
        "            if s[wc[0]] != '_' and \\\n",
        "                    s[wc[0]] == s[wc[1]] and \\\n",
        "                    s[wc[1]] == s[wc[2]]:\n",
        "                if s[wc[0]] == 'O':\n",
        "                    return 1\n",
        "                else:\n",
        "                    return 2\n",
        "        if '_' not in self.board:\n",
        "            return 3\n",
        "        else:\n",
        "            return 0\n",
        "\n",
        "    @staticmethod\n",
        "    def player_marker(p):\n",
        "        if p == 1:\n",
        "            return 'X'\n",
        "        else:\n",
        "            return 'O'\n",
        "\n",
        "    def player_input(self):\n",
        "        marker = TTT.player_marker(self.player)\n",
        "        input_msg = f'Player {self.player}({marker}), select your next position\\n'\n",
        "\n",
        "        while 1:\n",
        "            try:\n",
        "                v = int(input(input_msg))\n",
        "                if self.board[v] != '_':\n",
        "                    raise NotImplementedError\n",
        "                else:\n",
        "                    break\n",
        "            except NotImplementedError:\n",
        "                print(\"You can't place marker on that place\")\n",
        "\n",
        "        self.board[v] = marker\n",
        "        print()\n",
        "\n",
        "    def ai_input(self, v):\n",
        "        marker = TTT.player_marker(self.player)\n",
        "        self.board[v] = marker\n",
        "\n",
        "    def switch_player(self):\n",
        "        self.player = 3 - self.player\n",
        "\n",
        "    def play(self):\n",
        "        while self.result == 0:\n",
        "            self.render()\n",
        "            self.player_input()\n",
        "            self.checkresult()\n",
        "            self.switch_player()\n",
        "        self.render()\n",
        "        if self.result == 3:\n",
        "            print('Game ended in DRAW')\n",
        "        else:\n",
        "            print(f'Player {self.result}({TTT.player_marker(self.result)}) Won!')\n",
        "\n",
        "    def empty_spots(self):\n",
        "        empty=[]\n",
        "        for i in range(len(self.board)):\n",
        "            if self.board[i]=='_' or self.board[i]==0:\n",
        "                empty.append(i)\n",
        "        return np.array(empty)\n",
        "    \n",
        "    def move(self,act,turn):\n",
        "        self.board[act]=self.player_marker(turn)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DuekSktK65A-"
      },
      "source": [
        "winning_cases = [(0, 1, 2), (3, 4, 5), (6, 7, 8),\n",
        "                 (0, 3, 6), (1, 4, 7), (2, 5, 8),\n",
        "                 (0, 4, 8), (2, 4, 6)]\n",
        "\n",
        "class Node:\n",
        "    def __init__(self, s, par_node=None, pre_action=None):\n",
        "        self.parent = par_node\n",
        "        self.child = []\n",
        "        self.q = 0\n",
        "        self.n = 0\n",
        "        self.pre_action = pre_action\n",
        "        self.state = s\n",
        "        self.player = MCTS.current_player(s)\n",
        "        self.utc = float('inf')\n",
        "        self.result = MCTS.is_terminal(s)\n",
        "\n",
        "    def __repr__(self):\n",
        "        ratio = self.q / (self.n + 1)\n",
        "        l = [str(e) for e in (self.pre_action, ''.join(self.state), self.q, self.n, str(ratio)[:5], str(self.utc)[:5])]\n",
        "        return ' '.join(l)\n",
        "\n",
        "    def update(self, v):\n",
        "        self.n += 1\n",
        "        if v == 3:\n",
        "            self.q += 0.5\n",
        "        elif v == 3 - self.player:\n",
        "            self.q += 1\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "nI_eFkEB65BE"
      },
      "source": [
        "\n",
        "class MCTS:\n",
        "    def __init__(self, s):\n",
        "        self.root = Node(s)\n",
        "        self._expansion(self.root)\n",
        "\n",
        "    def mcts(self, mode='iteration', criteria=10000, new_board=None):\n",
        "        if new_board is not None:\n",
        "            self.__init__(new_board)\n",
        "        if mode == 'iter':\n",
        "            for _ in range(criteria):\n",
        "                self._mcts_loop()\n",
        "            return criteria\n",
        "        elif mode == 'time':\n",
        "            start_time = time.time()\n",
        "            time_criteria = criteria/1000\n",
        "            iii = 0\n",
        "            while time.time() - start_time < time_criteria:\n",
        "                self._mcts_loop()\n",
        "                iii += 1\n",
        "            return iii\n",
        "        else:\n",
        "            raise NotImplementedError\n",
        "\n",
        "    def result_view(self):\n",
        "        best_node, best_visits = None, 0\n",
        "        for n in self.root.child:\n",
        "            if n.n > best_visits: \n",
        "                best_visits, best_node = n.n, n\n",
        "        return int(best_node.pre_action)\n",
        "\n",
        "    def result_return(self):\n",
        "        best_node, best_visits = None, 0\n",
        "        for n in self.root.child:\n",
        "            if n.n > best_visits: best_visits, best_node = n.n, n\n",
        "        return best_node.pre_action\n",
        "\n",
        "    def _mcts_loop(self):\n",
        "        node = self._selection(self.root)\n",
        "        self._expansion(node)\n",
        "\n",
        "        if node.child:\n",
        "            selected_node = rndchoice(node.child)\n",
        "        else:\n",
        "            selected_node = node\n",
        "\n",
        "        v = self._simulation(deepcopy(selected_node.state))\n",
        "        self._backpropagation(selected_node, v)\n",
        "\n",
        "    def _selection(self, node):\n",
        "        if node.child:\n",
        "            imax, vmax = 0, 0\n",
        "            for i, n in enumerate(node.child):\n",
        "                n.utc = MCTS.utc(n)\n",
        "                v = n.utc\n",
        "                if v > vmax:\n",
        "                    imax, vmax = i, v\n",
        "            selected = node.child[imax]\n",
        "            return self._selection(selected)\n",
        "        else:\n",
        "            selected = node\n",
        "            return selected\n",
        "\n",
        "    def _expansion(self, node):\n",
        "        if self.is_terminal(node.state) == 0:\n",
        "            actions = self.actions_available(node.state)\n",
        "            for a in actions:\n",
        "                state_after_action = self.action_result(node.state, a)\n",
        "                node.child.append(Node(state_after_action, node, a))\n",
        "\n",
        "    def _simulation(self, s):\n",
        "        if self.is_terminal(s) == 0:\n",
        "            actions = self.actions_available(s)\n",
        "            a = rndchoice(actions)\n",
        "            s = self.action_result(s, a)\n",
        "            return self._simulation(s)\n",
        "        else:\n",
        "            return self.is_terminal(s)\n",
        "\n",
        "    def _backpropagation(self, node, v):\n",
        "        node.update(v)\n",
        "        if node.parent:\n",
        "            self._backpropagation(node.parent, v)\n",
        "\n",
        "    @staticmethod\n",
        "    def is_terminal(s):\n",
        "        for wc in winning_cases:\n",
        "            if s[wc[0]] != '_' and \\\n",
        "                    s[wc[0]] == s[wc[1]] and \\\n",
        "                    s[wc[1]] == s[wc[2]]:\n",
        "                if s[wc[0]] == 'X':\n",
        "                    return 1\n",
        "                else:\n",
        "                    return 2\n",
        "        if '_' not in s:\n",
        "            return 3\n",
        "        else:\n",
        "            return 0\n",
        "\n",
        "    @staticmethod\n",
        "    def actions_available(s):\n",
        "        l = []\n",
        "        for i in range(9):\n",
        "            if s[i] == '_': l.append(i)\n",
        "        return l\n",
        "\n",
        "    @staticmethod\n",
        "    def action_result(s, a):\n",
        "        p = MCTS.current_player(s)\n",
        "        new_s = deepcopy(s)\n",
        "        new_s[a] = 'X' if p == 1 else 'O'\n",
        "        return new_s\n",
        "\n",
        "    @staticmethod\n",
        "    def current_player(s):\n",
        "        n = s.count('_')\n",
        "        if n % 2 == 1: return 1\n",
        "        return 2\n",
        "\n",
        "    @staticmethod\n",
        "    def utc(node):\n",
        "        v = node.q / (node.n + 1e-12) + sqrt(2 * log(node.parent.n + 1) / (node.n + 1e-12))\n",
        "        return v\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wn9tOvpe65BI"
      },
      "source": [
        "def safe_agent(board,turn):\n",
        "    new = deepcopy(board)\n",
        "    for i in new.empty_spots():\n",
        "        new.board[i]==turn\n",
        "        if (new.result==1 and turn==-1) or (new.result==2 and turn==1):\n",
        "            return i\n",
        "        new = board\n",
        "    for i in new.empty_spots():\n",
        "        new.board[i]==-1*turn\n",
        "        if (new.result==2 and turn==-1) or (new.result==1 and turn==1):\n",
        "            return i\n",
        "        new = board\n",
        "    return random.choice(np.array(new.empty_spots()))"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Sfk-p_mN65BP"
      },
      "source": [
        "\n",
        "def startgame(inital_config=['_']*9,games=100,turn_arr=[-1,1],agent=0):\n",
        "    wins=0\n",
        "    ties=0\n",
        "    loss=0\n",
        "    startwins=0\n",
        "    startdraw=0\n",
        "    startloss=0\n",
        "    flag=0\n",
        "    for i in range(games):\n",
        "        t = TTT()\n",
        "        t.board = deepcopy(inital_config)\n",
        "        m = MCTS(t.board)\n",
        "        turn = np.random.choice(turn_arr)\n",
        "        flag=turn\n",
        "        while t.result == 0:\n",
        "            if turn==-1:\n",
        "                if agent==0:\n",
        "                    action = random.choice(t.empty_spots())\n",
        "                    t.move(action,-1)\n",
        "                elif agent==1 :\n",
        "                    action = safe_agent(t,turn)\n",
        "                    t.move(action,-1)\n",
        "                elif agent==2:\n",
        "                    time_start = time.time()\n",
        "                    ii = m.mcts(new_board=t.board, mode='time', criteria=2000)\n",
        "                    action=m.result_view()\n",
        "                    t.move(action,-1)    \n",
        "                turn*=-1\n",
        "                t.checkresult()\n",
        "            else:\n",
        "                time_start = time.time()\n",
        "                ii = m.mcts(new_board=t.board, mode='time', criteria=2000)\n",
        "                action=m.result_view()\n",
        "                t.move(action,1)\n",
        "                turn*=-1\n",
        "                t.checkresult()\n",
        "            t.switch_player()\n",
        "        if t.result==1:\n",
        "            wins+=1\n",
        "            if flag==1:\n",
        "                startwins+=1\n",
        "        elif t.result==2:\n",
        "            if flag==1:\n",
        "                startloss+=1\n",
        "        elif t.result == 3:\n",
        "            if flag==1:\n",
        "                startdraw+=1\n",
        "            ties+=1\n",
        "        if i%20==0 and i!=0:\n",
        "            print('--------------Summary so far. Game Number {}/{}---------------------'.format(i,games))\n",
        "            print('\\t \\t' ,' Games', ' Wins', ' Losses', ' Draws')\n",
        "            print('As Player 1 \\t',startwins+startloss+startdraw,'\\t',startwins,'\\t',startloss,'\\t',startdraw)\n",
        "            print('As Player 2 \\t',(wins+loss+ties)-(startwins+startloss+startdraw),'\\t',wins-startwins,'\\t',loss-startloss,'\\t',ties-startdraw)\n",
        "            print('In Total \\t',wins+loss+ties,'\\t',wins,'\\t',loss,'\\t',ties)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "B0PelZmD65BY"
      },
      "source": [
        "print('----------------------------Playing Against Random Agent----------------------------')\n",
        "startgame(games=1000,turn_arr=[-1,1],agent=0)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "sCKse61X65Bc"
      },
      "source": [
        "print('----------------------------Playing Against Safe Agent------------------------------')\n",
        "startgame(games=1000,turn_arr=[-1,1],agent=1)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "o5x3A_S065Bj"
      },
      "source": [
        "print('----------------------------Playing Against MCTS Agent------------------------------')\n",
        "startgame(games=1000,turn_arr=[-1,1],agent=2)"
      ],
      "execution_count": null,
      "outputs": []
    }
  ]
}