Body: <p><strong>Problem</strong></p>
  <p>I am creating a chess engine in Python using Minimax algorithm (with alpha/beta pruning) but I have some issues with performance. Currently the thinking time looks something like this for a mid game position:</p>
  <ul>
  <li>Depth 1: 0.01 s</li>
  <li>Depth 2: 0.07 s</li>
  <li>Depth 3: 0.76 s</li>
  <li>Depth 4: 19.8 s</li>
  </ul>
  <p>I have timed each function and here are the worst performing functions, time is per move at depth 4:</p>
  <ul>
  <li>get_valid_moves (10 s)</li>
  <li>deepcopy (8 s)</li>
  <li>get_all_possible_moves (8 s)</li>
  </ul>
  <p><strong>What I have tried</strong></p>
  <p>I have tried to have the board represented as a 2D array (8x8) which is the easiest solution. With a 1D representation (10x12) I got a tiny bit better performance but not enough to increase depth.</p>
  <p><strong>What I need feedback on</strong></p>
  <p>Before I try to optimize my minimax function with transposition table lookups and such, I was hoping to have the most efficient way of calculating valid moves and all moves. Here is the process I currently use:</p>
  <ul>
  <li>Looping through 8 directions from the king location to find if I am in check and what pieces are pinned (8x8 loop)</li>
  <li>Get all possible (pseudo?) moves without considering checks or pins (8x8 loop to find all pieces on board and then add each pieces possible moves to a list)</li>
  <li>Get valid moves by seeing if I am in check or double check (removing moves from the all_possible_moves list if they are not legal)</li>
  </ul>
  <p><strong>Here is an example of how I calculate possible moves for a piece, bishop in this case:</strong></p>
  <pre><code>def get_bishop_moves(self, row, col, moves):
      piece_pinned = False
      pin_direction = ()
      for i in range(len(self.pins)-1, -1, -1):
          if self.pins[i][0] == row and self.pins[i][1] == col:
              piece_pinned = True
              pin_direction = (self.pins[i][2], self.pins[i][3])
              self.pins.remove(self.pins[i])
              break
  
      directions = [(-1, -1), (-1, 1), (1, -1), (1, 1)]
      enemy_color = 'b' if self.is_white_turn else 'w'
      for d in directions:
          for i in range(1, 8):
              end_row, end_col = row + d[0] * i, col + d[1] * i
              if all(0 &lt;= x &lt;= 7 for x in (end_row, end_col)):
                  if not piece_pinned or pin_direction == d or pin_direction == (-d[0], -d[1]):
                      end_piece = self.board[end_row][end_col]
                      if end_piece == '--':
                          moves.append((row, col), (end_row, end_col))
                      elif end_piece[0] == enemy_color:
                          moves.append((row, col), (end_row, end_col))
                          break
                      else:
                          break
              else:
                  break
  </code></pre>
  <p><strong>Board 2D respresentation:</strong></p>
  <pre><code>start_board = np.array([
              ['bR', 'bN', 'bB', 'bQ', 'bK', 'bB', 'bN', 'bR'],
              ['bp', 'bp', 'bp', 'bp', 'bp', 'bp', 'bp', 'bp'],
              ['--', '--', '--', '--', '--', '--', '--', '--'],
              ['--', '--', '--', '--', '--', '--', '--', '--'],
              ['--', '--', '--', '--', '--', '--', '--', '--'],
              ['--', '--', '--', '--', '--', '--', '--', '--'],
              ['wp', 'wp', 'wp', 'wp', 'wp', 'wp', 'wp', 'wp'],
              ['wR', 'wN', 'wB', 'wQ', 'wK', 'wB', 'wN', 'wR']])
  </code></pre>
  <p><strong>Final questions</strong></p>
  <p>Is there any way of doing the valid move generation differently (without using bitboards)? Am I overlooking something? It is not fun to work on the evaluation function when my engine doesn't reach more than depth 4... :)</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-10-15T10:14:36.453Z
