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

Question

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

Answer 1

• 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?

Answer 2

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.

---

That said, I will now answer your question.

1. Look at the data types you use with scrutiny. Python has a tendency to hide what's going on under the hood, and there's a signifigant difference between, for instance, lists and tuples. I'm not an expert on this, but generally use integers whenever you can.

2. Dynamic Memory Allocation = bad. SmallChess mentioned this, but I'm not sure you understood (or maybe you did) that it is about way more than just avoiding copy.deepcopy(). In essence, it takes the computer a non-trivial amount of time for the computer to store something new in memory, as opposed to modifying something else in memory. To leverage this, you have one board stored in memory, and when you make a move you just modify that one board in memory. If you aren't doing this, it's basically free speed.