tic_tac_toe.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from tic_env import TictactoeEnv, OptimalPlayer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Tic Toc Toe environment"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Our 1st game is the famous Tic Toc Toe. You can read about the game and its rules here: https://en.wikipedia.org/wiki/Tic-tac-toe\n",
    "\n",
    "We implemented the game as an environment in the style of games in the [Python GYM library](https://gym.openai.com/). The commented source code is available in the file \"tic_env.py\". Here, we give a brief introduction to the environment and how it can be used."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Initialization and attributes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can initialize the environment / game as following:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "env = TictactoeEnv()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Which then has the following attributes with the corresponding initial values:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'grid': array([[0., 0., 0.],\n",
       "        [0., 0., 0.],\n",
       "        [0., 0., 0.]]),\n",
       " 'end': False,\n",
       " 'winner': None,\n",
       " 'player2value': {'X': 1, 'O': -1},\n",
       " 'num_step': 0,\n",
       " 'current_player': 'X'}"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "env.__dict__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The game is played by two players: player 'X' and player 'O'. The attribute 'current_player' shows whose turn it is. We assume that player 'X' always plays first.\n",
    "\n",
    "The attribute 'grid' is a 3x3 numpy array and presents the board in the real game and the state $s_t$ in the reinfocement learning language. Each elements can take a value in {0, 1, -1}:\n",
    "     0 : place unmarked\n",
    "     1 : place marked with X \n",
    "    -1 : place marked with O \n",
    "        \n",
    "The attribute 'end' shows if the game is over or not, and the attribute 'winner' shows the winner of the game: either \"X\", \"O\", or None.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can use function 'render' to visualize the current position of the board:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "|- - -|\n",
      "|- - -|\n",
      "|- - -|\n",
      "\n"
     ]
    }
   ],
   "source": [
    "env.render()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Taking actions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The game environment will recieve action from two players in turn and update the grid. At each time, one player can take the action $a_t$, where $a_t$ can either be an integer between 0 to 8 or a touple, corresponding to the 9 possible.\n",
    "\n",
    "Function 'step' is used to recieve the action of the player, update the grid:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(array([[0., 0., 1.],\n",
       "        [0., 0., 0.],\n",
       "        [0., 0., 0.]]),\n",
       " False,\n",
       " None)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "env.step(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "|- - X|\n",
      "|- - -|\n",
      "|- - -|\n",
      "\n"
     ]
    }
   ],
   "source": [
    "env.render()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'grid': array([[0., 0., 1.],\n",
       "        [0., 0., 0.],\n",
       "        [0., 0., 0.]]),\n",
       " 'end': False,\n",
       " 'winner': None,\n",
       " 'player2value': {'X': 1, 'O': -1},\n",
       " 'num_step': 1,\n",
       " 'current_player': 'O'}"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "env.__dict__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(array([[ 0.,  0.,  1.],\n",
       "        [ 0., -1.,  0.],\n",
       "        [ 0.,  0.,  0.]]),\n",
       " False,\n",
       " None)"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "env.step((1,1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "|- - X|\n",
      "|- O -|\n",
      "|- - -|\n",
      "\n"
     ]
    }
   ],
   "source": [
    "env.render()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'grid': array([[ 0.,  0.,  1.],\n",
       "        [ 0., -1.,  0.],\n",
       "        [ 0.,  0.,  0.]]),\n",
       " 'end': False,\n",
       " 'winner': None,\n",
       " 'player2value': {'X': 1, 'O': -1},\n",
       " 'num_step': 2,\n",
       " 'current_player': 'X'}"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "env.__dict__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But not all actions are available at each time: One cannot choose a place which has been taken before. There is an error if an unavailable action is taken:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "ename": "ValueError",
     "evalue": "There is already a chess on position (0, 2).",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mValueError\u001b[0m                                Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-11-d34f74f4d1da>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0menv\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mstep\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;36m2\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;32mc:\\Users\\MaximilianGangloff\\Documents\\Schweiz\\EPFL\\Master\\ANN\\Projects\\Miniproject1\\tic_env.py\u001b[0m in \u001b[0;36mstep\u001b[1;34m(self, position, print_grid)\u001b[0m\n\u001b[0;32m     59\u001b[0m             \u001b[0mposition\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mtuple\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mposition\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     60\u001b[0m         \u001b[1;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mgrid\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mposition\u001b[0m\u001b[1;33m]\u001b[0m \u001b[1;33m!=\u001b[0m \u001b[1;36m0\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 61\u001b[1;33m             \u001b[1;32mraise\u001b[0m \u001b[0mValueError\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m'There is already a chess on position {}.'\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mposition\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     62\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     63\u001b[0m         \u001b[1;31m# place a chess on the position\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mValueError\u001b[0m: There is already a chess on position (0, 2)."
     ]
    }
   ],
   "source": [
    "env.step((0,2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Reward"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Reward is always 0 until the end of the game. When the game is over, the reward is 1 if you win the game, -1 if you lose, and 0 besides. Function 'observe' can be used after each step to recieve the new state $s_t$, whether the game is over, and the winner, and function 'reward' to get the reward value $r_t$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(array([[ 0.,  0.,  1.],\n",
       "        [ 0., -1.,  0.],\n",
       "        [ 0.,  0.,  0.]]),\n",
       " False,\n",
       " None)"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "env.observe()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "env.reward(player='X')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "env.reward(player='O')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An example of finishing the game:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(array([[ 1.,  1.,  1.],\n",
       "        [-1., -1.,  0.],\n",
       "        [ 0.,  0.,  0.]]),\n",
       " True,\n",
       " 'X')"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "env.step(0)\n",
    "env.step(3)\n",
    "env.step(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "|X X X|\n",
      "|O O -|\n",
      "|- - -|\n",
      "\n"
     ]
    }
   ],
   "source": [
    "env.render()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(array([[ 1.,  1.,  1.],\n",
       "        [-1., -1.,  0.],\n",
       "        [ 0.,  0.,  0.]]),\n",
       " True,\n",
       " 'X')"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "env.observe()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "env.reward(player='X')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "env.reward(player='O')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Optimal policy for Tic Toc Toe environment"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Fortunately, we know the exact optimal policy for Tic Toc Toe. We have implemented and $\\epsilon$-greedy version of optimal polciy which you can use for the project."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "env.reset();"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "opt_player = OptimalPlayer(epsilon = 0., player = 'X')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, 1)"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "opt_player.act(env.grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'X'"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "opt_player.player"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### An example of optimal player playing against random player"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-------------------------------------------\n",
      "Game end, winner is player None\n",
      "Optimal player = O\n",
      "Random player = X\n",
      "|X X O|\n",
      "|O O X|\n",
      "|X X O|\n",
      "\n",
      "-------------------------------------------\n",
      "Game end, winner is player O\n",
      "Optimal player = O\n",
      "Random player = X\n",
      "|X O O|\n",
      "|- O X|\n",
      "|O X X|\n",
      "\n",
      "-------------------------------------------\n",
      "Game end, winner is player None\n",
      "Optimal player = X\n",
      "Random player = O\n",
      "|X O X|\n",
      "|X X O|\n",
      "|O X O|\n",
      "\n",
      "-------------------------------------------\n",
      "Game end, winner is player O\n",
      "Optimal player = O\n",
      "Random player = X\n",
      "|O - X|\n",
      "|X O X|\n",
      "|- - O|\n",
      "\n",
      "-------------------------------------------\n",
      "Game end, winner is player O\n",
      "Optimal player = O\n",
      "Random player = X\n",
      "|X - O|\n",
      "|- O -|\n",
      "|O X X|\n",
      "\n"
     ]
    }
   ],
   "source": [
    "Turns = np.array(['X','O'])\n",
    "for i in range(5):\n",
    "    env.reset()\n",
    "    grid, _, __ = env.observe()\n",
    "    Turns = Turns[np.random.permutation(2)]\n",
    "    player_opt = OptimalPlayer(epsilon=0., player=Turns[0])\n",
    "    player_rnd = OptimalPlayer(epsilon=1., player=Turns[1])\n",
    "    for j in range(9):\n",
    "        if env.current_player == player_opt.player:\n",
    "            move = player_opt.act(grid)\n",
    "        else:\n",
    "            move = player_rnd.act(grid)\n",
    "\n",
    "        grid, end, winner = env.step(move, print_grid=False)\n",
    "\n",
    "        if end:\n",
    "            print('-------------------------------------------')\n",
    "            print('Game end, winner is player ' + str(winner))\n",
    "            print('Optimal player = ' +  Turns[0])\n",
    "            print('Random player = ' +  Turns[1])\n",
    "            env.render()\n",
    "            env.reset()\n",
    "            break\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### An example of optimal player playing against optimal player"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-------------------------------------------\n",
      "Game end, winner is player None\n",
      "Optimal player 1 = O\n",
      "Optimal player 2 = X\n",
      "|X X O|\n",
      "|O O X|\n",
      "|X O X|\n",
      "\n",
      "-------------------------------------------\n",
      "Game end, winner is player None\n",
      "Optimal player 1 = X\n",
      "Optimal player 2 = O\n",
      "|X X O|\n",
      "|O O X|\n",
      "|X O X|\n",
      "\n",
      "-------------------------------------------\n",
      "Game end, winner is player None\n",
      "Optimal player 1 = X\n",
      "Optimal player 2 = O\n",
      "|X O X|\n",
      "|X O O|\n",
      "|O X X|\n",
      "\n",
      "-------------------------------------------\n",
      "Game end, winner is player None\n",
      "Optimal player 1 = X\n",
      "Optimal player 2 = O\n",
      "|X O X|\n",
      "|O O X|\n",
      "|X X O|\n",
      "\n",
      "-------------------------------------------\n",
      "Game end, winner is player None\n",
      "Optimal player 1 = O\n",
      "Optimal player 2 = X\n",
      "|O O X|\n",
      "|X X O|\n",
      "|O X X|\n",
      "\n"
     ]
    }
   ],
   "source": [
    "Turns = np.array(['X','O'])\n",
    "for i in range(5):\n",
    "    env.reset()\n",
    "    grid, _, __ = env.observe()\n",
    "    Turns = Turns[np.random.permutation(2)]\n",
    "    player_opt_1 = OptimalPlayer(epsilon=0., player=Turns[0])\n",
    "    player_opt_2 = OptimalPlayer(epsilon=0., player=Turns[1])\n",
    "    for j in range(9):\n",
    "        if env.current_player == player_opt.player:\n",
    "            move = player_opt_1.act(grid)\n",
    "        else:\n",
    "            move = player_opt_2.act(grid)\n",
    "\n",
    "        grid, end, winner = env.step(move, print_grid=False)\n",
    "\n",
    "        if end:\n",
    "            print('-------------------------------------------')\n",
    "            print('Game end, winner is player ' + str(winner))\n",
    "            print('Optimal player 1 = ' +  Turns[0])\n",
    "            print('Optimal player 2 = ' +  Turns[1])\n",
    "            env.render()\n",
    "            env.reset()\n",
    "            break\n"
   ]
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "d643e56c8356b332e138988d3326f90faf1438da2687a45045158120a5c71be7"
  },
  "kernelspec": {
   "display_name": "ANN_env_2022",
   "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.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}