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) #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