Faster chess engine in python (with move ordering algorithm?)

Question

I, an amateur coder, have been trying to code a chess engine with python as part of a larger research project. I started by following this tutorial (turns out creator of said tutorial has a github of the project) for the GUI and move handling, but I am trying to code the AI/evaluator myself.

I have discovered that the engine is extremely slow in evaluating positions/finding the best move. Even after implementing minimax with alpha-beta pruning (>10x performance improvement) and a move ordering algorithm (further 2x performance improvement) that maximizes pruning.

However, it still takes about 700 seconds to run the engine to depth 5.

Here's the code:

QiEngine.py: handles the move generation, board representation with classes.

import copy

#self.board = [
#            ['bR', '  ', 'bB', 'bQ', 'bK', 'bB', 'bN', 'bR'],
#            ['bP', 'bP', 'bP', 'bP', '  ', 'bP', 'bP', 'bP'],
#            ['  ', '  ', 'bN', '  ', '  ', '  ', '  ', '  '],
#            ['  ', 'wB', '  ', '  ', 'bP', '  ', '  ', '  '],
#            ['  ', '  ', '  ', '  ', 'wP', '  ', '  ', '  '],
#            ['  ', '  ', '  ', '  ', '  ', 'wN', '  ', '  '],
#            ['wP', 'wP', 'wP', 'wP', '  ', 'wP', 'wP', 'wP'],
#            ['wR', 'wN', 'wB', 'wQ', 'wK', '  ', '  ', 'wR']
#        ]

