Answers.Body: <p>If you are not yet using move ordering, I would strongly suggest you do so. Even some basic MVV-LVA helped increase my Python engine's speed by almost 500 percent. Here is some sample code if you want:</p>
  <pre><code>def OrderMoves(board, moveList):
      moveScores = []
      pieceIndexDelta = 6 * sideToMove  # given as zero or one, one for white
      for moveIndex in range(len(moveList)):
          currentMove = moveList[moveIndex]
          if move is castling:  # this is only necessary if you handle castling weirdly
              moveScores.append(0)
          elif move is promotion:
              moveScores.append(37 + promotionType)
          elif board[endSquare]:  # if move is a capture
              moveScores.append(6 * (board[endSquare] - pieceIndexDelta) -(board[startSquare] + PieceIndexDelta - 6))
          else:
              moveScores.append(0)
      return [n for _, n in sorted(zip(moveScores, moveList), reverse = True)]
  </code></pre>
  <p>This function will return the moves but sorted with good captures in front. If you have already done this I recommend you explore some more options such as null move pruning, MTD(f), iterative deepening, and quiescence search, all of which are easily accessible on Chess Programming Wiki.</p>
  <p>Edit: for this code my piece list is as follows:</p>
  <p>0: empty square<br />
  1: white pawn<br />
  2: white knight<br />
  3: white bishop<br />
  4: white rook<br />
  5: white queen<br />
  6: white king<br />
  7: black pawn<br />
  8: black knight<br />
  9: black bishop<br />
  10: black rook<br />
  11: black queen<br />
  12: black king</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-08-15T04:32:43.407Z
Answers.LastActivityDate: 2023-09-02T03:34:35.677Z
Answers.LastEditDate: 2023-09-02T03:34:35.677Z
Answers.UserDisplayName: Stockfischer
Body: <p>First, here's some context. My chess engine uses bitboards and works like this: A single gameboard is created as a 2d array at the start of the program. Like this:</p>
  <pre><code>[[-4 -2 -3 -5 -6 -3 -2 -4]
   [-1 -1 -1 -1 -1 -1 -1 -1]
   [ 0  0  0  0  0  0  0  0]
   [ 0  0  0  0  0  0  0  0]
   [ 0  0  0  0  0  0  0  0]
   [ 0  0  0  0  0  0  0  0]
   [ 1  1  1  1  1  1  1  1]
   [ 4  2  3  5  6  3  2  4]]
  </code></pre>
  <p>Where each number represents a piece. This 2d board is then converted to 12 bitboards, each representing a set of white or black pieces for each color. The possible legal moves are then generated using various bitboard techniques.</p>
  <p>Now to my question: I've written the engine in Python, and so far, the search and evaluate function (a.k.a the minimax function) can only reach a ply of 4. When I try to start going to a ply of 6, the program takes about a good 45-60 seconds to calculate the best move. Any higher ply would make the computer take too long.</p>
  <p>Is my implementation inefficient? If not, then any advice on why my engine is so slow would be appreciated. I imagined that with bitboards I could at least reach a ply of 8-12 in Python, even though it's not a very efficient language.</p>
  <p>Edit: Also yes, I'm using alpha-beta pruning.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-05-21T15:29:02.860Z
