Answers.Body: <ul>
  <li>Build a cache. You're exposing yourself to endless transposition.</li>
  <li>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 <code>O(n)</code>. I fail to see how it can address your repetition anyway.</li>
  <li>Double check your generator. Source code is not here, so I have no idea</li>
  <li>I don't know what exactly your <code>table</code> 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.</li>
  <li>Double check how exactly your chess board makes a move, is that efficient?</li>
  </ul>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-07T18:34:38.083Z
Answers.Text: The table is the chess board, and thank you for the answer.
Answers.UserDisplayName: Destaq
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-07T18:53:41.223Z
Answers.Text: 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.
Answers.UserDisplayName: Destaq
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-07T19:26:28.187Z
Answers.Text: 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.
Answers.UserDisplayName: Destaq
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-07T18:16:02.457Z
Answers.LastActivityDate: 2020-04-07T18:16:02.457Z
Answers.UserDisplayName: SmallChess
Answers.Body: <p>I need to get two things out of the way:</p>
  <ol>
  <li><p>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.</p>
  </li>
  <li><p>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 <em>might</em> get some respectable gains, but they are sure to be orders of magnitude smaller than the improvements from the search algorithm.</p>
  </li>
  </ol>
  <p>aside: you should use NegaMax. When I was young and naive, I decided I didn't need it, and ohhh boy was I wrong.</p>
  <hr />
  <p>That said, I will now answer your question.</p>
  <ol>
  <li><p>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.</p>
  </li>
  <li><p>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 <em>one</em> 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.</p>
  </li>
  </ol>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-16T11:44:23.450Z
Answers.LastActivityDate: 2020-10-16T11:44:23.450Z
Answers.UserDisplayName: Noah Caplinger
Body: <p>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.</p>
  
  <p>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.</p>
  
  <p><em>From SmallChess's suggestion I have already implemented</em></p>
  
  <ul>
  <li>no deepcopy</li>
  <li>no shuffling</li>
  <li>checked generator</li>
  </ul>
  
  <p>Below is my minimax function:</p>
  
  <pre><code>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 &gt; best_value:
              best_value = new_val
              best_move = child
              alpha = max(alpha, best_value)
          if maximizing_player == False and new_val &lt; best_value:
              best_value = new_val
              best_move = child
              beta = min(beta, best_value)
          if alpha &gt; beta:
              break
  
      return best_value, best_move
  </code></pre>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-04-07T17:15:31.050Z
Comments.Text: 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.
Comments.UserDisplayName: emdio
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-04-07T17:53:17.127Z
Comments.Text: @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.
Comments.UserDisplayName: Destaq
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-04-07T17:53:58.497Z
Comments.Text: 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.
Comments.UserDisplayName: Destaq
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-04-07T18:05:45.957Z
Comments.Text: Before starting with the search code I'd thoroughly test the move generator. Have you built a perft function? https://www.chessprogramming.org/Perft
  Until you're sure your move generator works perfectly testing it with several positions, don't start working on the search.
Comments.UserDisplayName: emdio
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-04-07T18:12:51.477Z
Comments.Text: 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
Comments.UserDisplayName: Destaq
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-04-07T18:20:21.767Z
Comments.Text: The move generator is the code that, given a certain position, returns all the possible legal moves that can be by the side to move. The search code uses the move generator to move up and down the tree of variations trying to find the best move (with the help of an evaluation function). https://www.chessprogramming.org/Move_Generation
Comments.UserDisplayName: emdio
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-04-07T18:33:34.667Z
Comments.Text: OK, thank you. From what I have seen, the python-chess move generator is not faulty.
Comments.UserDisplayName: Destaq
Tags: <engines><programming><python><minimax>
Title: How can I increase the search ply depth of my minimax function for my chess engine?
ThreadText: # How can I increase the search ply depth of my minimax function for my chess engine?
  
  (Asked by: username_0 on 2020-04-07)
  
  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 username_2'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
  
  **Tags:** engines, programming, python, minimax
  
  > **Comments:**
  > **username_1**: 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.  
  > **username_0**: @username_1 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.  
  > **username_0**: 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.  
  > **username_1**: Before starting with the search code I'd thoroughly test the move generator. Have you built a perft function? https://www.chessprogramming.org/Perft Until you're sure your move generator works perfectly testing it with several positions, don't start working on the search.  
  > **username_0**: 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  
  > **username_1**: The move generator is the code that, given a certain position, returns all the possible legal moves that can be by the side to move. The search code uses the move generator to move up and down the tree of variations trying to find the best move (with the help of an evaluation function). https://www.chessprogramming.org/Move_Generation  
  > **username_0**: OK, thank you. From what I have seen, the python-chess move generator is not faulty.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2020-04-07. Score: 3 | Accepted answer
  
  * 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?
  
  > **Comments:**
  > **username_0**: The table is the chess board, and thank you for the answer.  
  > **username_0**: 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.  
  > **username_0**: And @username_2 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.  
  
  ---
  
  ### Answer by username_3 on 2020-10-16. Score: 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. username_2 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.
  
  
  ---
  
  