class GameState:

    def __init__(self):
        # The board is a 8x8 matrix, each square represented by a string '{piece_color}{piece_type}'
        self.board = [
            ['bR', 'bN', 'bB', 'bQ', 'bK', 'bB', 'bN', 'bR'],
            ['bP', 'bP', 'bP', 'bP', 'bP', 'bP', 'bP', 'bP'],
            ['  ', '  ', '  ', '  ', '  ', '  ', '  ', '  '],
            ['  ', '  ', '  ', '  ', '  ', '  ', '  ', '  '],
            ['  ', '  ', '  ', '  ', '  ', '  ', '  ', '  '],
            ['  ', '  ', '  ', '  ', '  ', '  ', '  ', '  '],
            ['wP', 'wP', 'wP', 'wP', 'wP', 'wP', 'wP', 'wP'],
            ['wR', 'wN', 'wB', 'wQ', 'wK', 'wB', 'wN', 'wR']
        ]
        self.white_to_move = True
        # Will store the moves of a game
        self.move_log = []
        self.piece_moves = {
            'P': self.get_pawn_moves,
            'R': self.get_rook_moves,
            'B': self.get_bishop_moves,
            'Q': self.get_queen_moves,
            'N': self.get_knight_moves,
            'K': self.get_king_moves
        }
        self.white_king_position = (7, 4)
        self.black_king_position = (0, 4)
        self.checkmate = False
        self.stalemate = False
        self.in_check = False
        self.passant = ()  # Options where en passant is possible
        self.castling_rights = {
            'wks': True,
            'wqs': True,
            'bks': True,
            'bqs': True
        }
        self.castling_log = [{'wks': self.castling_rights['wks'], 'wqs': self.castling_rights['wqs'],
                              'bks': self.castling_rights['bks'], 'bqs': self.castling_rights['bqs']}]
        self.checks = []
        self.pins = []

    # Method to move the pieces
    def make_move(self, move):
        self.move_log.append(move)
        self.board[move.start_row][move.start_col] = '  '
        self.board[move.end_row][move.end_col] = move.moved_piece
        self.white_to_move = not self.white_to_move
        if move.moved_piece == 'wK':
            self.white_king_position = (move.end_row, move.end_col)
        if move.moved_piece == 'bK':
            self.black_king_position = (move.end_row, move.end_col)

        # Pawn Promotion
        if move.is_pawn_promotion:
            self.board[move.end_row][move.end_col] = move.moved_piece[0] + move.promotion_choice

        # En Passant
        if move.is_ep:
            self.board[move.start_row][move.end_col] = '  '  # Capturing the passing pawn

        # Update passants
        if move.moved_piece[1] == 'P' and abs(move.start_row - move.end_row) == 2:
            self.passant = ((int(move.start_row + move.end_row) / 2), move.start_col)
        else:
            self.passant = ()  # Always reset passants

        # Castling
        if move.is_castle:  # Move the rook
            if move.end_col - move.start_col == 2:
                self.board[move.end_row][move.end_col - 1] = self.board[move.end_row][move.end_col + 1]
                self.board[move.end_row][move.end_col + 1] = '  '
            else:
                self.board[move.end_row][move.end_col + 1] = self.board[move.end_row][move.end_col - 2]
                self.board[move.end_row][move.end_col - 2] = '  '
        self.update_castle_rights(move)
        self.castling_log.append({'wks': self.castling_rights['wks'], 'wqs': self.castling_rights['wqs'],
                                  'bks': self.castling_rights['bks'], 'bqs': self.castling_rights['bqs']})

    # Method to undo the move
    def undo(self):
        if len(self.move_log) != 0:  # In case the move log is empty
            self.checkmate = False
            self.stalemate = False
            move = self.move_log.pop()
            self.board[move.start_row][move.start_col] = move.moved_piece
            self.board[move.end_row][move.end_col] = move.captured_piece
            self.white_to_move = not self.white_to_move
            if move.moved_piece == 'wK':
                self.white_king_position = (move.start_row, move.start_col)
            if move.moved_piece == 'bK':
                self.black_king_position = (move.start_row, move.start_col)

            # En Passant
            if move.is_ep:
                self.board[move.end_row][move.end_col] = '  '
                self.board[move.start_row][move.end_col] = move.captured_piece
                self.passant = (move.end_row, move.end_col)
            if move.moved_piece[1] == 'P' and abs(move.start_row - move.end_row) == 2:
                self.passant = ()

            # Castling
            if move.is_castle:
                if move.end_col - move.start_col == 2:
                    self.board[move.end_row][move.end_col + 1] = self.board[move.end_row][move.end_col - 1]
                    self.board[move.end_row][move.end_col - 1] = '  '
                else:
                    self.board[move.end_row][move.end_col - 2] = self.board[move.end_row][move.end_col + 1]
                    self.board[move.end_row][move.end_col + 1] = '  '
            self.castling_log.pop()
            castle_rights = copy.deepcopy(self.castling_log[-1])
            self.castling_rights = castle_rights

    def update_castle_rights(self, move):
        if move.moved_piece == 'wK':
            self.castling_rights['wks'] = False  # wks
            self.castling_rights['wqs'] = False  # wqs
        elif move.moved_piece == 'bK':
            self.castling_rights['bks'] = False  # bks
            self.castling_rights['bqs'] = False  # bqs
        elif move.moved_piece == 'wR':
            if move.start_row == 7:
                if move.start_col == 0:
                    self.castling_rights['wqs'] = False
                elif move.start_col == 7:
                    self.castling_rights['wks'] = False
        elif move.moved_piece == 'bR':
            if move.start_row == 0:
                if move.start_col == 0:
                    self.castling_rights['bqs'] = False
                elif move.start_col == 7:
                    self.castling_rights['bks'] = False
        if move.captured_piece == 'wR':
            if move.end_row == 7:
                if move.end_col == 0:
                    self.castling_rights['wqs'] = False
                elif move.end_col == 7:
                    self.castling_rights['wks'] = False
        elif move.captured_piece == 'bR':
            if move.end_row == 0:
                if move.end_row == 0:
                    self.castling_rights['bqs'] = False
                elif move.end_row == 7:
                    self.castling_rights['bks'] = False

    def get_legal_moves(self):
        moves = []  # Get all moves
        self.in_check, self.pins, self.checks = self.check_for_pins_and_checks()
        if self.white_to_move:
            king_location = self.white_king_position
        else:
            king_location = self.black_king_position
        king_row, king_col = king_location

        self.get_castles(king_row, king_col, moves)

        if not self.in_check:
            moves.extend(self.get_moves())
            return moves
        if len(self.checks) == 1:  # No double check, -> blocks & captures possible
            moves = self.get_moves()
            check_row, check_col = self.checks[0][0], self.checks[0][1]
            check_dir = self.checks[0][2]
            checker = self.board[check_row][check_col]
            valid_moves = []  # Valid ways to stop check: capture or block
            if checker[1] == 'N':
                valid_moves.append((check_row, check_col))
            else:
                for i in range(1, 8):
                    sq = (king_row + i * check_dir[0], king_col + i * check_dir[1])
                    valid_moves.append(sq)
                    if sq == (check_row, check_col):  # Once you get to the checker
                        break
            for i in range(len(moves) - 1, -1, -1):
                if moves[i].moved_piece[1] != 'K':
                    if (moves[i].end_row, moves[i].end_col) not in valid_moves:
                        moves.remove(moves[i])
        else:
            self.get_king_moves(king_row, king_col, moves)
        return moves

    def get_moves(self):
        moves = []
        for row in range(len(self.board)):
            for col in range(len(self.board[row])):
                colour = self.board[row][col][0]
                if (colour == 'w' and self.white_to_move) or (colour == 'b' and not self.white_to_move):
                    self.piece_moves[self.board[row][col][1]](row, col, moves)  # Maps keys to dictionary
        return moves

    def under_attack(self, position):
        self.white_to_move = not self.white_to_move  # Switch to opponent's turn
        opponent_moves = self.get_moves()  # Generate opponent's moves
        self.white_to_move = not self.white_to_move  # Switch back
        for move in opponent_moves:
            if (move.end_row, move.end_col) == position:
                return True
        return False

    def check_for_pins_and_checks(self):
        pins = []
        checks = []
        in_check = False

        enemy = {True: 'b', False: 'w'}[self.white_to_move]
        ally = {True: 'w', False: 'b'}[self.white_to_move]
        position = {'w': self.white_king_position, 'b': self.black_king_position}[ally]
        row, col = position[0], position[1]
        knight_jumps = [(-2, 1), (-1, 2), (2, 1), (1, 2), (2, -1), (1, -2), (-1, -2), (-2, -1)]
        for direction in [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]:
            possible_pin = ()
            for i in range(1, 8):
                rowvector = row + i * direction[0]
                colvector = col + i * direction[1]
                if 0 <= rowvector <= 7 and 0 <= colvector <= 7:
                    target = self.board[rowvector][colvector]
                    if target[0] == ally and target[1] != 'K':  # Excluding own king
                        # We check for pins by examining how many pieces are between the king and possible enemy
                        if possible_pin == ():
                            possible_pin = (rowvector, colvector, direction)
                        else:  # Already a piece between the king and pinner, so no pin.
                            break
                    elif target[0] == enemy:
                        enemy_type = target[1]
                        #  Case checks for each of the piece, direction combinations that can attack the square
                        if (enemy_type == 'R' and 0 in direction) \
                                or (enemy_type == 'B' and (direction[0] + direction[1]) % 2 == 0) \
                                or (enemy_type == 'Q') or (enemy_type == 'K' and i == 1) \
                                or (enemy_type == 'P' and i == 1 and
                                    ((enemy == 'w' and direction in [(1, 1), (1, -1)]) or (enemy == 'b' and direction in
                                                                                           [(-1, 1), (-1, -1)]))):
                            if possible_pin == ():  # If there are no pins
                                in_check = True
                                checks.append((rowvector, colvector, direction))
                            else:  # The piece is pinned
                                pins.append(possible_pin)
                                break
                        else:  # Enemy piece does not check the king; it blocks any other checkers as well
                            break
                else:  # Hit the end of the board
                    break
        for jump in knight_jumps:
            rowvector = row + jump[0]
            colvector = col + jump[1]
            if 0 <= rowvector <= 7 and 0 <= colvector <= 7:
                target = self.board[rowvector][colvector]
                if target == enemy + 'N':
                    in_check = True
                    checks.append((rowvector, colvector, direction))
        return in_check, pins, checks

    def get_pawn_moves(self, row, col, moves):
        pinned = False
        pin_dir = ()
        for i in range(len(self.pins) - 1, -1, -1):
            if (self.pins[i][0], self.pins[i][1]) == (row, col):
                pinned = True
                pin_dir = self.pins[i][2]
                self.pins.remove(self.pins[i])
                break
        if self.white_to_move:
            if self.board[row - 1][col] == '  ':
                if not pinned or pin_dir == (-1, 0):
                    moves.append(Move((row, col), (row - 1, col), self.board))
                    if self.board[row - 2][col] == '  ' and row == 6:
                        moves.append(Move((row, col), (row - 2, col), self.board))
            if col - 1 >= 0:
                if not pinned or pin_dir == (-1, -1):
                    if self.board[row - 1][col - 1][0] == 'b':
                        moves.append(Move((row, col), (row - 1, col - 1), self.board))
                    elif (row - 1, col - 1) == self.passant:
                        moves.append(Move((row, col), (row - 1, col - 1), self.board, is_ep=True))
            if col + 1 <= 7:
                if not pinned or pin_dir == (-1, 1):
                    if self.board[row - 1][col + 1][0] == 'b':
                        moves.append(Move((row, col), (row - 1, col + 1), self.board))
                    elif (row - 1, col + 1) == self.passant:
                        moves.append(Move((row, col), (row - 1, col + 1), self.board, is_ep=True))

        else:
            if self.board[row + 1][col] == '  ':
                if not pinned or pin_dir == (1, 0):
                    moves.append(Move((row, col), (row + 1, col), self.board))
                    if self.board[row + 2][col] == '  ' and row == 1:
                        moves.append(Move((row, col), (row + 2, col), self.board))
            if col - 1 >= 0:
                if not pinned or pin_dir == (1, -1):
                    if self.board[row + 1][col - 1][0] == 'w':
                        moves.append(Move((row, col), (row + 1, col - 1), self.board))
                    elif (row + 1, col - 1) == self.passant:
                        moves.append(Move((row, col), (row + 1, col - 1), self.board, is_ep=True))
            if col + 1 <= 7:
                if not pinned or pin_dir == (1, 1):
                    if self.board[row + 1][col + 1][0] == 'w':
                        moves.append(Move((row, col), (row + 1, col + 1), self.board))
                    elif (row + 1, col + 1) == self.passant:
                        moves.append(Move((row, col), (row + 1, col + 1), self.board, is_ep=True))

    def get_rook_moves(self, row, col, moves):
        pinned = False
        pin_dir = ()
        for i in range(len(self.pins) - 1, -1, -1):
            if (self.pins[i][0], self.pins[i][1]) == (row, col):
                pinned = True
                pin_dir = self.pins[i][2]
                if self.board[row][col][1] != 'Q':  # Otherwise get_queen_moves removes pin twice
                    self.pins.remove(self.pins[i])
                break
        if self.white_to_move:
            enemy = 'b'
        else:
            enemy = 'w'
        for direction in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
            for i in range(1, 8):
                rowvector = row + i * direction[0]
                colvector = col + i * direction[1]
                if 0 <= rowvector <= 7 and 0 <= colvector <= 7:
                    if not pinned or pin_dir == direction or pin_dir == (-direction[0], -direction[1]):
                        target = self.board[rowvector][colvector]
                        if target == '  ':
                            moves.append(Move((row, col), (rowvector, colvector), self.board))
                        elif target[0] == enemy:
                            moves.append(Move((row, col), (rowvector, colvector), self.board))
                            break
                        else:
                            break
                else:
                    break

    def get_bishop_moves(self, row, col, moves):
        pinned = False
        pin_dir = ()
        for i in range(len(self.pins) - 1, -1, -1):
            if (self.pins[i][0], self.pins[i][1]) == (row, col):
                pinned = True
                pin_dir = self.pins[i][2]
                self.pins.remove(self.pins[i])
                break
        if self.white_to_move:
            enemy = 'b'
        else:
            enemy = 'w'

        for direction in [(-1, -1), (-1, 1), (1, 1), (1, -1)]:
            for i in range(1, 8):
                rowvector = row + i * direction[0]
                colvector = col + i * direction[1]
                if 0 <= rowvector <= 7 and 0 <= colvector <= 7:
                    if not pinned or pin_dir == direction or pin_dir == (-direction[0], -direction[1]):
                        target = self.board[rowvector][colvector]
                        if target == '  ':
                            moves.append(Move((row, col), (rowvector, colvector), self.board))
                        elif target[0] == enemy:
                            moves.append(Move((row, col), (rowvector, colvector), self.board))
                            break
                        else:
                            break
                else:
                    break

    def get_queen_moves(self, row, col, moves):
        self.get_rook_moves(row, col, moves)
        self.get_bishop_moves(row, col, moves)

    def get_knight_moves(self, row, col, moves):
        pinned = False
        for i in range(len(self.pins) - 1, -1, -1):
            if (self.pins[i][0], self.pins[i][1]) == (row, col):
                pinned = True
                self.pins.remove(self.pins[i])
                break
        jumps = [(-2, 1), (-1, 2), (2, 1), (1, 2), (2, -1), (1, -2), (-1, -2), (-2, -1)]
        if self.white_to_move:
            ally = 'w'
        else:
            ally = 'b'
        for jump in jumps:
            rowvector = row + jump[0]
            colvector = col + jump[1]
            if 0 <= rowvector <= 7 and 0 <= colvector <= 7:
                if self.board[rowvector][colvector][0] != ally and not pinned:
                    moves.append(Move((row, col), (rowvector, colvector), self.board))

    def get_king_moves(self, row, col, moves):
        king_moves = [(-1, -1), (-1, 1), (1, 1), (1, -1), (-1, 0), (0, -1), (1, 0), (0, 1)]
        if self.white_to_move:
            ally = 'w'
        else:
            ally = 'b'
        for move in king_moves:
            rowvector = row + move[0]
            colvector = col + move[1]
            if 0 <= rowvector <= 7 and 0 <= colvector <= 7:
                target = self.board[rowvector][colvector]
                if target[0] != ally:
                    if ally == 'w':
                        self.white_king_position = (rowvector, colvector)
                    else:
                        self.black_king_position = (rowvector, colvector)
                    in_check, pins, checks = self.check_for_pins_and_checks()
                    if not in_check:
                        moves.append(Move((row, col), (rowvector, colvector), self.board))
                    if ally == 'w':
                        self.white_king_position = (row, col)
                    else:
                        self.black_king_position = (row, col)

    def get_castles(self, row, col, moves):
        if not self.in_check:
            if (self.white_to_move and self.castling_rights['wks']) or \
                    (not self.white_to_move and self.castling_rights['bks']):
                if self.board[row][col + 1] == '  ' and self.board[row][col + 2] == '  ':
                    if not self.under_attack((row, col + 1)) and not self.under_attack((row, col + 2)):
                        moves.append(Move((row, col), (row, col + 2), self.board, is_castle=True))
            if (self.white_to_move and self.castling_rights['wqs']) or \
                    (not self.white_to_move and self.castling_rights['bqs']):
                if self.board[row][col - 1] == '  ' and self.board[row][col - 2] == '  ' and \
                        self.board[row][col - 3] == '  ':
                    if not self.under_attack((row, col - 1)) and not self.under_attack((row, col - 2)):
                        moves.append(Move((row, col), (row, col - 2), self.board, is_castle=True))


