chessAI.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chess AI\n",
    "<a rel=\"license\" href=\"http://creativecommons.org/licenses/by-sa/2.0/\"><img alt=\"Creative Commons License\" style=\"border-width:0\" src=\"https://i.creativecommons.org/l/by-sa/2.0/88x31.png\" /></a><br />This work is licensed under a <a rel=\"license\" href=\"http://creativecommons.org/licenses/by-sa/2.0/\">Creative Commons Attribution-ShareAlike 2.0 Generic License</a>.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I admit it. I've also seen Netflix's fascinating hit show: The Queen's Gambit and now I've been playing on `chess.com` almost every day. With my computer science background I was curious on how can we create a Chess AI, that is, an Artificial Intelligence algorithm that plays the game against a human player. In this article we will see how to create such an algorithm from scratch.\n",
    "\n",
    "<p>\n",
    "    <img src=\"https://www.cheatsheet.com/wp-content/uploads/2020/10/The-Queens-Gambit.jpg?x96556\" />\n",
    "    </p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.- Chess"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I suppose you already know chess is a very popular two-player strategy game that originated sometime before the 7th century which is played on a chessboard, a checkered board with 64 squares arranged in an 8×8 grid.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you are not a chess expert, you probably didn't know that chessboard squares and pieces are given names. The chessboard is split into rows named *ranks* (1,2, ..., 8) and columns named *files* (A,B,...,H) so each one of the 64 squares gets a unique name. Pieces are also given a short one letter name so it is easier to name them."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p float=\"middle\">\n",
    "<img src=\"chess_imgs/board_n_pieces.png\" width='510'/>\n",
    "</p>  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Just like musicians are able to listen the music inside their head from the notes in a music sheet, chess experts are able to play games just by reading symbols:"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "1. e4 e5 2. Nf3 Nc6 3. Bb5 a6 4. Ba4 Nf6 5. O-O Be7 \n",
    "6. Re1 b5 7. Bb3 d6 8. c3 O-O 9. h3 Nb8 10. d4 Nbd7\n",
    "11. c4 c6 12. cxb5 axb5 13. Nc3 Bb7 14. Bg5 b4 15. Nb1 h6 \n",
    "16. Bh4 c5 17. dxe5Nxe4 18. Bxe7 Qxe7 19. exd6 Qf6 20. Nbd2 Nxd6 \n",
    "21. Nc4 Nxc4 22. Bxc4 Nb6 23. Ne5 Rae8 24. Bxf7+ Rxf7 25. Nxf7 Rxe1+ \n",
    "26. Qxe1 Kxf7 27. Qe3 Qg5 28. Qxg5 hxg5 29. b3 Ke6 30. a3 Kd6 \n",
    "31. axb4 cxb4 32. Ra5 Nd5 33. f3 Bc8 34. Kf2 Bf5 35. Ra7 g6 \n",
    "36. Ra6+ Kc5 37. Ke1 Nf4 38. g3 Nxh3 39. Kd2 Kb5 40. Rd6 Kc5 \n",
    "41. Ra6 Nf2 42. g4 Bd3 43. Re6 1/2-1/2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This may look very complicated, but is just a set of text-like representation of the moves in the game. This notation called Standard Algebraic Notation (SAN), represents a move by the piece's uppercase letter, plus the coordinate of the destination square. However there is an exception to the rule, for pawn moves, the piece letter is omitted and only the destination square is given. \n",
    "\n",
    "There are some other special symbols like `x`which are placed before the destination square in case of a capture, `+`indicating check, `#` indicating checkmate and `O-O-O` or `O-O` representing special moves like castling.\n",
    "\n",
    "Let's see what the first four moves of the previous example would look like:\n",
    "\n",
    "<p float=\"left\">\n",
    "<img src=\"chess_imgs/two_moves.png\" width='252'/>\n",
    "</p>   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that we have all the knowledge required, let's go! "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2.- Minimax AI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How do we create an AI? The very first thing we need to think about is what we want to achieve and then we can go on and think how we can do so. Intuitively we want to win the game, but how can we express that? Well, we know for sure that some pieces are more powerful than others, that checkmating the king is what makes you win the game, but how do you express strategy?, what if sacrificing a piece can actually make us win the game? Well, this is very complicated...\n",
    "\n",
    "But for a moment let's suppose we can give to every player a score that sums up the number of pieces in the board and the position in the board (for instance, having a rook blocked is worse than having it attacking a piece, and having a pawn is better than not having one).\n",
    "\n",
    "Let's now simplify what means to win by saying that what we want to achieve is to have, in the near future, a better score than the one of our opponent. Note that by not forcing it to maximise the score at each move, we are allowing sacrifices to be made and leaving room for strategy. \n",
    "\n",
    "What we know is that computers are very good at performing computations, what if we played out all the possible moves with their help and then choose the one which guarantees us the best score in the near future?\n",
    "\n",
    "This intuitive idea is encoded by the Minimax algorithm. Each board state is represented by a node with the color of who's turn it is to move. Then from each move, we build out a tree of all the possible moves that can be done from that move on. \n",
    "\n",
    "Since both players get a score, let's supose that the white player has a positive (+) score and the black player has a negative score (-) so we can easily compare who has an advantage in the game. If at a state we have a negative value, it means black has an edge, while if the value is positive, white has an edge.\n",
    "\n",
    "<p float=\"left\">\n",
    "<img src=\"chess_imgs/minimax.png\" width='600'/>\n",
    "</p>   \n",
    "\n",
    "The minimax is an algorithm that simply explores states $n$ moves ahead and selects the action that is guaranteed to give an edge to the player assuming that the other opponent plays optimally. The algorithm is called this way because at each move the black player will aim to minimse the score, while the white player will aim to maximise it, hence minimax.\n",
    "\n",
    "We just evaluate the states $n$ moves ahead and then assign to each parent node the min/max value according to who is to play.\n",
    "\n",
    "<p float=\"left\">\n",
    "<img src=\"chess_imgs/minimax_example.png\" width='820'/>  \n",
    "</p>   \n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here we can see the tree that would be built with a game that for each state has only two valid moves (since each node has only two children). Chess is much more complicated, it is approximated that the average *branching factor*, that is the average number of possible moves at each state is somewhere about $b=35$. This example shows only tree of depth $d=3$ meaning that the algorithm is looking only at the possible outcomes in the next three moves.\n",
    "\n",
    "It is easy to see that the number of states we need to consider grows exponentially with the number of moves to consider, that is, we need to analyse approximately:\n",
    "$$ n = b^d \\text{ states }$$\n",
    "\n",
    "What is amazing is that it is estimated that chess Grandmasters can think approximately 14-20 moves ahead!\n",
    "That would be equivalent of considering 4,139,545,122,369,384,765,625 possible states! \n",
    "\n",
    "However we can build a pretty good chess AI looking only 6 moves ahead, which would consider approximately 1.83 billion states. Such an algorithm is able to achieve approximately an Elo rating of 1966 [\\[1\\]](http://web.ist.utl.pt/diogo.ferreira/papers/ferreira13impact.pdf). But only on Chess.com there would be around 150 people who could beat the algorithm (moreover it is estimated that Beth Harmon reached 2200 ELO). Yikes!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ok, but how do we assign a score to a board state? For now we will use some heuristics, piece advantage and board position. We will not look to other heuristics such as pawn structures or stategy, we assume looking into future positions will sove the rest.\n",
    "\n",
    "Here we can see some examples:\n",
    "<p float=\"left\">\n",
    "<img src=\"chess_imgs/piece_values.png\" width='600'/>\n",
    "</p>\n",
    "\n",
    "Essentially scores are taken according to the strength of a piece, for instance a rook is slightly better than a bishop since a bishop cannot reach squares which are not of its starting color therefore making half the board inaccessible. The position values are instead based on how many squares can the piece can attack (the more the better) and on the positional advantage (control of the center)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's see how this looks concretely in code:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.1 Python code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import chess\n",
    "import chess.svg\n",
    "import numpy as np\n",
    "from numba import njit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Static evaluation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def evaluate_board(board):\n",
    "    \"\"\"Assigns a score to the board according to several metrics:\n",
    "        - the value of the piece\n",
    "        - the position of the piece\n",
    "    \n",
    "    Parameters\n",
    "    ----------\n",
    "    board : chess.Board\n",
    "    \"\"\"\n",
    "    total_score = 0\n",
    "    \n",
    "    if board.is_checkmate():\n",
    "        if board.turn == chess.WHITE:\n",
    "            return -10000\n",
    "        else: \n",
    "            return 10000\n",
    "    \n",
    "    for square in chess.SQUARES:\n",
    "        piece = board.piece_at(square)\n",
    "        if piece is not None:\n",
    "            x = chess.square_file(square) # Letter - column\n",
    "            y = chess.square_rank(square) # Number - row\n",
    "    \n",
    "            value = piece_value[piece.piece_type] + \\\n",
    "                    position_value[piece.piece_type][piece.color][y][x]\n",
    "            \n",
    "            # invert sign if black\n",
    "            if piece.color == chess.BLACK: value = - value\n",
    "                \n",
    "            total_score += value   \n",
    "            \n",
    "    return total_score\n",
    "\n",
    "\n",
    "\"\"\" ----------------------------------------------------------------------\n",
    "    Positional and Piece Values\n",
    "    ----------------------------------------------------------------------\"\"\"\n",
    "piece_value = {\n",
    "    chess.PAWN  : 10, \n",
    "    chess.BISHOP: 30, \n",
    "    chess.KNIGHT: 30, \n",
    "    chess.ROOK  : 40, \n",
    "    chess.QUEEN : 90, \n",
    "    chess.KING  : 1000\n",
    "    }\n",
    "\n",
    "black_pawn_eval = np.array([\n",
    "    [0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0],\n",
    "    [5.0,  5.0,  5.0,  5.0,  5.0,  5.0,  5.0,  5.0],\n",
    "    [1.0,  1.0,  2.0,  3.0,  3.0,  2.0,  1.0,  1.0],\n",
    "    [0.5,  0.5,  1.0,  2.5,  2.5,  1.0,  0.5,  0.5],\n",
    "    [0.0,  0.0,  0.0,  2.0,  2.0,  0.0,  0.0,  0.0],\n",
    "    [0.5, -0.5, -1.0,  0.0,  0.0, -1.0, -0.5,  0.5],\n",
    "    [0.5,  1.0, 1.0,  -2.0, -2.0,  1.0,  1.0,  0.5],\n",
    "    [0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0]\n",
    "])\n",
    "\n",
    "black_rook_eval = np.array([\n",
    "    [  0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0],\n",
    "    [  0.5,  1.0,  1.0,  1.0,  1.0,  1.0,  1.0,  0.5],\n",
    "    [ -0.5,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0, -0.5],\n",
    "    [ -0.5,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0, -0.5],\n",
    "    [ -0.5,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0, -0.5],\n",
    "    [ -0.5,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0, -0.5],\n",
    "    [ -0.5,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0, -0.5],\n",
    "    [  0.0,   0.0, 0.0,  0.5,  0.5,  0.0,  0.0,  0.0]\n",
    "])\n",
    "\n",
    "black_bishop_eval = np.array([\n",
    "    [ -2.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -2.0],\n",
    "    [ -1.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0, -1.0],\n",
    "    [ -1.0,  0.0,  0.5,  1.0,  1.0,  0.5,  0.0, -1.0],\n",
    "    [ -1.0,  0.5,  0.5,  1.0,  1.0,  0.5,  0.5, -1.0],\n",
    "    [ -1.0,  0.0,  1.0,  1.0,  1.0,  1.0,  0.0, -1.0],\n",
    "    [ -1.0,  1.0,  1.0,  1.0,  1.0,  1.0,  1.0, -1.0],\n",
    "    [ -1.0,  0.5,  0.0,  0.0,  0.0,  0.0,  0.5, -1.0],\n",
    "    [ -2.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -2.0]\n",
    "])\n",
    "\n",
    "knight_eval = np.array([\n",
    "    [-5.0, -4.0, -3.0, -3.0, -3.0, -3.0, -4.0, -5.0],\n",
    "    [-4.0, -2.0,  0.0,  0.0,  0.0,  0.0, -2.0, -4.0],\n",
    "    [-3.0,  0.0,  1.0,  1.5,  1.5,  1.0,  0.0, -3.0],\n",
    "    [-3.0,  0.5,  1.5,  2.0,  2.0,  1.5,  0.5, -3.0],\n",
    "    [-3.0,  0.0,  1.5,  2.0,  2.0,  1.5,  0.0, -3.0],\n",
    "    [-3.0,  0.5,  1.0,  1.5,  1.5,  1.0,  0.5, -3.0],\n",
    "    [-4.0, -2.0,  0.0,  0.5,  0.5,  0.0, -2.0, -4.0],\n",
    "    [-5.0, -4.0, -3.0, -3.0, -3.0, -3.0, -4.0, -5.0]\n",
    "])\n",
    "\n",
    "black_king_eval = np.array([\n",
    "    [ -3.0, -4.0, -4.0, -5.0, -5.0, -4.0, -4.0, -3.0],\n",
    "    [ -3.0, -4.0, -4.0, -5.0, -5.0, -4.0, -4.0, -3.0],\n",
    "    [ -3.0, -4.0, -4.0, -5.0, -5.0, -4.0, -4.0, -3.0],\n",
    "    [ -3.0, -4.0, -4.0, -5.0, -5.0, -4.0, -4.0, -3.0],\n",
    "    [ -2.0, -3.0, -3.0, -4.0, -4.0, -3.0, -3.0, -2.0],\n",
    "    [ -1.0, -2.0, -2.0, -2.0, -2.0, -2.0, -2.0, -1.0],\n",
    "    [  2.0,  2.0,  0.0,  0.0,  0.0,  0.0,  2.0,  2.0 ],\n",
    "    [  2.0,  3.0,  1.0,  0.0,  0.0,  1.0,  3.0,  2.0 ]\n",
    "])\n",
    "\n",
    "queen_eval = np.array([\n",
    "    [ -2.0, -1.0, -1.0, -0.5, -0.5, -1.0, -1.0, -2.0],\n",
    "    [ -1.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0, -1.0],\n",
    "    [ -1.0,  0.0,  0.5,  0.5,  0.5,  0.5,  0.0, -1.0],\n",
    "    [ -0.5,  0.0,  0.5,  0.5,  0.5,  0.5,  0.0, -0.5],\n",
    "    [  0.0,  0.0,  0.5,  0.5,  0.5,  0.5,  0.0, -0.5],\n",
    "    [ -1.0,  0.5,  0.5,  0.5,  0.5,  0.5,  0.0, -1.0],\n",
    "    [ -1.0,  0.0,  0.5,  0.0,  0.0,  0.0,  0.0, -1.0],\n",
    "    [ -2.0, -1.0, -1.0, -0.5, -0.5, -1.0, -1.0, -2.0]\n",
    "])\n",
    "\n",
    "white_pawn_eval = np.flipud(np.fliplr(black_pawn_eval))\n",
    "white_bishop_eval = np.flipud(np.fliplr(black_bishop_eval))\n",
    "white_rook_eval = np.flipud(np.fliplr(black_rook_eval))\n",
    "white_king_eval = np.flipud(np.fliplr(black_king_eval))\n",
    "\n",
    "position_value = {\n",
    "    chess.PAWN   : {chess.WHITE: white_pawn_eval, chess.BLACK: black_pawn_eval},\n",
    "    chess.BISHOP : {chess.WHITE: white_bishop_eval, chess.BLACK: black_pawn_eval},\n",
    "    chess.KNIGHT : {chess.WHITE: knight_eval, chess.BLACK: knight_eval},            # same for both\n",
    "    chess.ROOK   : {chess.WHITE: white_rook_eval, chess.BLACK: black_pawn_eval},\n",
    "    chess.QUEEN  : {chess.WHITE: queen_eval, chess.BLACK: queen_eval},              # same for both\n",
    "    chess.KING   : {chess.WHITE: white_king_eval, chess.BLACK: black_pawn_eval}\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Minimax Algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def minimax(board, depth, to_move=None):\n",
    "    \"\"\"Minimax Tree evaluation\n",
    "\n",
    "    Parameters\n",
    "    ----------\n",
    "    board : chess.Board\n",
    "        a chess board with a particular setup (pieces->squares)\n",
    "    depth : int\n",
    "        how many moves ahead we want to think\n",
    "    to_move : chess.Player, optional\n",
    "        the player whose turn it is to make a move, by default None\n",
    "    \"\"\"\n",
    "    \n",
    "    if depth == 0 or board.is_game_over():\n",
    "        # static evaluation -> end of recursion\n",
    "        return board.peek(), evaluate_board(board)\n",
    "\n",
    "    if board.turn == chess.WHITE : # maximise\n",
    "        \n",
    "        max_val = -np.infty\n",
    "        best_move = None\n",
    "\n",
    "        # we should explore the tree\n",
    "        for move in board.legal_moves:\n",
    "            # simulate the move\n",
    "            board.push(move)\n",
    "            # evaluate it\n",
    "            _, value = minimax(board, depth -1, to_move=chess.BLACK)\n",
    "            # if best move seen, update it\n",
    "            if value > max_val:\n",
    "                best_move = move\n",
    "                max_val = value\n",
    "            # take it back\n",
    "            board.pop()\n",
    "        \n",
    "        return best_move, max_val\n",
    "    \n",
    "    else : # black -> minimise\n",
    "\n",
    "        min_val = np.infty\n",
    "        best_move = None\n",
    "\n",
    "        # we should explore the tree\n",
    "        for move in board.legal_moves:\n",
    "            # simulate the move\n",
    "            board.push(move)\n",
    "            # evaluate it\n",
    "            _, value = minimax(board, depth -1, to_move=chess.WHITE)\n",
    "            # if best move seen, update it\n",
    "            if value < min_val:\n",
    "                best_move = move\n",
    "                min_val = value\n",
    "            # take it back\n",
    "            board.pop()\n",
    "\n",
    "        return best_move, min_val"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Let's see it in action!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def play_game(AIcolor=chess.WHITE, depth=3, init_fen=None):\n",
    "        \n",
    "    #start a game with the default setup\n",
    "    if init_fen is None: init_fen = 'rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1'\n",
    "    board = chess.Board(fen=init_fen)\n",
    "    chess.svg.board(board, size=250)\n",
    "    states = []\n",
    "    \n",
    "    if AIcolor == chess.BLACK: \n",
    "        print('Enter the opponent\\'s move')\n",
    "        opponent_move = input()\n",
    "        board.push(chess.Move.from_uci(str(opponent_move)))\n",
    "        states.append(board.fen())\n",
    "        \n",
    "    while not board.is_game_over():\n",
    "        # AI_move\n",
    "        best_move, val = minimax(board, depth=depth, to_move=AIcolor)\n",
    "        print(f'You should play: {best_move}')\n",
    "        board.push(best_move)\n",
    "        states.append(board.fen())\n",
    "        \n",
    "        # Opponent move\n",
    "        print('Enter the opponent\\'s move')\n",
    "        opponent_move = input()\n",
    "        board.push(chess.Move.from_uci(str(opponent_move)))\n",
    "        states.append(board.fen())\n",
    "        \n",
    "    return states"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's suppose that we want to cheat while playing chess. We will enter all our opponent's move and the AI will choose the best move to take having considered all all posible states 3 moves ahead. (Be prepared to wait for long when setting the depth more than three!)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "#states = play_game(AIcolor=chess.WHITE, depth=3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Now let's visualize the game in a GIF!**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "from PIL import Image\n",
    "from cairosvg import svg2png\n",
    "import io\n",
    "import chess.pgn\n",
    "\n",
    "def make_gif(game_states, file_name='chess_game.gif'):\n",
    "    frames = []\n",
    "    for state in game_states:\n",
    "        img = svg2png(bytestring=str(chess.svg.board(chess.Board(fen=state), size=250)._repr_svg_()))\n",
    "        frames.append(Image.open(io.BytesIO(img)))\n",
    "    frames[0].save(file_name, save_all=True, append_images=frames, duration=100, loop=0, optimize=False)\n",
    "\n",
    "def pgn_gif(file, gif_name='pgn_game'):\n",
    "    states = []\n",
    "    game = chess.pgn.read_game(open(file))\n",
    "    board = game.board()\n",
    "    \n",
    "    for move in game.mainline_moves():\n",
    "        board.push(move)\n",
    "        states.append(board.fen())\n",
    "    \n",
    "    make_gif(states, file_name=f'chess_imgs/{gif_name}.gif')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# make_gif(states, file_name='chess_game.gif')\n",
    "# you can simulate the game on lichess.com and then download the PGN and load it here \n",
    "# below to see a GIF of your game\n",
    "# pgn_gif('lichess.pgn') "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p float=\"left\">\n",
    "<img src=\"chess_imgs/pgn_game_2.gif\" width='250'/>\n",
    "</p> \n",
    "Note that this game has been statically loaded, to see the GIF of your own game, download this notebook and use the algorithm."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.- Alpha-Beta Pruning + Minimax"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Even if our algorithm works, it would be painfully slow... No one wants to wait 30 min for the AI to make a move, so we normally limit it to explore future states at a reasonable depth. Note that our algorithm is pretty weak as we only consider a depth of 3.  But we previously mentioned that grandmasters are able to play as if they saw 14-20 levels of depth! Our algorithm takes a lot of time for a few levels, how can they compute all those levels? Well, they are so experienced that they already know that most of the states will never be reached, so they can efficiently explore the future states that actually matter, not all of them. \n",
    "What if there was an optimisation that would allow us to descend deeper into the tree without necessarily taking more computation time, similar to what grandmasters do?\n",
    "Such optimisation exists and is called alpha-beta pruning. It is called this way because we use two parameters: $\\alpha$ and $\\beta$, to prune the tree, that is to cut off some branches and avoid computing useless future states."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This optimisation is based on the simple idea: \"the opponent plays optimally, no sense to compute branches that will result in a bigger advantage for me, as he will play so that my advantage is minimised\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's see the following tree. Normally we would have to explore all the states at the final depth, that is we would need to perform an evaluation of the current situation (who has an advantage) at at least 8 states.\n",
    "<p float=\"left\">\n",
    "<img src=\"chess_imgs/empty_tree.png\" width='400'/>\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Instead of building the tree by depth level like we did before, let's try to build the tree by subtrees like shown in the animation.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's repeat the process taking into account the fact that the opponent plays optimally:\n",
    "<p float=\"left\">\n",
    "<img src=\"chess_imgs/ab_animation.gif\" width='520'/>\n",
    "</p> "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's see the final state:\n",
    "\n",
    "<p float=\"left\">\n",
    "<img src=\"chess_imgs/final_state.png\" width='440'/>\n",
    "</p> \n",
    "\n",
    "It is important to remark the fact that we avoided the computation of 3/8 states because their value is irrelevant, you can try any number you want on the states and the result would never change.\n",
    "\n",
    "Let's look closely how it works. When we arrive at the third state, At this point when we explore\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "But how do we formalise such mechanism. We simply keep two extra variables: alpha and beta:\n",
    "- alpha $\\alpha$: represents the highest value encountered. Set by maximiser player (white). By default $-\\infty$.\n",
    "- beta $\\beta$: represents the lowest value encountered. Set by minimiser player (black). By default $+\\infty$.\n",
    "\n",
    "$\\beta \\leq \\alpha$ -> prune unvisited subtrees\n",
    "\n",
    "<p float=\"left\">\n",
    "<img src=\"chess_imgs/ab_full.gif\" width='600'/>\n",
    "</p> \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "from tqdm.notebook import tqdm\n",
    "\n",
    "def pruning_minimax(board, depth, alpha=None, beta=None, to_move=None):\n",
    "    \"\"\"Minimax Tree evaluation improved by not considering positions \n",
    "    that can't affect the outcome.\n",
    "\n",
    "    Parameters\n",
    "    ----------\n",
    "    board : chess.Board\n",
    "        a chess board with a particular setup (pieces->squares)\n",
    "    depth : int\n",
    "        how many moves ahead we want to think\n",
    "    alpha : int, optional\n",
    "        highest value in the subtree, by default -np.infty\n",
    "    beta : int, optional\n",
    "        lowest value in the subtree, by default np.infty\n",
    "    to_move : chess.Player, optional\n",
    "        the player whose turn it is to make a move, by default None\n",
    "    \"\"\"\n",
    "    if alpha is None : alpha = -np.infty\n",
    "    if beta is None : beta = np.infty\n",
    "\n",
    "    if depth == 0 or board.is_game_over():\n",
    "        # static eval - end of recursion\n",
    "        return board.peek(), evaluate_board(board)\n",
    "\n",
    "\n",
    "    if board.turn == chess.WHITE : # maximise\n",
    "        \n",
    "        max_val = -np.infty\n",
    "        best_move = None\n",
    "\n",
    "        # we should explore each tree branch\n",
    "        for move in board.legal_moves:\n",
    "\n",
    "            # simulate the move (explore the branch)\n",
    "            board.push(move)\n",
    "\n",
    "            # evaluate it\n",
    "            _, value = pruning_minimax(board, depth -1, alpha, beta, to_move=chess.BLACK)\n",
    "\n",
    "            # if best move seen, update it\n",
    "            if value > max_val:\n",
    "                best_move = move\n",
    "                max_val = value\n",
    "            \n",
    "            # take it back (return to parent)\n",
    "            board.pop()\n",
    "            \n",
    "            alpha = max(alpha, value)\n",
    "            # no sense checking other options as the player is not\n",
    "            # likely to choose this branch under the hypothesis\n",
    "            # he performs the best move, otherwise if he does he \n",
    "            # will end in a situation worse for him\n",
    "            if beta <= alpha: break \n",
    "        \n",
    "        return best_move, max_val\n",
    "\n",
    "\n",
    "    else : # black -> minimise\n",
    "\n",
    "        min_val = np.infty\n",
    "        best_move = None\n",
    "\n",
    "        # we should explore the tree\n",
    "        for move in board.legal_moves:\n",
    "\n",
    "            # simulate the move (explore the branch)\n",
    "            board.push(move)\n",
    "\n",
    "            # evaluate it\n",
    "            _, value = pruning_minimax(board, depth -1, alpha, beta, to_move=chess.WHITE)\n",
    "\n",
    "            # if best move seen, update it\n",
    "            if value < min_val:\n",
    "                best_move = move\n",
    "                min_val = value\n",
    "            \n",
    "            # take it back (return to parent)\n",
    "            board.pop()\n",
    "            \n",
    "            beta = min(beta, value)\n",
    "            # no sense checking other options as the player is not\n",
    "            # likely to choose this branch under the hypothesis\n",
    "            # he performs the best move, otherwise if he does he \n",
    "            # will end in a situation worse for him\n",
    "            if beta <= alpha: break\n",
    "            \n",
    "        return best_move, min_val"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Let's see it in action!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def play_game(AIcolor=chess.WHITE, depth=3, init_fen=None):\n",
    "        \n",
    "    #start a game with the default setup\n",
    "    if init_fen is None: init_fen = 'rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1'\n",
    "    board = chess.Board(fen=init_fen)\n",
    "    chess.svg.board(board, size=250)\n",
    "    states = []\n",
    "    \n",
    "    if AIcolor == chess.BLACK: \n",
    "        print('Enter the opponent\\'s move')\n",
    "        opponent_move = input()\n",
    "        board.push(chess.Move.from_uci(str(opponent_move)))\n",
    "        states.append(board.fen())\n",
    "        \n",
    "    while not board.is_game_over():\n",
    "        # AI_move\n",
    "        best_move, val = pruning_minimax(board, depth=depth, to_move=AIcolor)\n",
    "        print(f'You should play: {best_move} Approx Value: {val}')\n",
    "        board.push(best_move)\n",
    "        states.append(board.fen())\n",
    "        \n",
    "        if board.is_game_over(): break\n",
    "            \n",
    "        # Opponent move\n",
    "        print('Enter the opponent\\'s move')\n",
    "        opponent_move = input()\n",
    "        board.push(chess.Move.from_uci(str(opponent_move)))\n",
    "        states.append(board.fen())\n",
    "    \n",
    "    print(f'Result White {board.result()} Black')\n",
    "    return states"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Take a look at this game of the AI just built against Aaron BOT AI (~ELO 700) at [chess.com](https://www.chess.com/game/computer/474). Feel free to reproduce the whole game uncommenting the line below. The AI we just built won with an accuracy of 94.20% w.r.t. to a top class AI! Not bad!\n",
    "<p float=\"left\">\n",
    "<img src=\"chess_imgs/pgn_game.gif\" width='250'/>\n",
    "</p> "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "# states = play_game(AIcolor=chess.WHITE, depth=5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Did you notice the speed increase with respect to the previous version?\n",
    "In the ideal case, we can double the depth at the same computational complexity! And that is a lot! That difference is like the one between an amateur and a world master!\n",
    "However, alpha-beta pruning is highly dependent on the order in which each node is examined."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3.- Further Improvements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.1- Zobrist Hashing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What happens with the current algorithm is that we might visit the same state multiple times. For example we can perform a couple of moves where the final state is the same, we must compute the score for the same state, multiple times. An idea could be to save the score for the state and then when we encounter that state again, we just used the value computed before. The question that naturally arises is: how can we save such values? To do so, we must implement a process to for creating a unique identifier out of the board so we can then retrieve the value when encountered again. But we need to do so efficiently, meaning that this process should be fast enough to justify the fact that to load the value is better than to recompute it again.\n",
    "\n",
    "The solution to this problem is to use a transposition table, a special kind of hash table that is indexed by board position. To generate an index out of the board position we use Zobrist hashing, a hash function invented by Albert Lindsey Zobrist which uses randmly generated bitstrings for every possible combination of a piece and position. Meaning that each of the 64 squares of the board will have associated 13 bitstrings, 12 for each the pieces and one associated to the fact of being empty. \n",
    "\n",
    "<p float=\"left\">\n",
    "<img src=\"chess_imgs/zobrist.png\" width='500'/>\n",
    "</p>  \n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Although it is possible that two numbers out of the `13 x 64 = 832` are the same, the probability should be so low that it is almost impossible."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "# init hash table / dict\n",
    "transposition_table = {}\n",
    "# Pieces encoding color and piece type:\n",
    "PIECES = [chess.Piece.from_symbol('P'), chess.Piece.from_symbol('B'), \n",
    "          chess.Piece.from_symbol('N'), chess.Piece.from_symbol('R'),\n",
    "          chess.Piece.from_symbol('Q'), chess.Piece.from_symbol('K'),\n",
    "          chess.Piece.from_symbol('p'), chess.Piece.from_symbol('b'), \n",
    "          chess.Piece.from_symbol('n'), chess.Piece.from_symbol('r'),\n",
    "          chess.Piece.from_symbol('q'), chess.Piece.from_symbol('k'),\n",
    "          'EMPTY']\n",
    "\n",
    "#initialise\n",
    "for square in chess.SQUARES: transposition_table[square] = {}\n",
    "# generate a random number for every square/piece combination\n",
    "for square in chess.SQUARES:\n",
    "    for piece in PIECES:\n",
    "        transposition_table[square][piece] = random.getrandbits(64)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def zobrist_hash(board):\n",
    "    h = 0\n",
    "    \n",
    "    for square in chess.SQUARES:\n",
    "        piece = board.piece_at(square)\n",
    "        if piece is not None:\n",
    "            h ^= transposition_table[square][piece]\n",
    "        else:\n",
    "            h ^= transposition_table[square]['EMPTY']\n",
    "            \n",
    "    return h"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Zobrist hash has some really nice properties, in fact, it is possible to efficiently recompute the hash from one position to another by simply XORing IN or OUT the changes in the board. \n",
    "\n",
    "This is due to the XOR function:\n",
    "$$A\\oplus B = {\\displaystyle (A\\cdot {\\overline {B}})+({\\overline {A}}\\cdot B)\\equiv (A+B)\\cdot ({\\overline {A}}+{\\overline {B}})}$$\n",
    "\n",
    "<p float=\"left\">\n",
    "<img src=\"chess_imgs/xor.png\" width='360'/>\n",
    "</p>  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In fact, the XOR function is \"reversible\" ($ A\\oplus B \\oplus B = A $):\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "C = A\\oplus B \\quad \\Rightarrow \\quad C \\oplus B &= (C\\cdot {\\overline {B}})+({\\overline {C}}\\cdot B)\\\\\n",
    "&= ([(A\\cdot {\\overline {B}})+({\\overline {A}}\\cdot B)]\\cdot {\\overline {B}})+({\\overline {[(A\\cdot {\\overline {B}})+({\\overline {A}}\\cdot B)]}}\\cdot B)\\\\\n",
    " &= [(A\\cdot {\\overline {B}})\\cdot {\\overline {B}}+({\\overline {A}}\\cdot B)\\cdot {\\overline {B}}]+[{\\overline {(A\\cdot {\\overline {B}})}+\\overline{({\\overline {A}}\\cdot B)}}]\\cdot B\\\\\n",
    "&= A\\cdot {\\overline {B}}+[(\\overline {A}+ \\overline {\\overline {B}}) + (\\overline{\\overline {A}}+\\overline{B})]\\cdot B\\\\\n",
    "&= A\\cdot {\\overline {B}}+[\\overline {A}+ B + A+ \\overline{B}]\\cdot B\\\\\n",
    "&= A\\cdot {\\overline {B}}+[1]\\cdot B\\\\\n",
    "&= A\\cdot ({\\overline {B}} + B)\\\\\n",
    "&= A\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "Moreover the XOR operation is an operation that can be efficiently performed by the computer, meaning that with a proper implementation this operation can be performed efficiently.\n",
    "\n",
    "Disclaimer: in the example below we might not see an advantage in terms of performance when computing the hash from scratch and when recomputing the hash based on the previous hash, this is due to the not so performant nature of Python which trades-off performance for flexibility and readability."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import namedtuple\n",
    "def recompute_zobrist_hash(board, prev_hash, move):\n",
    "    \"\"\"Efficiently recomputes the hash of the new state. \n",
    "    Assumes move is yet to be pushed.\n",
    "\n",
    "    Parameters\n",
    "    ----------\n",
    "    prev_hash : [type]\n",
    "        the zobrist hash at the previous move\n",
    "    move : chess.Move\n",
    "        the move taken at the last turn which lead to the new board state\n",
    "        in case of castling this is a set of two moves\n",
    "    \"\"\"\n",
    "    \n",
    "    new_hash = prev_hash\n",
    "    Move = namedtuple('Move', ['from_square', 'to_square'])\n",
    "\n",
    "    # create pseudo moves for castling\n",
    "    if move == chess.Move.from_uci('e8a8') : # black queen-side castling 0-0-0\n",
    "        moves = [Move(chess.E8, chess.C8), Move(chess.A8, chess.D8)]\n",
    "    elif move == chess.Move.from_uci('e8h8') : # black king side castling 0-0\n",
    "        moves = [Move(chess.E8, chess.G8), Move(chess.H8, chess.F8)]\n",
    "    elif move == chess.Move.from_uci('e1a1') : # white queen side castling 0-0-0\n",
    "        moves = [Move(chess.E8, chess.G8), Move(chess.H8, chess.F8)]\n",
    "    elif move == chess.Move.from_uci('e1h1') : # white king side castling 0-0\n",
    "        moves = [Move(chess.E8, chess.G8), Move(chess.H8, chess.F8)]\n",
    "    else:\n",
    "        moves = [move]\n",
    "    # doesn't handle promotion or en-passant, but you get the idea..\n",
    "\n",
    "\n",
    "    for move in moves :\n",
    "        \n",
    "        piece = board.piece_at(move.from_square)\n",
    "\n",
    "        # XOR out piece from old position\n",
    "        new_hash ^= transposition_table[move.from_square][piece]\n",
    "\n",
    "        # XOR in empty at old position\n",
    "        new_hash ^= transposition_table[move.from_square]['EMPTY']\n",
    "\n",
    "        # XOR in piece at new position\n",
    "        new_hash ^= transposition_table[move.to_square][piece]\n",
    "\n",
    "        captured_piece = board.piece_at(move.to_square)\n",
    "        if captured_piece is not None:\n",
    "            # XOR out position of captured piece\n",
    "            new_hash ^= transposition_table[move.to_square][captured_piece]\n",
    "        else:\n",
    "            # XOR out empty at new position\n",
    "            new_hash ^= transposition_table[move.to_square]['EMPTY']\n",
    "\n",
    "        return new_hash\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "b = chess.Board()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6985403784384968762"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "prev_hash = zobrist_hash(b)\n",
    "prev_hash"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10752312489903917219"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "recompute_zobrist_hash(b, prev_hash, chess.Move.from_uci('e2e4'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10752312489903917219"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b.push(chess.Move.from_uci('e2e4'))\n",
    "zobrist_hash(b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that the hashes yield the same value whether it is recomputed from scratch or by XORing IN or OUT the changes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2- Iterative Deepening"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Iterative deepening (IDS) is an algorithm used to visit a tree. It is an alternative to the commonly used Depth-first Search (DFS) or Breath-first Search (BFS). This algorithm acts like a depth-bounded DFS with increasing depth parameter like we can observe in the animation.\n",
    "\n",
    "<p float=\"left\">\n",
    "<img src=\"chess_imgs/ids.gif\" width='600'/>\n",
    "</p> \n",
    "\n",
    "Since iterative deepening visits states multiple times, it may seem wasteful, but it turns out to be not so costly, since in a tree most of the nodes are in the bottom level, so it does not matter much if the upper levels are visited multiple times, it matters even less if we use a transposition table to save the score of the visited state.\n",
    "\n",
    "This kind of algorithm provides two main advantages:\n",
    "- we can use searches at smaller depth to improve alpha-beta heuristics (alpha–beta pruning is most efficient if it searches the best moves first).\n",
    "- we can return the best move at any time. By repeating the process, each time with one level in depth more, we are able to return the current best move at any time. This is particularly useful if we have time constraints. For example, we can descend the tree for 30 seconds, then we will return the answer, in the openings probably there are fewer moves than in the endgame, thus in the openings we might be able to descend deeper into the tree."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Conclusion!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Et Voilà! You now understand the main concepts behind IBM's Deep Blue, the computer who managed to beat Garry Kasparov in 1997. With the only differences being the fact that Deep Blue used 512 VLSI chips in parallel to execute the alpha-beta search algorithm thus mitigating the problems concerning the computational tractability, it used a kind of book for openings and endings and used uneven tree development exploring some branches deeper (for instance when a piece was captured or when there was a check). But you already know the core concepts!\n",
    "\n",
    "<p>\n",
    "    <img src=\"https://i.insider.com/55947fbf2acae7b7188b5388?width=1100&format=jpeg&auto=webp\"/>\n",
    "   </p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Today the Artificial Intelligence has advanced a lot and today, Deep Blue's technique is considered quite old. In the last decade there has been a surge of better algorithms which use Reinforcement Learning and avoid the computation of million of states. \n",
    "\n",
    "In the image below we can see the evolution of several chess AI algorithms...\n",
    "<p>\n",
    "   <img src=\"chess_imgs/chess_ai_evolution.png\"/>\n",
    "</p> \n",
    "   \n",
    "but today Chess has lost its spark mainly because computers are better than us... The attention has shifted towards the game of Go which is much more complicated. The number of legal board positions in Go has been calculated to be approximately $2.1 \\times 10^{170}$ which is greater than the number of atoms in the observable universe ($10^{80}$)! So in order to beat humans we needed new, more intelligent strategies."
   ]
  }
 ],
 "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.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}