2015_05_TicTacOh.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "46823cb5-38bc-44d0-8cd7-22b98fcb380b",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from copy import copy\n",
    "import random\n",
    "import seaborn as sns\n",
    "import matplotlib.pyplot as plt\n",
    "from fractions import Fraction\n",
    "import requests\n",
    "from bs4 import BeautifulSoup\n",
    "from IPython.display import Markdown, display,IFrame,HTML,Image\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "7cc3a8b7-12ee-4ac5-b074-ffe705030f4d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "### Puzzle as published \n",
       "https://www.janestreet.com/puzzles/tic-tac-oh-index/"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<div class=\"inner-wrapper\">\n",
       "<p>You’re going to play Tic Tac Toe against a computer program, and you get to go\n",
       "first. The program is not very smart, and its strategy, which you are aware of,\n",
       "is to just mark a uniformly randomly chosen un-filled square on each turn. It\n",
       "would be really embarrassing not to beat this computer program, so in your eyes,\n",
       "a tie game is just as bad as a loss. What’s the maximum chance of winning you\n",
       "can give yourself?</p>\n",
       "</div>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "url='https://www.janestreet.com/puzzles/tic-tac-oh-index/'\n",
    "res = requests.get(url)\n",
    "soup = BeautifulSoup(res.content, 'html.parser')\n",
    "display(Markdown('### Puzzle as published \\n'+url))\n",
    "display(HTML(str(soup.find('div', {'class' :'inner-wrapper'}))))\n",
    "# Currently implemented minimax but best play against optimal != best play vs random\n",
    "\n",
    "#https://math.stackexchange.com/questions/4045893/if-two-computers-are-playing-tic-tac-toe-but-they-are-choosing-their-squares-ra"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "c3ba0d74-e666-4b19-925a-70fb6f2f21d9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAH4AAAB7CAYAAACy7jQ7AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAAsTAAALEwEAmpwYAAAFBUlEQVR4nO3dT0jTfxzH8ddXxJKgbx37ptd9E4k6tGF0ENzcMcZuwm6aHTp46N6tiA5lwaDVwD+dOmmXjiJi5BQPKkV48KCJhxoMHbWo8e5QP35E+4Pu8/1j79cDuvhd86VPdHPIR0tEQPq0BT2AgsHwSjG8UgyvFMMrxfBKtTe6aFkWf9Y7xkTEqnetYfjf/9nsmhZY1q+PI0ybgHDu+m9TPfxWrxTDK8XwSjG8UgyvFMMrxfBKMbxSDK9U01fu/kWLi4uYnJzExsYGvnz5AsdxkEgkMDo6Ctu2g57nC6vRy4yWZUkYX4ZsZdPTp0/x6NEjJBIJpFIp2LaNd+/e4fnz5zh16hSmp6dx7tw533eZZllWw9fqISJ1//26HB4ApJVNb9++Fdd15e7du39d297elmg0KplMxvddXvi9p25bVY/x+Xwetm3j9u3bf13r7u7GjRs3sLy8jLW1tQDW+UtN+B8/fmBlZQXXrl3DiRMnat5mYGAAALC0tOTntECoCV8qlVCpVHD+/Pm6t+nq6gIA7O3t+TUrMGrCS4ieeIWBmvBnz57FyZMnsbu7W/c2Hz9+BIBDP6s/jtSEb29vx5UrV/DmzRt8+/at5m3m5uYAAH19fX5OC4Sa8AAwMjKCUqmEhw8f/nVtZ2cH+Xwe0WgUly5dCmCdv9S9gJPNZvHkyRMMDg4ilUrh9OnTeP/+PZ49e4bOzk68ePECjuP4vsu0Zi/gqAsPAAsLC5iamsL6+jq+fv0Kx3EQj8dx8+ZNnDlzJrBdJjG8D8K4q1l4VY/x9D+GV4rhlWJ4pRheKYZXiuGVYnilGF4phleK4ZVq+nv1zU5WCEIYNwHh3VULv+KV4hk4BoRxF8/AoZoYXimGV4rhlWJ4pRheKYZXiuGVYnilPAs/NjaGWCyGT58+/fH2arWKdDqNZDKJSqXi1bs/NpsC0+i4DLRwvMfnz58lFovJrVu3/nh7LpcT13WlUCgc+j7R4pEjXmwyscsLaHIUiqdn4MzMzEgkEpHXr1+LiMjW1pZcvHhR7ty5c+QPJmybTO0yLdDwIiLDw8Ny9epVKRaLMjQ0JP39/XJwcHCk+zL1CTa5yeQukwIPv7u7K5cvX5Z4PC6RSETm5+ePfF+mPsEmN5ncZVKz8J4/q3ccB5lMBjs7O0gmk+jv7/f6XR7LTX7zPHy5XMarV69gWRY2NjZQLpe9fpfHcpPfPA//4MED7O/vI5fLoVgs1jyNwm9h3OS7Ro8DaPFxq1AoiOu6MjExISIi2WxWXNeV1dXVI90fDDyWmt5kapdpaPIY79nBCJVKBdevX4dt23j58iXa2trw/ft3pNNpVKtVzM7OoqOj41D32eqvOHmxycQuLwR2lu39+/elt7dXPnz48Mfb19bW5MKFC/L48eND3yda/MryYpOJXV5AED/Ora+vS09Pj4yPj9e8fu/ePent7ZXNzc1DfzBh29TqLq80C88zcAwI4y6egUM1MbxSDK8UwyvF8EoxvFIMrxTDK8XwSjG8UgyvFMMrxcOPDArrrlr4Fa8UDz8yIIy7ePgR1cTwSjG8UgyvFMMrxfBKMbxSDK8UwyvF8EoxvFIMrxTDK8XwSjG8UgyvFMMrxfBKMbxSDK8UwyvF8EoxvFIMrxTDK8XwSjG8UgyvFMMrxfBKMbxSDK8UwyvFM3AMCuuuWhr+hQr6d/FbvVIMrxTDK8XwSjG8Ugyv1E+68IsUdUFMhAAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 144x144 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "def to_board(moves):\n",
    "    x_moves = moves[::2]\n",
    "    o_moves = moves[1::2]\n",
    "    annots = np.array(['X' if v in x_moves else 'O' if v in o_moves else '' for v in range(9)]).reshape((3,3))\n",
    "    fig,ax = plt.subplots(1,1,figsize=(2,2))\n",
    "    ax = sns.heatmap(np.zeros((3,3)),annot=annots,cbar=False,cmap=\"Greys\",fmt=\"\",linewidths=2,linecolor='k',annot_kws={\"fontsize\":16})\n",
    "    ax.axis(\"off\")\n",
    "\n",
    "    plt.show()\n",
    "    \n",
    "to_board([4,1,3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "5f615305-6be2-4fa1-91de-7f771b04e170",
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_terminal(moves):\n",
    "    p1_moves = moves[::2]\n",
    "    p2_moves = moves[1::2]\n",
    "    wins = [(0,1,2),(3,4,5),(6,7,8),(0,3,6),(1,4,7),(2,5,8),(0,4,8),(2,4,6)]\n",
    "    for w in wins:\n",
    "        if all([x in p1_moves for x in w]):\n",
    "            return True,10\n",
    "        elif all([x in p2_moves for x in w]):\n",
    "            return True,-10\n",
    "    if len(moves) == 9:\n",
    "            return True,-10\n",
    "    return False,0\n",
    "\n",
    "def produce_children(state):\n",
    "    return [copy(state)+[i] for i in range(9) if i not in state]\n",
    "\n",
    "def maximize(state):\n",
    "    terminal_status,reward = is_terminal(state)\n",
    "    if terminal_status:\n",
    "        return state,reward # No further state so return same state    \n",
    "    max_state, max_score = None,-np.Inf\n",
    "    max_states = []\n",
    "    children = produce_children(state)\n",
    "    for child in children:\n",
    "        _,score = minimize(child)\n",
    "        if score > max_score:\n",
    "            max_state,max_score = child,score\n",
    "            max_states = [max_state]\n",
    "            \n",
    "        max_state = random.choice(max_states)\n",
    "    \n",
    "    return max_state,max_score\n",
    "\n",
    "def minimize(state):      \n",
    "    terminal_status,reward = is_terminal(state)\n",
    "    if terminal_status:\n",
    "        return state,reward # No further state so return same state    \n",
    "    min_state, min_score = None,np.Inf\n",
    "    min_states = []\n",
    "    children = produce_children(state)\n",
    "    for child in children:\n",
    "        _,score = maximize(child)\n",
    "        if score < min_score:\n",
    "            min_state,min_score = child,score\n",
    "            min_states = [min_state]\n",
    "    min_state = random.choice(min_states)\n",
    "    \n",
    "    return min_state,min_score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "1785893b-db0b-42bb-9d3f-c1c15e952a98",
   "metadata": {},
   "outputs": [],
   "source": [
    "def winner(moves):\n",
    "    p1_moves = moves[::2]\n",
    "    p2_moves = moves[1::2]\n",
    "    wins = [(0,1,2),(3,4,5),(6,7,8),(0,3,6),(1,4,7),(2,5,8),(0,4,8),(2,4,6)]\n",
    "    for w in wins:\n",
    "        if all([x in p1_moves for x in w]):\n",
    "            return 0\n",
    "        elif all([x in p2_moves for x in w]):\n",
    "            return 1\n",
    "    if len(moves) == 9:\n",
    "            return 2\n",
    "    return -1\n",
    "\n",
    "def games(moves=[],optimal=False):\n",
    "    score= [0,0,0]\n",
    "    games = [[moves,1]]\n",
    "    poss_games =[]\n",
    "    n=0\n",
    "    while len(games) >0:\n",
    "        moves,prob = games.pop()        \n",
    "        if winner(moves) != -1:\n",
    "            n +=1\n",
    "            score[winner(moves)] += prob\n",
    "            poss_games.append(moves)\n",
    "        else:\n",
    "            poss_moves = [i for i in range(9) if i not in moves]\n",
    "            if len(moves) % 2 ==1 or optimal == False:\n",
    "                next_prob = len(poss_moves)\n",
    "                for i in poss_moves:\n",
    "                    games.append([copy(moves)+[i],prob*Fraction(1,next_prob)])\n",
    "            else:\n",
    "                games.append([copy(moves)+[maximize(moves)[0][-1]],prob])    \n",
    "    return score,n,"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "81d7df4a-2edd-4046-82ae-d4abe2fc8528",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Start 0 results ([Fraction(191, 192), Fraction(1, 192), 0], 100)\n",
      "Start 1 results ([Fraction(353, 384), Fraction(13, 192), Fraction(5, 384)], 125)\n",
      "Start 4 results ([Fraction(185, 192), Fraction(13, 384), Fraction(1, 384)], 199)\n"
     ]
    }
   ],
   "source": [
    "for i in [0,1,4]:\n",
    "    print(\"Start {} results {}\".format(i,games([i],optimal=True)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "a5598ed3-48f2-4784-bef5-00f2349271e2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "### Solution as published \n",
       "https://www.janestreet.com/puzzles/tic-tac-oh-solution/"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<div class=\"inner-wrapper\">\n",
       "<p>The best way to face off against this computer program is to mark a corner. If\n",
       "the program does not select the middle square, you can always win. If it does\n",
       "(1/8), you select one of the 2 spots adjacent to your first mark. If the\n",
       "computer does not block you, you win. If it does block you (1/6), you block\n",
       "them, and have a chance to win. If the computer blocks you again (1/4), it has\n",
       "forced a tie, but otherwise you win. So, the best strategy yields a\n",
       "1-(1/8)(1/6)(1/4) = 191/192 chance of winning.</p>\n",
       "<p>Congratulations to those of you who submitted correct answers this month,\n",
       "especially Didrik Jonassen, this month’s winner of a Jane Street t-shirt!</p>\n",
       "<h4 class=\"omit-as-of\" id=\"correct-submissions-from\"></h4>\n",
       "<p class=\"correct-submissions\" data-directory=\"2015-05-01-tic-tac-oh\"></p>\n",
       "</div>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "url='https://www.janestreet.com/puzzles/tic-tac-oh-solution/'\n",
    "res = requests.get(url)\n",
    "soup = BeautifulSoup(res.content, 'html.parser')\n",
    "display(Markdown('### Solution as published \\n'+url))\n",
    "display(HTML(str(soup.find('div', {'class' :'inner-wrapper'}))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "fb7f1b14-c202-47a2-9c52-3f46862ae345",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([Fraction(737, 1260), Fraction(121, 420), Fraction(8, 63)], 255168)"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "games([])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "711bea91-9d00-4d17-a967-eb4a1e2e3806",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([Fraction(191, 192), Fraction(1, 192), 0], 100)"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "games([],optimal=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "f8bba89b-041e-4837-a280-84513072791f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.9947916666666666"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "191/192"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fd3ae881-a3aa-460f-be31-9eef6ceeb4fe",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}