8
\$\begingroup\$

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
Improve this question
\$\endgroup\$
2
  • 7
    \$\begingroup\$ 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! \$\endgroup\$
    – FMc
    Mar 22, 2022 at 1:20
  • 1
    \$\begingroup\$ 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.) \$\endgroup\$
    – greybeard
    May 28, 2022 at 11:53

1 Answer 1

Reset to default
1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.