Making this python chess engine faster

Question

I've implemented a chess engine using the python chess move generation library (which I assumed to be reasonably fast), and have implemented various optimisation techniques for search and move ordering, such as alpha-beta pruning (with negamax) and MVV LVA tables. However, it still takes more than 50 seconds (at depth > 4) for it to evaluate a normal position. The repository and source code can be found here. I have a feeling that the piece square tables in evaluation.py are slowing it down but how else would I implement it? I also thought about doing iterative searching and using transposition tables/Zobrist hashing. But if pruning, move ordering and MVV LVA tables are not making the engine much faster, then these other things will have little to no effect on its performance. I appreciate it if anyone with more experience could look at the source code and possibly point out the problem (if there is indeed an issue) as to why it's so dreadfully slow.

engine.py (entry point)

import chess
from opening import opening_book
from tablebase import tablebase
from search import root_search, nodes
from timeit import default_timer as timer
board = chess.Board("3r3r/4k3/1pn4p/5pp1/2P1p3/3N4/PPK2PPP/R3R3 w - - 0 29")
def search(board):
 book_move = opening_book(board, "openings.bin")
 if (book_move[0] == None):
 if (tablebase(board) == None):
 return root_search(board, 4)
 else: 
 return tablebase(board)
 else:
 return book_move[0]
print(board)
start = timer()
best_move = search(board)
end = timer()
print("Best move: ", best_move) 
print("Nodes: ", nodes)
print("Time: ", end - start)

evaluation.py

import chess
# Constant piece values
PAWN_VALUE = 100
BISHOP_VALUE = 300
KNIGHT_VALUE = 300
ROOK_VALUE = 500
QUEEN_VALUE = 900
# Piece square tables
pawns_table = [
 0, 0, 0, 0, 0, 0, 0, 0,
 50, 50, 50, 50, 50, 50, 50, 50,
 10, 10, 20, 30, 30, 20, 10, 10,
 5, 5, 10, 25, 25, 10, 5, 5,
 0, 0, 0, 20, 20, 0, 0, 0,
 5, -5,-10, 0, 0,-10, -5, 5,
 5, 10, 10,-20,-20, 10, 10, 5,
 0, 0, 0, 0, 0, 0, 0, 0
]
knights_table = [
 -50,-40,-30,-30,-30,-30,-40,-50,
 -40,-20, 0, 0, 0, 0,-20,-40,
 -30, 0, 10, 15, 15, 10, 0,-30,
 -30, 5, 15, 20, 20, 15, 5,-30,
 -30, 0, 15, 20, 20, 15, 0,-30,
 -30, 5, 10, 15, 15, 10, 5,-30,
 -40,-20, 0, 5, 5, 0,-20,-40,
 -50,-40,-30,-30,-30,-30,-40,-50,
]
bishops_table = [
 -20,-10,-10,-10,-10,-10,-10,-20,
 -10, 0, 0, 0, 0, 0, 0,-10,
 -10, 0, 5, 10, 10, 5, 0,-10,
 -10, 5, 5, 10, 10, 5, 5,-10,
 -10, 0, 10, 10, 10, 10, 0,-10,
 -10, 10, 10, 10, 10, 10, 10,-10,
 -10, 5, 0, 0, 0, 0, 5,-10,
 -20,-10,-10,-10,-10,-10,-10,-20,
]
rooks_table = [
 0, 0, 0, 0, 0, 0, 0, 0,
 5, 10, 10, 10, 10, 10, 10, 5,
 -5, 0, 0, 0, 0, 0, 0, -5,
 -5, 0, 0, 0, 0, 0, 0, -5,
 -5, 0, 0, 0, 0, 0, 0, -5,
 -5, 0, 0, 0, 0, 0, 0, -5,
 -5, 0, 0, 0, 0, 0, 0, -5,
 0, 0, 0, 5, 5, 0, 0, 0
]
queens_table = [
 -20,-10,-10, -5, -5,-10,-10,-20,
 -10, 0, 0, 0, 0, 0, 0,-10,
 -10, 0, 5, 5, 5, 5, 0,-10,
 -5, 0, 5, 5, 5, 5, 0, -5,
 0, 0, 5, 5, 5, 5, 0, -5,
 -10, 5, 5, 5, 5, 5, 0,-10,
 -10, 0, 5, 0, 0, 0, 0,-10,
 -20,-10,-10, -5, -5,-10,-10,-20
]
king_middle_table = [
 -30,-40,-40,-50,-50,-40,-40,-30,
 -30,-40,-40,-50,-50,-40,-40,-30,
 -30,-40,-40,-50,-50,-40,-40,-30,
 -30,-40,-40,-50,-50,-40,-40,-30,
 -20,-30,-30,-40,-40,-30,-30,-20,
 -10,-20,-20,-20,-20,-20,-20,-10,
 20, 20, 0, 0, 0, 0, 20, 20,
 20, 30, 10, 0, 0, 10, 30, 20
]
king_end_table = [
 -50,-40,-30,-20,-20,-30,-40,-50,
 -30,-20,-10, 0, 0,-10,-20,-30,
 -30,-10, 20, 30, 30, 20,-10,-30,
 -30,-10, 30, 40, 40, 30,-10,-30,
 -30,-10, 30, 40, 40, 30,-10,-30,
 -30,-10, 20, 30, 30, 20,-10,-30,
 -30,-30, 0, 0, 0, 0,-30,-30,
 -50,-30,-30,-30,-30,-30,-30,-50
]
# evaluate given position
def evaluate(board, depth):
 if board.is_stalemate():
 return 0
 
 elif board.is_repetition():
 return 0
 
 elif board.is_checkmate():
 return -99999 + (4 - depth)
 else:
 turn = board.turn
 white_eval = 0
 black_eval = 0
 white_material = count_material(board, chess.WHITE)
 black_material = count_material(board, chess.BLACK)
 white_eval += white_material
 black_eval += black_material
 white_eval += count_piece_square_tables(board, chess.WHITE)
 black_eval += count_piece_square_tables(board, chess.BLACK)
 evaluation = white_eval - black_eval
 
 return (evaluation * 1) if turn == chess.WHITE else (evaluation * -1)
 