Comments.Text: Welcome to our site! Unfortuantely this is focused on chess so don't expect folks over here to understand what you're talking about. A site dedicated to Math, machine learning or game theory is probably more suitable for this kind of question.
Comments.UserDisplayName: David
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-10-15T10:17:15.157Z
Comments.Text: Sorry, I thought this was a site to get help with programming as well, I will try another place! :)
Comments.UserDisplayName: eligolf
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-10-15T10:50:57.193Z
Comments.Text: @David: chess programming questions are explicitly on topic.
Comments.UserDisplayName: RemcoGerlich
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-10-15T11:04:54.717Z
Comments.Text: First things first: have you used a [perft function](https://www.chessprogramming.org/Perft) to ensure your move generator is bug free? This is quite a hard task when writing a chess engine. After you're sure you have a bug free move generator, then measure how long it takes to make it to depth 4, 5, 6... with no search function. If those values are huge, then there's something wrong with the design of the move generator itself.
Comments.UserDisplayName: emdio
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-10-15T11:12:15.237Z
Comments.Text: @emdio, I have just played it myself human vs human and tried all possible things of weird scenarios and it seems bug free. With an evaluation function of just going through the pieces on the board, assigning a value to the score, and sum it up gives me the above times for each depth
Comments.UserDisplayName: eligolf
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-10-15T11:18:01.853Z
Comments.Text: @eligolf just paying isn't enough; you must properly test it with a perft function. Besides, the thing is you could have a bug in the search function. So to be sure and give a step each time, I'd insist in building a perft function and check how fast it is. If the move generator takes "too much" time to make it to low plies, then the issue is in the move generator design.
Comments.UserDisplayName: emdio
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-10-15T11:25:06.700Z
Comments.Text: @emdio, Thank you for the advice, I will do this!
Comments.UserDisplayName: eligolf
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-10-15T11:31:39.120Z
Comments.Text: @RemcoGerlich I'm not asking for the question to be removed. They are allowed by the rules, I'm just pointing out that this may not be the best place to get an answer.
Comments.UserDisplayName: David
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-10-15T15:21:25.703Z
Comments.Text: Since you're using python maybe you want to take a look at this engine: https://github.com/thomasahle/sunfish
  Also, for hard programming chess engine questions, the place to go would be http://talkchess.com
Comments.UserDisplayName: emdio
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-10-15T18:44:26.977Z
Comments.Text: Also, its worth looking at bit boards, which can replace some of the for loops with single logic operations, which can be dozens of times faster.
Comments.UserDisplayName: Cort Ammon
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-10-16T05:47:41.620Z
Comments.Text: Cheers everyone!
Comments.UserDisplayName: eligolf
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-11-16T06:33:20.743Z
Comments.Text: If your engine has an expensive evaluation (e.g. neural net) Python is fine, but in circumstances where you want high node throughput Python is not the best choice for performance... something like C++ is much better
Comments.UserDisplayName: bcdan
Tags: <engines><candidate-move><minimax>
Title: The most efficient valid move generation for minimax
ThreadText: # The most efficient valid move generation for minimax
  
  (Asked by: username_0 on 2020-10-15)
  
  **Problem**
  
  I am creating a chess engine in Python using Minimax algorithm (with alpha/beta pruning) but I have some issues with performance. Currently the thinking time looks something like this for a mid game position:
  
  * Depth 1: 0.01 s
  * Depth 2: 0.07 s
  * Depth 3: 0.76 s
  * Depth 4: 19.8 s
  
  I have timed each function and here are the worst performing functions, time is per move at depth 4:
  
  * get\_valid\_moves (10 s)
  * deepcopy (8 s)
  * get\_all\_possible\_moves (8 s)
  
  **What I have tried**
  
  I have tried to have the board represented as a 2D array (8x8) which is the easiest solution. With a 1D representation (10x12) I got a tiny bit better performance but not enough to increase depth.
  
  **What I need feedback on**
  
  Before I try to optimize my minimax function with transposition table lookups and such, I was hoping to have the most efficient way of calculating valid moves and all moves. Here is the process I currently use:
  
  * Looping through 8 directions from the king location to find if I am in check and what pieces are pinned (8x8 loop)
  * Get all possible (pseudo?) moves without considering checks or pins (8x8 loop to find all pieces on board and then add each pieces possible moves to a list)
  * Get valid moves by seeing if I am in check or double check (removing moves from the all\_possible\_moves list if they are not legal)
  
  **Here is an example of how I calculate possible moves for a piece, bishop in this case:**
  
  ```
  def get_bishop_moves(self, row, col, moves):
      piece_pinned = False
      pin_direction = ()
      for i in range(len(self.pins)-1, -1, -1):
          if self.pins[i][0] == row and self.pins[i][1] == col:
              piece_pinned = True
              pin_direction = (self.pins[i][2], self.pins[i][3])
              self.pins.remove(self.pins[i])
              break
  
      directions = [(-1, -1), (-1, 1), (1, -1), (1, 1)]
      enemy_color = 'b' if self.is_white_turn else 'w'
      for d in directions:
          for i in range(1, 8):
              end_row, end_col = row + d[0] * i, col + d[1] * i
              if all(0 <= x <= 7 for x in (end_row, end_col)):
                  if not piece_pinned or pin_direction == d or pin_direction == (-d[0], -d[1]):
                      end_piece = self.board[end_row][end_col]
                      if end_piece == '--':
                          moves.append((row, col), (end_row, end_col))
                      elif end_piece[0] == enemy_color:
                          moves.append((row, col), (end_row, end_col))
                          break
                      else:
                          break
              else:
                  break
  
  ```
  
  **Board 2D respresentation:**
  
  ```
  start_board = np.array([
              ['bR', 'bN', 'bB', 'bQ', 'bK', 'bB', 'bN', 'bR'],
              ['bp', 'bp', 'bp', 'bp', 'bp', 'bp', 'bp', 'bp'],
              ['--', '--', '--', '--', '--', '--', '--', '--'],
              ['--', '--', '--', '--', '--', '--', '--', '--'],
              ['--', '--', '--', '--', '--', '--', '--', '--'],
              ['--', '--', '--', '--', '--', '--', '--', '--'],
              ['wp', 'wp', 'wp', 'wp', 'wp', 'wp', 'wp', 'wp'],
              ['wR', 'wN', 'wB', 'wQ', 'wK', 'wB', 'wN', 'wR']])
  
  ```
  
  **Final questions**
  
  Is there any way of doing the valid move generation differently (without using bitboards)? Am I overlooking something? It is not fun to work on the evaluation function when my engine doesn't reach more than depth 4... :)
  
  **Tags:** engines, candidate-move, minimax
  
  > **Comments:**
  > **username_1**: Welcome to our site! Unfortuantely this is focused on chess so don't expect folks over here to understand what you're talking about. A site dedicated to Math, machine learning or game theory is probably more suitable for this kind of question.  
  > **username_0**: Sorry, I thought this was a site to get help with programming as well, I will try another place! :)  
  > **username_2**: @username_1: chess programming questions are explicitly on topic.  
  > **username_3**: First things first: have you used a [perft function](https://www.chessprogramming.org/Perft) to ensure your move generator is bug free? This is quite a hard task when writing a chess engine. After you're sure you have a bug free move generator, then measure how long it takes to make it to depth 4, 5, 6... with no search function. If those values are huge, then there's something wrong with the design of the move generator itself.  
  > **username_0**: @username_3, I have just played it myself human vs human and tried all possible things of weird scenarios and it seems bug free. With an evaluation function of just going through the pieces on the board, assigning a value to the score, and sum it up gives me the above times for each depth  
  > **username_3**: @username_0 just paying isn't enough; you must properly test it with a perft function. Besides, the thing is you could have a bug in the search function. So to be sure and give a step each time, I'd insist in building a perft function and check how fast it is. If the move generator takes "too much" time to make it to low plies, then the issue is in the move generator design.  
  > **username_0**: @username_3, Thank you for the advice, I will do this!  
  > **username_1**: @username_2 I'm not asking for the question to be removed. They are allowed by the rules, I'm just pointing out that this may not be the best place to get an answer.  
  > **username_3**: Since you're using python maybe you want to take a look at this engine: https://github.com/thomasahle/sunfish Also, for hard programming chess engine questions, the place to go would be http://talkchess.com  
  > **username_4**: Also, its worth looking at bit boards, which can replace some of the for loops with single logic operations, which can be dozens of times faster.  
  > **username_0**: Cheers everyone!  
  > **username_5**: If your engine has an expensive evaluation (e.g. neural net) Python is fine, but in circumstances where you want high node throughput Python is not the best choice for performance... something like C++ is much better  
  
  ---
  
  ## 0 answers
  
  