class Move:
    # Dictionaries to convert rows to ranks and vice versa / cols to files and vice versa.
    rows = {'1': 7, '2': 6, '3': 5, '4': 4, '5': 3, '6': 2, '7': 1, '8': 0}
    ranks = {j: i for i, j in rows.items()}
    cols = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7}
    files = {j: i for i, j in cols.items()}

    def __init__(self, start, end, board, is_ep=False, is_castle=False):
        self.start_row = start[0]
        self.start_col = start[1]
        self.end_row = end[0]
        self.end_col = end[1]
        self.moved_piece = board[self.start_row][self.start_col]
        self.captured_piece = board[self.end_row][self.end_col]

        # Pawn Promotion
        self.promotion_choice = None
        self.is_pawn_promotion = (self.moved_piece == 'wP' and self.end_row == 0) or \
                                 (self.moved_piece == 'bP' and self.end_row == 7)

        # En Passant
        self.is_ep = is_ep
        if self.is_ep:
            if self.moved_piece == 'bP':
                self.captured_piece = 'wP'
            else:
                self.captured_piece = 'bP'

        # Castle
        self.is_castle = is_castle

        # Move Identification
        self.moveID = self.start_row * 1000 + self.start_col * 100 + self.end_row * 10 + self.end_col

        # Evaluation
        self.eval = 0

    # Overriding the equals method
    def __eq__(self, other):
        if isinstance(other, Move):
            return self.moveID == other.moveID

    # Retrieve the algebraic notation of the move
    def get_algebraic_notation(self):
        return self.get_rank_file(self.start_row, self.start_col) + self.get_rank_file(self.end_row, self.end_col)

    # Retrieve the algebraic notation of a square
    def get_rank_file(self, row, col):
        return self.files[col] + self.ranks[row]