# score of given side based on the placement of pieces
def count_piece_square_tables(board, turn):
 value = 0
 is_white = True
 if (turn == chess.BLACK): 
 is_white = False
 
 value += evaluate_piece_square_table(pawns_table, board.pieces(chess.PAWN, turn), is_white)
 value += evaluate_piece_square_table(knights_table, board.pieces(chess.KNIGHT, turn), is_white)
 value += evaluate_piece_square_table(bishops_table, board.pieces(chess.BISHOP, turn), is_white)
 value += evaluate_piece_square_table(rooks_table, board.pieces(chess.ROOK, turn), is_white)
 value += evaluate_piece_square_table(queens_table, board.pieces(chess.QUEEN, turn), is_white)
 value += evaluate_piece_square_table(king_middle_table, board.pieces(chess.KING, turn), is_white)
 return value
 
def evaluate_piece_square_table(table, piece_squares, is_white):
 value = 0
 for square in piece_squares:
 value += read_piece_square_table(table, square, is_white)
 return value
def read_piece_square_table(table, square, is_white):
 if is_white:
 file = chess.square_file(square)
 rank = chess.square_rank(square)
 rank = 7 - rank
 square = rank * 8 + file
 
 return table[square]
def count_material(board, color):
 material = 0
 material += chess.popcount(board.pieces(chess.PAWN, color)) * PAWN_VALUE
 material += chess.popcount(board.pieces(chess.KNIGHT, color)) * KNIGHT_VALUE
 material += chess.popcount(board.pieces(chess.BISHOP, color)) * BISHOP_VALUE
 material += chess.popcount(board.pieces(chess.ROOK, color)) * ROOK_VALUE
 material += chess.popcount(board.pieces(chess.QUEEN, color)) * QUEEN_VALUE
 return material

moves.py

import chess
# Map each piece to a value, for MVV LVA table
PT = {
 chess.Piece(chess.PAWN, chess.WHITE) : 0,
 chess.Piece(chess.KNIGHT, chess.WHITE) : 1,
 chess.Piece(chess.BISHOP, chess.WHITE) : 2,
 chess.Piece(chess.ROOK, chess.WHITE) : 3,
 chess.Piece(chess.QUEEN, chess.WHITE) : 4,
 chess.Piece(chess.KING, chess.WHITE) : 5,
 chess.Piece(chess.PAWN, chess.BLACK) : 6,
 chess.Piece(chess.KNIGHT, chess.BLACK) : 7,
 chess.Piece(chess.BISHOP, chess.BLACK) : 8,
 chess.Piece(chess.ROOK, chess.BLACK) : 9,
 chess.Piece(chess.QUEEN, chess.BLACK) : 10,
 chess.Piece(chess.KING, chess.BLACK) : 11,
}
# MVV LVA [attacker][victim]
mvv_lva = [
 [105, 205, 305, 405, 505, 605, 105, 205, 305, 405, 505, 605],
 [104, 204, 304, 404, 504, 604, 104, 204, 304, 404, 504, 604],
 [103, 203, 303, 403, 503, 603, 103, 203, 303, 403, 503, 603],
 [102, 202, 302, 402, 502, 602, 102, 202, 302, 402, 502, 602],
 [101, 201, 301, 401, 501, 601, 101, 201, 301, 401, 501, 601],
 [100, 200, 300, 400, 500, 600, 100, 200, 300, 400, 500, 600],
 [105, 205, 305, 405, 505, 605, 105, 205, 305, 405, 505, 605],
 [104, 204, 304, 404, 504, 604, 104, 204, 304, 404, 504, 604],
 [103, 203, 303, 403, 503, 603, 103, 203, 303, 403, 503, 603],
 [102, 202, 302, 402, 502, 602, 102, 202, 302, 402, 502, 602],
 [101, 201, 301, 401, 501, 601, 101, 201, 301, 401, 501, 601],
 [100, 200, 300, 400, 500, 600, 100, 200, 300, 400, 500, 600]
]
# Object for storing a move 
class Move:
 def __init__(self, move, score):
 self.move = move
 self.score = score
