4

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. – emdio Apr 7 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. – Destaq Apr 7 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. – Destaq Apr 7 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. – emdio Apr 7 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 – Destaq Apr 7 at 18:12
3
  • 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?
| improve this answer | |
  • The table is the chess board, and thank you for the answer. – Destaq Apr 7 at 18:34
  • 1
    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. – Destaq Apr 7 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. – Destaq Apr 7 at 19:26
1

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.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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