main.py: the driver of the code. The GUI is with Pygame.

import pygame
import pygame.mouse
import time

import QiEngine
import QiIntelligence

# Dimensions of the board

WIDTH = 400
HEIGHT = 400
DIMENSION = 8
SQ_SIZE = HEIGHT // DIMENSION
MAX_FPS = 15
IMAGES = {}

RED = pygame.Color('red')
WHITE = pygame.Color('white')
GRAY = pygame.Color('gray')
YELLOW = pygame.Color('yellow')
BLUE = pygame.Color('blue')

# Initialize images as a dictionary. IMAGES[piece] accesses the pygame.image load method.
def load_images():
    pieces = ['wP', 'bP', 'wR', 'bR', 'wN', 'bN', 'wB', 'bB', 'wQ', 'bQ', 'wK', 'bK']
    for piece in pieces:
        IMAGES[piece] = pygame.transform.scale(pygame.image.load('images/' + piece + '.png'), (SQ_SIZE, SQ_SIZE))


# Main driver: handles UI and graphics
def main():
    pygame.init()
    screen = pygame.display.set_mode((WIDTH, HEIGHT))
    clock = pygame.time.Clock()
    screen.fill(pygame.Color('white'))
    gamestate = QiEngine.GameState()
    legal_moves = gamestate.get_legal_moves()
    move_made = False
    load_images()  # Load images only once
    running = True
    sq_selected = ()  # The square the player selects by clicking
    player_clicks = []  # Keeps track of the clicks the player has performed
    while running:
        for e in pygame.event.get():
            if e.type == pygame.QUIT:
                running = False

            # Mouse Control
            if e.type == pygame.MOUSEBUTTONDOWN:
                position = pygame.mouse.get_pos()  # Coordinates of the mouse
                col = position[0]//SQ_SIZE
                row = position[1]//SQ_SIZE
                if sq_selected == (row, col):
                    sq_selected = ()
                    player_clicks = []
                else:
                    sq_selected = (row, col)
                    player_clicks.append(sq_selected)
                if len(player_clicks) == 2:
                    move = QiEngine.Move(player_clicks[0], player_clicks[1], gamestate.board)
                    print(move.get_algebraic_notation())
                    for i in range(len(legal_moves)):
                        if move == legal_moves[i]:
                            if legal_moves[i].is_pawn_promotion:
                                legal_moves[i].promotion_choice = input('<Promote to Q/R/B/N>')
                                while legal_moves[i].promotion_choice not in ('Q', 'R', 'B', 'N'):
                                    legal_moves[i].promotion_choice = input('<Invalid; Choose Q/R/B/N>')
                            gamestate.make_move(legal_moves[i])
                            move_made = True
                            sq_selected = ()
                            player_clicks = []

                    if not move_made:
                        player_clicks = [sq_selected]

            # Key Control
            elif e.type == pygame.KEYDOWN:
                if e.key == pygame.K_z:
                    if len(gamestate.move_log) != 0:
                        gamestate.undo()
                        move_made = True
                        print('Undone')
                    else:
                        print('Empty')
                if e.key == pygame.K_q:
                    print('Calculating...')
                    start = time.time()
                    QiIntelligence.print_best_moves(gamestate)
                    end = time.time()
                    print(end - start)

            if move_made:
                legal_moves = gamestate.get_legal_moves()
                move_made = False

        draw(screen, gamestate, legal_moves, sq_selected)
        clock.tick(MAX_FPS)
        pygame.display.flip()

