# How can I increase the search ply depth of my minimax function for my chess engine?

I have programmed a minimax function with alpha-beta pruning for a chess engine I am building. However, it is very slow and I cannot analyze to a deeper depth as it would take too much time. I believe this is because my alpha-beta pruning isn't efficient.

For example, for my engine to analyze a position to a depth of 4-ply (white moves, black moves, white moves, black moves), it takes 11.5 seconds to analyze about thirty thousand positions (taken from a middlegame chess example). Without the alpha-beta pruning, there would be about 100 000 positions, so the pruning removes 70%. Is this inefficient or is my computer just slow? And another piece of information (I don't know if this would affect the speed): the only analysis I am using is static analysis, so I count up how many points each side has in material as well as giving them a bonus of + or - 100 if there is checkmate.

From SmallChess's suggestion I have already implemented

• no deepcopy
• no shuffling
• checked generator

Below is my minimax function:

``````pose = 0
def minimax(board, depth, maximizing_player, alpha, beta): #table is board
global pose
children = list(board.legal_moves) #find all possible moves from certain position

if depth == 0 or board.is_game_over(): #don't go deeper if game over/depth ended
return calc_eval(board), None #calc-eval finds piece-values on board and adds them up. e.g. two pawns would be 2 points

if maximizing_player == True:
best_value = -float("Inf")
else:
best_value = float("Inf")

for child in children:
pose += 1
board.push(child) #copy board and change it by moving the child move
new_val = minimax(board, depth - 1, not maximizing_player, alpha, beta)[0] #recursively find value
board.pop()
if maximizing_player == True and new_val > best_value:
best_value = new_val
best_move = child
alpha = max(alpha, best_value)
if maximizing_player == False and new_val < best_value:
best_value = new_val
best_move = child
beta = min(beta, best_value)
if alpha > beta:
break

return best_value, best_move
``````
• 2 ply? That's "black moves and white moves" in chess programming slang. If you r program needs 11.5 seconds to analyze 2 ply then there's something really wrong with it. Even if you're misusing the term and you mean 2 moves (4 plys), 11 seconds is too much time. Apr 7, 2020 at 17:15
• @emdio By 2-ply I mean two entire rounds. So 11 seconds for white moves, black moves, white moves, and black moves. So I guess that means 4-ply then. Apr 7, 2020 at 17:53
• And yes, I know there is something wrong with the code. I was hoping someone more experienced could point out if it was a mistake in my function or alpha-beta implementation, etc. Apr 7, 2020 at 17:53
• Before starting with the search code I'd thoroughly test the move generator. Have you built a perft function? chessprogramming.org/Perft Until you're sure your move generator works perfectly testing it with several positions, don't start working on the search. Apr 7, 2020 at 18:05
• Isn't the search code itself the move generator? Because I am using the minimax to find the best move, and then pushing that move on the real original board. And I didn't create the move generator myself - I am using the python-chess module. I've checked and it supports en passant, castling, pawn promotion. etc Apr 7, 2020 at 18:12

• Build a cache. You're exposing yourself to endless transposition.
• Please don't shuffle your moves. I don't have the numbers but I doubt randomly shuffle all your lists can be quick. It's `O(n)`. I fail to see how it can address your repetition anyway.
• Double check your generator. Source code is not here, so I have no idea
• I don't know what exactly your `table` is, but deep copying can never be quick. Each deep copy would need to allocate some memory space. Don't copy, you need to make a move and then undo the move. In chess programming, we don't make a deep copy of the board at every node, we make a move and then undo it.
• Double check how exactly your chess board makes a move, is that efficient?
• The table is the chess board, and thank you for the answer. Apr 7, 2020 at 18:34
• I've used time.time() to see how long it takes to move a piece and calculate the evaluation, and the result is that this can be done around 2500 times per second. It seems that this may be the limiting factor in the speed of my algorithm. Perhaps I should create my own chess board movement function myself, then. Apr 7, 2020 at 18:53
• And @SmallChess as for the shuffling - I am doing that to prevent the save move from being chosen each time. For example, if I set the board to an opening state and run without shuffling, Nh3 is the output each and every time. However, if I shuffle then there are other outputs as well. Apr 7, 2020 at 19:26

I need to get two things out of the way:

1. If your are concerned about performance, Python is not for you. The language just isn't built for this kind of thing. That said, I do think it can be useful for learning/building your first engine, but it's unlikely your engine will be very strong.

2. Speed improvements for an engine come from optimizations to the search algorithm, not move generation. If you spend the next month on the move generation (without bitboards), you might get some respectable gains, but they are sure to be orders of magnitude smaller than the improvements from the search algorithm.

aside: you should use NegaMax. When I was young and naive, I decided I didn't need it, and ohhh boy was I wrong.