How to write a chess program in python.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Plan for the talk:\n",
    "==========\n",
    "- Who I am\n",
    "- Why is chess an interesting problem?\n",
    "- Board representation\n",
    "- Board evaluation\n",
    "- Minimax tree search\n",
    "\n",
    "At the end we will have a minimal working chess engine and I will do a live demo of a whole chess game. \n",
    "\n",
    "The notebook for this talk can be found in: \n",
    "https://github.com/DavidHowlett/family_chess_tournament"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Who I am\n",
    "========\n",
    "- I have worked with python for 6 years at 2 companies. This included roles in doing manufacturing automation, data analysis, windows applications and a bit of devops.\n",
    "- I have written some production code in C++ but I am most comfortable with Python and VBA.\n",
    "- I just got back from traveling, I am avalible for hire and I can start work next week."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Basics of chess\n",
    "=========\n",
    " - Chess is a two player competitive game\n",
    " - The game is white pieces vs black pieces\n",
    " - Players take turns moving their pieces on an 8x8 board\n",
    " - A player wins when the enemy king is certain to be captured. This is called checkmate.\n",
    " \n",
    "![alt text](chess3.png \"chess board\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Why is chess an interesting problem?\n",
    "====================\n",
    "- It is naturally competitive\n",
    "- Chess engines are simple enough to build in free time\n",
    "- There is a deep literature produced by lots of smart people working on the problem\n",
    "- I got to beat my brothers in competition ☺"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Board representation\n",
    "==================\n",
    "\n",
    "Speed is really important for a strong engine but today I will use a simple representation. The easiest way in python is a list of list of squares. I personally chose white pieces to be upper case letters, black pieces to be lowercase and empty squares to be dots. Therefore every square is one of: {‘K’, ‘Q’, ‘R’, ‘B’, ‘N’, ‘P’, ‘.’, ‘k’, ‘q’, ‘b’, ‘n’, ‘p’}\n",
    "\n",
    "\n",
    "Piece | White |  Black\n",
    "------|-------|--------\n",
    "King   | K | k\n",
    "Queen  | Q | q\n",
    "Rook   | R | r\n",
    "Bishop | B | b\n",
    "Knight | N | n\n",
    "Pawn   | P | p\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[['R', 'N', 'B', 'Q', 'K', 'B', 'N', 'R'], ['P', 'P', 'P', 'P', 'P', 'P', 'P', 'P'], ['.', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', '.'], ['p', 'p', 'p', 'p', 'p', 'p', 'p', 'p'], ['r', 'n', 'b', 'q', 'k', 'b', 'n', 'r']]\n"
     ]
    }
   ],
   "source": [
    "# I like this text representation as it is more human readable than a list of lists\n",
    "initialBoardAsText = '''\n",
    "r n b q k b n r\n",
    "p p p p p p p p\n",
    ". . . . . . . .\n",
    ". . . . . . . .\n",
    ". . . . . . . .\n",
    ". . . . . . . .\n",
    "P P P P P P P P\n",
    "R N B Q K B N R'''\n",
    "\n",
    "def text_to_board(text):\n",
    "    board = [[piece for piece in line] for line in text.replace(' ', '').split()]\n",
    "    board.reverse()\n",
    "    return board\n",
    "\n",
    "initial_board = text_to_board(initialBoardAsText)\n",
    "print(initial_board)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "k\n"
     ]
    }
   ],
   "source": [
    "# indexing is also easy, this is the 7th row and the 4th column (indexed from 0)\n",
    "board = initial_board\n",
    "print(board[7][4])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "76.12382899999992 ns\n"
     ]
    }
   ],
   "source": [
    "import timeit\n",
    "# lookups are fast enough for now\n",
    "print(timeit.timeit('board[7][4]', setup=\"from __main__ import board\", number=1_000_000)*1000, 'ns')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "88.24034099999989 ns\n",
      "94.85939099999996 ns\n"
     ]
    }
   ],
   "source": [
    "# I can also check for piece colour with isupper and islower\n",
    "print(timeit.timeit('x.isupper()', setup=\"x='Q'\", number=1_000_000)*1000, 'ns')\n",
    "print(timeit.timeit('x.islower()', setup=\"x='Q'\", number=1_000_000)*1000, 'ns')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "r n b q k b n r\n",
      "p p p p p p p p\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      "P P P P P P P P\n",
      "R N B Q K B N R\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# lets define a function to print the board\n",
    "def print_board(board: [[str]]):\n",
    "    print('\\n'.join(' '.join(piece for piece in row) for row in board.__reversed__()) + '\\n')\n",
    "\n",
    "print_board(board)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Board evaluation\n",
    "================\n",
    "\n",
    "I define high scores as good for white and low scores as good for black. The traditional human piece values are:\n",
    "\n",
    "Piece | Value\n",
    "------|-------\n",
    "Pawn   | 1\n",
    "Knight | 3\n",
    "Bishop | 3\n",
    "Rook   | 5\n",
    "Queen  | 9\n",
    "King   | ∞\n",
    "\n",
    "I choose to work in centipawns as this gives enough resolution that everything I care about can be expressed as integers.\n",
    "\n",
    "Piece | White |  Black\n",
    "------|-------|--------\n",
    "Pawn   | 100 | -100\n",
    "Knight | 320 | -320\n",
    "Bishop | 330 | -330\n",
    "Rook   | 500 | -500\n",
    "Queen  | 900 | -900\n",
    "King   | 20000 | -20000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "PIECE_VALUE = {\n",
    "    '.': 0,\n",
    "    'K': 20000, 'Q': 900, 'R': 500, 'B': 330, 'N': 320, 'P': 100,\n",
    "    'k': -20000, 'q': -900, 'r': -500, 'b': -330, 'n': -320, 'p': -100\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This gives a crude aproximation to the value of a position but the positions of the pieces matter too"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "POSITION_VALUE_READABLE = {\n",
    "    'P': [\n",
    "        [ 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]],\n",
    "    'N': [\n",
    "        [-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]],\n",
    "    'B': [\n",
    "        [-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]],\n",
    "    'R': [\n",
    "        [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]],\n",
    "    'Q': [\n",
    "        [-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]],\n",
    "    \n",
    "    # The positional value of a king should ideally change with the game's phase\n",
    "    # but I am ignoring this for now\n",
    "    'K': [[0 for _ in range(8)] for _ in range(8)],\n",
    "    \n",
    "    # Empty squares always have no value\n",
    "    '.': [[0 for _ in range(8)] for _ in range(8)]\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'P': [[100, 100, 100, 100, 100, 100, 100, 100],\n",
       "  [105, 110, 110, 80, 80, 110, 110, 105],\n",
       "  [105, 95, 90, 100, 100, 90, 95, 105],\n",
       "  [100, 100, 100, 120, 120, 100, 100, 100],\n",
       "  [105, 105, 110, 125, 125, 110, 105, 105],\n",
       "  [110, 110, 120, 130, 130, 120, 110, 110],\n",
       "  [150, 150, 150, 150, 150, 150, 150, 150],\n",
       "  [100, 100, 100, 100, 100, 100, 100, 100]],\n",
       " 'p': [[-100, -100, -100, -100, -100, -100, -100, -100],\n",
       "  [-150, -150, -150, -150, -150, -150, -150, -150],\n",
       "  [-110, -110, -120, -130, -130, -120, -110, -110],\n",
       "  [-105, -105, -110, -125, -125, -110, -105, -105],\n",
       "  [-100, -100, -100, -120, -120, -100, -100, -100],\n",
       "  [-105, -95, -90, -100, -100, -90, -95, -105],\n",
       "  [-105, -110, -110, -80, -80, -110, -110, -105],\n",
       "  [-100, -100, -100, -100, -100, -100, -100, -100]],\n",
       " 'N': [[270, 280, 290, 290, 290, 290, 280, 270],\n",
       "  [280, 300, 320, 325, 325, 320, 300, 280],\n",
       "  [290, 325, 330, 335, 335, 330, 325, 290],\n",
       "  [290, 320, 335, 340, 340, 335, 320, 290],\n",
       "  [290, 325, 335, 340, 340, 335, 325, 290],\n",
       "  [290, 320, 330, 335, 335, 330, 320, 290],\n",
       "  [280, 300, 320, 320, 320, 320, 300, 280],\n",
       "  [270, 280, 290, 290, 290, 290, 280, 270]],\n",
       " 'n': [[-270, -280, -290, -290, -290, -290, -280, -270],\n",
       "  [-280, -300, -320, -320, -320, -320, -300, -280],\n",
       "  [-290, -320, -330, -335, -335, -330, -320, -290],\n",
       "  [-290, -325, -335, -340, -340, -335, -325, -290],\n",
       "  [-290, -320, -335, -340, -340, -335, -320, -290],\n",
       "  [-290, -325, -330, -335, -335, -330, -325, -290],\n",
       "  [-280, -300, -320, -325, -325, -320, -300, -280],\n",
       "  [-270, -280, -290, -290, -290, -290, -280, -270]],\n",
       " 'B': [[310, 320, 320, 320, 320, 320, 320, 310],\n",
       "  [320, 335, 330, 330, 330, 330, 335, 320],\n",
       "  [320, 340, 340, 340, 340, 340, 340, 320],\n",
       "  [320, 330, 340, 340, 340, 340, 330, 320],\n",
       "  [320, 335, 335, 340, 340, 335, 335, 320],\n",
       "  [320, 330, 335, 340, 340, 335, 330, 320],\n",
       "  [320, 330, 330, 330, 330, 330, 330, 320],\n",
       "  [310, 320, 320, 320, 320, 320, 320, 310]],\n",
       " 'b': [[-310, -320, -320, -320, -320, -320, -320, -310],\n",
       "  [-320, -330, -330, -330, -330, -330, -330, -320],\n",
       "  [-320, -330, -335, -340, -340, -335, -330, -320],\n",
       "  [-320, -335, -335, -340, -340, -335, -335, -320],\n",
       "  [-320, -330, -340, -340, -340, -340, -330, -320],\n",
       "  [-320, -340, -340, -340, -340, -340, -340, -320],\n",
       "  [-320, -335, -330, -330, -330, -330, -335, -320],\n",
       "  [-310, -320, -320, -320, -320, -320, -320, -310]],\n",
       " 'R': [[500, 500, 500, 505, 505, 500, 500, 500],\n",
       "  [495, 500, 500, 500, 500, 500, 500, 495],\n",
       "  [495, 500, 500, 500, 500, 500, 500, 495],\n",
       "  [495, 500, 500, 500, 500, 500, 500, 495],\n",
       "  [495, 500, 500, 500, 500, 500, 500, 495],\n",
       "  [495, 500, 500, 500, 500, 500, 500, 495],\n",
       "  [505, 510, 510, 510, 510, 510, 510, 505],\n",
       "  [500, 500, 500, 500, 500, 500, 500, 500]],\n",
       " 'r': [[-500, -500, -500, -500, -500, -500, -500, -500],\n",
       "  [-505, -510, -510, -510, -510, -510, -510, -505],\n",
       "  [-495, -500, -500, -500, -500, -500, -500, -495],\n",
       "  [-495, -500, -500, -500, -500, -500, -500, -495],\n",
       "  [-495, -500, -500, -500, -500, -500, -500, -495],\n",
       "  [-495, -500, -500, -500, -500, -500, -500, -495],\n",
       "  [-495, -500, -500, -500, -500, -500, -500, -495],\n",
       "  [-500, -500, -500, -505, -505, -500, -500, -500]],\n",
       " 'Q': [[880, 890, 890, 895, 895, 890, 890, 880],\n",
       "  [890, 900, 905, 900, 900, 900, 900, 890],\n",
       "  [890, 905, 905, 905, 905, 905, 900, 890],\n",
       "  [900, 900, 905, 905, 905, 905, 900, 895],\n",
       "  [895, 900, 905, 905, 905, 905, 900, 895],\n",
       "  [890, 900, 905, 905, 905, 905, 900, 890],\n",
       "  [890, 900, 900, 900, 900, 900, 900, 890],\n",
       "  [880, 890, 890, 895, 895, 890, 890, 880]],\n",
       " 'q': [[-880, -890, -890, -895, -895, -890, -890, -880],\n",
       "  [-890, -900, -900, -900, -900, -900, -900, -890],\n",
       "  [-890, -900, -905, -905, -905, -905, -900, -890],\n",
       "  [-895, -900, -905, -905, -905, -905, -900, -895],\n",
       "  [-895, -900, -905, -905, -905, -905, -900, -900],\n",
       "  [-890, -900, -905, -905, -905, -905, -905, -890],\n",
       "  [-890, -900, -900, -900, -900, -905, -900, -890],\n",
       "  [-880, -890, -890, -895, -895, -890, -890, -880]],\n",
       " 'K': [[20000, 20000, 20000, 20000, 20000, 20000, 20000, 20000],\n",
       "  [20000, 20000, 20000, 20000, 20000, 20000, 20000, 20000],\n",
       "  [20000, 20000, 20000, 20000, 20000, 20000, 20000, 20000],\n",
       "  [20000, 20000, 20000, 20000, 20000, 20000, 20000, 20000],\n",
       "  [20000, 20000, 20000, 20000, 20000, 20000, 20000, 20000],\n",
       "  [20000, 20000, 20000, 20000, 20000, 20000, 20000, 20000],\n",
       "  [20000, 20000, 20000, 20000, 20000, 20000, 20000, 20000],\n",
       "  [20000, 20000, 20000, 20000, 20000, 20000, 20000, 20000]],\n",
       " 'k': [[-20000, -20000, -20000, -20000, -20000, -20000, -20000, -20000],\n",
       "  [-20000, -20000, -20000, -20000, -20000, -20000, -20000, -20000],\n",
       "  [-20000, -20000, -20000, -20000, -20000, -20000, -20000, -20000],\n",
       "  [-20000, -20000, -20000, -20000, -20000, -20000, -20000, -20000],\n",
       "  [-20000, -20000, -20000, -20000, -20000, -20000, -20000, -20000],\n",
       "  [-20000, -20000, -20000, -20000, -20000, -20000, -20000, -20000],\n",
       "  [-20000, -20000, -20000, -20000, -20000, -20000, -20000, -20000],\n",
       "  [-20000, -20000, -20000, -20000, -20000, -20000, -20000, -20000]],\n",
       " '.': [[0, 0, 0, 0, 0, 0, 0, 0],\n",
       "  [0, 0, 0, 0, 0, 0, 0, 0],\n",
       "  [0, 0, 0, 0, 0, 0, 0, 0],\n",
       "  [0, 0, 0, 0, 0, 0, 0, 0],\n",
       "  [0, 0, 0, 0, 0, 0, 0, 0],\n",
       "  [0, 0, 0, 0, 0, 0, 0, 0],\n",
       "  [0, 0, 0, 0, 0, 0, 0, 0],\n",
       "  [0, 0, 0, 0, 0, 0, 0, 0]]}"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# we can save time by including piece values in the positional tables\n",
    "import copy\n",
    "position_value = {}\n",
    "for piece in POSITION_VALUE_READABLE:\n",
    "    position_value[piece] = [[\n",
    "        PIECE_VALUE[piece] +\n",
    "        POSITION_VALUE_READABLE[piece][7-y][x] for x in range(8)] for y in range(8)]\n",
    "    position_value[piece.lower()] = [[\n",
    "        PIECE_VALUE[piece.lower()] -\n",
    "        POSITION_VALUE_READABLE[piece][y][7-x] for x in range(8)] for y in range(8)]\n",
    "\n",
    "position_value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def evaluate(board: [[str]])->int:\n",
    "    return sum(position_value[board[y][x]][y][x] for x in range(8) for y in range(8))\n",
    "\n",
    "evaluate(initial_board)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "r n b q k b n r\n",
      "p p p p p p p p\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . P . . .\n",
      ". . . . . . . .\n",
      "P P P P . P P P\n",
      "R N B Q K B N R\n",
      "\n"
     ]
    }
   ],
   "source": [
    "first_move_text = '''\n",
    "r n b q k b n r\n",
    "p p p p p p p p\n",
    ". . . . . . . .\n",
    ". . . . . . . .\n",
    ". . . . P . . .\n",
    ". . . . . . . .\n",
    "P P P P . P P P\n",
    "R N B Q K B N R'''\n",
    "\n",
    "first_move = text_to_board(first_move_text)\n",
    "print_board(first_move)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "40"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "evaluate(first_move)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "r n b q k b n r\n",
      "p p p . p p p p\n",
      ". . . . . . . .\n",
      ". . . p . . . .\n",
      ". . . . P . . .\n",
      ". . . . . . . .\n",
      "P P P P . P P P\n",
      "R N B Q K B N R\n",
      "\n"
     ]
    }
   ],
   "source": [
    "import copy\n",
    "\n",
    "def make_move(board: [[str]], y1, x1, y2, x2)-> [[str]]:\n",
    "    \"\"\"Returns a board with a move from (x1, y1) to (x2, y2)\"\"\"\n",
    "    board = copy.deepcopy(board)\n",
    "    # add piece to destination\n",
    "    board[y2][x2] = board[y1][x1]\n",
    "    # remove piece from source\n",
    "    board[y1][x1] = '.'\n",
    "    return board\n",
    "\n",
    "second_move = make_move(first_move, 6, 3, 4, 3)\n",
    "print_board(second_move)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Move generation\n",
    "===============\n",
    "This is unfortunately too complex to cover in detail in this talk :-("
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "There are 31 possible third moves\n",
      "Example move:\n",
      "r n b q k b n r\n",
      "p p p . p p p p\n",
      ". . . . . . . .\n",
      ". . . p . . . .\n",
      ". . . . P . . .\n",
      "P . . . . . . .\n",
      ". P P P . P P P\n",
      "R N B Q K B N R\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# each piece can move in a diffrent direction\n",
    "\n",
    "PIECE_MOVE_DIRECTION = {\n",
    "    'K': ((1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)),\n",
    "    'k': ((1, 0), (0, 1), (-1, 0), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)),\n",
    "    'Q': ((1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)),\n",
    "    'q': ((1, 0), (0, 1), (-1, 0), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)),\n",
    "    'R': ((1, 0), (0, 1), (-1, 0), (0, -1)),\n",
    "    'r': ((1, 0), (0, 1), (-1, 0), (0, -1)),\n",
    "    'B': ((1, 1), (1, -1), (-1, 1), (-1, -1)),\n",
    "    'b': ((1, 1), (1, -1), (-1, 1), (-1, -1)),\n",
    "    'N': ((1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2)),\n",
    "    'n': ((1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2)),\n",
    "}\n",
    "\n",
    "# what are the possible boards after one move?\n",
    "\n",
    "def possible_moves(board: [[str]], _player_is_white: bool)->[[[str]]]:\n",
    "    \"\"\"This generates a list of all possible game states after one move\"\"\"\n",
    "    _moves = []\n",
    "    for x in range(8):\n",
    "        for y in range(8):\n",
    "            piece = board[y][x]\n",
    "            if piece in 'KQRBN' if _player_is_white else piece in 'kqrbn':\n",
    "                for xd, yd in PIECE_MOVE_DIRECTION[piece]:\n",
    "                    for i in range(1, 100):\n",
    "                        x2 = x+i*xd\n",
    "                        y2 = y+i*yd\n",
    "                        if not (0 <= x2 <= 7 and 0 <= y2 <= 7):\n",
    "                            # then it is a move off the board\n",
    "                            break\n",
    "                        target_piece = board[y2][x2]\n",
    "                        if target_piece == '.':\n",
    "                            # then it is moving into an empty square\n",
    "                            _moves.append(make_move(board, y, x, y2, x2))\n",
    "                        elif target_piece.islower() if _player_is_white else target_piece.isupper():\n",
    "                            # then it is taking an opponent's piece\n",
    "                            _moves.append(make_move(board, y, x, y2, x2))\n",
    "                            break\n",
    "                        else:\n",
    "                            # then it is taking it's own piece\n",
    "                            break\n",
    "                        if piece in 'KkNn':\n",
    "                            # then it can't move more then one square\n",
    "                            break\n",
    "\n",
    "            # pawns are weird\n",
    "            if piece == 'P' if _player_is_white else piece == 'p':\n",
    "                y2 = y+1 if _player_is_white else y-1\n",
    "                # check if a take is possible\n",
    "                for x2 in (x - 1, x + 1):\n",
    "                    if 0 <= x2 <= 7:\n",
    "                        target_piece = board[y2][x2]\n",
    "                        if target_piece.islower() if _player_is_white else target_piece.isupper():\n",
    "                            # then a take is possible\n",
    "                            after_pawn_move = make_move(board, y, x, y2, x2)\n",
    "                            if y2 == 7 if _player_is_white else y2 == 0:\n",
    "                                # then the end of the board has been reached and promotion is needed\n",
    "                                for replacement_piece in ('QRBN' if _player_is_white else 'qrbn'):\n",
    "                                    after_pawn_replacement = after_pawn_move.copy()\n",
    "                                    after_pawn_replacement[y2] = after_pawn_replacement.copy()\n",
    "                                    after_pawn_replacement[y2][x2] = replacement_piece\n",
    "                                    _moves.append(after_pawn_replacement)\n",
    "                            else:\n",
    "                                _moves.append(after_pawn_move)\n",
    "                # check if pawn can move forwards 1\n",
    "                if board[y2][x] == '.':\n",
    "                    # check if pawn can be promoted\n",
    "                    if y2 == 7 if _player_is_white else y2 == 0:\n",
    "                        after_pawn_move = make_move(board, y, x, y2, x)\n",
    "                        # add each possible promotion to _moves\n",
    "                        for replacement_piece in ('QRBN' if _player_is_white else 'qrbn'):\n",
    "                            after_pawn_replacement = after_pawn_move.copy()\n",
    "                            after_pawn_replacement[y2] = after_pawn_replacement.copy()\n",
    "                            after_pawn_replacement[y2][x] = replacement_piece\n",
    "                            _moves.append(after_pawn_replacement)\n",
    "                    else:\n",
    "                        _moves.append(make_move(board, y, x, y2, x))\n",
    "                    # check if pawn can move forwards 2\n",
    "                    if y == 1 if _player_is_white else y == 6:\n",
    "                        y2 = y + 2 if _player_is_white else y - 2\n",
    "                        if board[y2][x] == '.':\n",
    "                            _moves.append(make_move(board, y, x, y2, x))\n",
    "    return _moves\n",
    "\n",
    "possible_third_moves = possible_moves(second_move, True)\n",
    "# print(possible_third_moves)\n",
    "print('There are', len(possible_third_moves), 'possible third moves')\n",
    "print('Example move:')\n",
    "print_board(possible_third_moves[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "before\n",
      "score: 0\n",
      "r n b q k b n r\n",
      "p p p . p p p p\n",
      ". . . . . . . .\n",
      ". . . p . . . .\n",
      ". . . . P . . .\n",
      ". . . . . . . .\n",
      "P P P P . P P P\n",
      "R N B Q K B N R\n",
      "\n",
      "after\n",
      "score: 125\n",
      "r n b q k b n r\n",
      "p p p . p p p p\n",
      ". . . . . . . .\n",
      ". . . P . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      "P P P P . P P P\n",
      "R N B Q K B N R\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# what is the best move if we search 1 move ahead?\n",
    "best_third_move_score = -999999\n",
    "for move in possible_third_moves:\n",
    "    move_score = evaluate(move)\n",
    "    if move_score > best_third_move_score:\n",
    "        best_third_move_score = move_score\n",
    "        best_third_move = move\n",
    "print('before')\n",
    "print('score:', evaluate(second_move))\n",
    "print_board(second_move)\n",
    "print('after')\n",
    "print('score:', evaluate(best_third_move))\n",
    "print_board(best_third_move)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Minimax tree search\n",
    "======\n",
    "To play well we need to search n moves ahead and find the best move taking into account that the white and black players will alternately try to minimise and maximise the score.\n",
    "\n",
    "![alt text](Principle_variation_16bit.PNG \"min-max tree search\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "r n b q k b n r\n",
      "p p p . p p p p\n",
      ". . . . . . . .\n",
      ". . . p . . . .\n",
      ". . . . P . . .\n",
      ". . . . . . . .\n",
      "P P P P . P P P\n",
      "R N B Q K B N R\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print_board(second_move)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "r n b q k b n r\n",
      "p p p . p p p p\n",
      ". . . . . . . .\n",
      ". . . P . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      "P P P P . P P P\n",
      "R N B Q K B N R\n",
      "\n"
     ]
    }
   ],
   "source": [
    "def search(board, depth, player_is_white):\n",
    "    # leaf of tree search\n",
    "    if depth == 0:\n",
    "        return board, evaluate(board)\n",
    "    best_score = -999999 if player_is_white else 9999999\n",
    "    for move in possible_moves(board, player_is_white):\n",
    "        _ , score = search(move, depth-1, not player_is_white)\n",
    "        if score > best_score if player_is_white else score < best_score:\n",
    "            best_score = score\n",
    "            best_move = move\n",
    "    return best_move, best_score\n",
    "\n",
    "# what is the best move if we search 1 move ahead?\n",
    "best_move, best_score = search(second_move, 1, True)\n",
    "print_board(best_move)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "r n b q k b n r\n",
      "p p p . p p p p\n",
      ". . . . . . . .\n",
      ". . . P . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      "P P P P . P P P\n",
      "R N B Q K B N R\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# what is the best move if we search 2 moves ahead?\n",
    "best_move, best_score = search(second_move, 2, True)\n",
    "print_board(best_move)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "r n b q k b n r\n",
      "p p p . p p p p\n",
      ". . . . . . . .\n",
      ". B . p . . . .\n",
      ". . . . P . . .\n",
      ". . . . . . . .\n",
      "P P P P . P P P\n",
      "R N B Q K . N R\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# what is the best move if we search 3 moves ahead?\n",
    "best_move, best_score = search(second_move, 3, True)\n",
    "print_board(best_move)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Turn: 1 score: 50\n",
      "\n",
      "r n b q k b n r\n",
      "p p p p p p p p\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . N . . . . .\n",
      "P P P P P P P P\n",
      "R . B Q K B N R\n",
      "\n",
      "Turn: 2 score: 0\n",
      "\n",
      "r . b q k b n r\n",
      "p p p p p p p p\n",
      ". . n . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . N . . . . .\n",
      "P P P P P P P P\n",
      "R . B Q K B N R\n",
      "\n",
      "Turn: 3 score: 50\n",
      "\n",
      "r . b q k b n r\n",
      "p p p p p p p p\n",
      ". . n . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . N . . N . .\n",
      "P P P P P P P P\n",
      "R . B Q K B . R\n",
      "\n",
      "Turn: 4 score: 0\n",
      "\n",
      "r . b q k b . r\n",
      "p p p p p p p p\n",
      ". . n . . n . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . N . . N . .\n",
      "P P P P P P P P\n",
      "R . B Q K B . R\n",
      "\n",
      "Turn: 5 score: 40\n",
      "\n",
      "r . b q k b . r\n",
      "p p p p p p p p\n",
      ". . n . . n . .\n",
      ". . . . . . . .\n",
      ". . . P . . . .\n",
      ". . N . . N . .\n",
      "P P P . P P P P\n",
      "R . B Q K B . R\n",
      "\n",
      "Turn: 6 score: -90\n",
      "\n",
      "r . b q k b . r\n",
      "p p p p p p p p\n",
      ". . . . . n . .\n",
      ". . . . . . . .\n",
      ". . . n . . . .\n",
      ". . N . . N . .\n",
      "P P P . P P P P\n",
      "R . B Q K B . R\n",
      "\n",
      "Turn: 7 score: 260\n",
      "\n",
      "r . b q k b . r\n",
      "p p p p p p p p\n",
      ". . . . . n . .\n",
      ". . . . . . . .\n",
      ". . . Q . . . .\n",
      ". . N . . N . .\n",
      "P P P . P P P P\n",
      "R . B . K B . R\n",
      "\n",
      "Turn: 8 score: 220\n",
      "\n",
      "r . b q k b . r\n",
      "p p p . p p p p\n",
      ". . . . . n . .\n",
      ". . . p . . . .\n",
      ". . . Q . . . .\n",
      ". . N . . N . .\n",
      "P P P . P P P P\n",
      "R . B . K B . R\n",
      "\n",
      "Turn: 9 score: 550\n",
      "\n",
      "r . b q k b . r\n",
      "p p p . p p p p\n",
      ". . . . . Q . .\n",
      ". . . p . . . .\n",
      ". . . . . . . .\n",
      ". . N . . N . .\n",
      "P P P . P P P P\n",
      "R . B . K B . R\n",
      "\n",
      "Turn: 10 score: -365\n",
      "\n",
      "r . b q k b . r\n",
      "p p p . . p p p\n",
      ". . . . . p . .\n",
      ". . . p . . . .\n",
      ". . . . . . . .\n",
      ". . N . . N . .\n",
      "P P P . P P P P\n",
      "R . B . K B . R\n",
      "\n",
      "Turn: 11 score: -235\n",
      "\n",
      "r . b q k b . r\n",
      "p p p . . p p p\n",
      ". . . . . p . .\n",
      ". . . N . . . .\n",
      ". . . . . . . .\n",
      ". . . . . N . .\n",
      "P P P . P P P P\n",
      "R . B . K B . R\n",
      "\n",
      "Turn: 12 score: -585\n",
      "\n",
      "r . b . k b . r\n",
      "p p p . . p p p\n",
      ". . . . . p . .\n",
      ". . . q . . . .\n",
      ". . . . . . . .\n",
      ". . . . . N . .\n",
      "P P P . P P P P\n",
      "R . B . K B . R\n",
      "\n",
      "Turn: 13 score: -545\n",
      "\n",
      "r . b . k b . r\n",
      "p p p . . p p p\n",
      ". . . . . p . .\n",
      ". . . q . . . .\n",
      ". . . . P . . .\n",
      ". . . . . N . .\n",
      "P P P . . P P P\n",
      "R . B . K B . R\n",
      "\n",
      "Turn: 14 score: -665\n",
      "\n",
      "r . b . k b . r\n",
      "p p p . . p p p\n",
      ". . . . . p . .\n",
      ". . . . . . . .\n",
      ". . . . q . . .\n",
      ". . . . . N . .\n",
      "P P P . . P P P\n",
      "R . B . K B . R\n",
      "\n",
      "Turn: 15 score: -645\n",
      "\n",
      "r . b . k b . r\n",
      "p p p . . p p p\n",
      ". . . . . p . .\n",
      ". . . . . . . .\n",
      ". . . . q . . .\n",
      ". . . . B N . .\n",
      "P P P . . P P P\n",
      "R . . . K B . R\n",
      "\n",
      "Turn: 16 score: -985\n",
      "\n",
      "r . b . k b . r\n",
      "p p p . . p p p\n",
      ". . . . . p . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . q N . .\n",
      "P P P . . P P P\n",
      "R . . . K B . R\n",
      "\n",
      "Turn: 17 score: -90\n",
      "\n",
      "r . b . k b . r\n",
      "p p p . . p p p\n",
      ". . . . . p . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . P N . .\n",
      "P P P . . . P P\n",
      "R . . . K B . R\n",
      "\n",
      "Turn: 18 score: -110\n",
      "\n",
      "r . . . k b . r\n",
      "p p p . . p p p\n",
      ". . . . b p . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . P N . .\n",
      "P P P . . . P P\n",
      "R . . . K B . R\n",
      "\n",
      "Turn: 19 score: -90\n",
      "\n",
      "r . . . k b . r\n",
      "p p p . . p p p\n",
      ". . . . b p . .\n",
      ". . . . . . . .\n",
      ". . . . P . . .\n",
      ". . . . . N . .\n",
      "P P P . . . P P\n",
      "R . . . K B . R\n",
      "\n",
      "Turn: 20 score: -175\n",
      "\n",
      "r . . . k b . r\n",
      "p p p . . p p p\n",
      ". . . . . p . .\n",
      ". . . . . . . .\n",
      ". . . . P . . .\n",
      ". . . . . N . .\n",
      "b P P . . . P P\n",
      "R . . . K B . R\n",
      "\n",
      "Turn: 21 score: 140\n",
      "\n",
      "r . . . k b . r\n",
      "p p p . . p p p\n",
      ". . . . . p . .\n",
      ". . . . . . . .\n",
      ". . . . P . . .\n",
      ". . . . . N . .\n",
      "R P P . . . P P\n",
      ". . . . K B . R\n",
      "\n",
      "Turn: 22 score: 120\n",
      "\n",
      "r . . . k . . r\n",
      "p p p . . p p p\n",
      ". . . b . p . .\n",
      ". . . . . . . .\n",
      ". . . . P . . .\n",
      ". . . . . N . .\n",
      "R P P . . . P P\n",
      ". . . . K B . R\n",
      "\n",
      "Turn: 23 score: 235\n",
      "\n",
      "r . . . k . . r\n",
      "R p p . . p p p\n",
      ". . . b . p . .\n",
      ". . . . . . . .\n",
      ". . . . P . . .\n",
      ". . . . . N . .\n",
      ". P P . . . P P\n",
      ". . . . K B . R\n",
      "\n",
      "Turn: 24 score: -265\n",
      "\n",
      ". . . . k . . r\n",
      "r p p . . p p p\n",
      ". . . b . p . .\n",
      ". . . . . . . .\n",
      ". . . . P . . .\n",
      ". . . . . N . .\n",
      ". P P . . . P P\n",
      ". . . . K B . R\n",
      "\n",
      "Turn: 25 score: -245\n",
      "\n",
      ". . . . k . . r\n",
      "r p p . . p p p\n",
      ". . . b . p . .\n",
      ". . . . . . . .\n",
      ". . . . P . . .\n",
      ". . . B . N . .\n",
      ". P P . . . P P\n",
      ". . . . K . . R\n",
      "\n",
      "Turn: 26 score: -330\n",
      "\n",
      ". . . . k . . r\n",
      "r p p . . p p p\n",
      ". . . . . p . .\n",
      ". . . . . . . .\n",
      ". . . . P . . .\n",
      ". . . B . N . .\n",
      ". P P . . . P b\n",
      ". . . . K . . R\n",
      "\n",
      "Turn: 27 score: -15\n",
      "\n",
      ". . . . k . . r\n",
      "r p p . . p p p\n",
      ". . . . . p . .\n",
      ". . . . . . . .\n",
      ". . . . P . . .\n",
      ". . . B . N . .\n",
      ". P P . . . P R\n",
      ". . . . K . . .\n",
      "\n",
      "Turn: 28 score: -25\n",
      "\n",
      ". . . . k . . r\n",
      ". p p . . p p p\n",
      ". . . . . p . .\n",
      ". . . . . . . .\n",
      ". . . . P . . .\n",
      ". . . B . N . .\n",
      "r P P . . . P R\n",
      ". . . . K . . .\n",
      "\n",
      "Turn: 29 score: 90\n",
      "\n",
      ". . . . k . . r\n",
      ". p p . . p p R\n",
      ". . . . . p . .\n",
      ". . . . . . . .\n",
      ". . . . P . . .\n",
      ". . . B . N . .\n",
      "r P P . . . P .\n",
      ". . . . K . . .\n",
      "\n",
      "Turn: 30 score: -410\n",
      "\n",
      ". . . . k . . .\n",
      ". p p . . p p r\n",
      ". . . . . p . .\n",
      ". . . . . . . .\n",
      ". . . . P . . .\n",
      ". . . B . N . .\n",
      "r P P . . . P .\n",
      ". . . . K . . .\n",
      "\n",
      "Turn: 31 score: -400\n",
      "\n",
      ". . . . k . . .\n",
      ". p p . . p p r\n",
      ". . . . . p . .\n",
      ". . . . . . . .\n",
      ". . . N P . . .\n",
      ". . . B . . . .\n",
      "r P P . . . P .\n",
      ". . . . K . . .\n",
      "\n",
      "Turn: 32 score: -515\n",
      "\n",
      ". . . . k . . .\n",
      ". p p . . p p r\n",
      ". . . . . p . .\n",
      ". . . . . . . .\n",
      ". . . N P . . .\n",
      ". . . B . . . .\n",
      ". r P . . . P .\n",
      ". . . . K . . .\n",
      "\n",
      "Turn: 33 score: -510\n",
      "\n",
      ". . . . k . . .\n",
      ". p p . . p p r\n",
      ". . . . . p . .\n",
      ". . . . P . . .\n",
      ". . . N . . . .\n",
      ". . . B . . . .\n",
      ". r P . . . P .\n",
      ". . . . K . . .\n",
      "\n",
      "Turn: 34 score: -665\n",
      "\n",
      ". . . . k . . .\n",
      ". p p . . p p r\n",
      ". . . . . . . .\n",
      ". . . . p . . .\n",
      ". . . N . . . .\n",
      ". . . B . . . .\n",
      ". r P . . . P .\n",
      ". . . . K . . .\n",
      "\n",
      "Turn: 35 score: -190\n",
      "\n",
      ". . . . k . . .\n",
      ". p p . . p p B\n",
      ". . . . . . . .\n",
      ". . . . p . . .\n",
      ". . . N . . . .\n",
      ". . . . . . . .\n",
      ". r P . . . P .\n",
      ". . . . K . . .\n",
      "\n",
      "Turn: 36 score: -535\n",
      "\n",
      ". . . . k . . .\n",
      ". p p . . p p B\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . p . . . .\n",
      ". . . . . . . .\n",
      ". r P . . . P .\n",
      ". . . . K . . .\n",
      "\n",
      "Turn: 37 score: -515\n",
      "\n",
      ". . . . k . . .\n",
      ". p p . . p p .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . p B . . .\n",
      ". . . . . . . .\n",
      ". r P . . . P .\n",
      ". . . . K . . .\n",
      "\n",
      "Turn: 38 score: -625\n",
      "\n",
      ". . . . k . . .\n",
      ". p p . . p p .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . p B . . .\n",
      ". . . . . . . .\n",
      ". . r . . . P .\n",
      ". . . . K . . .\n",
      "\n",
      "Turn: 39 score: -125\n",
      "\n",
      ". . . . k . . .\n",
      ". p p . . p p .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . p . . . .\n",
      ". . . . . . . .\n",
      ". . B . . . P .\n",
      ". . . . K . . .\n",
      "\n",
      "Turn: 40 score: -130\n",
      "\n",
      ". . . . k . . .\n",
      ". p p . . p p .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . p . . . .\n",
      ". . B . . . P .\n",
      ". . . . K . . .\n",
      "\n",
      "Turn: 41 score: 10\n",
      "\n",
      ". . . . k . . .\n",
      ". p p . . p p .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . B . . . .\n",
      ". . . . . . P .\n",
      ". . . . K . . .\n",
      "\n",
      "Turn: 42 score: 10\n",
      "\n",
      ". . . . . k . .\n",
      ". p p . . p p .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . B . . . .\n",
      ". . . . . . P .\n",
      ". . . . K . . .\n",
      "\n",
      "Turn: 43 score: 10\n",
      "\n",
      ". . . . . k . .\n",
      ". p p . . p p .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . B . . .\n",
      ". . . . . . . .\n",
      ". . . . . . P .\n",
      ". . . . K . . .\n",
      "\n",
      "Turn: 44 score: 10\n",
      "\n",
      ". . . . . . k .\n",
      ". p p . . p p .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . B . . .\n",
      ". . . . . . . .\n",
      ". . . . . . P .\n",
      ". . . . K . . .\n",
      "\n",
      "Turn: 45 score: 110\n",
      "\n",
      ". . . . . . k .\n",
      ". B p . . p p .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . P .\n",
      ". . . . K . . .\n",
      "\n",
      "Turn: 46 score: 110\n",
      "\n",
      ". . . . . . . k\n",
      ". B p . . p p .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . P .\n",
      ". . . . K . . .\n",
      "\n",
      "Turn: 47 score: 120\n",
      "\n",
      ". . . . . . . k\n",
      ". . p . . p p .\n",
      ". . . . . . . .\n",
      ". . . B . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . P .\n",
      ". . . . K . . .\n",
      "\n",
      "Turn: 48 score: 120\n",
      "\n",
      ". . . . . . k .\n",
      ". . p . . p p .\n",
      ". . . . . . . .\n",
      ". . . B . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . P .\n",
      ". . . . K . . .\n",
      "\n",
      "Turn: 49 score: 220\n",
      "\n",
      ". . . . . . k .\n",
      ". . p . . B p .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . P .\n",
      ". . . . K . . .\n",
      "\n",
      "Turn: 50 score: -110\n",
      "\n",
      ". . . . . . . .\n",
      ". . p . . k p .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . P .\n",
      ". . . . K . . .\n",
      "\n",
      "Turn: 51 score: -110\n",
      "\n",
      ". . . . . . . .\n",
      ". . p . . k p .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . P .\n",
      ". . . . . K . .\n",
      "\n",
      "Turn: 52 score: -110\n",
      "\n",
      ". . . . . k . .\n",
      ". . p . . . p .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . P .\n",
      ". . . . . K . .\n",
      "\n",
      "Turn: 53 score: -110\n",
      "\n",
      ". . . . . k . .\n",
      ". . p . . . p .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . P .\n",
      ". . . . . . K .\n",
      "\n",
      "Turn: 54 score: -110\n",
      "\n",
      ". . . . . . k .\n",
      ". . p . . . p .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . P .\n",
      ". . . . . . K .\n",
      "\n",
      "Turn: 55 score: -110\n",
      "\n",
      ". . . . . . k .\n",
      ". . p . . . p .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . P .\n",
      ". . . . . . . K\n",
      "\n",
      "Turn: 56 score: -110\n",
      "\n",
      ". . . . . . . k\n",
      ". . p . . . p .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . P .\n",
      ". . . . . . . K\n",
      "\n",
      "Turn: 57 score: -110\n",
      "\n",
      ". . . . . . . k\n",
      ". . p . . . p .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . P K\n",
      ". . . . . . . .\n",
      "\n",
      "Turn: 58 score: -110\n",
      "\n",
      ". . . . . . k .\n",
      ". . p . . . p .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . P K\n",
      ". . . . . . . .\n",
      "\n",
      "Turn: 59 score: -110\n",
      "\n",
      ". . . . . . k .\n",
      ". . p . . . p .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . K\n",
      ". . . . . . P .\n",
      ". . . . . . . .\n",
      "\n",
      "Turn: 60 score: -110\n",
      "\n",
      ". . . . . . . k\n",
      ". . p . . . p .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . K\n",
      ". . . . . . P .\n",
      ". . . . . . . .\n",
      "\n",
      "Turn: 61 score: -110\n",
      "\n",
      ". . . . . . . k\n",
      ". . p . . . p .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . K\n",
      ". . . . . . . .\n",
      ". . . . . . P .\n",
      ". . . . . . . .\n",
      "\n",
      "Turn: 62 score: -110\n",
      "\n",
      ". . . . . . k .\n",
      ". . p . . . p .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . K\n",
      ". . . . . . . .\n",
      ". . . . . . P .\n",
      ". . . . . . . .\n",
      "\n",
      "Turn: 63 score: -110\n",
      "\n",
      ". . . . . . k .\n",
      ". . p . . . p .\n",
      ". . . . . . . .\n",
      ". . . . . . . K\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . P .\n",
      ". . . . . . . .\n",
      "\n",
      "Turn: 64 score: -110\n",
      "\n",
      ". . . . . . . k\n",
      ". . p . . . p .\n",
      ". . . . . . . .\n",
      ". . . . . . . K\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . P .\n",
      ". . . . . . . .\n",
      "\n",
      "Turn: 65 score: -110\n",
      "\n",
      ". . . . . . . k\n",
      ". . p . . . p .\n",
      ". . . . . . . K\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . P .\n",
      ". . . . . . . .\n",
      "\n",
      "Turn: 66 score: -20105\n",
      "\n",
      ". . . . . . . k\n",
      ". . p . . . . .\n",
      ". . . . . . . p\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . . .\n",
      ". . . . . . P .\n",
      ". . . . . . . .\n",
      "\n",
      "Black won\n"
     ]
    }
   ],
   "source": [
    "# lets play a game\n",
    "board = initial_board\n",
    "search_depth = 1\n",
    "for turn in range(1, 1000):\n",
    "    board, score = search(board, search_depth, turn%2)\n",
    "    print(f'Turn: {turn} score: {score}\\n')\n",
    "    print_board(board)\n",
    "    if not any(board[y][x] == 'K' for x in range(8) for y in range(8)):\n",
    "        print('Black won')\n",
    "        break\n",
    "    if not any(board[y][x] == 'k' for x in range(8) for y in range(8)):\n",
    "        print('White won')\n",
    "        break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "At this point we have the core of a chess engine.\n",
    "\n",
    "Things we missed out:\n",
    "- checkmate\n",
    "- stalemate\n",
    "- castling\n",
    "- en passant\n",
    "- 50 move rule\n",
    "\n",
    "There is also a huge amount of optimisation that is possible from here. If there is spare time at the end of this talk I can briefly mention:\n",
    "\n",
    "- iterative deepening\n",
    "- alpha-beta tree search\n",
    "- efficent board representations\n",
    "    - a list of strings 8 characters long is faster than a list of lists\n",
    "    - arrays are faster then lists\n",
    "    - 1D arrays are faster then 2D arrays\n",
    "- transposition tables \n",
    "\n",
    "I am \n",
    "https://github.com/DavidHowlett and\n",
    "david.howlett3@gmail.com\n",
    "\n",
    "Thank you for listening! \n",
    "\n",
    "Any questions?"
   ]
  }
 ],
 "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.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}