def highlight(screen, gamestate, legal_moves, sq_selected):
    if sq_selected != ():
        row, col = sq_selected
        if gamestate.board[row][col][0] == ('w' if gamestate.white_to_move else 'b'):
            s = pygame.Surface((SQ_SIZE, SQ_SIZE))
            s.set_alpha(100)
            s.fill(BLUE)
            screen.blit(s, (col*SQ_SIZE, row*SQ_SIZE))
            s.fill(YELLOW)
            for move in legal_moves:
                if move.start_col == col and move.start_row == row:
                    screen.blit(s, (move.end_col * SQ_SIZE, move.end_row * SQ_SIZE))


def draw(screen, gamestate, legal_moves, sq_selected):
    draw_board(screen)
    highlight(screen, gamestate, legal_moves, sq_selected)
    draw_pieces(screen, gamestate.board)


# Draw the squares on the board
def draw_board(screen):
    colours = [WHITE, GRAY]
    for row in range(DIMENSION):
        for col in range(DIMENSION):
            colour = colours[(row + col) % 2]
            pygame.draw.rect(screen, colour, pygame.Rect(col*SQ_SIZE, row*SQ_SIZE, SQ_SIZE, SQ_SIZE))


# Draw the pieces on the board
def draw_pieces(screen, board):
    for row in range(DIMENSION):
        for col in range(DIMENSION):
            piece = board[row][col]
            if piece != '  ':
                screen.blit(IMAGES[piece], pygame.Rect(col*SQ_SIZE, row*SQ_SIZE, SQ_SIZE, SQ_SIZE))


if __name__ == '__main__':
    main()

QiIntelligence.py: The AI.

import random
from copy import deepcopy
import cProfile

import QiEngine

profiler = cProfile.Profile()

piece_score = {'K': 0, 'Q': 900, 'R': 500, 'B': 310, 'N': 290, 'P': 100}

knight_scores = [[0, 10, 20, 20, 20, 20, 10, 0],
                 [10, 30, 50, 50, 50, 50, 30, 10],
                 [20, 50, 60, 65, 65, 60, 50, 20],
                 [20, 55, 65, 70, 70, 65, 55, 20],
                 [20, 50, 65, 70, 70, 65, 50, 20],
                 [20, 55, 60, 65, 65, 60, 55, 20],
                 [10, 30, 50, 50, 50, 50, 30, 10],
                 [0, 10, 20, 20, 20, 20, 10, 0]]

bishop_scores = [[0, 20, 20, 20, 20, 20, 20, 0],
                 [20, 40, 40, 40, 40, 40, 40, 20],
                 [20, 40, 50, 60, 60, 50, 40, 20],
                 [20, 50, 50, 60, 60, 50, 50, 20],
                 [20, 40, 60, 60, 60, 60, 40, 20],
                 [20, 60, 60, 60, 60, 60, 60, 20],
                 [20, 50, 40, 40, 40, 40, 50, 20],
                 [0, 20, 20, 20, 20, 20, 20, 0]]

rook_scores = [[25, 25, 25, 25, 25, 25, 25, 25],
               [50, 75, 75, 75, 75, 75, 75, 50],
               [0, 25, 25, 25, 25, 25, 25, 0],
               [0, 25, 25, 25, 25, 25, 25, 0],
               [0, 25, 25, 25, 25, 25, 25, 0],
               [0, 25, 25, 25, 25, 25, 25, 0],
               [0, 25, 25, 25, 25, 25, 25, 0],
               [25, 25, 25, 50, 50, 25, 25, 25]]

queen_scores = [[0, 20, 20, 30, 30, 20, 20, 0],
                [20, 40, 40, 40, 40, 40, 40, 20],
                [20, 40, 50, 50, 50, 50, 40, 20],
                [30, 40, 50, 50, 50, 50, 40, 30],
                [40, 40, 50, 50, 50, 50, 40, 30],
                [20, 50, 50, 50, 50, 50, 40, 20],
                [20, 40, 50, 40, 40, 40, 40, 20],
                [0, 20, 20, 30, 30, 20, 20, 0]]

pawn_scores = [[80, 80, 80, 80, 80, 80, 80, 80],
               [70, 70, 70, 70, 70, 70, 70, 70],
               [30, 30, 40, 50, 50, 40, 30, 30],
               [25, 25, 30, 45, 45, 30, 25, 25],
               [20, 20, 20, 40, 40, 20, 20, 20],
               [25, 15, 10, 20, 20, 10, 15, 25],
               [25, 30, 30, 0, 0, 30, 30, 25],
               [20, 20, 20, 20, 20, 20, 20, 20]]