Comments.Text: Does the execution of the evaluation function take a relatively short amount of time? What about the algorythm that searches the move tree? How your board is not the only potential reason why your program is slow
Comments.UserDisplayName: David
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-05-21T16:31:42.220Z
Comments.Text: @David, yeah I understand that, but both my evaluation function and minimax function are both, from what I can see, pretty efficient. The evaluation function is just summing up a numpy array, very efficient. And the minimax function is based on the algorithm, so I imagine it's fairly efficient as well. I also already tested the move generation function and at a ply of 6, it begins working incredibly slow.
Comments.UserDisplayName: Chris
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-05-22T05:35:41.383Z
Comments.Text: Have you tried using a profiler? Do you have  a [perft function](https://www.chessprogramming.org/Perft)? (It's mainly for debugging tasks, but it's a way to compare how good your move generator is with other engines's). Don't know how efficient is python managing 2d arrays, but in other languages like C a [64 length](https://www.chessprogramming.org/8x8_Board) array seems to be preferred to represent the board.
Comments.UserDisplayName: emdio
Tags: <engines><programming><computer-chess><python>
Title: How can I make my chess engine more efficient?
ThreadText: # How can I make my chess engine more efficient?
  
  (Asked by: username_0 on 2021-05-21)
  
  First, here's some context. My chess engine uses bitboards and works like this: A single gameboard is created as a 2d array at the start of the program. Like this:
  
  ```
  [[-4 -2 -3 -5 -6 -3 -2 -4]
   [-1 -1 -1 -1 -1 -1 -1 -1]
   [ 0  0  0  0  0  0  0  0]
   [ 0  0  0  0  0  0  0  0]
   [ 0  0  0  0  0  0  0  0]
   [ 0  0  0  0  0  0  0  0]
   [ 1  1  1  1  1  1  1  1]
   [ 4  2  3  5  6  3  2  4]]
  
  ```
  
  Where each number represents a piece. This 2d board is then converted to 12 bitboards, each representing a set of white or black pieces for each color. The possible legal moves are then generated using various bitboard techniques.
  
  Now to my question: I've written the engine in Python, and so far, the search and evaluate function (a.k.a the minimax function) can only reach a ply of 4. When I try to start going to a ply of 6, the program takes about a good 45-60 seconds to calculate the best move. Any higher ply would make the computer take too long.
  
  Is my implementation inefficient? If not, then any advice on why my engine is so slow would be appreciated. I imagined that with bitboards I could at least reach a ply of 8-12 in Python, even though it's not a very efficient language.
  
  Edit: Also yes, I'm using alpha-beta pruning.
  
  **Tags:** engines, programming, computer-chess, python
  
  > **Comments:**
  > **username_1**: Does the execution of the evaluation function take a relatively short amount of time? What about the algorythm that searches the move tree? How your board is not the only potential reason why your program is slow  
  > **username_0**: @username_1, yeah I understand that, but both my evaluation function and minimax function are both, from what I can see, pretty efficient. The evaluation function is just summing up a numpy array, very efficient. And the minimax function is based on the algorithm, so I imagine it's fairly efficient as well. I also already tested the move generation function and at a ply of 6, it begins working incredibly slow.  
  > **username_2**: Have you tried using a profiler? Do you have  a [perft function](https://www.chessprogramming.org/Perft)? (It's mainly for debugging tasks, but it's a way to compare how good your move generator is with other engines's). Don't know how efficient is python managing 2d arrays, but in other languages like C a [64 length](https://www.chessprogramming.org/8x8_Board) array seems to be preferred to represent the board.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_3 on 2023-08-15. Score: 1
  
  If you are not yet using move ordering, I would strongly suggest you do so. Even some basic MVV-LVA helped increase my Python engine's speed by almost 500 percent. Here is some sample code if you want:
  
  ```
  def OrderMoves(board, moveList):
      moveScores = []
      pieceIndexDelta = 6 * sideToMove  # given as zero or one, one for white
      for moveIndex in range(len(moveList)):
          currentMove = moveList[moveIndex]
          if move is castling:  # this is only necessary if you handle castling weirdly
              moveScores.append(0)
          elif move is promotion:
              moveScores.append(37 + promotionType)
          elif board[endSquare]:  # if move is a capture
              moveScores.append(6 * (board[endSquare] - pieceIndexDelta) -(board[startSquare] + PieceIndexDelta - 6))
          else:
              moveScores.append(0)
      return [n for _, n in sorted(zip(moveScores, moveList), reverse = True)]
  
  ```
  
  This function will return the moves but sorted with good captures in front. If you have already done this I recommend you explore some more options such as null move pruning, MTD(f), iterative deepening, and quiescence search, all of which are easily accessible on Chess Programming Wiki.
  
  Edit: for this code my piece list is as follows:
  
  0: empty square  
  1: white pawn  
  2: white knight  
  3: white bishop  
  4: white rook  
  5: white queen  
  6: white king  
  7: black pawn  
  8: black knight  
  9: black bishop  
  10: black rook  
  11: black queen  
  12: black king
  
  
  ---
  
  