Ex_07_MCTS.ipynb

{"cells":[{"cell_type":"markdown","metadata":{"id":"sbxqwFRpKynK"},"source":["<center><img src='https://i.postimg.cc/TPR1n1rp/AI-Tech-PL-RGB.png' height=\"60\"></center>\n","\n","AI TECH - Akademia Innowacyjnych Zastosowań Technologii Cyfrowych. Programu Operacyjnego Polska Cyfrowa na lata 2014-2020\n","<hr>\n","\n","<center><img src='https://i.postimg.cc/Gpq2KRQz/logotypy-aitech.jpg'></center>\n","\n","<center>\n","Projekt współfinansowany ze środków Unii Europejskiej w ramach Europejskiego Funduszu Rozwoju Regionalnego \n","Program Operacyjny Polska Cyfrowa na lata 2014-2020,\n","Oś Priorytetowa nr 3 \"Cyfrowe kompetencje społeczeństwa\" Działanie  nr 3.2 \"Innowacyjne rozwiązania na rzecz aktywizacji cyfrowej\" \n","Tytuł projektu:  „Akademia Innowacyjnych Zastosowań Technologii Cyfrowych (AI Tech)”\n","</center>"]},{"cell_type":"markdown","metadata":{"id":"FwCSW80DLu5V"},"source":["# Lab ??: Monte-Carlo Tree Search\n","\n","In this lab, you'll play Connect4 against the Monte-Carlo Tree Search (MCTS) planner you need to implement yourself. MCTS is composed of four phases, which it iterates, that you'll implement in this order:\n","\n","1. Selection,\n","2. Expansion,\n","3. Simulation,\n","4. Backpropagation.\n","\n","\n","![MCTS diagram](https://www.researchgate.net/profile/Jacek-Mandziuk/publication/319126544/figure/fig1/AS:614155115581472@1523437398677/MCTS-algorithm-overview-6.png)"]},{"cell_type":"code","execution_count":11,"metadata":{"id":"Nmnze8RFu1Fi","executionInfo":{"status":"ok","timestamp":1683212580255,"user_tz":-120,"elapsed":3,"user":{"displayName":"Michał Janik","userId":"10483929333441523386"}}},"outputs":[],"source":["import copy\n","import random\n","import time\n","from dataclasses import dataclass\n","from functools import partial\n","\n","import numpy as np\n","\n","def prompt_for_integer(prompt):\n","    while True:\n","        try:\n","            return(int(input(prompt)))\n","        except ValueError:\n","            print(\"[!] Please enter a valid integer\")"]},{"cell_type":"markdown","metadata":{"id":"c9lyZ84G6pJ4"},"source":["## Connect4\n","\n","* The game is played on 6 by 7 board.\n","* Two players alternate turns dropping one of their stones (discs) at a time into an unfilled column.\n","* The goal is to Connect 4 of player's stones in a row/col/diagonal while preventing its opponent from doing the same.\n","* If the board fills up before either player achieves four in a row/col/diagonal, then the game is a draw.\n","\n","```\n"," | Player 1: x; Player -1: o |\\\n"," |---------------------------||\n"," | 0 | 1 | 2 | 3 | 4 | 5 | 6 ||\n"," |---|---|---|---|---|---|---||\n","[[ - | - | - | - | - | - | - ]|\n"," [ - | - | - | - | - | - | - ]|\n"," [ - | - | - | x | - | - | - ]|\n"," [ - | - | - | x | - | - | - ]|\n"," [ - | - | - | o | - | - | - ]|\n"," [ - | - | o | x | - | o | - ]]\n","```"]},{"cell_type":"code","execution_count":12,"metadata":{"id":"WNVnKKo0JRR_","executionInfo":{"status":"ok","timestamp":1683212580255,"user_tz":-120,"elapsed":2,"user":{"displayName":"Michał Janik","userId":"10483929333441523386"}}},"outputs":[],"source":["class Connect4Board():\n","    \"\"\"Connect4 board with the game logic.\"\"\"\n","\n","    def __init__(self, pieces=None, win_length=4):\n","        \"\"\"Initialize the board with the pieces position.\"\"\"\n","        if pieces is None:\n","            self._pieces = np.zeros([6, 7]) # Default height = 6 x width = 7\n","        else:\n","            self._pieces = pieces\n","        self._win_length = win_length\n","\n","        # Cache winner\n","        self._winner = self._get_winner()\n","\n","    def add_stone(self, column):\n","        \"\"\"Create copy of the board containing a new stone.\"\"\"\n","        available_idx, = np.where(self.pieces[:, column] == 0)\n","        if len(available_idx) == 0:\n","            raise ValueError(f'Can\\'t play column {column} on board {self}')\n","\n","        assert not self.is_terminal, 'Can\\'t plan on the terminal board'\n","\n","        pieces_ = np.copy(self.pieces)\n","        pieces_[available_idx[-1]][column] = self.player_turn\n","        return Connect4Board(pieces_, self._win_length)\n","\n","    def _get_winner(self):\n","        \"\"\"Checks if the board is terminal and returns a winner.\n","        \n","        Returns:\n","            1 if player 1 wins.\n","            -1 if player -1 wins.\n","            0 when draw.\n","            None when the game not ended yet.\n","        \"\"\"\n","        # Check if the previous player move won\n","        previous_player = self.player_turn * -1\n","        player_pieces = self.pieces == previous_player\n","        # Check rows, columns, and diagonals for a win\n","        if (self._is_straight_winner(player_pieces) or\n","            self._is_straight_winner(player_pieces.transpose()) or\n","            self._is_diagonal_winner(player_pieces)):\n","            return previous_player\n","\n","        # Return a draw\n","        if not self.valid_moves:\n","            return 0\n","\n","        # Game is not ended yet\n","        return None\n","\n","    def _is_diagonal_winner(self, player_pieces):\n","        \"\"\"Checks if `player_pieces` contains a diagonal win.\"\"\"\n","        for i in range(len(player_pieces) - self.win_length + 1):\n","            for j in range(len(player_pieces[0]) - self.win_length + 1):\n","                if all(player_pieces[i + x][j + x] for x in range(self.win_length)):\n","                    return True\n","            for j in range(self.win_length - 1, len(player_pieces[0])):\n","                if all(player_pieces[i + x][j - x] for x in range(self.win_length)):\n","                    return True\n","        return False\n","\n","    def _is_straight_winner(self, player_pieces):\n","        \"\"\"Checks if `player_pieces` contains a vertical or horizontal win.\"\"\"\n","        run_lengths = [player_pieces[:, i:i + self.win_length].sum(axis=1)\n","                       for i in range(len(player_pieces) - self.win_length + 2)]\n","        return max([x.max() for x in run_lengths]) >= self.win_length\n","\n","    @property\n","    def is_terminal(self):\n","        return self.winner is not None\n","\n","    @property\n","    def pieces(self):\n","        return self._pieces\n","\n","    @property\n","    def player_turn(self):\n","        sum_pieces = np.sum(self.pieces)\n","        if sum_pieces == 0:\n","            return 1\n","        elif sum_pieces == 1:\n","            return -1\n","        else:\n","            raise ValueError(f'Invalid state on board {self}')\n","\n","    @property\n","    def valid_moves(self):\n","        # Any zero value in top row in a valid move\n","        return list(np.where(self.pieces[0] == 0)[0])\n","\n","    @property\n","    def win_length(self):\n","        return self._win_length\n","\n","    @property\n","    def winner(self):\n","        \"\"\"Returns a winner or None.\n","\n","        Values:\n","            1 if player 1 wins.\n","            -1 if player -1 wins.\n","            0 when draw.\n","            None when the game not ended yet.\n","        \"\"\"\n","        return self._winner\n","\n","    def __str__(self):\n","        def piece_sign(piece):\n","            if piece == 1.0:\n","                return ' x '\n","            elif piece == -1.0:\n","                return ' o '\n","            else:\n","                return ' - '\n","        formatter = dict(float=piece_sign)\n","\n","        return ('\\n | Player 1: x; Player -1: o |\\\\\\n' +\n","                ' |' + ''.join([f'----' for i in range(self.pieces.shape[1] - 1)]) + '---||\\n' +\n","                ' |' + ''.join([f' {i} |' for i in range(self.pieces.shape[1])]) + '|\\n' +\n","                ' |' + ''.join(['---|' for _ in range(self.pieces.shape[1])]) + '|\\n' +  \n","                np.array2string(self.pieces, sign=' ', separator='|', formatter=formatter) + '\\n')\n","\n","    def __eq__(self, other):\n","        if not isinstance(other, Connect4Board):\n","            return False\n","        return (np.all(self.pieces == other.pieces) and\n","                self.win_length == other.win_length)\n","\n","    def __hash__(self):\n","        return hash((self.pieces.tobytes(), self.win_length))"]},{"cell_type":"code","execution_count":13,"metadata":{"id":"zzCwDZMqODqb","executionInfo":{"status":"ok","timestamp":1683212580960,"user_tz":-120,"elapsed":12,"user":{"displayName":"Michał Janik","userId":"10483929333441523386"}}},"outputs":[],"source":["def human(board):\n","    \"\"\"Returns the next board after the human move.\"\"\"\n","    print(board)\n","    while True:\n","        column = prompt_for_integer(\n","            f'Player {board.player_turn} adds stone in a column [0-{board.pieces.shape[1]-1}]: ')\n","        try:\n","            return board.add_stone(column)\n","        except ValueError as err:\n","            print(f'[!] Value Error: {err}')\n","            continue\n","        except IndexError as err:\n","            print(f'[!] Index Error: Column {column} is an illegal move')\n","            continue\n","\n","def play(player_first, player_second, board=None):\n","    \"\"\"Alternately calls two players starting from `board` until termination.\"\"\"\n","    if board is None:\n","        board = Connect4Board()\n","    \n","    players = [player_first, player_second]\n","    player_idx = 0\n","    while not board.is_terminal:\n","        board = players[player_idx](board)\n","        player_idx = (player_idx + 1) % 2\n","\n","    print(board)\n","    if board.winner == 0:\n","        print('No one wins...')\n","    else:\n","        print(f'Player {board.winner} wins!')"]},{"cell_type":"code","execution_count":14,"metadata":{"colab":{"base_uri":"https://localhost:8080/","height":532},"executionInfo":{"elapsed":3075,"status":"error","timestamp":1683212584024,"user":{"displayName":"Michał Janik","userId":"10483929333441523386"},"user_tz":-120},"id":"uGI6r6esMEiW","outputId":"67965800-06d4-462b-b54d-2ad3437eb270"},"outputs":[{"output_type":"stream","name":"stdout","text":["\n"," | Player 1: x; Player -1: o |\\\n"," |---------------------------||\n"," | 0 | 1 | 2 | 3 | 4 | 5 | 6 ||\n"," |---|---|---|---|---|---|---||\n","[[ - | - | - | - | - | - | - ]|\n"," [ - | - | - | - | - | - | - ]|\n"," [ - | - | - | - | - | - | - ]|\n"," [ - | - | - | - | - | - | - ]|\n"," [ - | - | - | - | - | - | - ]|\n"," [ - | - | - | - | - | - | - ]]\n","\n"]},{"output_type":"error","ename":"KeyboardInterrupt","evalue":"ignored","traceback":["\u001b[0;31m---------------------------------------------------------------------------\u001b[0m","\u001b[0;31mKeyboardInterrupt\u001b[0m                         Traceback (most recent call last)","\u001b[0;32m<ipython-input-14-0fe0869c49af>\u001b[0m in \u001b[0;36m<cell line: 1>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mplay\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mhuman\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mhuman\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m","\u001b[0;32m<ipython-input-13-ce38203df79e>\u001b[0m in \u001b[0;36mplay\u001b[0;34m(player_first, player_second, board)\u001b[0m\n\u001b[1;32m     22\u001b[0m     \u001b[0mplayer_idx\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     23\u001b[0m     \u001b[0;32mwhile\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0mboard\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mis_terminal\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 24\u001b[0;31m         \u001b[0mboard\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mplayers\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mplayer_idx\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mboard\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     25\u001b[0m         \u001b[0mplayer_idx\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0mplayer_idx\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m%\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     26\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n","\u001b[0;32m<ipython-input-13-ce38203df79e>\u001b[0m in \u001b[0;36mhuman\u001b[0;34m(board)\u001b[0m\n\u001b[1;32m      3\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mboard\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[0;32mwhile\u001b[0m \u001b[0;32mTrue\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m         column = prompt_for_integer(\n\u001b[0m\u001b[1;32m      6\u001b[0m             f'Player {board.player_turn} adds stone in a column [0-{board.pieces.shape[1]-1}]: ')\n\u001b[1;32m      7\u001b[0m         \u001b[0;32mtry\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n","\u001b[0;32m<ipython-input-11-e7af2e827b62>\u001b[0m in \u001b[0;36mprompt_for_integer\u001b[0;34m(prompt)\u001b[0m\n\u001b[1;32m     10\u001b[0m     \u001b[0;32mwhile\u001b[0m \u001b[0;32mTrue\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     11\u001b[0m         \u001b[0;32mtry\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 12\u001b[0;31m             \u001b[0;32mreturn\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0minput\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mprompt\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     13\u001b[0m         \u001b[0;32mexcept\u001b[0m \u001b[0mValueError\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m             \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"[!] Please enter a valid integer\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n","\u001b[0;32m/usr/local/lib/python3.10/dist-packages/ipykernel/kernelbase.py\u001b[0m in \u001b[0;36mraw_input\u001b[0;34m(self, prompt)\u001b[0m\n\u001b[1;32m    849\u001b[0m                 \u001b[0;34m\"raw_input was called, but this frontend does not support input requests.\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    850\u001b[0m             )\n\u001b[0;32m--> 851\u001b[0;31m         return self._input_request(str(prompt),\n\u001b[0m\u001b[1;32m    852\u001b[0m             \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_parent_ident\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    853\u001b[0m             \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_parent_header\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n","\u001b[0;32m/usr/local/lib/python3.10/dist-packages/ipykernel/kernelbase.py\u001b[0m in \u001b[0;36m_input_request\u001b[0;34m(self, prompt, ident, parent, password)\u001b[0m\n\u001b[1;32m    893\u001b[0m             \u001b[0;32mexcept\u001b[0m \u001b[0mKeyboardInterrupt\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    894\u001b[0m                 \u001b[0;31m# re-raise KeyboardInterrupt, to truncate traceback\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 895\u001b[0;31m                 \u001b[0;32mraise\u001b[0m \u001b[0mKeyboardInterrupt\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"Interrupted by user\"\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mfrom\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    896\u001b[0m             \u001b[0;32mexcept\u001b[0m \u001b[0mException\u001b[0m \u001b[0;32mas\u001b[0m \u001b[0me\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    897\u001b[0m                 \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mlog\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mwarning\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"Invalid Message:\"\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mexc_info\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;32mTrue\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n","\u001b[0;31mKeyboardInterrupt\u001b[0m: Interrupted by user"]}],"source":["play(human, human)"]},{"cell_type":"markdown","metadata":{"id":"V2U3psA0-cW-"},"source":["## Tree\n","\n","Our tree will be represented by a dictionary where keys are boards and values are tree nodes. It's important to check if a tree node isn't in the tree already before creating a new one!\n","\n","### Exercise\n","\n","Answer the questions.\n","\n","- Is it tree search or graph search?\n","  > Answer: it is graph search - nodes in the tree are path indifferent\n","- How it changes the planner performance?\n","  > Answer: for graph, statistics can be reused enabling faster convergence"]},{"cell_type":"code","execution_count":15,"metadata":{"id":"L8dHZcUIPyuZ","executionInfo":{"status":"ok","timestamp":1683212589000,"user_tz":-120,"elapsed":3,"user":{"displayName":"Michał Janik","userId":"10483929333441523386"}}},"outputs":[],"source":["tree = dict() # Keys are boards and values are tree nodes\n","\n","@dataclass\n","class TreeNode():\n","    \"\"\"Class for keeping track of a tree node statistics.\"\"\"\n","    board: Connect4Board\n","    children: tuple = None # None means unexplored (non-expanded)\n","    total_reward: float = 0.0\n","    visit_count: int = 0\n","\n","def get_node(tree, board):\n","    \"\"\"Either gets a node from `tree` or adds and returns a new node.\"\"\"\n","    if board in tree:\n","        return tree[board]\n","    \n","    node = TreeNode(board)\n","    tree[board] = node\n","    return node"]},{"cell_type":"markdown","metadata":{"id":"ldadhDpK9Qej"},"source":["## 1. Selection\n","\n","Starting from the root `node`, select successive child nodes until a leaf node is reached. The root being the current game state and the leaf being either a terminal state or a node from which no simulation (playout/rollout) has yet been initiated -- we call such node \"unexplored\". In order to expand the game tree towards the most promising moves, we select children according to the UCT (Upper Confidence Bound applied to trees) selection rule. We choose children that that maximize:\n","\n","$$\n","\\max\\big( \\underbrace{\\frac{w_i}{n_i}}_{\\text{exploitation}} + c \\cdot \\underbrace{\\sqrt{\\frac{\\ln N_i}{n_i}}}_{\\text{exploration}} \\big)\n","$$\n","\n","where $w_i$ is a total reward, $n_i$ is a visit count, and $N_i$ is a parent visit count of the considered child node after $i$-th MCTS iteration.\n","\n","The first component of the formula above corresponds to exploitation -- it is high for nodes with high win rate. The second component corresponds to exploration -- it is high for nodes which haven't been selected recently.\n","\n","### Exercise\n","\n","Implement the selection phase below."]},{"cell_type":"code","execution_count":117,"metadata":{"executionInfo":{"elapsed":436,"status":"ok","timestamp":1683232321987,"user":{"displayName":"Michał Janik","userId":"10483929333441523386"},"user_tz":-120},"id":"Wwk-rGq0-l2d"},"outputs":[],"source":["def select(tree, node, expl_weight):\n","    \"\"\"Returns a path to an unexplored (or terminal) descendent of `node`.\"\"\"\n","    path = []\n","    \n","    path.append(node)\n","\n","    while not (node.children is None or node.children == ()):\n","      max_score = -float('inf')\n","      best_child = None\n","\n","      for child in node.children:\n","          if child.children is None:\n","              # If child is unexplored and not terminal, visit it\n","              path.append(child)\n","              return path\n","\n","          # UCT formula\n","          if child.visit_count > 0:\n","            score = (child.total_reward / child.visit_count) + expl_weight * (\n","                np.sqrt(np.log(node.visit_count) / child.visit_count))\n","\n","            if score > max_score:\n","                max_score = score\n","                best_child = child\n","\n","\n","      if best_child is None:  # If all children are terminal states, pick a random one\n","        node = random.choice(node.children)\n","        path.append(node)\n","        return path\n","\n","      node = best_child\n","      path.append(node)\n","\n","    return path\n","\n"]},{"cell_type":"code","execution_count":118,"metadata":{"executionInfo":{"elapsed":1,"status":"ok","timestamp":1683232322521,"user":{"displayName":"Michał Janik","userId":"10483929333441523386"},"user_tz":-120},"id":"LwQ7Lp0HRCO-"},"outputs":[],"source":["# TEST find unexplored\n","\n","# Set-up\n","tree_test = dict()\n","board_test = Connect4Board(np.zeros([3, 3]), win_length=3)\n","node = get_node(tree_test, board_test)\n","node.children = (TreeNode(board_test), TreeNode(board_test), TreeNode(board_test))\n","node.children[0].children = tuple()\n","node.children[1].children = tuple()\n","\n","# Run\n","path = select(tree_test, node, 2.)\n","\n","# Test\n","assert path[0] == node\n","assert path[1] == node.children[2], [path[1] is child for child in node.children]\n","\n","# TEST pick greedy best\n","\n","# Set-up\n","tree_test = dict()\n","board_test = Connect4Board(np.zeros([3, 3]), win_length=3)\n","node = get_node(tree_test, board_test)\n","node.children = (TreeNode(board_test), TreeNode(board_test), TreeNode(board_test))\n","node.visit_count = 16\n","node.children[0].children = (TreeNode(board_test),)\n","node.children[0].total_reward = 3.\n","node.children[0].visit_count = 3\n","node.children[1].children = (TreeNode(board_test),)\n","node.children[1].total_reward = 10.\n","node.children[1].visit_count = 9.\n","node.children[2].children = (TreeNode(board_test),)\n","node.children[2].total_reward = 1.\n","node.children[2].visit_count = 5\n","\n","# Run\n","path = select(tree_test, node, 0.)\n","\n","# Test\n","assert path[0] == node\n","assert path[1] == node.children[1]\n","assert path[2] == node.children[1].children[0]\n","\n","# TEST pick UCB best\n","\n","# Set-up\n","# Same as above...\n","\n","# Run\n","path = select(tree_test, node, 2.)\n","\n","# Test\n","assert path[0] == node\n","assert path[1] == node.children[0]\n","assert path[2] == node.children[0].children[0]"]},{"cell_type":"markdown","metadata":{"id":"KJnOOsIPFzKs"},"source":["## 2. Expansion\n","\n","Unless the leaf `node` ends the game (i.e. win/loss/draw) for either player, create the node's children and add them to the node. Child nodes are any valid moves from the game position defined by the leaf.\n","\n","> Hint: The terminal state shall have empty children tuple.\n","\n","> Hint 2: It's important to check if a tree node isn't in the tree already before creating a new one!\n","\n","### Exercise\n","\n","Implement the expansion phase below."]},{"cell_type":"code","execution_count":119,"metadata":{"id":"vKhdKRfnDr57","executionInfo":{"status":"ok","timestamp":1683232323035,"user_tz":-120,"elapsed":2,"user":{"displayName":"Michał Janik","userId":"10483929333441523386"}}},"outputs":[],"source":["def expand(tree, node):\n","    \"\"\"Expands `node` children.\"\"\"\n","    board = node.board\n","    if node.children is not None:\n","        assert board.is_terminal\n","        return # Already expanded, it can happen for terminal boards\n","\n","    node.children = tuple(\n","        get_node(tree, board.add_stone(move)) for move in board.valid_moves\n","    ) if not board.is_terminal else tuple()"]},{"cell_type":"code","execution_count":120,"metadata":{"id":"z3CLPwTsXMJr","executionInfo":{"status":"ok","timestamp":1683232323036,"user_tz":-120,"elapsed":2,"user":{"displayName":"Michał Janik","userId":"10483929333441523386"}}},"outputs":[],"source":["# TEST expand terminal\n","\n","# Set-up\n","tree_test = dict()\n","board_test = Connect4Board(np.zeros([3, 3]), win_length=3)\n","board_test._winner = 0 # Draw is a terminal state\n","node = get_node(tree_test, board_test)\n","\n","# Run\n","expand(tree_test, node)\n","\n","# Test\n","assert node.children == tuple()\n","\n","# TEST expand non-terminal\n","\n","# Set-up\n","tree_test = dict()\n","board_test = Connect4Board(np.zeros([3, 3]), win_length=3)\n","node = get_node(tree_test, board_test)\n","\n","# Run\n","expand(tree_test, node)\n","\n","# Test\n","assert node.children == tuple(get_node(tree_test, board_test.add_stone(column))\n","                              for column in board_test.valid_moves)"]},{"cell_type":"markdown","metadata":{"id":"pFGdKor4GK2B"},"source":["## 3. Simulation\n","\n","Complete one random simulation (playout/rollout) from the leaf `node` by choosing uniform random moves until the game is decided (i.e. either player win, loss, or draw). Return the winner (1 if player 1 wins; -1 if player -1 wins; 0 when draw).\n","\n","### Exercise\n","\n","Implement the simulation phase below."]},{"cell_type":"code","execution_count":121,"metadata":{"id":"bE9GH7nTMKBj","executionInfo":{"status":"ok","timestamp":1683232324002,"user_tz":-120,"elapsed":2,"user":{"displayName":"Michał Janik","userId":"10483929333441523386"}}},"outputs":[],"source":["def simulate(node):\n","    \"\"\"Returns a winner of a random simulation (to completion) from `node`.\"\"\"\n","    board = node.board\n","    while True:\n","      if board.is_terminal:\n","        return board.winner\n","\n","      random_move = random.choice(board.valid_moves)\n","      board = board.add_stone(random_move)"]},{"cell_type":"code","execution_count":122,"metadata":{"id":"iOkdKJvgYdzu","executionInfo":{"status":"ok","timestamp":1683232325245,"user_tz":-120,"elapsed":2,"user":{"displayName":"Michał Janik","userId":"10483929333441523386"}}},"outputs":[],"source":["# TEST simulate, winner is 0\n","\n","# Set-up\n","tree_test = dict()\n","board_test = Connect4Board(np.zeros([3, 3]), win_length=3)\n","node = get_node(tree_test, board_test)\n","random.seed(42)\n","\n","# Run\n","winner = simulate(node)\n","\n","# Test\n","assert winner == 0\n","\n","# TEST simulate, winner is 1\n","\n","# Set-up\n","tree_test = dict()\n","board_test = Connect4Board(np.zeros([3, 3]), win_length=3)\n","node = get_node(tree_test, board_test)\n","random.seed(7)\n","\n","# Run\n","winner = simulate(node)\n","\n","# Test\n","assert winner == 1\n","\n","# TEST simulate, winner is -1\n","\n","# Set-up\n","tree_test = dict()\n","board_test = Connect4Board(np.zeros([3, 3]), win_length=3)\n","node = get_node(tree_test, board_test)\n","random.seed(666)\n","\n","# Run\n","winner = simulate(node)\n","\n","# Test\n","assert winner == -1"]},{"cell_type":"markdown","metadata":{"id":"Ncpd2f4xGQIk"},"source":["## 4. Backpropagation\n","\n","Use the result of the simulation to update information in the nodes on the path from the leaf to the root. Invert the reward for each player so its children have positive values when it wins.\n","\n","### Exercise\n","\n","Implement the backpropagation phase below."]},{"cell_type":"code","execution_count":123,"metadata":{"id":"Bh8mksF6PBM9","executionInfo":{"status":"ok","timestamp":1683232328874,"user_tz":-120,"elapsed":1,"user":{"displayName":"Michał Janik","userId":"10483929333441523386"}}},"outputs":[],"source":["def backprop(path, winner):\n","    \"\"\"Back-propagates the reward throughout `path`.\"\"\"\n","    for node in reversed(path):\n","        node.visit_count += 1\n","        winner *= -1\n","        node.total_reward += winner"]},{"cell_type":"code","execution_count":124,"metadata":{"id":"9dwiYQY9a20e","executionInfo":{"status":"ok","timestamp":1683232333125,"user_tz":-120,"elapsed":2,"user":{"displayName":"Michał Janik","userId":"10483929333441523386"}}},"outputs":[],"source":["# TEST backprop, winner is 1\n","\n","# Set-up\n","board_test = Connect4Board(np.zeros([3, 3]), win_length=3)\n","path = [TreeNode(board_test), TreeNode(board_test), TreeNode(board_test)]\n","\n","# Run\n","backprop(path, 1)\n","\n","# Test\n","assert path[0].total_reward == -1.\n","assert path[0].visit_count == 1\n","assert path[1].total_reward == 1.\n","assert path[1].visit_count == 1\n","assert path[2].total_reward == -1.\n","assert path[2].visit_count == 1\n","\n","# TEST backprop, winner is 0\n","\n","# Set-up\n","board_test = Connect4Board(np.zeros([3, 3]), win_length=3)\n","path = [TreeNode(board_test), TreeNode(board_test), TreeNode(board_test)]\n","\n","# Run\n","backprop(path, 0)\n","\n","# Test\n","assert path[0].total_reward == 0.\n","assert path[0].visit_count == 1\n","assert path[1].total_reward == 0.\n","assert path[1].visit_count == 1\n","assert path[2].total_reward == 0.\n","assert path[2].visit_count == 1\n","\n","# TEST backprop, winner is -1\n","\n","# Set-up\n","board_test = Connect4Board(np.zeros([3, 3]), win_length=3)\n","path = [TreeNode(board_test), TreeNode(board_test), TreeNode(board_test)]\n","\n","# Run\n","backprop(path, -1)\n","\n","# Test\n","assert path[0].total_reward == 1.\n","assert path[0].visit_count == 1\n","assert path[1].total_reward == -1.\n","assert path[1].visit_count == 1\n","assert path[2].total_reward == 1.\n","assert path[2].visit_count == 1"]},{"cell_type":"markdown","metadata":{"id":"NQrk_68qB1II"},"source":["## MCTS\n","\n","![MCTS diagram](https://www.researchgate.net/profile/Jacek-Mandziuk/publication/319126544/figure/fig1/AS:614155115581472@1523437398677/MCTS-algorithm-overview-6.png)\n","\n","### Exercise\n","\n","- Put the four phases together.\n","- Play against the MCTS planner with different number of iterations `n_iter` and exploration weights `expl_weight`.\n","- How it behaves? Can you beat it?"]},{"cell_type":"code","execution_count":125,"metadata":{"id":"fhMWU9JLLYvN","executionInfo":{"status":"ok","timestamp":1683232335836,"user_tz":-120,"elapsed":3,"user":{"displayName":"Michał Janik","userId":"10483929333441523386"}}},"outputs":[],"source":["def mcts(tree, board, n_iter=200, expl_weight=2.):\n","    \"\"\"Returns the best move (next board) after `n_iter` MCTS iterations.\"\"\"\n","    root = get_node(tree, board)\n","    for i in range(n_iter):\n","        path = select(tree, root, expl_weight)\n","\n","        selected_node = path[-1]\n","        expand(tree, selected_node)\n","\n","        winner = simulate(selected_node)\n","        backprop(path, winner)\n","    \n","    print('DEBUG | <column>: (<value>, <count>) ' + '; '.join(\n","        [f'{move}: ({node.total_reward/node.visit_count:.2f}, {node.visit_count})'\n","         for move, node in map(lambda move: (move, tree[board.add_stone(move)]), board.valid_moves)]\n","    ))\n","\n","    return max(root.children, key=lambda node: node.visit_count).board"]},{"cell_type":"code","execution_count":137,"metadata":{"id":"gDsRIpk7AJXC","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1683235159047,"user_tz":-120,"elapsed":43228,"user":{"displayName":"Michał Janik","userId":"10483929333441523386"}},"outputId":"eba9c0d0-996f-408a-d053-89ed9de51143"},"outputs":[{"output_type":"stream","name":"stdout","text":["\n"," | Player 1: x; Player -1: o |\\\n"," |---------------------------||\n"," | 0 | 1 | 2 | 3 | 4 | 5 | 6 ||\n"," |---|---|---|---|---|---|---||\n","[[ - | - | - | - | - | - | - ]|\n"," [ - | - | - | - | - | - | - ]|\n"," [ - | - | - | - | - | - | - ]|\n"," [ - | - | - | - | - | - | - ]|\n"," [ - | - | - | - | - | - | - ]|\n"," [ - | - | - | - | - | - | - ]]\n","\n","Player 1 adds stone in a column [0-6]: 1\n","DEBUG | <column>: (<value>, <count>) 0: (0.02, 883); 1: (-1.00, 2); 2: (-1.00, 2); 3: (-1.00, 2); 4: (-1.00, 2); 5: (-0.38, 16); 6: (-0.14, 92)\n","\n"," | Player 1: x; Player -1: o |\\\n"," |---------------------------||\n"," | 0 | 1 | 2 | 3 | 4 | 5 | 6 ||\n"," |---|---|---|---|---|---|---||\n","[[ - | - | - | - | - | - | - ]|\n"," [ - | - | - | - | - | - | - ]|\n"," [ - | - | - | - | - | - | - ]|\n"," [ - | - | - | - | - | - | - ]|\n"," [ - | - | - | - | - | - | - ]|\n"," [ o | x | - | - | - | - | - ]]\n","\n","Player 1 adds stone in a column [0-6]: 1\n","DEBUG | <column>: (<value>, <count>) 0: (-0.21, 38); 1: (-0.04, 421); 2: (-1.00, 2); 3: (-1.00, 2); 4: (-0.06, 293); 5: (0.03, 231); 6: (-0.25, 24)\n","\n"," | Player 1: x; Player -1: o |\\\n"," |---------------------------||\n"," | 0 | 1 | 2 | 3 | 4 | 5 | 6 ||\n"," |---|---|---|---|---|---|---||\n","[[ - | - | - | - | - | - | - ]|\n"," [ - | - | - | - | - | - | - ]|\n"," [ - | - | - | - | - | - | - ]|\n"," [ - | o | - | - | - | - | - ]|\n"," [ - | x | - | - | - | - | - ]|\n"," [ o | x | - | - | - | - | - ]]\n","\n","Player 1 adds stone in a column [0-6]: 2\n","DEBUG | <column>: (<value>, <count>) 0: (-1.00, 2); 1: (-0.18, 44); 2: (-1.00, 2); 3: (-1.00, 2); 4: (-1.00, 2); 5: (-0.09, 152); 6: (-0.00, 845)\n","\n"," | Player 1: x; Player -1: o |\\\n"," |---------------------------||\n"," | 0 | 1 | 2 | 3 | 4 | 5 | 6 ||\n"," |---|---|---|---|---|---|---||\n","[[ - | - | - | - | - | - | - ]|\n"," [ - | - | - | - | - | - | - ]|\n"," [ - | - | - | - | - | - | - ]|\n"," [ - | o | - | - | - | - | - ]|\n"," [ - | x | - | - | - | - | - ]|\n"," [ o | x | x | - | - | - | o ]]\n","\n","Player 1 adds stone in a column [0-6]: 2\n","DEBUG | <column>: (<value>, <count>) 0: (0.14, 671); 1: (0.01, 197); 2: (-1.00, 2); 3: (-0.23, 26); 4: (0.01, 235); 5: (-0.26, 19); 6: (-0.03, 101)\n","\n"," | Player 1: x; Player -1: o |\\\n"," |---------------------------||\n"," | 0 | 1 | 2 | 3 | 4 | 5 | 6 ||\n"," |---|---|---|---|---|---|---||\n","[[ - | - | - | - | - | - | - ]|\n"," [ - | - | - | - | - | - | - ]|\n"," [ - | - | - | - | - | - | - ]|\n"," [ - | o | - | - | - | - | - ]|\n"," [ o | x | x | - | - | - | - ]|\n"," [ o | x | x | - | - | - | o ]]\n","\n","Player 1 adds stone in a column [0-6]: 2\n","DEBUG | <column>: (<value>, <count>) 0: (-1.00, 2); 1: (0.05, 262); 2: (-0.33, 9); 3: (-0.18, 22); 4: (-1.00, 2); 5: (0.09, 813); 6: (-0.22, 18)\n","\n"," | Player 1: x; Player -1: o |\\\n"," |---------------------------||\n"," | 0 | 1 | 2 | 3 | 4 | 5 | 6 ||\n"," |---|---|---|---|---|---|---||\n","[[ - | - | - | - | - | - | - ]|\n"," [ - | - | - | - | - | - | - ]|\n"," [ - | - | - | - | - | - | - ]|\n"," [ - | o | x | - | - | - | - ]|\n"," [ o | x | x | - | - | - | - ]|\n"," [ o | x | x | - | - | o | o ]]\n","\n","Player 1 adds stone in a column [0-6]: 6\n","DEBUG | <column>: (<value>, <count>) 0: (-1.00, 2); 1: (-1.00, 2); 2: (-0.50, 4); 3: (-0.25, 8); 4: (0.21, 1019); 5: (-0.12, 16); 6: (-1.00, 2)\n","\n"," | Player 1: x; Player -1: o |\\\n"," |---------------------------||\n"," | 0 | 1 | 2 | 3 | 4 | 5 | 6 ||\n"," |---|---|---|---|---|---|---||\n","[[ - | - | - | - | - | - | - ]|\n"," [ - | - | - | - | - | - | - ]|\n"," [ - | - | - | - | - | - | - ]|\n"," [ - | o | x | - | - | - | - ]|\n"," [ o | x | x | - | - | - | x ]|\n"," [ o | x | x | - | o | o | o ]]\n","\n","Player 1 adds stone in a column [0-6]: 6\n","DEBUG | <column>: (<value>, <count>) 0: (-1.00, 1); 1: (-1.00, 1); 2: (0.00, 2); 3: (1.00, 1015); 4: (0.60, 10); 5: (-1.00, 1); 6: (-1.00, 1)\n","\n"," | Player 1: x; Player -1: o |\\\n"," |---------------------------||\n"," | 0 | 1 | 2 | 3 | 4 | 5 | 6 ||\n"," |---|---|---|---|---|---|---||\n","[[ - | - | - | - | - | - | - ]|\n"," [ - | - | - | - | - | - | - ]|\n"," [ - | - | - | - | - | - | - ]|\n"," [ - | o | x | - | - | - | x ]|\n"," [ o | x | x | - | - | - | x ]|\n"," [ o | x | x | o | o | o | o ]]\n","\n","Player -1 wins!\n"]}],"source":["random.seed(time.time())\n","tree = dict() # Keys are boards and values are tree nodes\n","# play(human, partial(mcts, tree, n_iter=200, expl_weight=2.)) # n_iter=200\n","play(human, partial(mcts, tree, n_iter=1000, expl_weight=.5))"]},{"cell_type":"markdown","metadata":{"id":"SSjKk6WKK8IC"},"source":["### Extra\n","\n","Calculate and print additional statistics after each MCTS move:\n","\n","- Tree size (nodes number),\n","- Depth of the tree (longest path),\n","- Breadth of the tree (leafs number),\n","- Values of the root children,\n","- Counts of the root children,\n","- ...?"]}],"metadata":{"colab":{"provenance":[{"file_id":"1ewn94nhK_xigby-ZbDDf8QUFtCrVvd6T","timestamp":1682609985699},{"file_id":"1KKjpQpK3-9s36ZcYSE3l11kjuKlYplJ3","timestamp":1650898618709}]},"kernelspec":{"display_name":"Python 3","name":"python3"},"language_info":{"name":"python"}},"nbformat":4,"nbformat_minor":0}