piece_position_scores = {'wN': knight_scores,
                         'bN': knight_scores[::-1],
                         'wB': bishop_scores,
                         'bB': bishop_scores[::-1],
                         'wQ': queen_scores,
                         'bQ': queen_scores[::-1],
                         'wR': rook_scores,
                         'bR': rook_scores[::-1],
                         'wP': pawn_scores,
                         'bP': pawn_scores[::-1]}



DEPTH = 3
CHECKMATE = 99999

# Prints the best moves in a state of the game
def print_best_moves(gamestate):
    legal_moves = gamestate.get_legal_moves()
    move_evals = []
    for move in legal_moves:
        if not move.is_pawn_promotion:
            gamestate.make_move(move)
            move_eval = minimax(static_eval, DEPTH, gamestate, gamestate.get_legal_moves(), -CHECKMATE, CHECKMATE)
            gamestate.undo()
            move_evals.append((move, move_eval))
        else:
            for choice in ['Q', 'N', 'B', 'R']:
                move_copy = deepcopy(move)
                move_copy.promotion_choice = choice
                gamestate.make_move(move_copy)
                move_eval = minimax(static_eval, DEPTH, gamestate, gamestate.get_legal_moves(), -CHECKMATE, CHECKMATE)
                gamestate.undo()
                move_evals.append((move_copy, move_eval))

    move_evals.sort(key=lambda x: x[1], reverse=gamestate.white_to_move)  # Sorting to print the best moves first
    for i in move_evals:
        if not i[0].is_pawn_promotion:
            print(f'{i[0].get_algebraic_notation()}: {i[1]}')
        else:
            print(f'{i[0].get_algebraic_notation()}={i[0].promotion_choice}: {i[1]}')

# Minimax Algorithm with ab pruning
def minimax(static_eval, depth, gamestate, legal_moves, alpha, beta):
    # Sorting
    order_moves(gamestate, legal_moves)

    if depth == 0 or gamestate.checkmate or gamestate.stalemate:
        return static_eval(gamestate)

    if gamestate.white_to_move:
        max_eval = -CHECKMATE
        for move in legal_moves:
            if not move.is_pawn_promotion:
                gamestate.make_move(move)
                eval = minimax(static_eval, depth - 1, gamestate, gamestate.get_legal_moves(), alpha, beta)
                gamestate.undo()
                max_eval = max(eval, max_eval)
                alpha = max(alpha, max_eval)
                if beta <= alpha:
                    break
            else:
                for choice in ['Q', 'R', 'B', 'N']:
                    move_copy = deepcopy(move)
                    move_copy.promotion_choice = choice
                    gamestate.make_move(move_copy)
                    eval = minimax(static_eval, depth - 1, gamestate, gamestate.get_legal_moves(), alpha, beta)
                    gamestate.undo()
                    max_eval = max(eval, max_eval)
                    alpha = max(alpha, max_eval)
                    if beta <= alpha:
                        break
        return max_eval

    else:
        min_eval = CHECKMATE
        for move in legal_moves:
            if not move.is_pawn_promotion:
                gamestate.make_move(move)
                eval = minimax(static_eval, depth - 1, gamestate, gamestate.get_legal_moves(), alpha, beta)
                gamestate.undo()
                min_eval = min(eval, min_eval)
                beta = min(beta, min_eval)
                if beta <= alpha:
                    break
            else:
                for choice in ['Q', 'R', 'B', 'N']:
                    move_copy = deepcopy(move)
                    move_copy.promotion_choice = choice
                    gamestate.make_move(move_copy)
                    eval = minimax(static_eval, depth - 1, gamestate, gamestate.get_legal_moves(), alpha, beta)
                    gamestate.undo()
                    min_eval = min(eval, min_eval)
                    beta = min(beta, min_eval)
                    if beta <= alpha:
                        break
        return min_eval

def static_eval(gamestate):
    if gamestate.stalemate:
        return 0
    elif gamestate.checkmate:
        return CHECKMATE * (-1 if gamestate.white_to_move else 1)

    score = 0
    for row in range(len(gamestate.board)):
        for col in range(len(gamestate.board[row])):
            piece = gamestate.board[row][col]
            if piece != '  ':
                piece_position_score = 0
                if piece[1] != 'K':
                    pass
                    piece_position_score = piece_position_scores[piece][row][col]
                if piece[0] == 'w':
                    score += piece_score[piece[1]] + piece_position_score
                if piece[0] == 'b':
                    score -= piece_score[piece[1]] + piece_position_score
    return score

def order_moves(gamestate, legal_moves):
    turn = 1 if gamestate.white_to_move else -1 
    board = gamestate.board
    for move in legal_moves:
        spec_eval = 0  # We speculate how good the move will be
        if move.captured_piece != '  ':  # If a piece is captured, we add on the spec_eval
            spec_eval = 10 * piece_score[move.captured_piece[1]] - piece_score[move.moved_piece[1]]

        if move.is_pawn_promotion:  # Move ordering likes pawn promotions
            spec_eval += piece_score[move.promotion_choice]

        if 1 <= move.end_col <= 6 and 1 <= move.end_row <= 6:  # Move ordering dislikes going to a square attacked by enemy pawn.
            if ('P' == board[move.end_row + 1 * turn][move.end_col + 1][1] or
                 'P' == board[move.end_row + 1 * turn][move.end_col - 1][1]):
                spec_eval -= piece_score[move.moved_piece[1]]

        move.eval = spec_eval
    
    legal_moves.sort(key=lambda x: x.eval, reverse=True)  # Sort the legal moves by how good the speculated eval is


if __name__ == '__main__':
    profiler.runcall(print_best_moves, QiEngine.GameState())
    profiler.print_stats()

Right now, the AI is wired to print the evaluation in centipawns for every legal move in a position if i press Q in the pygame interface. The main point for optimization should be print_best_moves in QiIntelligence.py. Right now print_best_moves simply prints out the evaluation of each legal move in the position.

In order to identify performance bottlenecks, I ran cProfile on print_best_moves with DEPTH=5. Here is the result:

