chess_core.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chess core functions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Imports"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import chess\n",
    "import chess.polyglot\n",
    "import math\n",
    "import random\n",
    "import heapq"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Styling"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<link href='http://fonts.googleapis.com/css?family=Alegreya+Sans:100,300,400,500,700,800,900,100italic,300italic,400italic,500italic,700italic,800italic,900italic' rel='stylesheet' type='text/css'>\n",
       "<link href='http://fonts.googleapis.com/css?family=Arvo:400,700,400italic' rel='stylesheet' type='text/css'>\n",
       "<link href='http://fonts.googleapis.com/css?family=PT+Mono' rel='stylesheet' type='text/css'>\n",
       "<link href='http://fonts.googleapis.com/css?family=Shadows+Into+Light' rel='stylesheet' type='text/css'>\n",
       "<link href='http://fonts.googleapis.com/css?family=Philosopher:400,700,400italic,700italic' rel='stylesheet' type='text/css'>\n",
       "\n",
       "<style>\n",
       "\n",
       "@font-face {\n",
       "    font-family: \"Computer Modern\";\n",
       "    src: url('http://mirrors.ctan.org/fonts/cm-unicode/fonts/otf/cmunss.otf');\n",
       "}\n",
       "\n",
       ".container { width: 100% }\n",
       "\n",
       "/* Formatting for header cells */\n",
       ".text_cell_render h1 {\n",
       "    font-family: 'Philosopher', sans-serif;\n",
       "    font-weight: 400;\n",
       "    font-size: 2.2em;\n",
       "    line-height: 100%;\n",
       "    color: rgb(0, 80, 120);\n",
       "    margin-bottom: 0.1em;\n",
       "    margin-top: 0.1em;\n",
       "    display: block;\n",
       "}\t\n",
       ".text_cell_render h2 {\n",
       "    font-family: 'Philosopher', serif;\n",
       "    font-weight: 400;\n",
       "    font-size: 1.9em;\n",
       "    line-height: 100%;\n",
       "    color: rgb(200,100,0);\n",
       "    margin-bottom: 0.1em;\n",
       "    margin-top: 0.1em;\n",
       "    display: block;\n",
       "}\t\n",
       "\n",
       ".text_cell_render h3 {\n",
       "    font-family: 'Philosopher', serif;\n",
       "    margin-top:12px;\n",
       "    margin-bottom: 3px;\n",
       "    font-style: italic;\n",
       "    color: rgb(94,127,192);\n",
       "}\n",
       "\n",
       ".text_cell_render h4 {\n",
       "    font-family: 'Philosopher', serif;\n",
       "}\n",
       "\n",
       ".text_cell_render h5 {\n",
       "    font-family: 'Alegreya Sans', sans-serif;\n",
       "    font-weight: 300;\n",
       "    font-size: 16pt;\n",
       "    color: grey;\n",
       "    font-style: italic;\n",
       "    margin-bottom: .1em;\n",
       "    margin-top: 0.1em;\n",
       "    display: block;\n",
       "}\n",
       "\n",
       ".text_cell_render h6 {\n",
       "    font-family: 'PT Mono', sans-serif;\n",
       "    font-weight: 300;\n",
       "    font-size: 10pt;\n",
       "    color: grey;\n",
       "    margin-bottom: 1px;\n",
       "    margin-top: 1px;\n",
       "}\n",
       "\n",
       ".CodeMirror{\n",
       "        font-family: \"PT Mono\";\n",
       "        font-size: 100%;\n",
       "}\n",
       "\n",
       "</style>\n",
       "\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from IPython.core.display import HTML\n",
    "\n",
    "with open('style.css', 'r') as file:\n",
    "    css = file.read()\n",
    "HTML(css)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Zobrist Hash override\n",
    "This is an override to enable zobrist hash for caching. It should speed the AI up a bit but it sometimes has hash collisions which can lead to bad or invalid moves. The entire notebook should be rerun if this variable changes as all cached values will be invalid after doing so. Because the collisions happened a few times during development, we decided to let it default to `False` to prevent possible errors."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "ENABLE_ZOBRIST_HASH = False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Auxiliary functions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Piece-Square Tables\n",
    "Values are taken from: https://www.chessprogramming.org/Simplified_Evaluation_Function#Piece-Square_Tables  \n",
    "These tables represent the values for the **black pieces**.  \n",
    "For the king, two different tables are used, depending on whether the board is in the endgame or not (for further explanation, see below). <br><br>\n",
    "Why the tables have the values is explained briefly. For more details you can check the source."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pawns should be motivated to move forward. The negative values should also discourage the engine to leave central pawns unmoved."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "PAWN_VALUES = [0, 0, 0, 0, 0, 0, 0, 0,\n",
    "               50, 50, 50, 50, 50, 50, 50, 50,\n",
    "               10, 10, 20, 30, 30, 20, 10, 10,\n",
    "               5, 5, 10, 25, 25, 10, 5, 5,\n",
    "               0, 0, 0, 20, 20, 0, 0, 0,\n",
    "               5, -5, -10, 0, 0, -10, -5, 5,\n",
    "               5, 10, 10, -20, -20, 10, 10, 5,\n",
    "               0, 0, 0, 0, 0, 0, 0, 0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Knights should be positioned in the center of the board. As you can see it is very bad to place them on the edge or even in the corner because they have less possible squares to move to. Knights also move rather slowly so it is useful to have them in as central as possible."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "KNIGHT_VALUES = [-50, -40, -30, -30, -30, -30, -40, -50,\n",
    "                 -40, -20, 0, 0, 0, 0, -20, -40,\n",
    "                 -30, 0, 10, 15, 15, 10, 0, -30,\n",
    "                 -30, 5, 15, 20, 20, 15, 5, -30,\n",
    "                 -30, 0, 15, 20, 20, 15, 0, -30,\n",
    "                 -30, 5, 10, 15, 15, 10, 5, -30,\n",
    "                 -40, -20, 0, 5, 5, 0, -20, -40,\n",
    "                 -50, -40, -30, -30, -30, -30, -40, -50]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bishops should be positioned in the center of the board. There are also some positions like b3, c4, b5, d3 that are especially good so they get rather high values. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "BISHOP_VALUES = [-20, -10, -10, -10, -10, -10, -10, -20,\n",
    "                 -10, 0, 0, 0, 0, 0, 0, -10,\n",
    "                 -10, 0, 5, 10, 10, 5, 0, -10,\n",
    "                 -10, 5, 5, 10, 10, 5, 5, -10,\n",
    "                 -10, 0, 10, 10, 10, 10, 0, -10,\n",
    "                 -10, 10, 10, 10, 10, 10, 10, -10,\n",
    "                 -10, 5, 0, 0, 0, 0, 5, -10,\n",
    "                 -20, -10, -10, -10, -10, -10, -10, -20]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For rooks the difference in values is not that high because of their high mobility. Rooks are rather good on the 7th ranks and in the center (d1,e1)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "ROOK_VALUES = [0, 0, 0, 0, 0, 0, 0, 0,\n",
    "               5, 10, 10, 10, 10, 10, 10, 5,\n",
    "               -5, 0, 0, 0, 0, 0, 0, -5,\n",
    "               -5, 0, 0, 0, 0, 0, 0, -5,\n",
    "               -5, 0, 0, 0, 0, 0, 0, -5,\n",
    "               -5, 0, 0, 0, 0, 0, 0, -5,\n",
    "               -5, 0, 0, 0, 0, 0, 0, -5,\n",
    "               0, 0, 0, 5, 5, 0, 0, 0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The queen should be oriented towards the center because she can cover many squares from there."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "QUEEN_VALUES = [-20, -10, -10, -5, -5, -10, -10, -20,\n",
    "                -10, 0, 0, 0, 0, 0, 0, -10,\n",
    "                -10, 0, 5, 5, 5, 5, 0, -10,\n",
    "                -5, 0, 5, 5, 5, 5, 0, -5,\n",
    "                0, 0, 5, 5, 5, 5, 0, -5,\n",
    "                -10, 5, 5, 5, 5, 5, 0, -10,\n",
    "                -10, 0, 5, 0, 0, 0, 0, -10,\n",
    "                -20, -10, -10, -5, -5, -10, -10, -20]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the early stages of the game, the king should stay protected by other pieces. He should be discouraged to have a vulnerable position, open to many enemy pieces."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "KING_VALUES_MIDDLEGAME = [-30, -40, -40, -50, -50, -40, -40, -30,\n",
    "                          -30, -40, -40, -50, -50, -40, -40, -30,\n",
    "                          -30, -40, -40, -50, -50, -40, -40, -30,\n",
    "                          -30, -40, -40, -50, -50, -40, -40, -30,\n",
    "                          -20, -30, -30, -40, -40, -30, -30, -20,\n",
    "                          -10, -20, -20, -20, -20, -20, -20, -10,\n",
    "                          20, 20, 0, 0, 0, 0, 20, 20,\n",
    "                          20, 30, 10, 0, 0, 10, 30, 20]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the endgame, due to the absence of many pieces and threats, the king should become more offensive. The king also has more possibilities to move around in the center which is important due to his low mobility."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "KING_VALUES_ENDGAME = [-50, -40, -30, -20, -20, -30, -40, -50,\n",
    "                       -30, -20, -10, 0, 0, -10, -20, -30,\n",
    "                       -30, -10, 20, 30, 30, 20, -10, -30,\n",
    "                       -30, -10, 30, 40, 40, 30, -10, -30,\n",
    "                       -30, -10, 30, 40, 40, 30, -10, -30,\n",
    "                       -30, -10, 20, 30, 30, 20, -10, -30,\n",
    "                       -30, -30, 0, 0, 0, 0, -30, -30,\n",
    "                       -50, -30, -30, -30, -30, -30, -30, -50]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Checking for endgame\n",
    "\n",
    "The function `is_endgame` takes the current `board` and returns with help of `color_endgame` whether both players match one of the two criteria for the endgame according to the simple evaluation function. This means, the endgame begins if:\n",
    "1. Both sides have no queens or\n",
    "2. Every side which has a queen has additionally no other pieces or one minorpiece maximum\n",
    "\n",
    "(See https://www.chessprogramming.org/Simplified_Evaluation_Function#King)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_endgame(board):\n",
    "    white_endgame = color_endgame(board, chess.WHITE)\n",
    "    black_endgame = color_endgame(board, chess.BLACK)\n",
    "    return white_endgame and black_endgame\n",
    "\n",
    "\n",
    "def color_endgame(board, color):\n",
    "    return (len(board.pieces(chess.QUEEN, color)) == 0 or\n",
    "            len(board.pieces(chess.BISHOP, color)) + len(board.pieces(chess.KNIGHT, color)) < 2 and\n",
    "            len(board.pieces(chess.ROOK, color)) == 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Function for the Piece-Square Tables\n",
    "\n",
    "This function calculates the value using the `piece_square_values` (according to the piece-square tables), for `player_pieces` and `enemy_pieces` (the list of the player's and respectively the opponent's pieces) as well as the current `turn`. It returns the calculated value for the positions of the pieces. It is used inside the evaluation function to evaluate the positions of the pieces on the board. The values are taken from https://www.chessprogramming.org/Simplified_Evaluation_Function#Piece-Square_Tables as stated above."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def piece_square_tables(piece_square_values, player_pieces, enemy_pieces, turn):\n",
    "    value = 0\n",
    "    black_piece_square_values = piece_square_values\n",
    "    white_piece_square_values = piece_square_values[::-1]\n",
    "    for piece in player_pieces:\n",
    "        if turn:\n",
    "            value += white_piece_square_values[piece]\n",
    "        else:\n",
    "            value += black_piece_square_values[piece]\n",
    "    for piece in enemy_pieces:\n",
    "        if turn:\n",
    "            value -= black_piece_square_values[piece]\n",
    "        else:\n",
    "            value -= white_piece_square_values[piece]\n",
    "    return value"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Maximum value (32-bit integer), used in case of checkmate"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "WIN_VALUE = 2147483647"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Static evaluation\n",
    "\n",
    "The function `static_eval` takes the parameters `board` (the current board) and `endgame` (if the players are in the endgame) and evaluates the current state of the board. First, the function checks, if the game is over and returns the corresponding value (e.g. if it is white's turn and white won, it returns the maximum value defined above). If the game is not over, the function computes the total values for each piece type of both sides by multiplying the piece value* with the amount of pieces on the board. Lastly, the function uses the auxiliary function `piece_square_tables` to calculate the values given by the positions of the pieces.\n",
    "\n",
    "*The piece values are:\n",
    "- Pawn = 100 cp\n",
    "- Knight = 320 cp\n",
    "- Bishop = 330 cp\n",
    "- Rook = 500 cp\n",
    "- Queen = 900 cp\n",
    "\n",
    "`cp` stands for *centipawn* i.e. 0.01 pawn."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def static_eval(board, endgame):\n",
    "    # STEP ONE: Check, if the game is over\n",
    "    win_state = winning_state(board)\n",
    "    if win_state != None:\n",
    "        return win_state\n",
    "    # STEP TWO: Calculate piece values using the piece-square tables\n",
    "    # Value that will be returned eventually\n",
    "    value = 0\n",
    "    # Piece values in centipawns as explained above\n",
    "    piece_values = [100, 320, 330, 500, 900, 10000]\n",
    "    for piece_type, piece_value in enumerate(piece_values):\n",
    "        piece_type += 1\n",
    "        player_pieces = board.pieces(piece_type, board.turn)\n",
    "        enemy_pieces = board.pieces(piece_type, not board.turn)\n",
    "        value += len(player_pieces) * piece_value\n",
    "        value -= len(enemy_pieces) * piece_value\n",
    "        if piece_type == chess.PAWN:\n",
    "            value += piece_square_tables(PAWN_VALUES, player_pieces, enemy_pieces, board.turn)\n",
    "        elif piece_type == chess.KNIGHT:\n",
    "            value += piece_square_tables(KNIGHT_VALUES, player_pieces, enemy_pieces, board.turn)\n",
    "        elif piece_type == chess.BISHOP:\n",
    "            value += piece_square_tables(BISHOP_VALUES, player_pieces, enemy_pieces, board.turn)\n",
    "        elif piece_type == chess.ROOK:\n",
    "            value += piece_square_tables(ROOK_VALUES, player_pieces, enemy_pieces, board.turn)\n",
    "        elif piece_type == chess.QUEEN:\n",
    "            value += piece_square_tables(QUEEN_VALUES, player_pieces, enemy_pieces, board.turn)\n",
    "        elif piece_type == chess.KING:\n",
    "            if endgame:\n",
    "                value += piece_square_tables(KING_VALUES_ENDGAME, player_pieces, enemy_pieces, board.turn)\n",
    "            else:\n",
    "                value += piece_square_tables(KING_VALUES_MIDDLEGAME, player_pieces, enemy_pieces, board.turn)\n",
    "    return value"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Positive: current player won\n",
    "- Negative: enemy player won\n",
    "- Zero: draw\n",
    "- None: not finished"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def winning_state(board):\n",
    "    # Current player won\n",
    "    if board.result() == \"1-0\" and board.turn or board.result() == \"0-1\" and not board.turn:\n",
    "        return WIN_VALUE\n",
    "    # Enemy player won\n",
    "    elif board.result() == \"0-1\" and board.turn or board.result() == \"1-0\" and not board.turn:\n",
    "        return -WIN_VALUE\n",
    "    # Draw\n",
    "    elif (board.result() == \"1/2-1/2\" or\n",
    "          board.is_stalemate() or\n",
    "          board.is_insufficient_material() or\n",
    "          board.is_seventyfive_moves() or\n",
    "          board.is_fivefold_repetition()):\n",
    "        return 0\n",
    "    return None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Memoization\n",
    "Memoization is used to cache the results of the minimax function. This can greatly reduce calculation time which makes it possible to play with more depth. The basic concept is taken from [this](https://github.com/karlstroetmann/Artificial-Intelligence/blob/master/Python/3%20Games/Memoization.ipynb) notebook of Prof. Dr. Stroetmann. In there it is implemented like this:\n",
    "```python\n",
    "def memoize(f):\n",
    "    Cache = {}\n",
    "    def f_memoized(*args):\n",
    "        if (f, args) in Cache:\n",
    "            return Cache[(f, args)]\n",
    "        result = f(*args)\n",
    "        Cache[(f, args)] = result\n",
    "        return result\n",
    "    return f_memoized\n",
    "```\n",
    "As you can see, the function `memoize` takes a function and returns a function with the same functionality. The difference is, that all results of the returned function are being cached. If the function is called again with the same parameters, the result will be returned much faster because looking up the value from the cache dictionary is (almost) always faster than calculating it from scratch. \n",
    "\n",
    "<br> <br>\n",
    "\n",
    "We adjusted the function a bit to make it a better fit for caching our minimax function. The first thing you notice if you cache minimax with alpha beta pruning is that you get almost no cache hits and therefore no performance improvement. This is because there are many possible combinations of game states, depth, alpha and beta. All of these would have to be inside the key and all of them would have to be exactly the same. This results in very inefficient caching. Because alpha beta pruning gives us a very big performance improvement, it is also not possible to just remove that. The solution we used is to just put the state of the board and the depht in the cache key. This results in much more cache hits. If you would just do that, the AI would sometimes do moves that are bad. This is the result of not including alpha and beta. What has to be done is checking if the current (not from the cache) alpha is bigger or equal to the alpha from the cache. It is very similar for beta: the beta from the cache has to be bigger or equal than the other beta. This ensures the correctness while still getting a very noticable performance benefit. As you can see above the `minimax()` function, we included `@memoize_minimax`. This always calls minimax with caching (using `memoize_minimax`) instead of the \"regular\" minimax."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "def memoize_minimax(f):\n",
    "    global CACHE\n",
    "    global BEST_MOVE\n",
    "    global CACHE_HITS\n",
    "\n",
    "    def f_memoized(*args):\n",
    "        global CACHE\n",
    "        global BEST_MOVE\n",
    "        global CACHE_HITS\n",
    "        board, depth, alpha, beta, is_quiesce = args[0], args[1], args[2], args[3], args[4]\n",
    "        key = (board.fen(), depth, is_quiesce)\n",
    "        if key in CACHE:\n",
    "            CACHE_HITS += 1\n",
    "            c_value, c_move, c_alpha, c_beta = CACHE[key]\n",
    "            if c_alpha <= alpha and beta <= c_beta:\n",
    "                if depth == ANALYZING_DEPTH:\n",
    "                    BEST_MOVE = c_move\n",
    "                return c_value\n",
    "        result = f(*args)\n",
    "        CACHE[key] = result, BEST_MOVE, alpha, beta\n",
    "        return result\n",
    "    return f_memoized"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Minimax function\n",
    "\n",
    "In the following is the main *Minimax* algorithm implemented. To be technically precise, the used algorithm is called *Negamax* due to the fact that **both** players are maximizing while the Minimax algorithm has a maximizing (white) and a minimizing (black) player. This also means that the algorithm recursively calls itself but inverts the returned value. Apart from that, the Negamax algorithm is identical to the Minimax algorithm. Goal of the algorithm is to go recursively through the decision tree, finding the best possible move. To evaluate the moves and to decide how \"good\" they are, the function uses `static_eval` which can analyze the current board for each state.\n",
    "\n",
    "![minimax image](https://upload.wikimedia.org/wikipedia/commons/thumb/6/6f/Minimax.svg/400px-Minimax.svg.png)\n",
    "\n",
    "The image above (taken from https://upload.wikimedia.org/wikipedia/commons/thumb/6/6f/Minimax.svg/400px-Minimax.svg.png) shows a simple overview of how the Minimax algorithm works. It analyzes for each possible state—a state being a specific board—the value for each player. As the function works recursively, it analyzes each next state until the maximum depth (in the `play_vs_ai` notebook the default depth is 5) is achieved. To prevent redundant computations, the function uses the above explained `memoize_minimax` function.\n",
    "\n",
    "Additionally, the function uses **Alpha-Beta-Pruning**. This means that the function checks, using the two values `alpha` and `beta`, whether a \"branch\" can be cut off. The image below (taken from https://upload.wikimedia.org/wikipedia/commons/thumb/9/91/AB_pruning.svg/1200px-AB_pruning.svg.png) visualizes this:\n",
    "\n",
    "<img src=\"https://upload.wikimedia.org/wikipedia/commons/thumb/9/91/AB_pruning.svg/1200px-AB_pruning.svg.png\" width=\"500\">\n",
    "\n",
    "As shown, some branches can be completely ignored because the enemy player will not play a move which would result in achieving the respective state. Together with the memoization, this improvement can result in lower computation time.\n",
    "\n",
    "The input parameters for the function are as follows:\n",
    "- `board`, the current board\n",
    "- `depth`, the depth to which the board will be analyzed (decrements with each recursive call)\n",
    "- `alpha` and `beta`, needed for Alpha-Beta-Pruning\n",
    "\n",
    "The function uses two global variables, `BEST_MOVE` and `MINIMAX_CALLS`. The first variable is the move to play which will be set only if the function is at the \"top\" of the decision tree i.e. when the `depth` is equal to the `ANAlYZING_DEPTH` (which is being set in the function `minimax_input`). The variable `MINIMAX_CALLS` is only needed for debugging/analysis purposes.\n",
    "\n",
    "If the function arrived at the \"bottom\" of the decision tree i.e. the `depth` is equal to 0, it returns the value calculated by `static_eval`. If the `depth` is still greater than 0, the function uses *game move ordering*. This means that the possible moves will be ordered **before** going through them recursively. This greatly improves the chance of Alpha-Beta-Pruning being successful.\n",
    "\n",
    "Lastly, the function goes through the ordered moves and calls itself with a different board (the new board having a move from the list). It saves the maximum value together with the best move—which will only be set if the depth is at its highest value as explained above—while applying the Alpha-Beta-Pruning, performing a `break` if the maximum value is bigger than `beta`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "@memoize_minimax\n",
    "def minimax(board, depth, alpha, beta, is_quiesce):\n",
    "    global BEST_MOVE\n",
    "    global MINIMAX_CALLS\n",
    "    MINIMAX_CALLS += 1\n",
    "    # Check, if current board is in cache\n",
    "    # If the depth is zero, give the static evaluation of the current board and save it in the cache\n",
    "    if depth == 0 or not board.legal_moves:\n",
    "        value = static_eval(board, is_endgame(board))\n",
    "        if is_quiesce:\n",
    "            return value\n",
    "        return quiesce(board,alpha,beta,value)\n",
    "    max_value = alpha\n",
    "    ordered_moves = []\n",
    "    cnt = 0\n",
    "    # Order the moves roughly, using a static evaluation for every move\n",
    "    for move in board.legal_moves:\n",
    "        cnt += 1\n",
    "        board.push(move)\n",
    "        v = static_eval(board, is_endgame(board))\n",
    "        board.pop()\n",
    "        heapq.heappush(ordered_moves, (v, cnt, move))\n",
    "    # Calculate the minimax value recursively, using alpha-beta-pruning\n",
    "    for _, _, move in ordered_moves:\n",
    "        board.push(move)\n",
    "        value = -minimax(board, depth - 1, -beta, -max_value, is_quiesce)\n",
    "        board.pop()\n",
    "        if value > max_value:\n",
    "            max_value = value\n",
    "            if depth == ANALYZING_DEPTH and not is_quiesce:\n",
    "                BEST_MOVE = move\n",
    "            if max_value >= beta:\n",
    "                break\n",
    "    return max_value"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Input function for minimax\n",
    "This function is the first to call; it sets the `cache`, initialises some debug/logging parameters and checks, if the move is covered by the opening library (`get_polyglot_move`). The function takes the `board` and the desired `depth`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "BEST_MOVE = None\n",
    "CACHE = {}\n",
    "CACHE_HITS = 1\n",
    "MINIMAX_CALLS = 1\n",
    "ANALYZING_DEPTH = None\n",
    "\n",
    "\n",
    "def minimax_input(board, depth):\n",
    "    global MINIMAX_CALLS\n",
    "    MINIMAX_CALLS = 1\n",
    "    global CACHE_HITS\n",
    "    CACHE_HITS = 1\n",
    "    # DEBUG/LOGGING\n",
    "    global ANALYZING_DEPTH\n",
    "    ANALYZING_DEPTH = depth\n",
    "    value, polyglot_move = get_polyglot_move(board)\n",
    "    if polyglot_move:\n",
    "        return value, polyglot_move\n",
    "    return minimax(board, depth, -math.inf, math.inf, False), BEST_MOVE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Using the opening library\n",
    "This auxiliary function takes the current `board` and checks if the played move is in an external opening library. It then chooses a random move, proposed by the library and returns the value 0 and the `move`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "POLYGLOT_PATH = \"data/polyglot/performance.bin\"\n",
    "\n",
    "\n",
    "def get_polyglot_move(board):\n",
    "    with chess.polyglot.open_reader(POLYGLOT_PATH) as reader:\n",
    "        l = list(reader.find_all(board))\n",
    "        if l:\n",
    "            return 0, random.choice(l).move\n",
    "        return 0, None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Make it possible to disable quiescence search for some tests"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "ENABLE_QUIESCENCE_SEARCH = True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "QUIESCE_DEPTH = 2\n",
    "\n",
    "def quiesce(board,alpha,beta,value):\n",
    "    if not ENABLE_QUIESCENCE_SEARCH:\n",
    "        return value\n",
    "    pieces_after_move = get_pieces_sum(board)\n",
    "    move = board.pop()\n",
    "    pieces_before_move = get_pieces_sum(board)\n",
    "    board.push(move)\n",
    "    if(pieces_after_move != pieces_before_move):\n",
    "        value = minimax(board,QUIESCE_DEPTH,max(value,alpha),beta,True)\n",
    "    return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_pieces_sum(board):\n",
    "    value = 0\n",
    "    for piece_type in range(1,6):\n",
    "        value += len(board.pieces(piece_type,chess.WHITE))\n",
    "        value += len(board.pieces(piece_type,chess.BLACK))\n",
    "    return value"
   ]
  }
 ],
 "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.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}