reinforcement_learning_for_tic-tac-toe.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Reinforcement learning for tic-tac-toe\n",
    "\n",
    "In which we solve the problem of teaching a neural network to play tic-tac-toe.\n",
    "\n",
    "* First, we import libraries for this example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Using TensorFlow backend.\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "import numpy as np\n",
    "import keras\n",
    "from keras.models import Sequential\n",
    "from keras.layers import Dense\n",
    "from keras.layers import Dropout\n",
    "from keras.backend import reshape\n",
    "from keras.utils.np_utils import to_categorical"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Next we write helper methods to initialize the board, get a list of valid moves, declare a winner, and print the current board."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Get an empty board\n",
    "#\n",
    "# 0 indicates an empty space, 1 indicates an 'X' (player 1), and 2 indicates an 'O' (player 2)\n",
    "#\n",
    "# Initially the board is empty, so we return a 3x3 array of zeroes.\n",
    "def initBoard():\n",
    "    board = [\n",
    "        [0, 0, 0],\n",
    "        [0, 0, 0],\n",
    "        [0, 0, 0]\n",
    "    ]\n",
    "    return board\n",
    "\n",
    "# Print the current state of the board\n",
    "def printBoard(board):\n",
    "    for i in range(len(board)):\n",
    "        for j in range(len(board[i])):\n",
    "            mark = ' '\n",
    "            if board[i][j] == 1:\n",
    "                mark = 'X'\n",
    "            elif board[i][j] == 2:\n",
    "                mark = 'O'\n",
    "            if (j == len(board[i]) - 1):\n",
    "                print(mark)\n",
    "            else:\n",
    "                print(str(mark) + \"|\", end='')\n",
    "        if (i < len(board) - 1):\n",
    "            print(\"-----\")\n",
    "\n",
    "# Get a list of valid moves (indices into the board)\n",
    "def getMoves(board):\n",
    "    moves = []\n",
    "    for i in range(len(board)):\n",
    "        for j in range(len(board[i])):\n",
    "            if board[i][j] == 0:\n",
    "                moves.append((i, j))\n",
    "    return moves\n",
    "\n",
    "# Declare a winner\n",
    "#\n",
    "# -1 = game not over\n",
    "#  0 = draw\n",
    "#  1 = 'X' wins (player 1)\n",
    "#  2 = 'O' wins (player 2)\n",
    "def getWinner(board):\n",
    "    candidate = 0\n",
    "    won = 0\n",
    "    \n",
    "    # Check rows\n",
    "    for i in range(len(board)):\n",
    "        candidate = 0\n",
    "        for j in range(len(board[i])):\n",
    "            \n",
    "            # Make sure there are no gaps\n",
    "            if board[i][j] == 0:\n",
    "                break\n",
    "            \n",
    "            # Identify the front-runner\n",
    "            if candidate == 0:\n",
    "                candidate = board[i][j]\n",
    "            \n",
    "            # Determine whether the front-runner has all the slots\n",
    "            if candidate != board[i][j]:\n",
    "                break\n",
    "            elif j == len(board[i]) - 1:\n",
    "                won = candidate\n",
    "    \n",
    "    if won > 0:\n",
    "        return won\n",
    "    \n",
    "    # Check columns\n",
    "    for j in range(len(board[0])):\n",
    "        candidate = 0\n",
    "        for i in range(len(board)):\n",
    "            \n",
    "            # Make sure there are no gaps\n",
    "            if board[i][j] == 0:\n",
    "                break\n",
    "            \n",
    "            # Identify the front-runner\n",
    "            if candidate == 0:\n",
    "                candidate = board[i][j]\n",
    "            \n",
    "            # Determine whether the front-runner has all the slots\n",
    "            if candidate != board[i][j]:\n",
    "                break\n",
    "            elif i == len(board) - 1:\n",
    "                won = candidate\n",
    "    \n",
    "    if won > 0:\n",
    "        return won\n",
    "    \n",
    "    # Check diagonals\n",
    "    candidate = 0\n",
    "    for i in range(len(board)):\n",
    "        if board[i][i] == 0:\n",
    "            break\n",
    "        if candidate == 0:\n",
    "            candidate = board[i][i]\n",
    "        if candidate != board[i][i]:\n",
    "            break\n",
    "        elif i == len(board) - 1:\n",
    "            won = candidate\n",
    "    \n",
    "    if won > 0:\n",
    "        return won\n",
    "    \n",
    "    candidate = 0\n",
    "    for i in range(len(board)):\n",
    "        if board[i][2 - i] == 0:\n",
    "            break\n",
    "        if candidate == 0:\n",
    "            candidate = board[i][2 - i]\n",
    "        if candidate != board[i][2 - i]:\n",
    "            break\n",
    "        elif i == len(board) - 1:\n",
    "            won = candidate\n",
    "    \n",
    "    if won > 0:\n",
    "        return won\n",
    "    \n",
    "    # Still no winner?\n",
    "    if (len(getMoves(board)) == 0):\n",
    "        # It's a draw\n",
    "        return 0\n",
    "    else:\n",
    "        # Still more moves to make\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Next, we test the helper methods to demonstrate that they work."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " | | \n",
      "-----\n",
      " | | \n",
      "-----\n",
      " | | \n",
      "-1\n",
      "[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]\n",
      "X| | \n",
      "-----\n",
      " |X| \n",
      "-----\n",
      " | |X\n",
      "1\n",
      "X| |O\n",
      "-----\n",
      " |X|O\n",
      "-----\n",
      " | |O\n",
      "2\n",
      "O|X|O\n",
      "-----\n",
      "O|X|O\n",
      "-----\n",
      "X|O|X\n",
      "0\n"
     ]
    }
   ],
   "source": [
    "# Test helper methods\n",
    "b = initBoard()\n",
    "printBoard(b)\n",
    "print(getWinner(b))\n",
    "print(getMoves(b))\n",
    "\n",
    "b[0][0] = 1\n",
    "b[1][1] = 1\n",
    "b[2][2] = 1\n",
    "printBoard(b)\n",
    "print(getWinner(b))\n",
    "\n",
    "b[0][2] = 2\n",
    "b[1][2] = 2\n",
    "b[2][2] = 2\n",
    "printBoard(b)\n",
    "print(getWinner(b))\n",
    "\n",
    "b[0][1] = 1\n",
    "b[1][0] = 2\n",
    "b[2][0] = 1\n",
    "b[2][1] = 2\n",
    "b[2][2] = 1\n",
    "b[0][0] = 2\n",
    "printBoard(b)\n",
    "print(getWinner(b))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Next, we take everything we've done so far and create a random game simulator"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(1, (2, 1)), (2, (0, 1)), (1, (1, 0)), (2, (2, 2)), (1, (2, 0)), (2, (1, 2)), (1, (0, 2)), (2, (1, 1)), (1, (0, 0))]\n"
     ]
    }
   ],
   "source": [
    "random.seed()\n",
    "\n",
    "# Get best next move for the given player at the given board position\n",
    "def bestMove(board, model, player, rnd=0):\n",
    "    scores = []\n",
    "    moves = getMoves(board)\n",
    "    \n",
    "    # Make predictions for each possible move\n",
    "    for i in range(len(moves)):\n",
    "        future = np.array(board)\n",
    "        future[moves[i][0]][moves[i][1]] = player\n",
    "        prediction = model.predict(future.reshape((-1, 9)), verbose=0)[0]\n",
    "        if player == 1:\n",
    "            winPrediction = prediction[1]\n",
    "            lossPrediction = prediction[2]\n",
    "        else:\n",
    "            winPrediction = prediction[2]\n",
    "            lossPrediction = prediction[1]\n",
    "        drawPrediction = prediction[0]\n",
    "        if winPrediction - lossPrediction > 0:\n",
    "            scores.append(winPrediction - lossPrediction)\n",
    "        else:\n",
    "            scores.append(drawPrediction - lossPrediction)\n",
    "\n",
    "    # Choose the best move with a random factor\n",
    "    bestMoves = np.flip(np.argsort(scores))\n",
    "    for i in range(len(bestMoves)):\n",
    "        if random.random() * rnd < 0.5:\n",
    "            return moves[bestMoves[i]]\n",
    "\n",
    "    # Choose a move completely at random\n",
    "    return moves[random.randint(0, len(moves) - 1)]\n",
    "\n",
    "# Simulate a game\n",
    "def simulateGame(p1=None, p2=None, rnd=0):\n",
    "    history = []\n",
    "    board = initBoard()\n",
    "    playerToMove = 1\n",
    "    \n",
    "    while getWinner(board) == -1:\n",
    "        \n",
    "        # Chose a move (random or use a player model if provided)\n",
    "        move = None\n",
    "        if playerToMove == 1 and p1 != None:\n",
    "            move = bestMove(board, p1, playerToMove, rnd)\n",
    "        elif playerToMove == 2 and p2 != None:\n",
    "            move = bestMove(board, p2, playerToMove, rnd)\n",
    "        else:\n",
    "            moves = getMoves(board)\n",
    "            move = moves[random.randint(0, len(moves) - 1)]\n",
    "        \n",
    "        # Make the move\n",
    "        board[move[0]][move[1]] = playerToMove\n",
    "        \n",
    "        # Add the move to the history\n",
    "        history.append((playerToMove, move))\n",
    "        \n",
    "        # Switch the active player\n",
    "        playerToMove = 1 if playerToMove == 2 else 2\n",
    "        \n",
    "    return history\n",
    "\n",
    "# Simulate a game\n",
    "history = simulateGame()\n",
    "print(history)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "X|O|X\n",
      "-----\n",
      "X|O|O\n",
      "-----\n",
      "O|X|X\n",
      "0\n"
     ]
    }
   ],
   "source": [
    "# Reconstruct the board from the move list\n",
    "def movesToBoard(moves):\n",
    "    board = initBoard()\n",
    "    for move in moves:\n",
    "        player = move[0]\n",
    "        coords = move[1]\n",
    "        board[coords[0]][coords[1]] = player\n",
    "    return board\n",
    "\n",
    "board = movesToBoard(history)\n",
    "printBoard(board)\n",
    "print(getWinner(board))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Next, we generate a set of simulated games to train our neural network and calculate some win statistics for each random player. We predict that 'X' (player 1) should have a slight edge due to first mover advantage, but that both players have roughly the same number of wins, draws, and losses overall."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "games = [simulateGame() for _ in range(10000)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Results for player 1:\n",
      "Wins: 51934 (51.9%)\n",
      "Loss: 24212 (24.2%)\n",
      "Draw: 23854 (23.9%)\n",
      "\n",
      "Results for player 2:\n",
      "Wins: 24212 (24.2%)\n",
      "Loss: 51934 (51.9%)\n",
      "Draw: 23854 (23.9%)\n"
     ]
    }
   ],
   "source": [
    "# Aggregate win/loss/draw stats for a player\n",
    "def gameStats(games, player=1):\n",
    "    stats = {\"win\": 0, \"loss\": 0, \"draw\": 0}\n",
    "    for game in games:\n",
    "        result = getWinner(movesToBoard(game))\n",
    "        if result == -1:\n",
    "            continue\n",
    "        elif result == player:\n",
    "            stats[\"win\"] += 1\n",
    "        elif result == 0:\n",
    "            stats[\"draw\"] += 1\n",
    "        else:\n",
    "            stats[\"loss\"] += 1\n",
    "    \n",
    "    winPct = stats[\"win\"] / len(games) * 100\n",
    "    lossPct = stats[\"loss\"] / len(games) * 100\n",
    "    drawPct = stats[\"draw\"] / len(games) * 100\n",
    "\n",
    "    print(\"Results for player %d:\" % (player))\n",
    "    print(\"Wins: %d (%.1f%%)\" % (stats[\"win\"], winPct))\n",
    "    print(\"Loss: %d (%.1f%%)\" % (stats[\"loss\"], lossPct))\n",
    "    print(\"Draw: %d (%.1f%%)\" % (stats[\"draw\"], drawPct))\n",
    "\n",
    "gameStats(games)\n",
    "print()\n",
    "gameStats(games, player=2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* As shown above, when moves are chosen at random, player 1 has a significant advantage! However, we know that when people play tic-tac-toe, it's easy to force a draw, so we'd expect similar behavior from a neural network trained to play tic-tac-toe.\n",
    "* We choose a DNN architecture since we effectively want to predict the outcome of a game based on the given board state.\n",
    "* The input for each cell is the board state, which we reshape into a flat array of 9 elements, each element of which can be a 0 (empty cell), 1 (player 1 move), or 2 (player 2 move).\n",
    "* The output is the result of the game (win, loss, or draw). We use a one-hot encoded array for this."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "_________________________________________________________________\n",
      "Layer (type)                 Output Shape              Param #   \n",
      "=================================================================\n",
      "dense_6 (Dense)              (None, 200)               2000      \n",
      "_________________________________________________________________\n",
      "dropout_3 (Dropout)          (None, 200)               0         \n",
      "_________________________________________________________________\n",
      "dense_7 (Dense)              (None, 125)               25125     \n",
      "_________________________________________________________________\n",
      "dense_8 (Dense)              (None, 75)                9450      \n",
      "_________________________________________________________________\n",
      "dropout_4 (Dropout)          (None, 75)                0         \n",
      "_________________________________________________________________\n",
      "dense_9 (Dense)              (None, 25)                1900      \n",
      "_________________________________________________________________\n",
      "dense_10 (Dense)             (None, 3)                 78        \n",
      "=================================================================\n",
      "Total params: 38,553\n",
      "Trainable params: 38,553\n",
      "Non-trainable params: 0\n",
      "_________________________________________________________________\n",
      "None\n"
     ]
    }
   ],
   "source": [
    "def getModel():\n",
    "    numCells = 9 # How many cells in a 3x3 tic-tac-toe board?\n",
    "    outcomes = 3 # How many outcomes are there in a game? (draw, X-wins, O-wins)\n",
    "    model = Sequential()\n",
    "    model.add(Dense(200, activation='relu', input_shape=(9, )))\n",
    "    model.add(Dropout(0.2))\n",
    "    model.add(Dense(125, activation='relu'))\n",
    "    model.add(Dense(75, activation='relu'))\n",
    "    model.add(Dropout(0.1))\n",
    "    model.add(Dense(25, activation='relu'))\n",
    "    model.add(Dense(outcomes, activation='softmax'))\n",
    "    model.compile(loss='categorical_crossentropy', optimizer='rmsprop', metrics=['acc'])\n",
    "    return model\n",
    "model = getModel()\n",
    "print(model.summary())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Next, we reshape our data in preparation for training. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Get a set of board states labelled by who eventually won that game\n",
    "def gamesToWinLossData(games):\n",
    "    X = []\n",
    "    y = []\n",
    "    for game in games:\n",
    "        winner = getWinner(movesToBoard(game))\n",
    "        for move in range(len(game)):\n",
    "            X.append(movesToBoard(game[:(move + 1)]))\n",
    "            y.append(winner)\n",
    "\n",
    "    X = np.array(X).reshape((-1, 9))\n",
    "    y = to_categorical(y)\n",
    "    \n",
    "    # Return an appropriate train/test split\n",
    "    trainNum = int(len(X) * 0.8)\n",
    "    return (X[:trainNum], X[trainNum:], y[:trainNum], y[trainNum:])\n",
    "\n",
    "# Split out train and validation data\n",
    "X_train, X_test, y_train, y_test = gamesToWinLossData(games)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Next, we train our model on the random tic-tac-toe games we generated earlier."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Train on 62306 samples, validate on 15577 samples\n",
      "Epoch 1/100\n",
      "62306/62306 [==============================] - 3s 41us/step - loss: 0.8223 - acc: 0.6135 - val_loss: 0.8075 - val_acc: 0.6164\n",
      "Epoch 2/100\n",
      "62306/62306 [==============================] - 2s 25us/step - loss: 0.8130 - acc: 0.6185 - val_loss: 0.7963 - val_acc: 0.6221\n",
      "Epoch 3/100\n",
      "62306/62306 [==============================] - 2s 29us/step - loss: 0.8056 - acc: 0.6214 - val_loss: 0.8031 - val_acc: 0.6237\n",
      "Epoch 4/100\n",
      "62306/62306 [==============================] - 2s 37us/step - loss: 0.8005 - acc: 0.6232 - val_loss: 0.7932 - val_acc: 0.6248\n",
      "Epoch 5/100\n",
      "62306/62306 [==============================] - 2s 38us/step - loss: 0.7976 - acc: 0.6247 - val_loss: 0.7943 - val_acc: 0.6257\n",
      "Epoch 6/100\n",
      "62306/62306 [==============================] - 2s 38us/step - loss: 0.7933 - acc: 0.6255 - val_loss: 0.7888 - val_acc: 0.6290\n",
      "Epoch 7/100\n",
      "62306/62306 [==============================] - 2s 38us/step - loss: 0.7907 - acc: 0.6272 - val_loss: 0.7824 - val_acc: 0.6291\n",
      "Epoch 8/100\n",
      "62306/62306 [==============================] - 2s 38us/step - loss: 0.7877 - acc: 0.6291 - val_loss: 0.7769 - val_acc: 0.6336\n",
      "Epoch 9/100\n",
      "62306/62306 [==============================] - 2s 37us/step - loss: 0.7855 - acc: 0.6286 - val_loss: 0.7869 - val_acc: 0.6243\n",
      "Epoch 10/100\n",
      "62306/62306 [==============================] - 2s 38us/step - loss: 0.7842 - acc: 0.6291 - val_loss: 0.7790 - val_acc: 0.6286\n",
      "Epoch 11/100\n",
      "62306/62306 [==============================] - 2s 38us/step - loss: 0.7813 - acc: 0.6318 - val_loss: 0.7810 - val_acc: 0.6291\n",
      "Epoch 12/100\n",
      "62306/62306 [==============================] - 2s 38us/step - loss: 0.7804 - acc: 0.6324 - val_loss: 0.7796 - val_acc: 0.6304\n",
      "Epoch 13/100\n",
      "62306/62306 [==============================] - 2s 38us/step - loss: 0.7785 - acc: 0.6328 - val_loss: 0.7763 - val_acc: 0.6300\n",
      "Epoch 14/100\n",
      "62306/62306 [==============================] - 2s 38us/step - loss: 0.7785 - acc: 0.6311 - val_loss: 0.7843 - val_acc: 0.6305\n",
      "Epoch 15/100\n",
      "62306/62306 [==============================] - 2s 38us/step - loss: 0.7752 - acc: 0.6343 - val_loss: 0.7747 - val_acc: 0.6298\n",
      "Epoch 16/100\n",
      "62306/62306 [==============================] - 3s 43us/step - loss: 0.7743 - acc: 0.6350 - val_loss: 0.7731 - val_acc: 0.6319\n",
      "Epoch 17/100\n",
      "62306/62306 [==============================] - 3s 45us/step - loss: 0.7730 - acc: 0.6348 - val_loss: 0.7731 - val_acc: 0.6310\n",
      "Epoch 18/100\n",
      "62306/62306 [==============================] - 3s 45us/step - loss: 0.7718 - acc: 0.6354 - val_loss: 0.7767 - val_acc: 0.6260\n",
      "Epoch 19/100\n",
      "62306/62306 [==============================] - 2s 37us/step - loss: 0.7701 - acc: 0.6358 - val_loss: 0.7714 - val_acc: 0.6284\n",
      "Epoch 20/100\n",
      "62306/62306 [==============================] - 2s 34us/step - loss: 0.7716 - acc: 0.6352 - val_loss: 0.7717 - val_acc: 0.6294\n",
      "Epoch 21/100\n",
      "62306/62306 [==============================] - 2s 34us/step - loss: 0.7687 - acc: 0.6367 - val_loss: 0.7765 - val_acc: 0.6209\n",
      "Epoch 22/100\n",
      "62306/62306 [==============================] - 2s 34us/step - loss: 0.7700 - acc: 0.6364 - val_loss: 0.7732 - val_acc: 0.6280\n",
      "Epoch 23/100\n",
      "62306/62306 [==============================] - 2s 34us/step - loss: 0.7668 - acc: 0.6363 - val_loss: 0.7728 - val_acc: 0.6252\n",
      "Epoch 24/100\n",
      "62306/62306 [==============================] - 2s 34us/step - loss: 0.7669 - acc: 0.6359 - val_loss: 0.7668 - val_acc: 0.6327\n",
      "Epoch 25/100\n",
      "62306/62306 [==============================] - 3s 43us/step - loss: 0.7658 - acc: 0.6371 - val_loss: 0.7655 - val_acc: 0.6282\n",
      "Epoch 26/100\n",
      "62306/62306 [==============================] - 3s 48us/step - loss: 0.7639 - acc: 0.6380 - val_loss: 0.7691 - val_acc: 0.6349\n",
      "Epoch 27/100\n",
      "62306/62306 [==============================] - 3s 48us/step - loss: 0.7661 - acc: 0.6365 - val_loss: 0.7698 - val_acc: 0.6302\n",
      "Epoch 28/100\n",
      "62306/62306 [==============================] - 3s 48us/step - loss: 0.7633 - acc: 0.6385 - val_loss: 0.7743 - val_acc: 0.6315\n",
      "Epoch 29/100\n",
      "62306/62306 [==============================] - 3s 48us/step - loss: 0.7640 - acc: 0.6382 - val_loss: 0.7680 - val_acc: 0.6289\n",
      "Epoch 30/100\n",
      "62306/62306 [==============================] - 3s 48us/step - loss: 0.7613 - acc: 0.6392 - val_loss: 0.7656 - val_acc: 0.6321\n",
      "Epoch 31/100\n",
      "62306/62306 [==============================] - 3s 48us/step - loss: 0.7626 - acc: 0.6383 - val_loss: 0.7698 - val_acc: 0.6315\n",
      "Epoch 32/100\n",
      "62306/62306 [==============================] - 3s 48us/step - loss: 0.7642 - acc: 0.6364 - val_loss: 0.7684 - val_acc: 0.6300\n",
      "Epoch 33/100\n",
      "62306/62306 [==============================] - 3s 48us/step - loss: 0.7615 - acc: 0.6399 - val_loss: 0.7660 - val_acc: 0.6307\n",
      "Epoch 34/100\n",
      "62306/62306 [==============================] - 3s 49us/step - loss: 0.7630 - acc: 0.6379 - val_loss: 0.7638 - val_acc: 0.6334\n",
      "Epoch 35/100\n",
      "62306/62306 [==============================] - 3s 48us/step - loss: 0.7613 - acc: 0.6396 - val_loss: 0.7660 - val_acc: 0.6351\n",
      "Epoch 36/100\n",
      "62306/62306 [==============================] - 3s 48us/step - loss: 0.7628 - acc: 0.6396 - val_loss: 0.7633 - val_acc: 0.6316\n",
      "Epoch 37/100\n",
      "62306/62306 [==============================] - 3s 48us/step - loss: 0.7604 - acc: 0.6390 - val_loss: 0.7659 - val_acc: 0.6327\n",
      "Epoch 38/100\n",
      "62306/62306 [==============================] - 3s 48us/step - loss: 0.7616 - acc: 0.6402 - val_loss: 0.7625 - val_acc: 0.6341\n",
      "Epoch 39/100\n",
      "62306/62306 [==============================] - 3s 48us/step - loss: 0.7600 - acc: 0.6395 - val_loss: 0.7765 - val_acc: 0.6249\n",
      "Epoch 40/100\n",
      "62306/62306 [==============================] - 3s 48us/step - loss: 0.7608 - acc: 0.6399 - val_loss: 0.7623 - val_acc: 0.6359\n",
      "Epoch 41/100\n",
      "62306/62306 [==============================] - 3s 48us/step - loss: 0.7605 - acc: 0.6408 - val_loss: 0.7680 - val_acc: 0.6315\n",
      "Epoch 42/100\n",
      "62306/62306 [==============================] - 3s 44us/step - loss: 0.7620 - acc: 0.6386 - val_loss: 0.7631 - val_acc: 0.6335\n",
      "Epoch 43/100\n",
      "62306/62306 [==============================] - 3s 45us/step - loss: 0.7604 - acc: 0.6401 - val_loss: 0.7655 - val_acc: 0.6306\n",
      "Epoch 44/100\n",
      "62306/62306 [==============================] - 3s 45us/step - loss: 0.7568 - acc: 0.6401 - val_loss: 0.7653 - val_acc: 0.6311\n",
      "Epoch 45/100\n",
      "62306/62306 [==============================] - 3s 45us/step - loss: 0.7576 - acc: 0.6412 - val_loss: 0.7656 - val_acc: 0.6293\n",
      "Epoch 46/100\n",
      "62306/62306 [==============================] - 2s 38us/step - loss: 0.7575 - acc: 0.6418 - val_loss: 0.7618 - val_acc: 0.6314\n",
      "Epoch 47/100\n",
      "62306/62306 [==============================] - 2s 39us/step - loss: 0.7586 - acc: 0.6402 - val_loss: 0.7581 - val_acc: 0.6338\n",
      "Epoch 48/100\n",
      "62306/62306 [==============================] - 3s 42us/step - loss: 0.7568 - acc: 0.6403 - val_loss: 0.7610 - val_acc: 0.6322\n",
      "Epoch 49/100\n",
      "62306/62306 [==============================] - 3s 42us/step - loss: 0.7577 - acc: 0.6425 - val_loss: 0.7642 - val_acc: 0.6285\n",
      "Epoch 50/100\n",
      "62306/62306 [==============================] - 3s 43us/step - loss: 0.7570 - acc: 0.6408 - val_loss: 0.7613 - val_acc: 0.6341\n",
      "Epoch 51/100\n",
      "62306/62306 [==============================] - 3s 43us/step - loss: 0.7579 - acc: 0.6387 - val_loss: 0.7614 - val_acc: 0.6299\n",
      "Epoch 52/100\n",
      "62306/62306 [==============================] - 3s 42us/step - loss: 0.7588 - acc: 0.6401 - val_loss: 0.7609 - val_acc: 0.6313\n",
      "Epoch 53/100\n",
      "62306/62306 [==============================] - 3s 50us/step - loss: 0.7575 - acc: 0.6422 - val_loss: 0.7614 - val_acc: 0.6321\n",
      "Epoch 54/100\n",
      "62306/62306 [==============================] - 3s 52us/step - loss: 0.7570 - acc: 0.6400 - val_loss: 0.7614 - val_acc: 0.6317\n",
      "Epoch 55/100\n",
      "62306/62306 [==============================] - 3s 52us/step - loss: 0.7572 - acc: 0.6408 - val_loss: 0.7611 - val_acc: 0.6338\n",
      "Epoch 56/100\n",
      "62306/62306 [==============================] - 3s 56us/step - loss: 0.7567 - acc: 0.6422 - val_loss: 0.7658 - val_acc: 0.6330\n",
      "Epoch 57/100\n",
      "62306/62306 [==============================] - 3s 43us/step - loss: 0.7569 - acc: 0.6412 - val_loss: 0.7607 - val_acc: 0.6303\n",
      "Epoch 58/100\n",
      "62306/62306 [==============================] - 3s 45us/step - loss: 0.7556 - acc: 0.6408 - val_loss: 0.7597 - val_acc: 0.6324\n",
      "Epoch 59/100\n",
      "62306/62306 [==============================] - 3s 45us/step - loss: 0.7564 - acc: 0.6411 - val_loss: 0.7640 - val_acc: 0.6287\n",
      "Epoch 60/100\n",
      "62306/62306 [==============================] - 3s 55us/step - loss: 0.7572 - acc: 0.6410 - val_loss: 0.7578 - val_acc: 0.6325\n",
      "Epoch 61/100\n",
      "62306/62306 [==============================] - 3s 52us/step - loss: 0.7567 - acc: 0.6418 - val_loss: 0.7591 - val_acc: 0.6327\n",
      "Epoch 62/100\n",
      "62306/62306 [==============================] - 2s 26us/step - loss: 0.7567 - acc: 0.6410 - val_loss: 0.7595 - val_acc: 0.6321\n",
      "Epoch 63/100\n",
      "62306/62306 [==============================] - 1s 22us/step - loss: 0.7533 - acc: 0.6423 - val_loss: 0.7578 - val_acc: 0.6298\n",
      "Epoch 64/100\n",
      "62306/62306 [==============================] - 1s 23us/step - loss: 0.7549 - acc: 0.6416 - val_loss: 0.7566 - val_acc: 0.6331\n",
      "Epoch 65/100\n",
      "62306/62306 [==============================] - 2s 34us/step - loss: 0.7536 - acc: 0.6426 - val_loss: 0.7599 - val_acc: 0.6363\n",
      "Epoch 66/100\n",
      "62306/62306 [==============================] - 2s 38us/step - loss: 0.7557 - acc: 0.6425 - val_loss: 0.7584 - val_acc: 0.6329\n",
      "Epoch 67/100\n",
      "62306/62306 [==============================] - 2s 38us/step - loss: 0.7543 - acc: 0.6434 - val_loss: 0.7570 - val_acc: 0.6340\n",
      "Epoch 68/100\n",
      "62306/62306 [==============================] - 2s 38us/step - loss: 0.7539 - acc: 0.6421 - val_loss: 0.7663 - val_acc: 0.6356\n",
      "Epoch 69/100\n",
      "62306/62306 [==============================] - 2s 38us/step - loss: 0.7556 - acc: 0.6409 - val_loss: 0.7659 - val_acc: 0.6348\n",
      "Epoch 70/100\n",
      "62306/62306 [==============================] - 3s 41us/step - loss: 0.7553 - acc: 0.6431 - val_loss: 0.7626 - val_acc: 0.6308\n",
      "Epoch 71/100\n",
      "62306/62306 [==============================] - 3s 45us/step - loss: 0.7545 - acc: 0.6444 - val_loss: 0.7553 - val_acc: 0.6361\n",
      "Epoch 72/100\n",
      "62306/62306 [==============================] - 3s 45us/step - loss: 0.7527 - acc: 0.6432 - val_loss: 0.7580 - val_acc: 0.6333\n",
      "Epoch 73/100\n",
      "62306/62306 [==============================] - 3s 45us/step - loss: 0.7538 - acc: 0.6450 - val_loss: 0.7592 - val_acc: 0.6305\n",
      "Epoch 74/100\n",
      "62306/62306 [==============================] - 3s 45us/step - loss: 0.7560 - acc: 0.6424 - val_loss: 0.7575 - val_acc: 0.6325\n",
      "Epoch 75/100\n",
      "62306/62306 [==============================] - 3s 45us/step - loss: 0.7538 - acc: 0.6431 - val_loss: 0.7599 - val_acc: 0.6320\n",
      "Epoch 76/100\n",
      "62306/62306 [==============================] - 3s 45us/step - loss: 0.7546 - acc: 0.6427 - val_loss: 0.7590 - val_acc: 0.6318\n",
      "Epoch 77/100\n",
      "62306/62306 [==============================] - 3s 45us/step - loss: 0.7536 - acc: 0.6426 - val_loss: 0.7590 - val_acc: 0.6323\n",
      "Epoch 78/100\n",
      "62306/62306 [==============================] - 3s 45us/step - loss: 0.7522 - acc: 0.6440 - val_loss: 0.7604 - val_acc: 0.6341\n",
      "Epoch 79/100\n",
      "62306/62306 [==============================] - 3s 45us/step - loss: 0.7537 - acc: 0.6443 - val_loss: 0.7584 - val_acc: 0.6345\n",
      "Epoch 80/100\n",
      "62306/62306 [==============================] - 3s 45us/step - loss: 0.7520 - acc: 0.6433 - val_loss: 0.7570 - val_acc: 0.6328\n",
      "Epoch 81/100\n",
      "62306/62306 [==============================] - 3s 45us/step - loss: 0.7545 - acc: 0.6440 - val_loss: 0.7594 - val_acc: 0.6339\n",
      "Epoch 82/100\n",
      "62306/62306 [==============================] - 3s 45us/step - loss: 0.7536 - acc: 0.6436 - val_loss: 0.7544 - val_acc: 0.6347\n",
      "Epoch 83/100\n",
      "62306/62306 [==============================] - 3s 45us/step - loss: 0.7539 - acc: 0.6438 - val_loss: 0.7588 - val_acc: 0.6339\n",
      "Epoch 84/100\n",
      "62306/62306 [==============================] - 3s 45us/step - loss: 0.7539 - acc: 0.6427 - val_loss: 0.7601 - val_acc: 0.6341\n",
      "Epoch 85/100\n",
      "62306/62306 [==============================] - 3s 45us/step - loss: 0.7524 - acc: 0.6425 - val_loss: 0.7593 - val_acc: 0.6351\n",
      "Epoch 86/100\n",
      "62306/62306 [==============================] - 3s 45us/step - loss: 0.7546 - acc: 0.6417 - val_loss: 0.7589 - val_acc: 0.6336\n",
      "Epoch 87/100\n",
      "62306/62306 [==============================] - 3s 45us/step - loss: 0.7524 - acc: 0.6444 - val_loss: 0.7582 - val_acc: 0.6326\n",
      "Epoch 88/100\n",
      "62306/62306 [==============================] - 3s 45us/step - loss: 0.7541 - acc: 0.6441 - val_loss: 0.7543 - val_acc: 0.6371\n",
      "Epoch 89/100\n",
      "62306/62306 [==============================] - 3s 45us/step - loss: 0.7555 - acc: 0.6432 - val_loss: 0.7563 - val_acc: 0.6342\n",
      "Epoch 90/100\n",
      "62306/62306 [==============================] - 3s 45us/step - loss: 0.7539 - acc: 0.6428 - val_loss: 0.7566 - val_acc: 0.6321\n",
      "Epoch 91/100\n",
      "62306/62306 [==============================] - 3s 45us/step - loss: 0.7538 - acc: 0.6439 - val_loss: 0.7573 - val_acc: 0.6343\n",
      "Epoch 92/100\n",
      "62306/62306 [==============================] - 3s 45us/step - loss: 0.7542 - acc: 0.6435 - val_loss: 0.7566 - val_acc: 0.6343\n",
      "Epoch 93/100\n",
      "62306/62306 [==============================] - 3s 45us/step - loss: 0.7536 - acc: 0.6427 - val_loss: 0.7554 - val_acc: 0.6371\n",
      "Epoch 94/100\n",
      "62306/62306 [==============================] - 3s 45us/step - loss: 0.7533 - acc: 0.6427 - val_loss: 0.7548 - val_acc: 0.6347\n",
      "Epoch 95/100\n",
      "62306/62306 [==============================] - 2s 35us/step - loss: 0.7533 - acc: 0.6417 - val_loss: 0.7605 - val_acc: 0.6365\n",
      "Epoch 96/100\n",
      "62306/62306 [==============================] - 1s 21us/step - loss: 0.7557 - acc: 0.6430 - val_loss: 0.7545 - val_acc: 0.6345\n",
      "Epoch 97/100\n",
      "62306/62306 [==============================] - 1s 23us/step - loss: 0.7556 - acc: 0.6432 - val_loss: 0.7558 - val_acc: 0.6368\n",
      "Epoch 98/100\n",
      "62306/62306 [==============================] - 2s 32us/step - loss: 0.7524 - acc: 0.6441 - val_loss: 0.7565 - val_acc: 0.6352\n",
      "Epoch 99/100\n",
      "62306/62306 [==============================] - 2s 32us/step - loss: 0.7547 - acc: 0.6424 - val_loss: 0.7567 - val_acc: 0.6368\n",
      "Epoch 100/100\n",
      "62306/62306 [==============================] - 2s 32us/step - loss: 0.7536 - acc: 0.6431 - val_loss: 0.7588 - val_acc: 0.6314\n"
     ]
    }
   ],
   "source": [
    "nEpochs = 100\n",
    "batchSize = 100\n",
    "history = model.fit(X_train, y_train, validation_data=(X_test, y_test), epochs=nEpochs, batch_size=batchSize)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* We see that our very simple model caps out at around 58% validation accuracy.\n",
    "* Next, we use this trained model to play a game and see if we do any better than random chance."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "games2 = [simulateGame(p1=model) for _ in range(1000)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Results for player 1:\n",
      "Wins: 950 (95.0%)\n",
      "Loss: 16 (1.6%)\n",
      "Draw: 34 (3.4%)\n"
     ]
    }
   ],
   "source": [
    "gameStats(games2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Wow, we've gone from losing 24.2% of games to only losing 1.6% of the time! Let's see how our model fares as player 2."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "games3 = [simulateGame(p2=model) for _ in range(1000)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Results for player 2:\n",
      "Wins: 427 (42.7%)\n",
      "Loss: 43 (4.3%)\n",
      "Draw: 530 (53.0%)\n"
     ]
    }
   ],
   "source": [
    "gameStats(games3, player=2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* This is equally impressive! Player 2 has gone from losing 51.9% of games to only losing 4.3% of the time.\n",
    "* Now what happens when the model is used to play both sides (with some random factor applied to force the model to choose different moves each game)?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "games4 = [simulateGame(p1=model, p2=model, rnd=0.6) for _ in range(1000)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Results for player 1:\n",
      "Wins: 483 (48.3%)\n",
      "Loss: 44 (4.4%)\n",
      "Draw: 473 (47.3%)\n",
      "\n",
      "Results for player 2:\n",
      "Wins: 44 (4.4%)\n",
      "Loss: 483 (48.3%)\n",
      "Draw: 473 (47.3%)\n"
     ]
    }
   ],
   "source": [
    "gameStats(games4, player=1)\n",
    "print()\n",
    "gameStats(games4, player=2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* We see that the game tends toward a draw, which is what we would expect from a couple of human players. Still, neither player is particularly good."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* As a final measure of skill, let's see how the length of the average game has changed. We would expect this to go down with an increased imbalance in skill levels."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Average length of fully random game is 7.788300 moves\n",
      "Average length of game where P1 uses NN is 6.762000 moves\n",
      "Average length of game where P2 uses NN is 7.711000 moves\n",
      "Average length of game where both use NN is 8.036000 moves\n"
     ]
    }
   ],
   "source": [
    "print(\"Average length of fully random game is %f moves\" % (np.mean([float(len(game)) for game in games])))\n",
    "print(\"Average length of game where P1 uses NN is %f moves\" % (np.mean([float(len(game)) for game in games2])))\n",
    "print(\"Average length of game where P2 uses NN is %f moves\" % (np.mean([float(len(game)) for game in games3])))\n",
    "print(\"Average length of game where both use NN is %f moves\" % (np.mean([float(len(game)) for game in games4])))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* As shown above, the games are a move shorter for player 1 and a big longer for player 2."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Now, we play a game against our model and see how well it does. We let it make the first move."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " | | \n",
      "-----\n",
      " | | \n",
      "-----\n",
      " | |X\n"
     ]
    }
   ],
   "source": [
    "# Create new board\n",
    "board = initBoard()\n",
    "\n",
    "# Move 1 (computer)\n",
    "move = bestMove(board, model, 1)\n",
    "board[move[0]][move[1]] = 1\n",
    "printBoard(board)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " | | \n",
      "-----\n",
      " |O| \n",
      "-----\n",
      " | |X\n"
     ]
    }
   ],
   "source": [
    "# Move 2 (human)\n",
    "board[1][1] = 2\n",
    "printBoard(board)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "X| | \n",
      "-----\n",
      " |O| \n",
      "-----\n",
      " | |X\n"
     ]
    }
   ],
   "source": [
    "# Move 3 (computer)\n",
    "move = bestMove(board, model, 1)\n",
    "board[move[0]][move[1]] = 1\n",
    "printBoard(board)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "X| |O\n",
      "-----\n",
      " |O| \n",
      "-----\n",
      " | |X\n"
     ]
    }
   ],
   "source": [
    "# Move 4 (human)\n",
    "board[0][2] = 2\n",
    "printBoard(board)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "X| |O\n",
      "-----\n",
      " |O| \n",
      "-----\n",
      "X| |X\n"
     ]
    }
   ],
   "source": [
    "# Move 5 (computer)\n",
    "move = bestMove(board, model, 1)\n",
    "board[move[0]][move[1]] = 1\n",
    "printBoard(board)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "X| |O\n",
      "-----\n",
      " |O| \n",
      "-----\n",
      "X|O|X\n"
     ]
    }
   ],
   "source": [
    "# Move 6 (human)\n",
    "board[2][1] = 2\n",
    "printBoard(board)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "X| |O\n",
      "-----\n",
      "X|O| \n",
      "-----\n",
      "X|O|X\n"
     ]
    }
   ],
   "source": [
    "# Move 7 (computer)\n",
    "move = bestMove(board, model, 1)\n",
    "board[move[0]][move[1]] = 1\n",
    "printBoard(board)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Computer wins! This might be bad for humanity. :-)"
   ]
  }
 ],
 "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}