358416229 function calls (343023756 primitive calls) in 706.696 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
  1710277    1.841    0.000    1.841    0.000 QiEngine.py:127(update_castle_rights)
  1710278    7.359    0.000  479.331    0.000 QiEngine.py:159(get_legal_moves)
  1724437   66.301    0.000  411.455    0.000 QiEngine.py:195(get_moves)
    14163    0.102    0.000    3.664    0.000 QiEngine.py:204(under_attack)
  3105980   91.035    0.000   91.070    0.000 QiEngine.py:213(check_for_pins_and_checks)
 13664433   64.629    0.000  127.338    0.000 QiEngine.py:265(get_pawn_moves)
  5166285   36.922    0.000   46.903    0.000 QiEngine.py:312(get_rook_moves)
  5155279   40.141    0.000   59.685    0.000 QiEngine.py:343(get_bishop_moves)
  1718658    2.463    0.000   39.056    0.000 QiEngine.py:374(get_queen_moves)
  3422629   28.290    0.000   51.253    0.000 QiEngine.py:378(get_knight_moves)
  1724441   12.334    0.000   55.068    0.000 QiEngine.py:397(get_king_moves)
  1710278    2.530    0.000    6.213    0.000 QiEngine.py:421(get_castles)
 45504923  106.019    0.000  106.019    0.000 QiEngine.py:443(__init__)
  6984022    3.038    0.000    3.962    0.000 QiEngine.py:474(__eq__)
       20    0.000    0.000    0.000    0.000 QiEngine.py:479(get_algebraic_notation)
       40    0.000    0.000    0.000    0.000 QiEngine.py:483(get_rank_file)
  1710277    8.274    0.000   11.040    0.000 QiEngine.py:57(make_move)
  1710277    9.419    0.000   66.286    0.000 QiEngine.py:94(undo)
  1477616   59.284    0.000   61.361    0.000 QiIntelligence.py:155(static_eval)
  1710277   48.756    0.000   71.866    0.000 QiIntelligence.py:176(order_moves)
 44577596    8.332    0.000    8.332    0.000 QiIntelligence.py:194(<lambda>)
        1    0.000    0.000  706.696  706.696 QiIntelligence.py:72(print_best_moves)
       20    0.000    0.000    0.000    0.000 QiIntelligence.py:74(<lambda>)
       20    0.000    0.000    0.000    0.000 QiIntelligence.py:91(<lambda>)