def make_move(board, move):
 board.push(chess.Move.from_uci(move.uci()))
 
def unmake_move(board):
 board.pop()
def sort_moves(board, moveList):
 move_scores = []
 
 # score each move and add to move_scores
 for move in moveList:
 move_scores.append(score_move(board, move))
 # sort moves based on score
 for move in range(0, len(moveList)):
 for next_move in range(move + 1, len(moveList)):
 if move_scores[move] < move_scores[next_move]:
 # swap scores
 temp_score = move_scores[move]
 move_scores[move] = move_scores[next_move]
 move_scores[next_move] = temp_score
 # swap moves
 temp_move = moveList[move]
 moveList[move] = moveList[next_move]
 moveList[next_move] = temp_move
 
def score_move(board, move):
 # assign score to move
 move_score = 0
 if (board.is_capture(move)):
 if board.is_en_passant(move):
 op_color = chess.BLACK if board.turn==chess.WHITE else chess.WHITE
 move_score = mvv_lva[PT[chess.Piece(chess.PAWN, board.turn)]][PT[chess.Piece(chess.PAWN, op_color)]] + 1000
 else:
 move_score = mvv_lva[PT[board.piece_at(move.from_square)]][PT[board.piece_at(move.to_square)]] + 1000
 return move_score

search.py

from moves import make_move, unmake_move, sort_moves
from evaluation import evaluate
nodes = 0
# Search all captures 
def quiescence(board, alpha, beta, depth):
 global nodes
 pos_eval = evaluate(board, depth)
 if (pos_eval >= beta):
 return beta
 if (alpha < pos_eval):
 alpha = pos_eval
 capture_moves = list(board.generate_legal_captures())
 sort_moves(board, capture_moves)
 for move in capture_moves:
 nodes += 1
 make_move(board, move)
 score = -quiescence(board, -beta, -alpha, depth)
 unmake_move(board)
 if score >= beta:
 return beta
 
 if score > alpha:
 alpha = score
 
 return alpha
# Search all moves until max depth
def negamax(board, alpha, beta, depth):
 global nodes
 if depth == 0 or board.is_game_over() or board.is_repetition():
 return quiescence(board, alpha, beta, depth)
 max = -99999
 moveList = list(board.legal_moves)
 sort_moves(board, moveList)
 for move in moveList:
 nodes += 1
 
 make_move(board, move)
 score = -negamax(board, -beta, -alpha, depth-1)
 unmake_move(board)
 
 if (score > max):
 max = score
 if max > alpha:
 alpha = max
 if (alpha >= beta):
 break
 return max
# Begin search here
def root_search(board, depth):
 global nodes
 nodes += 1
 best_move = None
 max = -99999
 moveList = list(board.legal_moves)
 if len(list(moveList)) == 0:
 if board.is_check():
 return -99999 
 return 0
 sort_moves(board, moveList)
 for move in moveList:
 nodes += 1
 make_move(board, move)
 score = -negamax(board, -99999, 99999, depth - 1)
 unmake_move(board)
 if (score > max):
 max = score
 best_move = move
 return best_move

• FMc: When code looks generally reasonable, as yours does, I encourage people facing a performance bottleneck to measure rather than theorize. Hook it up to a profiler (there's a bit of a learning curve to do that effectively, but I suspect you're up to the task) and pinpoint the portions of your code (or the libraries you are using) that are actually consuming most of the time. I've seen several projects that wasted a lot of time optimizing code that wasn't really the source of their trouble – and I've gone down that fruitless path a few times myself!
• greybeard: What is board.legal_moves, board.generate_legal_captures()? sort_moves() as a culprit looks too easy. (using the length of one list for ranges of indexes into another list looks off in sort_moves(), slice or hand-rolled twin.)

Answer 1

OP declined to offer cProfiler function timings, despite FMc's request on 22nd March. Knuth preaches about the evils of premature optimization.

---

If and when it becomes of interest to use a stopwatch to make objective improvements, these two lines are of interest:

 white_eval += count_piece_square_tables(board, chess.WHITE)
 black_eval += count_piece_square_tables(board, chess.BLACK)

Comment out first one, then the other. If both players have a dozen pieces still alive, we would expect similar timings. But if you look at the if in read_piece_square_table, it seems Black might go faster than White.

The various foo_table matrices are symmetric within a rank but not within a file. This reflects e.g. that pawns just move forward.

Precalculating upside-down tables would let read_piece_square_table go a bit faster. It is called many times by innermost loop, so it might matter.

---

Don't believe theorizing. Believe what the stopwatch says.