Python chess engine is too slow

Question

I have a working 1600 blitz level bot but it works too slow in python using python chess library. I tried to optimize the functions in eval function but the best it can do is depth 4 since it takes a second for average of 6000 nodes, and the functions are not even that complex, doubled pawns, king safety,material,piece tables etc. Even without an evaluation function it takes 1 second for 8000 nodes on average, i looked at other python engines and it seems that it's slow in general, should I switch to C++? On average 6 second is passed for a move but sometimes it takes like 18 seconds for a move with quiescence search with minimax alpha beta pruning. I use MVV-LVA move ordering; therefore, it reduces time by half but still its too much for some moves. Tried delta pruning, don't know if the implementation is correct tho, the execution time is about the same if delta = 880(queen) but when its around 200 it halves in middle game. Don't know if it's the best approach to keep it 200, open to any ideas, i'm new at these topics, and this engine really needs to work faster. It really plays bad when delta is 200.

This is the quiescence search:

def search_captures(self, alpha, beta, maximizing_player, delta=200):
    
    self.number_of_positions += 1

    # Static evaluation at the current position
    if self.board.is_checkmate():
        return -10000 if maximizing_player else 10000

    stand_pat = self.eval_func(maximizing_player)

    # Delta pruning: Skip this branch if even the best possible gain
    # cannot exceed alpha (for maximizing player) or beta (for minimizing player)
    if maximizing_player:
        if stand_pat + delta <= alpha:
            return alpha
    else:
        if stand_pat -delta >= beta:
            return beta

    # Alpha-beta bounds adjustment
    if maximizing_player:

        if stand_pat >= beta:
            return beta
        alpha = max(alpha, stand_pat)
    else:
        if stand_pat <= alpha:
            return alpha
        beta = min(beta, stand_pat)

    # Generate capture moves
    capture_moves = [
        move for move in self.board.legal_moves if self.board.is_capture(move)
    ]

    # Sort capture moves to improve pruning
    capture_moves = sorted(
        capture_moves,
        key=lambda move: self.capture_heuristic(move),
        reverse=True
    )

    # Evaluate each capture move
    for move in capture_moves:
        self.board.push(move)

        # Recursive quiescence search for the new position
        eval = self.search_captures(alpha, beta, not maximizing_player, delta)

        self.board.pop()

        # Alpha-beta pruning
        if maximizing_player:
            if eval >= beta:
                return beta
            alpha = max(alpha, eval)
        else:
            if eval <= alpha:
                return alpha
            beta = min(beta, eval)

    return alpha if maximizing_player else beta

Profiler: Normally it takes 8 seconds for this move but with profiler it took 27 seconds.

Answer 1

I looked at other python engines and it seems that it's slow in general, should I switch to C++?

The short answer is: yes C++ would solve many of your problems.

Especially for move generation, there are C++ libraries that generate around 200M positions per second, so this should make a big difference for your engine. If you do not want to switch to C++, you may benefit from storing information about the encountered positions, and perform incremental updates.

However, speed is not everything. There are some optimisations to minimax that gain as much as making the engine faster. First of all, I don't see code to handle transposition tables. It avoids searching the same positions multiple times, and will probably make your engine a lot stronger. Also, to avoid code duplication, I would advise you to switch from the minimax algorithm you are using to negamax, which is the same idea implemented more concisely.

the execution time is about the same if delta = 880(queen) but when its around 200 it halves in middle game. Don't know if it's the best approach to keep it 200

According to what you said, you seem to be estimating your engine's strength using execution time. Be aware that there is a standardized testing method called SPRT to see if a chess engine has improved: The idea is to make the newer version play a lot of games against the older version, and estimate the elo gain. SPRT is supported by fast chess or cute chess.

Also, I don't think that the exact delta value will make a large strength difference. I would rather focus on other aspects of search. For instance, here is a list of the usual optimisations.

---

Now more broadly about chess programming:

If you do not already have, I would advise you to implement the UCI protocol. This will allow your engine to communiquate with GUIs and other tools, which is very handy.

To make your engine stronger, you can also consider switching from a handcrafted evaluation function to a neural network (especially an efficiently updatable one).

Finally, reading the code of other chess engines can give you ideas.
You can also join the stockfish discord server. A lot of helpful people can answer your questions there.

I hope this helps!