1710277/20   15.310    0.000  706.689   35.334 QiIntelligence.py:98(minimax)
15392493/1710277   29.255    0.000   55.440    0.000 copy.py:128(deepcopy)
 13682216    2.410    0.000    2.410    0.000 copy.py:182(_deepcopy_atomic)
  1710277    9.775    0.000   44.447    0.000 copy.py:226(_deepcopy_dict)
  1710277    3.238    0.000    3.861    0.000 copy.py:242(_keep_alive)
  1754646    0.487    0.000    0.487    0.000 {built-in method builtins.abs}
 20523324    4.005    0.000    4.005    0.000 {built-in method builtins.id}
  6984022    0.923    0.000    0.923    0.000 {built-in method builtins.isinstance}
 57983846    9.019    0.000    9.019    0.000 {built-in method builtins.len}
   396920    0.172    0.000    0.172    0.000 {built-in method builtins.max}
  3023594    1.328    0.000    1.328    0.000 {built-in method builtins.min}
       20    0.000    0.000    0.000    0.000 {built-in method builtins.print}
        1    0.000    0.000    0.000    0.000 {built-in method builtins.sorted}
 49120675    8.874    0.000    8.874    0.000 {method 'append' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
  1687043    0.544    0.000    0.544    0.000 {method 'extend' of 'list' objects}
 30784986    6.288    0.000    6.288    0.000 {method 'get' of 'dict' objects}
  1710277    0.470    0.000    0.470    0.000 {method 'items' of 'dict' objects}
  3420554    0.903    0.000    0.903    0.000 {method 'pop' of 'list' objects}
       20    0.000    0.000    0.000    0.000 {method 'random' of '_random.Random' objects}
   608255    1.848    0.000    5.810    0.000 {method 'remove' of 'list' objects}
  1710278   14.778    0.000   23.110    0.000 {method 'sort' of 'list' objects}

So my question is: how do I optimize this code? The profiler seems to identify the slowest processes in the move generation (check_for_pins_and_checks takes 91 seconds, __init__ for Move and GameState over 100 secs), but I see limited improvement opportunities.

I am considering a few things...

• Should I completely abandon the use of classes like GameState() and Move() if I want a faster engine? Is there some ready-made efficient move generation that can be connected to code like this easily?
• Maybe my computer just has bad performance?
• Maybe more pruning or other tricks to enhance performance would help? There are many ideas on CPW but I don't know what will be most beneficial for performance in my case.
• Is slowness because of Python? It's the only language I know, and learning something like C++ just for this is not appealing.

If the code is too unintelligible, I will edit the question to add more comments.

Answer 1

Wow, a performance submission that actually includes profiler data. Amazing, thank you, thank you!

ratios

I'm assuming the profiling is for the early-game depicted, where {pawns, bishops, knights} have each made a single move. Therefore players have eight pawns, single royalty, two of everything else.

For each get_FOO_moves I draw your attention to the ratio of cumulative to total time. For a given method cumtime describes time spent in the method plus its called children, whereas the smaller tottime covers just the method's code.

get_pawn_moves's ratio of just about 2 is striking. For bishop and rook we spend a smaller fraction of time in child calls, a bit less so for knight. And then we come to royalty. Ratio is nearly 5 for king, and more than 15 for queen! Ok, now I'm curious to read the source to see what's going on.

---

mypy

Consider adding optional type hinting to method signatures, or at least to some of them.

It will prove helpful if / when you refactor to use a different board representation, as it supports making incremental edits rather than one big flag day.

Single-character strings of 'P' .. 'K' work fine, but consider making them Enums instead.

---

arrays

The list-of-lists representation clearly works. But it has lots of overhead storage for pointers, and pointer de-references cause random read stalls.

Consider representing the board more compactly with an array. Then we're not consuming space in a cache line for unnecessary pointers, and we largely do predictable sequential reads.

Better, use a numpy NDarray. Then you get a bunch of nicely tuned vector operations for free.

---

reduce state variables

I like much of the board representation. Consider evicting these:

        self.checkmate = False
        self.stalemate = False

My rationale is that these feel like attributes of a "game" rather than of a point-in-time "board position".

Certainly a board position can be in_check. But why would we even consider mutating a position to make it be in checkmate or stalemate? Those feel like status values that should come back from evaluating a candidate, but not something that could be True for a "viable" candidate position.

---

simplify expressions

This is just a readability thing.

In get_rook_moves, asking whether self.board[row][col][1] is a queen seems less natural than asking about a self.piece_at(loc) property, where (row, col) form a single location or square.

        if self.white_to_move:
            enemy = 'b'
        else:
            enemy = 'w'

I'm surprised this isn't a @property based on self.white_to_move.

                if 0 <= rowvector <= 7 and 0 <= colvector <= 7:
                    if not pinned or pin_dir == direction or pin_dir == (-direction[0], -direction[1]):

We're asking permission rather than forgiveness, fair enough. Consider arranging matters so we can never fall off the edge, by adding padding squares around the edge of your board representation. Alternatively, consider adopting the ever popular bitboard representation.

The not pinned clause is a little worrisome. It precludes deliberate sacrifice of a pinned piece, or moving a pinned piece to give check (or mate!). I can understand wanting to prune sacrificial paths by giving them a low score, but here we treat it as a score of -∞.

EDIT

Ok, I read the "check for pins by examining how many pieces are between the king and possible enemy" comment just now. A bishop can e.g. pin a knight against a queen. When I read the self.pins = [] declaration, it did not occur to me that you were restricting the notion of "pin" to "pinned against your king".

I don't understand why tracking either kind of pin is beneficial. Won't we see a large eval score change when we evaluate the next ply, and so reject blunders like an illegal "discovered check" move?

---

extract helper

The get_{rook,bishop}_moves methods are, understandably, very similar. Consider having them call a common helper, which accepts four {orthogonal or diagonal} (dx, dy) unit vectors.

Kudos on taking queen moves as their composition, that worked quite cleanly. I wonder if the queen's "no double-accounting!" clause could be moved up to that level?

I think of a queen as "a king that can move up to 7 squares". Maybe pass in a parameter of 1 or 7 to the helper?

---

expense of each Move

In get_pawn_moves we spend about half the cumulative time making child calls. I think that is mostly the Move __init__ ctor. Quite a few attributes are assigned there, hardly any of which are relevant for contemplating a given pawn move. Find a way to avoid that busy work, perhaps by caching a Move object or by copying out just the aspects that are relevant to pawns.

Yeah, now that I look at it, for rook and others it appears that constructing the relatively heavyweight Move is much of the cumulative time. Figure out how to put it on a diet. Start by writing a """docstring""" for that class. Then ask yourself if it really needs to be responsible for all that, of if you can get away with making weaker promises and letting some other class pick up the slack for rare corner cases.

For example, a UI method may need start in order to animate the ultimately selected computer move. But during evaluation you just need end or perhaps only the resulting board, right?

BTW, thank you for the # comment which helpfully explained that is_ep deals with En Passant.

---

unique names vs. a length-2 vector

In get_king_moves this is tedious:

                    if ally == 'w':
                        self.white_king_position = (rowvector, colvector)
                    else:
                        self.black_king_position = (rowvector, colvector)

Ditch the pair of names, let ally be either 0 or 1, and then talk about self.king_position[ally]. Also, in get_pawn_moves the white / black copy-pasta code is out of control.

---

explicit return value

In Move an equality test can fall off the end of the method:

    def __eq__(self, other):
        if isinstance(other, Move):
            return self.moveID == other.moveID

Please add an explicit return None, since that's what implicitly happens now.

Better, make it return False, add type hints, and lint with mypy.

Also, in minimax, by convention we would name it eval_, to avoid shadowing a builtin identifier.

---

speedup strategies

Consider sending candidate board positions to a pub-sub channel that will evaluate a few ply and send back scores. That would let you keep more cores (or hosts) busy.

Represent the board with cache-friendly NDarrays that use modern CPU instructions to vectorize access. Better, adopt bitboards (granted, probably a rewrite).

Add an automated test suite for leaf helpers.

Add type annotation, and use numba to JIT some of the leaf helper methods, such as get_rook_moves. Or convert selected helpers to a faster language like Cython or even Rust.

---

This code achieves most of its design goals. Changes to datastructures and algorithms will be needed for it to make significant progress, possibly resulting in discarding much of the current source code.

I would be willing to delegate or accept maintenance tasks on it.

Answer 2

• Domain knowledge

  • There is no way to resign a game, or to offer/accept a draw.
  • Three-fold repetition and 50 moves rule are also sorely missing.

• Separation of responsibilities

  • It feels really weird that a knowledge of rules is spread around. In your implementation only UI knows that the piece at move must change its position. A Move constructor happily accepts start being equal to end. Does not feel right to me.

  • Ditto for promotion.

• Testing for the legality of the move also looks backward. Instead of looping over the legal moves

                for i in range(len(legal_moves)):
                    if move == legal_moves[i]:
  

  ... which is not very pythonic to begin with; it should be

                for legal_move in legal_moves:
                     if move == legal_move:
  

  consider

                if gamestate.move_is_legal(move):
  

• Performance

  • I don't see any benefit in testing for pins (at least the way you do it). Better blindly try the (geometrically legal) move, and reject it if it leaves a King exposed.

  • Checking for a check iterates the entire board. Better iterate the enemy pieces.

  • I don't see QiEngine class, so I can't comment on its __init__ method.