community/games/quantum_tic_tac_toe.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"../../images/qiskit-heading.gif\" alt=\"Note: In order for images to show up in this jupyter notebook you need to select File => Trusted Notebook\" width=\"500 px\" align=\"left\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# _*Quantum Tic-Tac-Toe*_\n",
    "\n",
    "The latest version of this notebook is available on https://github.com/qiskit/qiskit-tutorial.\n",
    "\n",
    "***\n",
    "### Contributors\n",
    "[Maor Ben-Shahar](https://github.com/MA0R)\n",
    "***\n",
    "\n",
    "An example run of quantum Tic-Tac-Toe is provided below, with explanations of the game workings following after. Despite the ability to superimpose moves, a winning strategy still exists for both players (meaning the game will be a draw if both implement it). See if you can work it out."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Import the game!\n",
    "import sys\n",
    "sys.path.append('game_engines')\n",
    "from q_tic_tac_toe import Board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "#inputs are (X,Y,print_info).\n",
    "#X,Y are the dimensions of the board. print_info boolean controls if to print instructions at game launch.\n",
    "#Since it is our first time playing, lets set it True and see the instructions!\n",
    "B = Board(3,3,True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Welcome to Quantum tic tac toe!\n",
      "At each turn choose if to make one or two moves.\n",
      "Playing one move at a time is a classic tic tac toe game.\n",
      "At each turn the game state is printed.\n",
      "This constitutes a 3x3 grid (standard game!).\n",
      "You will see empty cells if no move was made on that part of the board.\n",
      "Moves made by X are marked with Xi, 'i' some number.\n",
      "e.g. X3 is the third move, played by X. When a move is made in a super position,\n",
      "You will see its label, say X3, appear in several places.\n",
      "This means your move is in a superposition of two classical moves!\n",
      "A superposition of classical moves does not guarantee that a spot is occupied,\n",
      "so other players can attempt to occupy it too.\n",
      "Then the new move will be anti-correlated with the move already in that spot.\n",
      "And so the game branches out into many simultaneous states.\n",
      "The outcome is then computed by simulation...\n",
      "so don't make too many quantum moves or it will take long to compute!\n",
      "Enter 'q' at any time to quit\n",
      "Enter 'end' to end the game, and compute the winner(s).\n",
      "Good luck!\n",
      "PLAYER X :\n",
      "Play in 1 or 2 cells?q\n"
     ]
    }
   ],
   "source": [
    "B.run()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When playing the game, the two players are asked in turn if to make a classical (1 cell) or quantum move (1 or 2 cells at most, for now). When making any move there are several scenarios that can happen, they are explained below. The terminology used:\n",
    "\n",
    "- Each turn a \"move\" is made\n",
    "- Each move consists of one or two \"cells\", the location(s) where the move is made. It is a superposition of classical moves.\n",
    "\n",
    "\n",
    "Quantum moves are restricted to two cells only due to them requiring an increasing number of qubits, which is slow to simulate."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## One move on an empty cell "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is the simplest move, it is a \"classical\" move. The game registers this move as a set of coordinates, and the player who made the move. No qubits are used here. \n",
    "It is registered as such:  \n",
    "`Play in one or two cells?1\n",
    "x index: 0\n",
    "y index: 0`  \n",
    "First the player is asked how many moves (we chose 1, classical). Then it asks for the index of the move.\n",
    "And the board registers it as  \n",
    "`\n",
    "[['O1','',''],\n",
    " ['','',''],\n",
    " ['','','']]\n",
    "`  \n",
    "This move is *always* present at the end of the game."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Two-cell moves in empty cells\n",
    "This is a quantum move, the game stores a move that is in a superposition of being played at *two* cells. Ordered coordinates for the two cells to be occupied need to be provided. A row in the board with a superposition move would look like so  \n",
    "`[X1,X1,'']`   \n",
    "Two qubits were used in order to register this move. They are in a state $|10>+|01>$, if the first qubit is measured to be 1 then the board becomes `[X1,'','']` and vice versa. Why can we not use just one qubit to record this? We can, and the qubit would have to be put into a state $|0>+|1>$ but I did not implement this yet since this is method will be consistant with later types of quantum moves.\n",
    "\n",
    "Let us see this in action:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "PLAYER X :\n",
      "Play in 1 or 2 cells?2\n",
      "x1 index:0\n",
      "y1 index:0\n",
      "x2 index:1\n",
      "y2 index:0\n",
      "[['X1' 'X1' '']\n",
      " ['' '' '']\n",
      " ['' '' '']]\n",
      "PLAYER O :\n",
      "Play in 1 or 2 cells?end\n",
      "simulation:  COMPLETED\n",
      "{'010': 53, '100': 47}\n",
      "X wins: 0\n",
      "O wins: 0\n",
      "Shots: 53\n",
      "[['x' '' '']\n",
      " ['' '' '']\n",
      " ['' '' '']]\n",
      "X wins: 0\n",
      "O wins: 0\n",
      "Shots: 47\n",
      "[['' 'x' '']\n",
      " ['' '' '']\n",
      " ['' '' '']]\n"
     ]
    }
   ],
   "source": [
    "B = Board(3,3)\n",
    "B.run()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The game outcome is almost 50% in each cell, as we would expect. There is a redundant bit at the end of the bit code (to be removed soon!). And note that the bit strings are the inversed order to what we write here, this is because the quantum register in qiskit has positions $|q_n,...,q_0>$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## One-cell move plyed in a maybe-occupied cell\n",
    "It is possible that after the game is in state `[X1,X1,'']` one would definitely want to make a move at position (0,0). This could be when the game is completely full perhaps, since it is not a very good strategy. Such a move can be erased from the game history! Let us see how it is recorded. The first row of the board is now \n",
    "`[X1 O2,X1,'']`  \n",
    "and the state of the game qubits is  \n",
    "$$ |100>+|011> $$  \n",
    "with the first qubit recording sucess of the first move at cell (0,0), the second qubit is the success of the first move in cell (0,1) and the third qubit is the move by player O, which is anti correlated with the move by X at cell (0,0).  \n",
    "Notice that this move can be completely erased!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[['X1' 'X1' '']\n",
      " ['' '' '']\n",
      " ['' '' '']]\n",
      "[['X1 O2' 'X1' '']\n",
      " ['' '' '']\n",
      " ['' '' '']]\n",
      "simulation:  COMPLETED\n",
      "{'0010': 48, '1100': 52}\n",
      "X wins: 0\n",
      "O wins: 0\n",
      "Shots: 48\n",
      "[['x' '' '']\n",
      " ['' '' '']\n",
      " ['' '' '']]\n",
      "X wins: 0\n",
      "O wins: 0\n",
      "Shots: 52\n",
      "[['o' 'x' '']\n",
      " ['' '' '']\n",
      " ['' '' '']]\n"
     ]
    }
   ],
   "source": [
    "B = Board(3,3)\n",
    "B.add_move([[0,0],[0,1]],0) #Directly adding moves, ([indx1,indx2],player) 0=X, 1=O.\n",
    "B.add_move([[0,0]],1)\n",
    "B.compute_winner()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Once again note that the move could be erased completely, and in fact this happens 50% of the time. Notice how the bit string output from QISKIT is translated into a board state."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Two-cell moves in maybe-occupied cells\n",
    "Instead of the above, player O might like to choose a better strategy. Perhaps O is interested in a quantum move on cells (0,0) and (0,2). In such a case the game records the two moves in the order they are entered.\n",
    "\n",
    "- In order (0,0) then (0,2): The state of the game is first made into $ |100>+|011> $ as above, with the third qubit recording the sucess of player O getting position (0,0). Then the (0,2) position is registered, anti-correlated with suceeding in position (0,0): $|1001>+|0110>$. Now, unlike before, player O suceeds in registering a move regardless of the outcome. \n",
    "- In order (0,2) then (0,0): Now playing at (0,2) is not dependent on anything, and so the game state is $(|10>+|01>)\\otimes (|1>+|0>) = |101>+|100>+|011>+|010>$. And when the move in position (0,0) is added too, it is anti correlated with BOTH the move in (0,2) AND the pre-existing move in (0,0). So qubit state becomes $|1010>+|1000>+|0110>+|0101>$. Notice how now the move could be erased, so order does matter!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[['X1' 'X1' '']\n",
      " ['' '' '']\n",
      " ['' '' '']]\n",
      "[['X1 O2' 'X1' 'O2']\n",
      " ['' '' '']\n",
      " ['' '' '']]\n",
      "simulation:  COMPLETED\n",
      "{'10010': 42, '01100': 58}\n",
      "X wins: 0\n",
      "O wins: 0\n",
      "Shots: 42\n",
      "[['x' '' 'o']\n",
      " ['' '' '']\n",
      " ['' '' '']]\n",
      "X wins: 0\n",
      "O wins: 0\n",
      "Shots: 58\n",
      "[['o' 'x' '']\n",
      " ['' '' '']\n",
      " ['' '' '']]\n"
     ]
    }
   ],
   "source": [
    "B = Board(3,3)\n",
    "#Instead of running the game, for the purpose of demonstrating, we can just create the appropriate state manually.\n",
    "#Directly adding moves, ([[y1,x1],[x2,y2]],player) with player=0->X, 1->O.\n",
    "B.add_move([[0,0],[0,1]],0)\n",
    "B.add_move([[0,0],[0,2]],1)\n",
    "B.compute_winner()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise: what if player O chose coordinates (x=0,y=0) and (x=1,y=0) instead?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise: At this stage, can player X ensure that no matter what O plays, both  (x=0,y=0) and (x=1,y=0) are occupied by X?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And that is all there is to quantum tic tic toe! Remember, to run the game, import the board:\n",
    "\n",
    "`from q_tic_tac_toe import Board`\n",
    "\n",
    "Create the board you want to play on:\n",
    "\n",
    "`B = Board(3,3,True)`\n",
    "\n",
    "and run!\n",
    "\n",
    "`B.run()`"
   ]
  }
 ],
 "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.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}