MCTS-tutorial.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Make equations look bigger"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "\n",
       "<style>\n",
       ".MathJax {\n",
       "font-size: 1.3em;\n",
       "}\n",
       "</style>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from IPython.core.display import HTML\n",
    "HTML(\"\"\"\n",
    "<style>\n",
    ".MathJax {\n",
    "font-size: 1.3em;\n",
    "}\n",
    "</style>\n",
    "\"\"\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part 0: Imports"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Mandatory imports"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "from math import sqrt, log\n",
    "import random"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Implementing the vanilla version of Monte Carlo Tree Search does not require any fancy library (not even NumPy!). We will only require two built in packages:\n",
    "+ `math` package to calculate square roots and logarithms, necessary operations for the UCB1 formula used in the Selection phase of MCTS.\n",
    "+ `random` package to sample uniformly for both sampling a random new child to expand in the Expansion phase, and for sampling random actions in the Rollout phase."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Fashion imports"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "import colorama     # Pretty colours :3\n",
    "from colorama import Fore"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`colorama` is a package used to print coloured text to the terminal. It's usage in this tutorial is purely aesthetic. It will be used to print coloured text game representations to the terminal."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part 1: Game state, action and model definitions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/pacman.jpeg\" alt=\"drawing\" width=\"500\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A game state is a snapshot of a game at a point in time. Mathematically it can be regarded as the set of all variables $s_t$ that fully specify a game at a given timestep $t$. Understanding the game representation of a game is paramount to conceptualize the inner workings of tree search based algorithms.\n",
    "\n",
    "As an example, let's define both the **state space** and the **action space** for the snapshot of Pacman shown above:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**State space**:\n",
    "\n",
    "+ The position of all ghosts\n",
    "+ The position of Pacman\n",
    "+ The direction of Pacman\n",
    "+ The position of all active pellets\n",
    "+ The position of all power-up pills\n",
    "+ Time left for the powerup to expire\n",
    "+ The position of all walls\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Action space**:\n",
    "\n",
    "\n",
    "+ Move up\n",
    "+ Move down\n",
    "+ (Note that the walls to the left and right of Pacman make the right / left movement impossible, hence these actions cannot be taken in this state)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The model"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The model is a function that takes a state $s_t$ and an action $a_t$ as inputs, and outputs the state $s_{t+1}$ resulting from executing action $a_t$ in state $s_t$. It contains the game's logic (or game rules) that determine how the actions of the players affect the game being played.\n",
    "\n",
    "$$ s_{t+1} = Model(s_t, a_t) $$\n",
    "\n",
    "The model only needs to capture the parts of the game that influence the game state and its transitions to other game states. In games there often are a multitude of visual and auditorial elements that don't affect the transition from one game state to another."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As an example, below there is a heavily visual video game and its game model, which contains only the location and hitboxes of the entities inside of the game. This is useful to save computation time, and allows your algorithms to run more quickly."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<table><tr><td><img src='images/Vaperio.png'></td><td><img src='images/VaperioModel.png'></td></tr></table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Generic Gamestate interface"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "MCTS is an extremely generic tool for performing (game) tree searches. In order to remain agnostic to the underlying game being played, it requires a generic interface to interact with game trees. This interface is comprised of the following functions:\n",
    "\n",
    "1. `Clone()`: Creates a deep copy of the a game state. This is done so that we can simulate play in a separate environment without modifying the real game being played.\n",
    "2. `GetMoves()`: Returns a list containing all the possible moves (actions) that an agent can execute at this state. A state with no available moves is also known as a terminal state, as the game cannot advance from this state onwards.\n",
    "3. `GetResult()`: To query the outcome of a game upon termination.\n",
    "4. `DoMove()`: The model of the environment. Performs an action in a given state, modifying state. This function is sometimes refered to as the `Step()` function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "class GameState:\n",
    "    \"\"\"\n",
    "        A GameState represents a valid configuration of the 'state' of a game.\n",
    "        For instance:\n",
    "            - the position of all the active pieces on a chess board.\n",
    "            - The position and velocities of all the entities in a 3D world.\n",
    "        This interface presents the minimal functionality required to implement\n",
    "        an MCTS-UCT algorithm for a 2 player game.        \n",
    "    \"\"\"\n",
    "\n",
    "    def __init__(self):\n",
    "        self.playerJustMoved = 2 # Game starts with Player 1.\n",
    "\n",
    "    def Clone(self):\n",
    "        \"\"\" \n",
    "        :returns: deep copy of this GameState\n",
    "        \"\"\"\n",
    "        st = GameState()\n",
    "        st.playerJustMoved = self.playerJustMoved\n",
    "        return st\n",
    "\n",
    "    def DoMove(self, move):\n",
    "        \"\"\"\n",
    "        !! This is the environment's model !!\n",
    "        Changes the GameState by carrying out the param move.\n",
    "        :param move: (int) action taken by an agent.\n",
    "        \"\"\"\n",
    "        self.playerJustMoved = 3 - self.playerJustMoved\n",
    "\n",
    "    def GetMoves(self):\n",
    "        \"\"\" :returns: int array with all available moves at this state\n",
    "        \"\"\"\n",
    "        pass\n",
    "        \n",
    "    def IsGameOver(self):\n",
    "        \"\"\" :returns: whether this GameState is a terminal state\n",
    "        \"\"\"\n",
    "        return self.GetMoves() == []\n",
    "\n",
    "    def GetResult(self, player):\n",
    "        \"\"\" \n",
    "        :param player: (int) player which we want to see if he / she is a winner\n",
    "        :returns: winner from the perspective of the param player\n",
    "        \"\"\"\n",
    "        pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Connect 4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/connect4.png\" alt=\"drawing\" width=\"350\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Connect 4 is a **two player**, **zero-sum**, **symetrical** connection game, in which players take turns dropping one coloured disc from the top into a seven-column, six-row grid. The pieces fall straight down, occupying the lowest available space within the column. The objective of the game is to be the first to form a horizontal, vertical or diagonal line of four of one's own discs.\n",
    "\n",
    "**Fun fact**: Connect 4 is a solved game. The first player is guaranteed to win by playing the right moves."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The game of Connect 4 can be represented programatically using the `GameState` interface shown above in the following way:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "class Connect4State(GameState):\n",
    "    \"\"\"\n",
    "        GameState for the Connect 4 game.\n",
    "        The board is represented as a 2D array (rows and columns).\n",
    "        Each entry on the array can be:\n",
    "            - 0 = empty    (.)\n",
    "            - 1 = player 1 (X)\n",
    "            - 2 = player 2 (O)\n",
    "    \"\"\"\n",
    "\n",
    "    def __init__(self, width=7, height=6, connect=4):\n",
    "        self.playerJustMoved = 2\n",
    "        self.winner = 0 # 0 = no winner, 1 = Player 1 wins, 2 = Player 2 wins.\n",
    "\n",
    "        self.width = width\n",
    "        self.height = height\n",
    "        self.connect = connect\n",
    "        self.InitializeBoard()\n",
    "\n",
    "    def InitializeBoard(self):\n",
    "        \"\"\" \n",
    "        Initialises the Connect 4 gameboard.\n",
    "        \"\"\"\n",
    "        self.board = []\n",
    "        for y in range(self.width):\n",
    "            self.board.append([0] * self.height)\n",
    "\n",
    "    def Clone(self):\n",
    "        \"\"\" \n",
    "        Creates a deep copy of the game state.\n",
    "        NOTE: it is _really_ important that a copy is used during simulations\n",
    "              Because otherwise MCTS would be operating on the real game board.\n",
    "        :returns: deep copy of this GameState\n",
    "        \"\"\"\n",
    "        st = Connect4State(width=self.width, height=self.height)\n",
    "        st.playerJustMoved = self.playerJustMoved\n",
    "        st.winner = self.winner\n",
    "        st.board = [self.board[col][:] for col in range(self.width)]\n",
    "        return st\n",
    "\n",
    "    def DoMove(self, movecol):\n",
    "        \"\"\" \n",
    "        Changes this GameState by \"dropping\" a chip in the column\n",
    "        specified by param movecol.\n",
    "        :param movecol: column over which a chip will be dropped\n",
    "        \"\"\"\n",
    "        assert movecol >= 0 and movecol <= self.width and self.board[movecol][self.height - 1] == 0\n",
    "        row = self.height - 1\n",
    "        while row >= 0 and self.board[movecol][row] == 0:\n",
    "            row -= 1\n",
    "\n",
    "        row += 1\n",
    "\n",
    "        self.playerJustMoved = 3 - self.playerJustMoved\n",
    "        self.board[movecol][row] = self.playerJustMoved\n",
    "        if self.DoesMoveWin(movecol, row):\n",
    "            self.winner = self.playerJustMoved\n",
    "            \n",
    "    def GetMoves(self):\n",
    "        \"\"\"\n",
    "        :returns: array with all possible moves, index of columns which aren't ful\n",
    "        \"\"\"\n",
    "        if self.winner != 0:\n",
    "            return []\n",
    "        return [col for col in range(self.width) if self.board[col][self.height - 1] == 0]\n",
    "\n",
    "    def DoesMoveWin(self, x, y):\n",
    "        \"\"\" \n",
    "        Checks whether a newly dropped chip at position param x, param y\n",
    "        wins the game.\n",
    "        :param x: column index\n",
    "        :param y: row index\n",
    "        :returns: (boolean) True if the previous move has won the game\n",
    "        \"\"\"\n",
    "        me = self.board[x][y]\n",
    "        for (dx, dy) in [(0, +1), (+1, +1), (+1, 0), (+1, -1)]:\n",
    "            p = 1\n",
    "            while self.IsOnBoard(x+p*dx, y+p*dy) and self.board[x+p*dx][y+p*dy] == me:\n",
    "                p += 1\n",
    "            n = 1\n",
    "            while self.IsOnBoard(x-n*dx, y-n*dy) and self.board[x-n*dx][y-n*dy] == me:\n",
    "                n += 1\n",
    "\n",
    "            if p + n >= (self.connect + 1): # want (p-1) + (n-1) + 1 >= 4, or more simply p + n >- 5\n",
    "                return True\n",
    "\n",
    "        return False\n",
    "\n",
    "    def IsOnBoard(self, x, y):\n",
    "        return x >= 0 and x < self.width and y >= 0 and y < self.height\n",
    "\n",
    "    def GetResult(self, player):\n",
    "        \"\"\" \n",
    "        :param player: (int) player which we want to see if he / she is a winner\n",
    "        :returns: winner from the perspective of the param player\n",
    "        \"\"\"\n",
    "        return player == self.winner\n",
    "\n",
    "    def __repr__(self):\n",
    "        s = \"\"\n",
    "        for x in range(self.height - 1, -1, -1):\n",
    "            for y in range(self.width):\n",
    "                s += [Fore.WHITE + '.', Fore.RED + 'X', Fore.YELLOW + 'O'][self.board[y][x]]\n",
    "                s += Fore.RESET\n",
    "            s += \"\\n\"\n",
    "        return s"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The Game loop"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The game loop is probably the most important coding pattern in the field of video game programming. A game loop runs continuously during gameplay. Each turn of the loop, it processes user input, updates the game state, and renders the game. Here we will have the game play out randomly, as this is the simplest way to do rollouts in MCTS."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/game-loop.png\" alt=\"drawing\" width=\"800\"/>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "def PlayGame(initialState):\n",
    "    state = initialState\n",
    "    while not state.IsGameOver():\n",
    "        # Render\n",
    "        print(str(state))\n",
    "        # Capture user input\n",
    "        if state.playerJustMoved == 1:\n",
    "            # Player 2 turn\n",
    "            move = random.choice(state.GetMoves())\n",
    "        else:\n",
    "            # Player 1 turn\n",
    "            move = random.choice(state.GetMoves())\n",
    "        # Update game state\n",
    "        state.DoMove(move)\n",
    "\n",
    "    PrintGameResults(state)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "def PrintGameResults(state):\n",
    "    \"\"\" \n",
    "    Print match results. Function assumes match is over.\n",
    "    \"\"\"\n",
    "    if state.GetResult(state.playerJustMoved) == 1.0:\n",
    "        print(str(state))\n",
    "        print(\"Player \" + str(state.playerJustMoved) + \" wins!\")\n",
    "    elif state.GetResult(state.playerJustMoved) == 0.0:\n",
    "        print(str(state))\n",
    "        print(\"Player \" + str(3 - state.playerJustMoved) + \" wins!\")\n",
    "    else:\n",
    "        print(\"Nobody wins!\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "env = Connect4State(width=7, height= 6)\n",
    "PlayGame(env)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Game Trees"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "class Node:\n",
    "    \"\"\" Node of a game tree. A tree is a connected acyclic graph.\n",
    "        Note: self.wins is from the perspective of playerJustMoved.\n",
    "    \"\"\"\n",
    "\n",
    "    def __init__(self, move=None, parent=None, state=None):\n",
    "        self.move = move  # Move that was taken to reach this game state \n",
    "        self.parentNode = parent  # \"None\" for the root node\n",
    "        self.childNodes = []\n",
    "        \n",
    "        self.wins = 0\n",
    "        self.visits = 0\n",
    "        self.untriedMoves = state.GetMoves()  # Future childNodes\n",
    "        self.playerJustMoved = state.playerJustMoved  # To check who won or who lost.\n",
    "        \n",
    "    def IsFullyExpanded(self):\n",
    "        return self.untriedMoves == []\n",
    "\n",
    "    def AddChild(self, move, state):\n",
    "        \"\"\"\n",
    "        Adds a new child node to this Node. \n",
    "        :param move: (int) action taken by the player\n",
    "        :param state: (GameState) state corresponding to new child node\n",
    "        :returns: new expanded node added to the tree\n",
    "        \"\"\"\n",
    "        node = Node(move=move, parent=self, state=state)\n",
    "        self.untriedMoves.remove(move)\n",
    "        self.childNodes.append(node)\n",
    "        return node\n",
    "\n",
    "    def Update(self, result):\n",
    "        \"\"\"\n",
    "        Updates the node statistics saved in this node with the param result\n",
    "         which is the information obtained during the latest rollout.\n",
    "        :param result: (bool) 1 for victory, 0 for draw / loss.\n",
    "        \"\"\"\n",
    "        self.visits += 1\n",
    "        self.wins += result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part 2: Monte Carlo Tree Search (MCTS-UCT)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Monte Carlo Tree Search is a best-first (greedy) search algorithm that gradually builds up a search tree and uses Monte Carlo simulations to approximate the value of game states. Given a current state of the game, by estimating the value of all possible next game states, we can take the action which will take us the next game state with highest value.\n",
    "\n",
    "MCTS is initialized with only the root node of a tree. This root node represents the current game state in which the decision is to be made. The algorithm repeats a 4-phase iteration loop until a computational budget expires. The concept of computational budget normally takes the shape of a fixed amount of iterations, or a fixed amount of computational time. The latter being the most common. \n",
    "\n",
    "UCT stands for UCB applied to trees, and is used in the selection phase depicted below."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/mcts-diagram.png\" alt=\"drawing\" width=\"800\"/>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "def MCTS_UCT(rootstate, itermax, exploration_factor_ucb1=sqrt(2)):\n",
    "    \"\"\" \n",
    "    Conducts a game tree search using the MCTS-UCT algorithm\n",
    "    for a total of param itermax iterations. The search begins\n",
    "    in the param rootstate. Assumes that 2 players are alternating\n",
    "    with results being [0.0, 1.0].\n",
    "\n",
    "    :param rootstate: The game state for which an action must be selected.\n",
    "    :param itermax: number of MCTS iterations to be carried out. Also knwon as the computational budget.\n",
    "    :returns: (int) Action that will be taken by an agent.\n",
    "    \"\"\"\n",
    "    rootnode = Node(state=rootstate)\n",
    "    \n",
    "    for i in range(itermax):\n",
    "        node  = rootnode\n",
    "        state = rootstate.Clone()\n",
    "\n",
    "        node  = selection_phase(node, state, selection_policy=UCB1, selection_policy_args=[exploration_factor_ucb1])\n",
    "\n",
    "        node  = expansion_phase(node, state)\n",
    "            \n",
    "        rollout_phase(state)\n",
    "            \n",
    "        backpropagation_phase(node, state)\n",
    "    \n",
    "    return action_selection_phase(rootnode)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Selection Phase\n",
    "\n",
    "\n",
    "The selection phase chooses which part of the tree will be explored next, based on the previous information collected during the MCTS run. It always begins in the root node of the game tree, and it is repeated recursively until a node which isn't fully expanded has been reached. A node is considered fully expanded if all of its child nodes have been visited at least once. The selection phase traverses the known tree until a leave node is reached. This is the node that MCTS deems most promising, hence we get the notion of \"best-first\". \n",
    "\n",
    "The selection phase is carried out thus:\n",
    "\n",
    "1. If the current node is fully expanded, continue, else finish phase.\n",
    "2. Use a selection equation to determine the best child node. The selection phase of the algorithm we are covering, MCTS-UCT, is governed by the UCB1 equation below.\n",
    "3. Traverse the tree to the node with the highest selection value.\n",
    "4. Repeat\n",
    "\n",
    "$$UCB1 = \\frac{w_i}{n_i} + c \\sqrt{\\frac{\\log{N_i}}{n_i}}$$\n",
    "\n",
    "+ $w_i$: Number of victories accumulated at **child node** $i$.\n",
    "+ $n_i$: Number of visits accumulated at **child node** $i$.\n",
    "+ $N_i$: Number of visits accumulated at currently selected node.\n",
    "+ $c$: exploration parameter. Constant value that allows a tradeoff between exploration and exploitation. A lower value for $c$ increases the importance of exploitation, and a higher value biases the selection towards exploration. Further reading on [exploitation vs exploration](https://medium.com/@dennybritz/exploration-vs-exploitation-f46af4cf62fe)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "def UCB1(node, child, exploration_constant=sqrt(2)):\n",
    "    return child.wins / child.visits + exploration_constant * sqrt(log(node.visits) / child.visits)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "def selection_phase(node, state, selection_policy=UCB1, selection_policy_args=[]):\n",
    "    if not node.IsFullyExpanded() or node.childNodes == []:\n",
    "        return node\n",
    "    selected_node = sorted(node.childNodes, key=lambda child: selection_policy(node, child, *selection_policy_args))[-1]\n",
    "    state.DoMove(selected_node.move)\n",
    "    return selection_phase(selected_node, state)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Expansion Phase"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Once a node which isn't fully expanded has been reached, one of it's unvisited child nodes is choosen at random, increasing the tree by adding one more node with some initialized statistics. This child node is *expanded* by:\n",
    "\n",
    "1. Adding the child node to the MCTS tree, as a child to the node selected in the Selection phase.\n",
    "2. Instantiating all relevant statistics used in the selection formula for in the Selection phase. For UCB1, these statistics are:\n",
    "\n",
    "\n",
    "+ $w$: number of victories achieved in a rollout where this node was selected.\n",
    "+ $n$: number of times this node has been visited (i.e selected during selection phase)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "def expansion_phase(node, state):\n",
    "    if node.untriedMoves != []:  # if we can expand (i.e. state/node is non-terminal)\n",
    "        move = random.choice(node.untriedMoves)\n",
    "        state.DoMove(move)\n",
    "        node = node.AddChild(move, state)\n",
    "    return node"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Rollout Phase"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In our context, a rollout is a Monte Carlo (i.e random) tree traversal that begins in a node of the game tree and ends in a terminal node. It's a game simulation that takes place in a cloned version of the real game being played. The simulation of the rollout phase begins in the last node expanded in the expansion phase. Random actions are taken for all players until a termninal node is reached. The fact that we are taking random actions by all agents is important, as it ensures that we are computing an unbiased monte carlo estimate of the value function for the state represented in the node where the simulation began.\n",
    "\n",
    "**Note**: Except for the node where the simulation begins, all game tree nodes visited during a rollout are *NOT* part of the tree being built by MCTS."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "def rollout_phase(state):\n",
    "    while state.GetMoves() != []:\n",
    "        state.DoMove(random.choice(state.GetMoves()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Backpropagation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Once a terminal node is reached during the rollout phase, the result of the simulation is observed. For vanilla MCTS, the result is a binary random variable, either a win or a loss. This result is backpropagated through both the newly expanded node, and all the nodes selected during the selection phase. To backpropagate the result means to update the statistics of all nodes on the route from the root of the tree to the node where the rollout began. These statistics are the number of visits $n_i$ and wins $w_i$ for a given node $i$. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "def backpropagation_phase(node, state):\n",
    "    if node is not None:\n",
    "        node.Update(state.GetResult(node.playerJustMoved))\n",
    "        backpropagation_phase(node.parentNode, state)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Action selection\n",
    "\n",
    "Once the computational budget has run out, the last step in any MCTS algorithm is to select an action to take in the actual game being played. As it is the case with all phases of MCTS, there are different approaches. The two most common ones are the following:\n",
    "\n",
    "1. If we stay true to the assumption that MCTS searches a game tree using a best-first (greedy) heuristic, the most visited child node must correspond to the most valuable action explored by MCTS. Thus, we select the action corresponding to the child node $i$ which features the highest visit count $n_i$.\n",
    "\n",
    "2. Alternatively, we can select the action which has the highest expected winrate. That is, for all child nodes of the root node, select the action that maximises $\\frac{w_i}{n_i}$, the empirical winrate of the action encoded in the edge linking the root node with the child node $i$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "def action_selection_phase(node):\n",
    "    return sorted(node.childNodes, key=lambda c: c.wins / c.visits)[-1].move"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Algorithm termination"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "One of the greatest advantages of MCTS is that it is an *anytime algorithm*, meaning that its computation can be stopped an any time and queried for the best action computed given the computational time that it has used until then. This is particularly useful in videogames, as the computational resources often need to be divided between rendering, player input, network features, etc. In these cases it may not be possible to assign a constant computational budget to the AI algorithm being used."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Open loop VS Closed Loop MCTS"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/open-vs-close-loop.png\" alt=\"drawing\" width=\"800\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An **open-loop** approach keeps only one state representation at the root node of the game tree being computed by MCTS, and each of the edges represent an action. As the game tree is being traversed, the actions stored in the nodes being traversed are used as input to the *model* of the game. Thus the initial state stored at the root of the tree changes according to the actions selected during the game tree traversal. Once an MCTS iteration is over, this stated modified during the tree traversal is discarded, and a new clone of the state of the root node is created. Furthermore, we don't store the intermediate states obtained during the traversal. This means that we are esentially throwing away the computation performed by the model as soon as we don't need it.\n",
    "\n",
    "A **closed-loop** approach stores a complete state of the game on each of the nodes of the game tree computed by MCTS. This means that the actions stored in the nodes only need to be used with the game's model once, because we are caching the resulting state of running the model on a state represented by a node with a given action.\n",
    "\n",
    "Both approaches are valid, and each feature their own set of advantages and disadvantages. The open loop approach is (slightly) more computationally demanding because the model is called more often. However, the closed loop approach needs to store potentially tens of thousands of game states, which may be unfeasible for games which require a significant amount of space to simple denote a game state.\n",
    "\n",
    "For nondeterministic games with probabilistic models that are not exposed to the agent, open loop implementations are preferred."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Combining everything"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's put all phases together into a unique function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "def MCTS_UCT(rootstate, itermax, exploration_factor_ucb1=sqrt(2)):\n",
    "    \"\"\" \n",
    "    Conducts a game tree search using the MCTS-UCT algorithm\n",
    "    for a total of param itermax iterations. The search begins\n",
    "    in the param rootstate. Assumes that 2 players are alternating\n",
    "    with results being [0.0, 1.0].\n",
    "\n",
    "    :param rootstate: The game state for which an action must be selected.\n",
    "    :param itermax: number of MCTS iterations to be carried out. Also knwon as the computational budget.\n",
    "    :returns: (int) Action that will be taken by an agent.\n",
    "    \"\"\"\n",
    "    rootnode = Node(state=rootstate)\n",
    "    \n",
    "    for i in range(itermax):\n",
    "        node  = rootnode\n",
    "        state = rootstate.Clone()\n",
    "\n",
    "        node  = selection_phase(node, state, selection_policy=UCB1, selection_policy_args=[exploration_factor_ucb1])\n",
    "\n",
    "        node  = expansion_phase(node, state)\n",
    "            \n",
    "        rollout_phase(state)\n",
    "            \n",
    "        backpropagation_phase(node, state)\n",
    "    \n",
    "    return action_selection_phase(rootnode)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part 3: Playing!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "def PlayGame(initialState):\n",
    "    state = initialState\n",
    "    while not state.IsGameOver():  # If we're not in a terminal state\n",
    "        print(str(state))\n",
    "        if state.playerJustMoved == 1:\n",
    "            # Player 2 turn\n",
    "            move = MCTS_UCT(state, itermax=10000) # Now we are using UCT instead of random!\n",
    "        else:\n",
    "            # Player 1 turn\n",
    "            move = MCTS_UCT(state, itermax=10000)\n",
    "        state.DoMove(move)\n",
    "    PrintGameResults(state)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "InitialState = Connect4State()\n",
    "PlayGame(InitialState)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part 4: Algorithm robustness"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Definition of robustness**: qualitative property of the algorithm of maintaining a good performance whilst being agnostic to changes of the underlying problem."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Robustness to game modification"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/connect-four-thousand.jpeg\" alt=\"drawing\" width=\"300\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's change the rules of the game. Instead of playing Connect 4 on a 7x6 board. Let's play Connect 4 on a 20x14 board. What are the effects of these changes on the game tree representing this new game?\n",
    "\n",
    "+ Increases complexity of the underlying game tree, requiring more rollouts to reach a good approximation.\n",
    "+ The branching factor of the game tree increases greatly since a player now has 20 possible actions rather than 7.\n",
    "+ Increases rollout length, increasing computational need of each iteration.\n",
    "\n",
    "Now let's try Connect 4 on a 7x40 board. What are the effects of these changes on the game tree representing this new game?\n",
    "\n",
    "\n",
    "+ Increases complexity of the underlying game tree, requiring more rollouts to reach a good approximation.\n",
    "+ The branching factor of the game tree actually remains the same as the original game since a player has 7 possible actions at each move.\n",
    "+ Increases rollout length, increasing computational need of each iteration."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "initialState = Connect4State(width=20, height=14, connect=4)\n",
    "PlayGame(initialState)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plot\n",
    "import time\n",
    "import numpy as np\n",
    "\n",
    "\n",
    "def plot_action_frequencies(state, budget, bins=[0,1,2,3,4,5,6,7], runs=100):\n",
    "    x=[]\n",
    "    mctsAverageRuntime = 0\n",
    "    for i in range(runs):\n",
    "        startTime = time.time()\n",
    "        move = MCTS_UCT(state, itermax=budget)\n",
    "        x += [move]\n",
    "        mctsAverageRuntime += (time.time() - startTime) / runs\n",
    "    \n",
    "    plot.hist(x, align='left', bins=bins, edgecolor='black', density=True)\n",
    "    plot.xlabel(\"Move ID\")\n",
    "    plot.ylabel(\"Frequency\")\n",
    "    print(\"Average MCTS Runtime - \" + str(mctsAverageRuntime))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Average MCTS Runtime - 0.019856595993041987\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYUAAAEKCAYAAAD9xUlFAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4xLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvDW2N/gAAEadJREFUeJzt3XuwXWV9xvHvQwJFUHSUVBmSEFQGzSgVGtHWa710YFDAqhVGHe/UqVQdO1Op7aDSdkbU4qVDOyLieENAvDTVWNTRepmpkiBUBKSkCJKoJVgr4g2BX//YK293T0/O3ifJOuuc5PuZ2cNaa797nyeZzHlYt3elqpAkCWCfoQNIkhYPS0GS1FgKkqTGUpAkNZaCJKmxFCRJjaUgSWosBUlSYylIkprlQweYr4MPPrjWrFkzdAxJWlKuuOKK26pqxaRxS64U1qxZw6ZNm4aOIUlLSpKbpxnn4SNJUmMpSJIaS0GS1FgKkqTGUpAkNZaCJKmxFCRJjaUgSWosBUlSYylor3TIytUkWRKvQ1auHvqvS3uRJTfNhbQ7/HDrLRz2+k8PHWMqN5/9jKEjaC/inoIkqbEUJEmNpSBJaiwFSVJjKUiSGktBktRYCpKkxlKQJDWWgiSp6bUUkhyX5Pokm5OcMce4ZyepJOv6zCNJmltvpZBkGXAucDywFjg1ydpZxt0HeA3wjb6ySJKm0+eewrHA5qq6saruBC4CTppl3F8BZwO/7DGLJGkKfZbCocAtY+tbum1NkmOAVVX1mbm+KMlpSTYl2bRt27bdn1SSBAx4ojnJPsA5wJ9OGltV51XVuqpat2LFiv7DSdJeqs9S2AqsGltf2W3b7j7AI4B/SXIT8FhgvSebJWk4fZbCRuCIJIcn2Q84BVi//c2q+klVHVxVa6pqDfB14MSq2tRjJknSHHorhaq6CzgduAy4Drikqq5JclaSE/v6uZKkndfrk9eqagOwYca2M3cw9sl9ZpEkTeYdzZKkxlKQJDWWgiSpsRQkSY2lIElqLAVJUmMpSJIaS0GS1FgKkqTGUpAkNZaCJKmxFCRJjaUgSWosBUlSYylIkhpLQZLUWAqSpMZSkCQ1loIkqbEUJEmNpSBJaiwFSVJjKUiSGktBktRYCpKkxlKQJDWWgiSpsRQkSY2lIElqLAVJUmMpSJIaS0GS1FgKkqTGUpAkNZaCJKmxFCRJjaUgSWosBUlSYylIkppeSyHJcUmuT7I5yRmzvP/KJFcnuSrJ15Ks7TOPJGluvZVCkmXAucDxwFrg1Fl+6V9YVY+sqkcBbwXO6SuPJGmyPvcUjgU2V9WNVXUncBFw0viAqrp9bPVAoHrMI0maYHmP330ocMvY+hbgMTMHJXkV8DpgP+Aps31RktOA0wBWr16924NKkkYGP9FcVedW1UOA1wN/uYMx51XVuqpat2LFioUNKEl7kT5LYSuwamx9ZbdtRy4CTu4xjyRpgj5LYSNwRJLDk+wHnAKsHx+Q5Iix1ROAG3rMI0maoLdzClV1V5LTgcuAZcAFVXVNkrOATVW1Hjg9ydOAXwM/Bl7UVx5J0mR9nmimqjYAG2ZsO3Ns+TV9/nxJ0vwMfqJZkrR4WAqSpMZSkCQ1loIkqbEUJEmNpSBJaqYqhSSP7DuIJGl40+4p/H2Sy5P8cZL79ppIkjSYqUqhqp4APJ/RXEZXJLkwydN7TSZJWnBTn1OoqhsYzWL6euBJwLuTfCfJH/QVTpK0sKY9p3BUkncA1zF65sEzq+rh3fI7eswnSVpA08599HfA+cAbquoX2zdW1feTzPoMBEnS0jNtKZwA/KKq7gZIsg+wf1X9vKo+1Fs6SdKCmvacwheAe42tH9BtkyTtQaYthf2r6o7tK93yAf1EkiQNZdpS+FmSY7avJPlt4BdzjJckLUHTnlN4LfCxJN8HAjwIeF5vqSRJg5iqFKpqY5KHAUd2m66vql/3F0uSNIT5PI7z0cCa7jPHJKGqPthLKknSIKYqhSQfAh4CXAXc3W0uwFKQpD3ItHsK64C1VVV9hpEkDWvaq4++zejksiRpDzbtnsLBwLVJLgd+tX1jVZ3YSypJ0iCmLYU39RlCkrQ4THtJ6peTHAYcUVVfSHIAsKzfaJKkhTbt1NmvAC4F3tNtOhT4VF+hJEnDmPZE86uAxwG3Q3vgzm/2FUqSNIxpS+FXVXXn9pUkyxndpyBJ2oNMWwpfTvIG4F7ds5k/BvxTf7EkSUOYthTOALYBVwN/BGxg9LxmSdIeZNqrj+4B3tu9JEl7qGnnPvous5xDqKoH7/ZEkqTBzGfuo+32B54L3H/3x5EkDWmqcwpV9aOx19aqeidwQs/ZJEkLbNrDR8eMre7DaM9hPs9ikCQtAdP+Yv/bseW7gJuAP9ztaSRJg5r26qPf6zuIJGl40x4+et1c71fVObsnjiRpSPO5+ujRwPpu/ZnA5cANfYSSJA1j2lJYCRxTVT8FSPIm4DNV9YK5PpTkOOBdjKbZPr+q3jLj/dcBL2d0nmIb8NKqunlefwJJ0m4z7TQXDwTuHFu/s9u2Q0mWAecCxwNrgVOTrJ0x7EpgXVUdxWhq7rdOmUeS1INp9xQ+CFye5JPd+snAByZ85lhgc1XdCJDkIuAk4NrtA6rqS2Pjvw7MuechSerXtFcf/U2SzwJP6Da9pKqunPCxQ4Fbxta3AI+ZY/zLgM/O9kaS04DTAFavXj1NZEnSTpj28BHAAcDtVfUuYEuSw3dXiCQvYHQy+22zvV9V51XVuqpat2LFit31YyVJM0x7SeobGf3SPhJ4P7Av8GFGT2Pbka3AqrH1ld22md/9NOAvgCdV1a+miy1J6sO0ewrPAk4EfgZQVd8H7jPhMxuBI5IcnmQ/4BT+95JWAJIczei5zydW1a3zCS5J2v2mLYU7q6rops9OcuCkD1TVXcDpwGXAdcAlVXVNkrOSnNgNextwb+BjSa5Ksn4HXydJWgDTXn10SZL3APdL8grgpUzxwJ2q2sDoKW3j284cW37aPLJKkno27dVHb++ezXw7o/MKZ1bV53tNJklacBNLobsJ7QvdpHgWgSTtwSaeU6iqu4F7ktx3AfJIkgY07TmFO4Crk3ye7gokgKp6dS+pJEmDmLYUPtG9JEl7sDlLIcnqqvpeVU2a50iStAeYdE7hU9sXkny85yySpIFNKoWMLT+4zyCSpOFNKoXawbIkaQ806UTzbyW5ndEew726Zbr1qqqDek0nSVpQc5ZCVS1bqCCSpOHN53kKkqQ9nKUgSWosBUlSYylIkhpLQZLUWAqSpMZSkCQ1loIkqbEUJEmNpSBJaiwFSVJjKUiSGktBktRYCpKkxlKQJDWWgiSpsRQkSc2kx3FKGtqyfUkydIqpPejQVfxgy/eGjqGdZClIi93dv+aw13966BRTu/nsZwwdQbvAw0eSpMZSkCQ1loIkqfGcgnaLQ1au5odbbxk6hqRdZClot/jh1ls8GSrtATx8JElqLAVJUmMpSJIaS0GS1PRaCkmOS3J9ks1Jzpjl/Scm+WaSu5I8p88skqTJeiuFJMuAc4HjgbXAqUnWzhj2PeDFwIV95ZAkTa/PS1KPBTZX1Y0ASS4CTgKu3T6gqm7q3runxxySpCn1efjoUGD8bqYt3TZJ0iK1JE40JzktyaYkm7Zt27bT33PIytUkWTKvQ1au3o1/i5I0WZ+Hj7YCq8bWV3bb5q2qzgPOA1i3bl3tbCDvupWkufW5p7AROCLJ4Un2A04B1vf48yRJu6i3Uqiqu4DTgcuA64BLquqaJGclOREgyaOTbAGeC7wnyTV95ZEkTdbrhHhVtQHYMGPbmWPLGxkdVpIkLQJL4kSzJGlhWAqSpMZSkCQ1loIkqfHJa4vZsn1JMnQKaX6W0L/bBx26ih9s+d7QMRYVS2Exu/vXS+ZmO2+0U+O/2yXNw0eSpMZSkCQ1loIkqbEUJEmNpSBJaiwFSVJjKUiSGktBktR485qkvdcSuvsaFuYObEtB0t5rCd19DQtzB7aHjyRJjaUgSWosBUlSYylIkhpLQZLUWAqSpMZSkCQ1loIkqbEUJEmNpSBJaiwFSVJjKUiSGktBktRYCpKkxlKQJDWWgiSpsRQkSY2lIElqLAVJUmMpSJIaS0GS1FgKkqTGUpAkNb2WQpLjklyfZHOSM2Z5/zeSXNy9/40ka/rMI0maW2+lkGQZcC5wPLAWODXJ2hnDXgb8uKoeCrwDOLuvPJKkyfrcUzgW2FxVN1bVncBFwEkzxpwEfKBbvhR4apL0mEmSNIc+S+FQ4Jax9S3dtlnHVNVdwE+AB/SYSZI0h1RVP1+cPAc4rqpe3q2/EHhMVZ0+Nubb3Zgt3fp/dGNum/FdpwGndatHAtf3EnrnHQzcNnHU4rGU8pq1P0sp71LKCosz72FVtWLSoOU9BtgKrBpbX9ltm23MliTLgfsCP5r5RVV1HnBeTzl3WZJNVbVu6BzTWkp5zdqfpZR3KWWFpZd3XJ+HjzYCRyQ5PMl+wCnA+hlj1gMv6pafA3yx+tp1kSRN1NueQlXdleR04DJgGXBBVV2T5CxgU1WtB94HfCjJZuC/GBWHJGkgfR4+oqo2ABtmbDtzbPmXwHP7zLBAFu2hrR1YSnnN2p+llHcpZYWll7fp7USzJGnpcZoLSVJjKeyiSVN5LBZJLkhya3cZ8KKXZFWSLyW5Nsk1SV4zdKYdSbJ/ksuT/FuX9c1DZ5okybIkVyb59NBZJklyU5Krk1yVZNPQeeaS5H5JLk3ynSTXJfmdoTPNl4ePdkE3lce/A09ndHPeRuDUqrp20GCzSPJE4A7gg1X1iKHzTJLkEOCQqvpmkvsAVwAnL9K/2wAHVtUdSfYFvga8pqq+PnC0HUryOmAdcFBVPWPoPHNJchOwbub9S4tRkg8AX62q87urLg+oqv8eOtd8uKewa6aZymNRqKqvMLrCa0moqh9U1Te75Z8C1/H/74hfFGrkjm513+61aP9vK8lK4ATg/KGz7EmS3Bd4IqOrKqmqO5daIYClsKummcpDu6ibPfdo4BvDJtmx7nDMVcCtwOeratFmBd4J/Blwz9BBplTA55Jc0c1usFgdDmwD3t8dmjs/yYFDh5ovS0GLWpJ7Ax8HXltVtw+dZ0eq6u6qehSjO/ePTbIoD9EleQZwa1VdMXSWeXh8VR3DaMblV3WHQhej5cAxwD9U1dHAz4BFe55xRyyFXTPNVB7aSd3x+Y8DH6mqTwydZxrd4YIvAccNnWUHHgec2B2nvwh4SpIPDxtpblW1tfvvrcAnGR22XYy2AFvG9hIvZVQSS4qlsGummcpDO6E7efs+4LqqOmfoPHNJsiLJ/brlezG68OA7w6aaXVX9eVWtrKo1jP69frGqXjBwrB1KcmB3oQHdoZjfBxblFXRV9UPgliRHdpueCiy6CyMm6fWO5j3djqbyGDjWrJJ8FHgycHCSLcAbq+p9w6aa0+OAFwJXd8fqAd7Q3SW/2BwCfKC7Gm0f4JKqWvSXei4RDwQ+2T1mZTlwYVX987CR5vQnwEe6/0m8EXjJwHnmzUtSJUmNh48kSY2lIElqLAVJUmMpSJIaS0GS1FgK2qslqfGbt5IsT7Ktz9lDkzx5+/cneXH3865MckOSy5L8bl8/W5rEUtDe7mfAI7qbzmB049lC35V+cVUdXVVHAG8BPpHk4QucQQIsBQlGj4w9oVs+Ffjo9jeS3D/Jp5J8K8nXkxyVZJ9ujv/7jY27IckDu7ubP55kY/d63HyCVNWXGD3KcTFP/KY9mKUgjeYAOiXJ/sBR/N/ZWN8MXFlVRwFvYPQ8inuAfwSeBZDkMcDNVfWfwLuAd1TVo4Fns3PTU38TeNjO/mGkXeE0F9rrVdW3uum5T2W01zDu8Yx+uVNVX0zygCQHARcDZwLvZzSH0MXd+KcBa7tpGQAOSnLvsectTCOTh0j9sBSkkfXA2xnND/WAKcb/K/DQJCuAk4G/7rbvAzy2qn65C1mOZvRQIWnBefhIGrkAeHNVXT1j+1eB58PoqiHgtqq6vUaThn0SOIfRTK4/6sZ/jtGkaHSfedR8QiR5EqPzCe/dmT+EtKvcU5CAqtoCvHuWt94EXJDkW8DPgReNvXcxo+nTXzy27dXAud345cBXgFdO+PHPS/J44ADgu8Czq8o9BQ3CWVIlSY2HjyRJjaUgSWosBUlSYylIkhpLQZLUWAqSpMZSkCQ1loIkqfkf+lqZBs9SDuEAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plot_action_frequencies(Connect4State(), budget=100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Average MCTS Runtime - 0.025738804340362548\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYsAAAEKCAYAAADjDHn2AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4xLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvDW2N/gAAGFlJREFUeJzt3X+0XWV95/H3hyAg+FvuKM0PEjVa8ccAvcLM+HMqaFxSQpc6hqld6HKasUNGu5hZA1oXajrOEtuhnc6Ko6nG5Y/SQEGdOzYOxYK2rhbJDVBoYjOEIORGGSIwUgUJCd/54+y0h9vk7pOQnXNu8n6tdVb2fvbznPO9LHI/2fvZ59mpKiRJmslRwy5AkjT6DAtJUivDQpLUyrCQJLUyLCRJrQwLSVIrw0KS1MqwkCS1MiwkSa2OHnYBB8uJJ55YCxcuHHYZkjSrbNiw4UdVNdbW77AJi4ULFzI5OTnsMiRpVkly9yD9Or0MlWRJks1JtiS5ZIZ+b0tSScb72j7YjNuc5M1d1ilJmllnZxZJ5gCrgLOBKWB9komq2jSt39OBDwDf7Ws7BVgGvAz4OeCbSV5cVbu7qleStG9dnlmcAWypqq1VtRNYCyzdS7/fAi4DftbXthRYW1WPVtVdwJbm/SRJQ9BlWMwFtvXtTzVtfy/J6cD8qvqT/R3bjF+eZDLJ5I4dOw5O1ZKkf2Rot84mOQq4HPgPB/oeVbW6qsaranxsrHUyX5J0gLq8G2o7ML9vf17TtsfTgZcD30oC8HxgIsm5A4yVJB1CXZ5ZrAcWJ1mU5Bh6E9YTew5W1Y+r6sSqWlhVC4EbgXOrarLptyzJsUkWAYuBmzqsVZI0g87OLKpqV5IVwLXAHGBNVW1MshKYrKqJGcZuTHIVsAnYBVzonVCSNDw5XJ7BPT4+Xn4pT5L2T5INVTXe1s+1oaQ+J81bQJJZ8zpp3oJh/yfTEeKwWe5DOhju3b6Nky/++rDLGNjdl50z7BJ0hPDMQpLUyrCQJLUyLCRJrQwLSVIrw0KS1MqwkCS1MiwkSa0MC0lSK8NCktTKsJAktTIsJEmtDAtJUivDQpLUyrCQJLUyLCRJrToNiyRLkmxOsiXJJXs5/r4ktye5Ncl3kpzStC9M8kjTfmuST3dZpyRpZp09/CjJHGAVcDYwBaxPMlFVm/q6XVFVn276nwtcDixpjt1ZVad2VZ8kaXBdnlmcAWypqq1VtRNYCyzt71BVD/XtngAcHg8El6TDTJdhMRfY1rc/1bQ9QZILk9wJfBJ4f9+hRUluSfLtJK/tsE5JUouhT3BX1aqqeiFwMfDhpvmHwIKqOg24CLgiyTOmj02yPMlkkskdO3YcuqIl6QjTZVhsB+b37c9r2vZlLXAeQFU9WlX3N9sbgDuBF08fUFWrq2q8qsbHxsYOWuGSpCfqMizWA4uTLEpyDLAMmOjvkGRx3+5bgTua9rFmgpwkLwAWA1s7rFWSNIPO7oaqql1JVgDXAnOANVW1MclKYLKqJoAVSc4CHgMeBC5ohr8OWJnkMeBx4H1V9UBXtUqSZtZZWABU1Tpg3bS2S/u2P7CPcdcA13RZmyRpcEOf4JYkjT7DQpLUyrCQJLUyLCRJrQwLSVIrw0KS1MqwkCS1MiwkSa0MC0lSK8NCktTKsJAktTIsJEmtDAtJUivDQpLUyrCQJLUyLCRJrQwLSVIrw0KS1KrTsEiyJMnmJFuSXLKX4+9LcnuSW5N8J8kpfcc+2IzbnOTNXdYpSZpZZ2GRZA6wCngLcApwfn8YNK6oqldU1anAJ4HLm7GnAMuAlwFLgE817ydJGoIuzyzOALZU1daq2gmsBZb2d6iqh/p2TwCq2V4KrK2qR6vqLmBL836SpCE4usP3ngts69ufAs6c3inJhcBFwDHAL/aNvXHa2LndlClJajP0Ce6qWlVVLwQuBj68P2OTLE8ymWRyx44d3RQoSeo0LLYD8/v25zVt+7IWOG9/xlbV6qoar6rxsbGxJ1muJGlfugyL9cDiJIuSHENvwnqiv0OSxX27bwXuaLYngGVJjk2yCFgM3NRhrZKkGXQ2Z1FVu5KsAK4F5gBrqmpjkpXAZFVNACuSnAU8BjwIXNCM3ZjkKmATsAu4sKp2d1WrJGlmXU5wU1XrgHXT2i7t2/7ADGM/Dny8u+okSYMa+gS3JGn0GRaSpFaGhSSplWEhSWplWEiSWhkWkqRWhoUkqZVhIUlqZVhIkloZFpKkVoaFJKmVYSFJamVYSJJaGRaSpFaGhSSplWEhSWplWEiSWnUaFkmWJNmcZEuSS/Zy/KIkm5LcluTPkpzcd2x3klub18T0sZKkQ6ezx6ommQOsAs4GpoD1SSaqalNft1uA8ap6OMmvA58E3tkce6SqTu2qPknS4Lo8szgD2FJVW6tqJ7AWWNrfoapuqKqHm90bgXkd1iNJOkBdhsVcYFvf/lTTti/vBb7Rt39ckskkNyY5r4sCJUmDGegyVJJXVNXtXRWR5F3AOPD6vuaTq2p7khcA1ye5varunDZuObAcYMGCBV2VJ0lHvEHPLD6V5KYk/y7JMwccsx2Y37c/r2l7giRnAb8JnFtVj+5pr6rtzZ9bgW8Bp00fW1Wrq2q8qsbHxsYGLEuStL8GCouqei3wK/R++W9IckWSs1uGrQcWJ1mU5BhgGfCEu5qSnAZ8hl5Q3NfX/uwkxzbbJwKvBvonxiVJh9DAd0NV1R1JPgxMAr8PnJYkwIeq6it76b8ryQrgWmAOsKaqNiZZCUxW1QTw28DTgD/uvRX3VNW5wEuBzyR5nF6gfWLaXVSSpENo0DmLVwLvAd4KXAf8UlXdnOTngL8C/lFYAFTVOmDdtLZL+7bP2se4vwReMUhtkqTuDXpm8d+Bz9I7i3hkT2NV/aA525AkHcYGDYu30vuS3G6AJEcBx1XVw1X1pc6qkySNhEHvhvom8NS+/eObNknSEWDQsDiuqn6yZ6fZPr6bkiRJo2bQsPhpktP37CT5BeCRGfpLkg4jg85Z/Aa921t/AAR4Pv+w4J8k6TA3UFhU1fokPw+8pGnaXFWPdVeWJGmU7M8S5a8CFjZjTk9CVX2xk6okSSNl0C/lfQl4IXArsLtpLsCwkKQjwKBnFuPAKVVVXRYjSRpNg94N9Tf0JrUlSUegQc8sTgQ2JbkJ6F9G/NxOqpIkjZRBw+KjXRYhSRptg946++0kJwOLq+qbSY6nt+y4JOkIMNCcRZJfA66m96Ai6D1L+2tdFSVJGi2DTnBfSO9pdQ9B70FIwD/pqihJ0mgZNCweraqde3aSHE3vexaSpCPAoGHx7SQfAp7aPHv7j4H/1V1ZkqRRMmhYXALsAG4H/i29R6W2PiEvyZIkm5NsSXLJXo5flGRTktuS/Fkzib7n2AVJ7mheFwxYpySpA4PeDfU48AfNayBJ5gCrgLOBKWB9komq2tTX7RZgvKoeTvLrwCeBdyZ5DvARet8cL2BDM/bBQT9fknTwDHo31F1Jtk5/tQw7A9hSVVub+Y61wNL+DlV1Q1U93OzeCMxrtt8MXFdVDzQBcR2wZNAfSpJ0cO3P2lB7HAe8A3hOy5i5wLa+/SngzBn6vxf4xgxj5w5UqSTpoBv0MtT905p+L8kG4NKDUUSSd9ELpNfv57jlwHKABQsWHIxSJEl7MegS5af37R5F7xd729jtwPy+/XlN2/T3Pgv4TeD1VfVo39g3TBv7reljq2o1sBpgfHzcW3klqSODXob6r33bu4DvA/+qZcx6YHGSRfR++S8D/nV/hySn0ftW+JKquq/v0LXAf0ny7Gb/TcAHB6xVknSQDXoZ6l/u7xtX1a4kK+j94p8DrKmqjUlWApNVNQH8NvA0es/3Brinqs6tqgeS/Ba9wAFYWVUP7G8NkqSDY9DLUBfNdLyqLt9H+zp638nob7u0b/usGd5zDbBmkPokSd3an7uhXgVMNPu/BNwE3NFFUZKk0TJoWMwDTq+qvwNI8lHgT6rqXV0VJkkaHYMu9/E8YGff/s6mTZJ0BBj0zOKLwE1Jvtrsnwd8oZuSJEmjZtC7oT6e5BvAa5um91TVLd2VJUkaJYOeWQAcDzxUVZ9PMpZkUVXd1VVhOnycNG8B927f1t5R0sga9NbZPSvAvgT4PPAU4Mv0np4nzeje7ds4+eKvD7uMgdx92TnDLkEaSYNOcP8ycC7wU4Cq+gHw9K6KkiSNlkHDYmdVFc2jVJOc0F1JkqRRM2hYXJXkM8Czkvwa8E3240FIkqTZbdC7oX6nefb2Q/TmLS6tqus6rUySNDJaw6J5POo3m8UEDQhJOgK1Xoaqqt3A40meeQjqkSSNoEG/Z/ET4PYk19HcEQVQVe/vpCpJ0kgZNCy+0rwkSUegGcMiyYKquqeqXAdKko5gbXMWX9uzkeSajmuRJI2otrBI3/YL9vfNkyxJsjnJliSX7OX465LcnGRXkrdPO7Y7ya3Na2L6WEnSodM2Z1H72G7V3HK7CjgbmALWJ5moqk193e4B3g38x728xSNVder+fKYkqRttYfFPkzxE7wzjqc02zX5V1TNmGHsGsKWqtgIkWQssBf4+LKrq+82xxw+sfEnSoTBjWFTVnCfx3nOB/nWpp4Az92P8cUkmgV3AJ6rqa20DJEnd2J/nWRxqJ1fV9iQvAK5PcntV3dnfIclyYDnAggULhlGjJB0RBl1I8EBsB+b37c9r2gZSVdubP7cC3wJO20uf1VU1XlXjY2NjT65aSdI+dRkW64HFSRYlOQZYBgx0V1OSZyc5ttk+kd5DljbNPEqS1JXOwqKqdgErgGuB7wFXVdXGJCuTnAuQ5FVJpoB3AJ9JsrEZ/lJgMslfAzfQm7MwLCRpSDqds6iqdcC6aW2X9m2vp3d5avq4vwRe0WVtkqTBdXkZSpJ0mDAsJEmtDAtJUivDQpLUyrCQJLUyLCRJrUZ5uQ9JbeY8hSTt/UbAnGOOY/fOnw27jIE9f+58fjh1z7DLGBmGhTSb7X6Mky/++rCrGMjdl50za2qFXr36B16GkiS1MiwkSa0MC0lSK8NCktTKsJAktTIsJEmtDAtJUivDQpLUyrCQJLUyLCRJrToNiyRLkmxOsiXJJXs5/rokNyfZleTt045dkOSO5nVBl3VKkmbWWVgkmQOsAt4CnAKcn+SUad3uAd4NXDFt7HOAjwBnAmcAH0ny7K5qlSTNrMszizOALVW1tap2AmuBpf0dqur7VXUb8Pi0sW8GrquqB6rqQeA6YEmHtUqSZtBlWMwFtvXtTzVtXY+VJB1ks3qCO8nyJJNJJnfs2DHsciTpsNVlWGwH5vftz2vaDtrYqlpdVeNVNT42NnbAhUqSZtZlWKwHFidZlOQYYBkwMeDYa4E3JXl2M7H9pqZNkjQEnYVFVe0CVtD7Jf894Kqq2phkZZJzAZK8KskU8A7gM0k2NmMfAH6LXuCsB1Y2bZKkIej0sapVtQ5YN63t0r7t9fQuMe1t7BpgTZf1SZIGM6snuCVJh4ZhIUlqZVhIkloZFpKkVoaFJKmVYSFJamVYSJJaGRaSpFaGhSSplWEhSWplWEiSWhkWkqRWhoUkqZVhIUlqZVhIkloZFpKkVp0+/EjdOGneAu7dvm3YZUiHtzlPIcmwqxjI8+fO54dT93T6GYbFLHTv9m2cfPHXh13GwO6+7JxhlyDtv92PzZq/Z4fi71inl6GSLEmyOcmWJJfs5fixSa5sjn83ycKmfWGSR5Lc2rw+3WWdkqSZdXZmkWQOsAo4G5gC1ieZqKpNfd3eCzxYVS9Ksgy4DHhnc+zOqjq1q/okSYPr8sziDGBLVW2tqp3AWmDptD5LgS8021cDb8xsuUgoSUeQLsNiLtA/CzvVtO21T1XtAn4MPLc5tijJLUm+neS1e/uAJMuTTCaZ3LFjx5Mq9qR5C0gyK16SdKiN6gT3D4EFVXV/kl8AvpbkZVX1UH+nqloNrAYYHx+vJ/OBs2nS2AljSYdal2cW24H5ffvzmra99klyNPBM4P6qerSq7geoqg3AncCLO6xVkjSDLsNiPbA4yaIkxwDLgIlpfSaAC5rttwPXV1UlGWsmyEnyAmAxsLXDWiVJM+jsMlRV7UqyArgWmAOsqaqNSVYCk1U1AXwO+FKSLcAD9AIF4HXAyiSPAY8D76uqB7qqVZI0s07nLKpqHbBuWtulfds/A96xl3HXANd0WZskaXCuDSVJamVYSJJaGRaSpFaGhSSplWEhSWplWEiSWhkWkqRWhoUkqZVhIUlqZVhIkloZFpKkVoaFJKmVYSFJamVYSJJaGRaSpFaGhSSplWEhSWrVaVgkWZJkc5ItSS7Zy/Fjk1zZHP9ukoV9xz7YtG9O8uYu65QkzayzsEgyB1gFvAU4BTg/ySnTur0XeLCqXgT8LnBZM/YUes/jfhmwBPhU836SpCHo8sziDGBLVW2tqp3AWmDptD5LgS8021cDb0ySpn1tVT1aVXcBW5r3kyQNQZdhMRfY1rc/1bTttU9V7QJ+DDx3wLGSpEMkVdXNGydvB5ZU1b9p9n8VOLOqVvT1+Zumz1SzfydwJvBR4Maq+nLT/jngG1V19bTPWA4sb3ZfAmzu5Ic5cCcCPxp2EfthNtU7m2qF2VXvbKoVZle9o1jryVU11tbp6A4L2A7M79uf17Ttrc9UkqOBZwL3DziWqloNrD6INR9USSaranzYdQxqNtU7m2qF2VXvbKoVZle9s6nW6bq8DLUeWJxkUZJj6E1YT0zrMwFc0Gy/Hbi+eqc6E8Cy5m6pRcBi4KYOa5UkzaCzM4uq2pVkBXAtMAdYU1Ubk6wEJqtqAvgc8KUkW4AH6AUKTb+rgE3ALuDCqtrdVa2SpJl1eRmKqloHrJvWdmnf9s+Ad+xj7MeBj3dZ3yEwspfI9mE21TubaoXZVe9sqhVmV72zqdYn6GyCW5J0+HC5D0lSK8OiI21LnYySJGuS3NfcyjzSksxPckOSTUk2JvnAsGvalyTHJbkpyV83tX5s2DUNIsmcJLck+fqwa5lJku8nuT3JrUkmh11PmyTPSnJ1kr9N8r0k/3zYNe0PL0N1oFma5P8AZ9P7QuF64Pyq2jTUwvYhyeuAnwBfrKqXD7uemSQ5CTipqm5O8nRgA3DeKP63bVYjOKGqfpLkKcB3gA9U1Y1DLm1GSS4CxoFnVNU5w65nX5J8HxivqlH73sJeJfkC8BdV9dnmDtHjq+r/DbuuQXlm0Y1BljoZGVX15/TuRht5VfXDqrq52f474HuM6Lf7q+cnze5TmtdI/+ssyTzgrcBnh13L4STJM4HX0bsDlKraOZuCAgyLrrhcySHQrFJ8GvDd4Vayb80lnVuB+4Drqmpka238HvCfgMeHXcgACvjTJBua1RxG2SJgB/D55hLfZ5OcMOyi9odhoVkpydOAa4DfqKqHhl3PvlTV7qo6ld4qBGckGdnLfEnOAe6rqg3DrmVAr6mq0+mtbH1hczl1VB0NnA78j6o6DfgpMNJzmdMZFt0YaLkSHZjm+v81wB9W1VeGXc8gmksON9Bbcn9UvRo4t5kLWAv8YpIvD7ekfauq7c2f9wFfZbRXpp4CpvrOLK+mFx6zhmHRjUGWOtEBaCaNPwd8r6ouH3Y9M0kyluRZzfZT6d3w8LfDrWrfquqDVTWvqhbS+3/2+qp615DL2qskJzQ3ONBcznkTMLJ381XVvcC2JC9pmt5Ib4WKWaPTb3Afqfa11MmQy9qnJH8EvAE4MckU8JGq+txwq9qnVwO/CtzezAUAfKhZLWDUnAR8obk77ijgqqoa6dtRZ5HnAV/t/duBo4Erqup/D7ekVv8e+MPmH5BbgfcMuZ794q2zkqRWXoaSJLUyLCRJrQwLSVIrw0KS1MqwkCS1MiykfUhS/V9KS3J0kh1drsaa5A173j/Ju5vPuyXJHUmuTfIvuvpsaSaGhbRvPwVe3nyhDnpfqjvU38S/sqpOq6rFwCeAryR56SGuQTIspBbr6K3CCnA+8Ed7DiR5TpKvJbktyY1JXpnkqOY5C8/q63dHkuc13+i+Jsn65vXq/Smkqm6g91jOUV80T4chw0Ka2VpgWZLjgFfyxBVuPwbcUlWvBD5E73kgjwP/E/hlgCRnAndX1f8F/hvwu1X1KuBtHNgy4DcDP3+gP4x0oFzuQ5pBVd3WLIV+Pr2zjH6vofdLn6q6PslzkzwDuBK4FPg8vTWWrmz6nwWc0ixRAfCMJE/re+bFINLeRTr4DAup3QTwO/TWz3ruAP3/CnhRkjHgPOA/N+1HAf+sqn72JGo5jd4Dn6RDystQUrs1wMeq6vZp7X8B/Ar07mICflRVD1VvwbWvApfTWx33/qb/n9JbTI5mzKn7U0SS19Obr/iDA/khpCfDMwupRVVNAb+/l0MfBdYkuQ14GLig79iV9Jaqf3df2/uBVU3/o4E/B97X8vHvTPIa4HjgLuBtVeWZhQ45V52VJLXyMpQkqZVhIUlqZVhIkloZFpKkVoaFJKmVYSFJamVYSJJaGRaSpFb/H+A5eOmvpgngAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plot_action_frequencies(Connect4State(width=7, height=40), budget=100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Average MCTS Runtime - 0.03149103641510009\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYsAAAEKCAYAAADjDHn2AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4xLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvDW2N/gAAFxdJREFUeJzt3XvUXXV95/H3x4SrVlCIlhJCaGG08U4jOqNVR6oNIxIdoYZaC5ZpOmtkbMfOKmhnIVLtkhlHbKd0xrSgCCpQvExGYxFLp3Z1KSagggGpEYUkSI1AoWAxBL7zx9nPeDw8efZOPDvnJHm/1jore//2b+/zPbk8n+zL+f1SVUiSNJfHTboASdL0MywkSa0MC0lSK8NCktTKsJAktTIsJEmtDAtJUivDQpLUyrCQJLWaP+kCxuXQQw+txYsXT7oMSdqtXH/99d+vqgVt/faYsFi8eDHr1q2bdBmStFtJcnuXfl6GkiS1MiwkSa0MC0lSK8NCktTKsJAktTIsJEmtDAtJUivDQpLUyrCQJLUyLDS1Dlu4iCRjex22cNGkP5K029pjhvvQnueuzRs58qxPj+14t59/4tiOJe1tPLOQJLUyLCRJrQwLSVIrw0KS1MqwkCS1MiwkSa0MC0lSK8NCktTKsJAktTIsJEmteg2LJMuS3JpkQ5KzZ9n+kiQ3JNmW5OSh9ucm+WKS9UluTPL6PuuUJM2tt7BIMg+4EDgBWAKcmmTJSLc7gNOBj460/wD49ap6BrAMeH+Sg/uqVZI0tz4HEjwO2FBVtwEkuRxYDtw806GqvtNse3R4x6r6+6HlO5N8D1gA/GOP9UqStqPPy1CHAxuH1jc1bTskyXHAvsC3xlSXJGkHTfUN7iSHAZcCb6qqR2fZvjLJuiTrtmzZsusL1F7POTe0t+jzMtRm4Iih9YVNWydJngh8Bvj9qvrSbH2qahWwCmDp0qW186VKO8c5N7S36PPMYi1wTJKjkuwLrABWd9mx6f9J4MNVdVWPNUqSOugtLKpqG3AmcDVwC3BlVa1Pcl6SkwCSPD/JJuAU4ANJ1je7/wrwEuD0JF9tXs/tq1ZJ0tx6nVa1qtYAa0bazhlaXsvg8tTofpcBl/VZmySpu6m+wS1Jmg6GhSSplWEhSWplWEiSWhkWkqRWhoUkqZVhIUlqZVhIkloZFpKkVoaFJKmVYSFJamVYSJJaGRaSpFaGhSSplWEhSWplWEiSWhkWkqRWhoUkqZVhIUlqZVhIkloZFpKkVoaFJKmVYSFJatVrWCRZluTWJBuSnD3L9pckuSHJtiQnj2w7Lck3m9dpfdYpSZpbb2GRZB5wIXACsAQ4NcmSkW53AKcDHx3Z98nAO4AXAMcB70jypL5qlSTNrc8zi+OADVV1W1VtBS4Hlg93qKrvVNWNwKMj+/4ycE1V3VNV9wLXAMt6rFWSNIc+w+JwYOPQ+qamre99JUljtlvf4E6yMsm6JOu2bNky6XKkqXPYwkUkGetr/n4HjPV4hy1cNOnfJnUwv8djbwaOGFpf2LR13fdlI/v+39FOVbUKWAWwdOnS2pkipT3ZXZs3cuRZnx7rMW8//8SxHvP2808c27HUnz7PLNYCxyQ5Ksm+wApgdcd9rwZemeRJzY3tVzZtkqQJ6C0sqmobcCaDH/K3AFdW1fok5yU5CSDJ85NsAk4BPpBkfbPvPcAfMAictcB5TZskaQL6vAxFVa0B1oy0nTO0vJbBJabZ9r0YuLjP+iRJ3ezWN7glSbuGYSFJamVYSJJaGRaSpFaGhSSplWEhSWplWEiSWhkWkqRWhoUkqZVhIUlqZVhI02TePmMd/ntvNO5h2R1CfaDXsaEk7aBHHnb475/QuIdl3xt/D2fjmYUkqZVhIUlqZVhIkloZFpKkVoaFJKmVYSFJamVYSJJaGRaSpFaGhSSpVaewSPKsvguRJE2vrmcWf5rky0n+Q5KDeq1IkjR1OoVFVf0i8AbgCOD6JB9N8oq2/ZIsS3Jrkg1Jzp5l+35Jrmi2X5dkcdO+T5JLktyU5JYkb9uhTyVJGqvO9yyq6pvAfwHOAl4K/HGSbyT5t7P1TzIPuBA4AVgCnJpkyUi3M4B7q+po4ALg/Kb9FGC/qnoW8AvAb80EiSRp1+t6z+LZSS4AbgFeDry6qn6+Wb5gO7sdB2yoqtuqaitwObB8pM9y4JJm+Srg+AzGVS7g8UnmAwcAW4H7u38sSdI4dT2z+B/ADcBzqurNVXUDQFXdyeBsYzaHAxuH1jc1bbP2qaptwH3AIQyC40Hgu8AdwHur6p7RN0iyMsm6JOu2bNnS8aNoxl437v+Y54rYW+eL0N6p63wWrwL+uaoeAUjyOGD/qvpBVV3aQ13HAY8APwM8CfjbJJ+vqtuGO1XVKmAVwNKlS6uHOvZoe924/2OeKwJ2g88sjUnXM4vPM7gcNOPApm0umxncEJ+xsGmbtU9zyekg4G7gV4G/rKqHq+p7wN8BSzvWKkkas65hsX9VPTCz0iwf2LLPWuCYJEcl2RdYAawe6bMaOK1ZPhm4tqqKwaWnlwMkeTzwQuAbHWuVJI1Z17B4MMmxMytJfgH457l2aO5BnAlczeDG+JVVtT7JeUlOarpdBBySZAPwVmDm8doLgSckWc8gdD5YVTd2/VCSpPHqes/id4C/SHInEOCngde37VRVa4A1I23nDC0/xOAx2dH9HpitXZI0GZ3CoqrWJnk68LSm6daqeri/siRJ06TrmQXA84HFzT7HJqGqPtxLVZKkqdIpLJJcCvwc8FUGj7TC4ItzhoUk7QW6nlksBZY0TypJkvYyXZ+G+jqDm9qSpL1Q1zOLQ4Gbk3wZ+OFMY1WdtP1dJEl7iq5hcW6fRUiSplvXR2f/JsmRwDFV9fkkBwLz+i1NkjQtug5R/psMRoL9QNN0OPCpvoqSJE2Xrje43wy8iGZOiWYipKf0VZQkabp0DYsfNhMYAf9/hFgfo5WkvUTXsPibJG8HDmjm3v4L4P/0V5YkaZp0DYuzgS3ATcBvMRgccHsz5EmS9jBdn4Z6FPiz5iVJ2st0HRvq28xyj6KqfnbsFUmSps6OjA01Y38Gc008efzlSJKmUad7FlV199Brc1W9H3hVz7VJkqZE18tQxw6tPo7BmcaOzIUhSdqNdf2B/9+HlrcB3wF+ZezVSJKmUtenof5134VIkqZX18tQb51re1W9bzzlSJKm0Y48DfV8YHWz/mrgy8A3+yhKkjRduobFQuDYqvongCTnAp+pql/rqzBJ0vToOtzHU4GtQ+tbm7Y5JVmW5NYkG5KcPcv2/ZJc0Wy/LsnioW3PTvLFJOuT3JRk/461SpLGrOuZxYeBLyf5ZLP+GuCSuXZIMg+4EHgFsAlYm2R1Vd081O0M4N6qOjrJCuB84PXNqLaXAW+sqq8lOQR4uPOnkiSNVdcv5b0beBNwb/N6U1X9YctuxwEbquq2Znjzy4HlI32W86PQuQo4PkmAVwI3VtXXmve/u6oe6VKrJGn8ul6GAjgQuL+q/gjYlOSolv6HAxuH1jc1bbP2qaptwH3AIcC/ACrJ1UluSPJ7s71BkpVJ1iVZt2XLlh34KJKkHdF1WtV3AGcBb2ua9mFwmagv84EXA29ofn1tkuNHO1XVqqpaWlVLFyxY0GM5krR363pm8VrgJOBBgKq6E/ipln02A0cMrS9s2mbt09ynOAi4m8FZyBeq6vtV9QMG82cciyRpIrqGxdaqKpphypM8vsM+a4FjkhyVZF9gBT/6nsaM1cBpzfLJwLXN+1wNPCvJgU2IvBS4GUnSRHR9GurKJB8ADk7ym8Bv0DIRUlVtS3Imgx/884CLq2p9kvOAdVW1GrgIuDTJBuAeBoFCVd2b5H0MAqeANVX1mZ34fJKkMeg6NtR7m7m37weeBpxTVdd02G8Ng0tIw23nDC0/xGBujNn2vYx+74tIkjpqDYvm+xKfbwYTbA0ISdKep/WeRfP9hkeTHLQL6pEkTaGu9yweAG5Kcg3NE1EAVfWWXqqSJE2VrmHxieYlSdoLzRkWSRZV1R1VNec4UJKkPVvbPYtPzSwk+XjPtUiSplRbWGRo+Wf7LESSNL3awqK2syxJ2ou03eB+TpL7GZxhHNAs06xXVT2x1+okSVNhzrCoqnm7qhBJ0vTakfksJEl7KcNCktTKsJAktTIsJEmtDAtJUivDQpLUyrCQJLUyLCRJrQwLSVIrw0KS1MqwkCS1MiwkSa16DYsky5LcmmRDkrNn2b5fkiua7dclWTyyfVGSB5L85z7rlCTNrbewSDIPuBA4AVgCnJpkyUi3M4B7q+po4ALg/JHt7wM+21eNkqRu+jyzOA7YUFW3VdVW4HJg+Uif5cDM/N5XAccnCUCS1wDfBtb3WKMkqYM+w+JwYOPQ+qambdY+VbUNuA84JMkTgLOAd/ZYnySpo7aZ8iblXOCCqnqgOdGYVZKVwEqARYsW7ZrKOjps4SLu2ryxvWNH8/bdn0e2PjS24/Vi3j7M9eclzcq/N7uFPsNiM3DE0PrCpm22PpuSzAcOAu4GXgCcnOS/AgcDjyZ5qKr+ZHjnqloFrAJYunTpVM0RftfmjRx51qfHdrzbzz9xrMebOeZYPfLw2D+z9gL+vdkt9BkWa4FjkhzFIBRWAL860mc1cBrwReBk4NqqKuAXZzokORd4YDQoJEm7Tm9hUVXbkpwJXA3MAy6uqvVJzgPWVdVq4CLg0iQbgHsYBIokacr0es+iqtYAa0bazhlafgg4peUY5/ZSnCSpM7/BLUlqZVhIkloZFpKkVoaFJKmVYSFJamVYSJJaGRaSpFaGhSSplWEhSWplWEiSWhkWkqRWhoUkzaWZb2Ocr8MWTtf8O11M6+RHkjQdxjzfBuyec254ZiFJamVYSJJaGRaSpFaGhSSplWEhSWplWEiSWhkWkqRWhoUkqZVhIUlqZVhIklr1GhZJliW5NcmGJGfPsn2/JFc0269Lsrhpf0WS65Pc1Pz68j7rlCTNrbewSDIPuBA4AVgCnJpkyUi3M4B7q+po4ALg/Kb9+8Crq+pZwGnApX3VKUlq1+eZxXHAhqq6raq2ApcDy0f6LAcuaZavAo5Pkqr6SlXd2bSvBw5Isl+PtUqS5tBnWBwObBxa39S0zdqnqrYB9wGHjPR5HXBDVf2wpzolSS2meojyJM9gcGnqldvZvhJYCbBo0e43Prwk7S76PLPYDBwxtL6waZu1T5L5wEHA3c36QuCTwK9X1bdme4OqWlVVS6tq6YIFC8ZcviRpRp9hsRY4JslRSfYFVgCrR/qsZnADG+Bk4NqqqiQHA58Bzq6qv+uxRklSB72FRXMP4kzgauAW4MqqWp/kvCQnNd0uAg5JsgF4KzDzeO2ZwNHAOUm+2rye0letkqS59XrPoqrWAGtG2s4ZWn4IOGWW/d4FvKvP2iRJ3fkNbklSK8NCktTKsJAktTIsJEmtDAtJUivDQpLUyrCQJLUyLCRJrQwLSVIrw0KS1MqwkCS1Miwahy1cRJKxvSRpu+btM9afN4ct7H8+n6me/GhXumvzRo4869NjO97t5584tmNJ2sM88vBu9/PGMwtJUivDQpLUyrCQJLUyLCRJrQwLSVIrw0KS1MqwkCS1MiwkSa0MC0lSK8NCktSq17BIsizJrUk2JDl7lu37Jbmi2X5dksVD297WtN+a5Jf7rFOSNLfewiLJPOBC4ARgCXBqkiUj3c4A7q2qo4ELgPObfZcAK4BnAMuAP22OJ0magD7PLI4DNlTVbVW1FbgcWD7SZzlwSbN8FXB8BkO2Lgcur6ofVtW3gQ3N8SRJE9BnWBwObBxa39S0zdqnqrYB9wGHdNxXkrSLpKr6OXByMrCsqv5ds/5G4AVVdeZQn683fTY1698CXgCcC3ypqi5r2i8CPltVV428x0pgZbP6NODWXj7MjzsU+P4ueJ+dNe31gTWOw7TXB9Nf47TXB7umxiOrakFbpz7ns9gMHDG0vrBpm63PpiTzgYOAuzvuS1WtAlaNseZWSdZV1dJd+Z47YtrrA2sch2mvD6a/xmmvD6arxj4vQ60FjklyVJJ9GdywXj3SZzVwWrN8MnBtDU51VgMrmqeljgKOAb7cY62SpDn0dmZRVduSnAlcDcwDLq6q9UnOA9ZV1WrgIuDSJBuAexgECk2/K4GbgW3Am6vqkb5qlSTNrddpVatqDbBmpO2coeWHgFO2s++7gXf3Wd9O2qWXvXbCtNcH1jgO014fTH+N014fTFGNvd3gliTtORzuQ5LUyrDoqG3okklLckSSv05yc5L1SX570jXNJsm8JF9J8ulJ1zKbJAcnuSrJN5LckuRfTrqmUUn+U/Nn/PUkH0uy/xTUdHGS7zWPw8+0PTnJNUm+2fz6pCmr7781f843JvlkkoMnVd/2ahza9rtJKsmhk6gNDItOOg5dMmnbgN+tqiXAC4E3T2GNAL8N3DLpIubwR8BfVtXTgecwZbUmORx4C7C0qp7J4OGRFZOtCoAPMRiaZ9jZwF9V1THAXzXrk/IhHlvfNcAzq+rZwN8Db9vVRY34EI+tkSRHAK8E7tjVBQ0zLLrpMnTJRFXVd6vqhmb5nxj8kJuqb70nWQi8CvjzSdcymyQHAS9h8JQeVbW1qv5xslXNaj5wQPPdpAOBOydcD1X1BQZPNA4bHs7nEuA1u7SoIbPVV1Wfa0aOAPgSg+9zTcx2fg9hMG7e7wETvcFsWHSzWw0/0oze+zzguslW8hjvZ/CX/tFJF7IdRwFbgA82l8r+PMnjJ13UsKraDLyXwf8yvwvcV1Wfm2xV2/XUqvpus3wX8NRJFtPiN4DPTrqIUUmWA5ur6muTrsWw2MMkeQLwceB3qur+SdczI8mJwPeq6vpJ1zKH+cCxwP+squcBDzLZSyeP0Vz3X84g2H4GeHySX5tsVe2aL9tO5aOXSX6fwWXcj0y6lmFJDgTeDpzT1ndXMCy66TT8yKQl2YdBUHykqj4x6XpGvAg4Kcl3GFzGe3mSyyZb0mNsAjZV1cwZ2VUMwmOa/BLw7araUlUPA58A/tWEa9qef0hyGEDz6/cmXM9jJDkdOBF4Q03f9wh+jsF/Cr7W/LtZCNyQ5KcnUYxh0U2XoUsmqhna/SLglqp636TrGVVVb6uqhVW1mMHv37VVNVX/I66qu4CNSZ7WNB3PYBSBaXIH8MIkBzZ/5sczZTfhhwwP53Ma8L8nWMtjJFnG4LLoSVX1g0nXM6qqbqqqp1TV4ubfzSbg2Obv6S5nWHTQ3ASbGbrkFuDKqlo/2aoe40XAGxn8j/2rzevfTLqo3dB/BD6S5EbgucAfTrieH9Oc9VwF3ADcxODf8MS/5ZvkY8AXgacl2ZTkDOA9wCuSfJPBGdF7pqy+PwF+Crim+ffyvyZV3xw1Tg2/wS1JauWZhSSplWEhSWplWEiSWhkWkqRWhoUkqZVhIW1HM8rnZUPr85Ns6XPE3CQvmzl+ktOb9/tKM3Lr1Umm9Qt42sMZFtL2PQg8M8kBzfor2PXf3L+iqp7XjNz6HuATSX5+F9cgGRZSizUMRsoFOBX42MyGZr6GTzXzIXwpybOTPC7Jd4bnRmjOCp6aZEGSjydZ27xetCOFVNVfM/gC3soxfC5phxgW0twuB1Y0Eww9mx8fyfedwFea+RDeDny4qh5lMKzFawGSvAC4var+gcFcGRdU1fOB17FzQ7XfADx9Zz+MtLPmT7oAaZpV1Y3NkO+nMjjLGPZiBj/0qaprkxyS5InAFQxGCv0gg3Gwrmj6/xKwZDCkEwBPTPKEqnpgB0pKexdp/AwLqd1qBnNIvAw4pEP/LwJHJ1nAYMKfdzXtjwNeWFUP/QS1PI/pHThQezAvQ0ntLgbeWVU3jbT/LfAGGDzFBHy/qu5vhrr+JPA+BqMA3930/xyDgQpp9nnujhSR5KUM7lf82c58COkn4ZmF1KKqNgF/PMumc4GLmxFqf8CPhuOGwaWntcDpQ21vAS5s+s8HvgD8+5a3f32SFzOYPvXbwOuqyjML7XKOOitJauVlKElSK8NCktTKsJAktTIsJEmtDAtJUivDQpLUyrCQJLUyLCRJrf4f6T+n6Kyv8osAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plot_action_frequencies(Connect4State(width=15, height=19), budget=100, bins=np.arange(0,16))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "def calculate_optimality_of_move(state, bins, budget=50000, runs=50, optimal_move=3, exploration_factor=sqrt(2)):\n",
    "    x = []\n",
    "    for i in range(runs):\n",
    "        move = MCTS_UCT(state, itermax=budget, exploration_factor_ucb1=exploration_factor)\n",
    "        x += [move]\n",
    "    density, bins = np.histogram(x, bins=bins, density=True)\n",
    "    return density[optimal_move]\n",
    "        \n",
    "def plot_optimality_of_moves_over_exploration_factor(state, bins=[0,1,2,3,4,5,6], min_value=0, max_value=1, step=0.3):\n",
    "    optimal_move = int((len(bins)-1)/2)\n",
    "    y = []\n",
    "    x = np.arange(min_value, max_value, step)\n",
    "    for exploration_factor in x:\n",
    "        move_optimality = calculate_optimality_of_move(state, optimal_move=optimal_move, bins=bins, exploration_factor=exploration_factor)\n",
    "        y += [move_optimality]\n",
    "    plot.plot(x,y, marker='o', linestyle='--')\n",
    "    plot.xlabel(\"Exploration factor\")\n",
    "    plot.ylabel(\"Move optimality\")\n",
    "    \n",
    "def plot_optimality_of_moves_over_budget(state, bins=[0,1,2,3,4,5,6], min_value=0, max_value=1, step=0.3):\n",
    "    optimal_move = int((len(bins)-1)/2)\n",
    "    y = []\n",
    "    x = np.arange(min_value, max_value, step)\n",
    "    for budget in x:\n",
    "        move_optimality = calculate_optimality_of_move(state, optimal_move=optimal_move, bins=bins, budget=budget)\n",
    "        y += [move_optimality]\n",
    "    plot.plot(x,y, marker='o', linestyle='--')\n",
    "    plot.xlabel(\"Budget (iterations)\")\n",
    "    plot.ylabel(\"Move optimality\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "plot_optimality_of_moves_over_exploration_factor(Connect4State(), bins=np.arange(0,8), min_value=-2, max_value=4, step=0.1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/exploration-factor-plot.png\" align=\"left\" alt=\"drawing\" width=\"500\"/>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "plot_optimality_of_moves_over_budget(Connect4State(), bins=np.arange(0,8), min_value=100, max_value=2000, step=100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/budget-plot.png\" align=\"left\" alt=\"drawing\" width=\"500\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Robustness to other games"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/tic-tac-toe.png\" alt=\"drawing\" width=\"300\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tic tac toe needs no introduction ;).\n",
    "\n",
    "Let's jump straight into the code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "class TicTacToeState(GameState):\n",
    "    \"\"\" A state of the game, i.e. the game board.\n",
    "        Squares in the board are in this arrangement\n",
    "        012\n",
    "        345\n",
    "        678\n",
    "        where 0 = empty, 1 = player 1 (X), 2 = player 2 (O)\n",
    "    \"\"\"\n",
    "\n",
    "    def __init__(self):\n",
    "        self.playerJustMoved = 2  # At the root pretend the player just moved is p2 - p1 has the first move\n",
    "        self.board = [0, 0, 0, 0, 0, 0, 0, 0, 0]  # 0 = empty, 1 = player 1, 2 = player 2\n",
    "\n",
    "    def Clone(self):\n",
    "        \"\"\" Create a deep clone of this game state.\n",
    "        \"\"\"\n",
    "        st = TicTacToeState()\n",
    "        st.playerJustMoved = self.playerJustMoved\n",
    "        st.board = self.board[:]\n",
    "        return st\n",
    "\n",
    "    def DoMove(self, move):\n",
    "        \"\"\" Update a state by carrying out the given move.\n",
    "            Must update playerToMove.\n",
    "        \"\"\"\n",
    "        assert move >= 0 and move <= 8 and move == int(move) and self.board[move] == 0\n",
    "        self.playerJustMoved = 3 - self.playerJustMoved\n",
    "        self.board[move] = self.playerJustMoved\n",
    "\n",
    "    def GetMoves(self):\n",
    "        \"\"\" Get all possible moves from this state.\n",
    "        \"\"\"\n",
    "        return [i for i in range(9) if self.board[i] == 0]\n",
    "\n",
    "    def GetResult(self, playerjm):\n",
    "        \"\"\" Get the game result from the viewpoint of playerjm for a finished game.\n",
    "        \"\"\"\n",
    "        for (x, y, z) in [(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",
    "            if self.board[x] == self.board[y] == self.board[z]:\n",
    "                if self.board[x] == playerjm:\n",
    "                    return 1.0\n",
    "                else:\n",
    "                    return 0.0\n",
    "        if self.GetMoves() == []: return 0.5  # draw\n",
    "        assert False  # Should not be possible to get here\n",
    "\n",
    "    def __repr__(self):\n",
    "        s = \"\"\n",
    "        for i in range(9):\n",
    "            s += [Fore.WHITE + '.', Fore.GREEN + 'X', Fore.BLUE + 'O'][self.board[i]]\n",
    "            s += Fore.RESET\n",
    "            if i % 3 == 2: s += \"\\n\"\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "initialState = TicTacToeState()\n",
    "PlayGame(initialState)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The game ends in a draw everytime! Unsurprisingly, as Tic-tac-toe has been solved for many, many years. If both players play optimally, it leads to a draw. The takeaway is that even though MCTS takes only a few lines of code to write, it can *literally* play optimally for simple games, it reaches an expert level for games like Connect 4, and novice levels for much more complex games like Go. And this is only the vanilla version of MCTS! There are dozens of different variations that improve upon MCTS's *many* initial shortcomings.\n",
    "\n",
    "Some of these variations include:\n",
    "+ Tree reusage\n",
    "+ Loss avoidance\n",
    "+ Optimistic pruning\n",
    "+ Information sets for partially observable environments\n",
    "+ Limited depth rollouts with evaluation functions\n",
    "+ And many, many more.\n",
    "\n",
    "For a beautiful overview of all these and many other improvements over the vanilla MCTS, We will leave you with [A survey of Monte Carlo Tree Search methods](http://mcts.ai/pubs/mcts-survey-master.pdf)."
   ]
  }
 ],
 "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}