Answers.Body: <h2>Iterate on the search by increasing search depth.</h2>
  <p>Also find a way to save the principal variation from your search or minimax.</p>
  <pre><code># Iterative deepening
  def iterative_deepening(board, max_depth):
      global ply
  
      t1 = time.perf_counter()
  
      for depth in range(1, max_depth + 1):
          ply = 0
  
          eval, pvs = minimax(board, depth, INIT_ALPHA, INIT_BETA, board.turn)
  
          t2 = time.perf_counter()
          elapse_ms = int((t2 - t1) * 1000)
  
          print(f&quot;depth {depth} score cp {int(eval)} time {elapse_ms} pv {' '.join([m.uci() for m in pvs])}&quot;)
  
      return pvs[0].uci()
  
  
  # Example usage
  if __name__ == &quot;__main__&quot;:
      fen = '2k5/7Q/1K6/8/8/8/8/8 w - - 0 1'  # mate in 1, Qc7
      fen = 'Q7/8/8/5p2/3r1k2/8/4K3/6q1 b - - 0 1'  # mate in 2, Qd1
  
      fen = chess.STARTING_FEN
      board = chess.Board(fen)
  
      max_depth = 8
      best_move = iterative_deepening(board, max_depth)
      print(f'bestmove {best_move}')
  </code></pre>
  <h3>Sample output</h3>
  <pre><code>depth 1 score cp 56 time 3 pv e2e3
  depth 2 score cp 0 time 25 pv e2e3 e7e6
  depth 3 score cp 85 time 249 pv e2e3 e7e6 d1g4
  depth 4 score cp 8 time 1998 pv e2e3 g8f6 b1c3 b8c6
  depth 5 score cp 29 time 25516 pv g1f3 d7d5 d2d4 d8d6 d1d3
  bestmove g1f3
  </code></pre>
  <h2>Optimize evaluation</h2>
  <pre><code>def evaluate_board(board):
      &quot;&quot;&quot;
      Evaluate the chess position based on the material difference and the positions of the pieces.
      &quot;&quot;&quot;
      # Calculate the material difference
      material_difference = 0
  
      # Calculate positional bonuses
      positional_bonus = 0
  
      for square in chess.SQUARES:
          piece = board.piece_at(square)
          if piece:
              material_difference += piece_values_list[piece.piece_type] * (1 if piece.color == chess.WHITE else -1)
  
              rank, file = chess.square_rank(square), chess.square_file(square)
              positional_bonus += positional_bonuses[piece.piece_type].get((rank, file), 0) * (0.3 if piece.color == chess.WHITE else -0.3)
  
              material_difference += len(board.attacks(square)) * (1 if piece == chess.KING else 8) * (1 if piece.color == chess.WHITE else -1)
  
      return material_difference + positional_bonus
  </code></pre>
  <h2>Testing</h2>
  <p>Test your engine if it can solve mate in 1 or 2 positions.</p>
  <h2>Add uci protocol</h2>
  <p>Add uci protocol to allow it to play against other engines.</p>
  <h2>Code profiling</h2>
  <p>Profile your code to see where the bottlenecks where.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-06-03T17:04:42.683Z
Answers.Text: Thank you so much! I will try to implement these mechanisms as much as possible. May I ask why simply evaluating the material difference is sufficient enough? Also, do I need a specific function to check whether black's move at depth 0 is a fake threat?
Answers.UserDisplayName: Chris Wong
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-06-03T19:17:16.390Z
Answers.Text: Sufficient enough with respect to what?
  Checkmate and stalemate are usually handled in the search or in your case minimax. Position evaluation are usually called at the leaf for quiet positions. Checkmate, stalemate, repetitions, fifty-move draw rule must be handled in the search, so that it can reject lines / variation that leads to unfavorable positions quickly without calling an expensive static evaluation.
Answers.UserDisplayName: ferdy
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-06-03T16:03:06.643Z
Answers.LastActivityDate: 2024-06-03T16:03:06.643Z
Answers.UserDisplayName: ferdy
Body: <p>I am building a chess engine in python, as a project for school.
  I am required not to use any engines of course, but I am allowed to use the chess module. The code I tried to develop uses a rough evaluation, minimax, and alpha beta pruning. It is currently very slow with only up to 6 ply, I am not sure how to enhance it and what moves to prune further.</p>
  <pre><code>import chess
  import random
  import math
  import time
  
  timer = 0
  black_move = 0
  
  # Define piece values in a dictionary
  piece_values = {
      chess.PAWN: 100,
      chess.KNIGHT: 320,
      chess.BISHOP: 330,
      chess.ROOK: 500,
      chess.QUEEN: 900,
      chess.KING: 20000
  }
  
  # Pre-calculate the piece values for efficiency
  piece_values_list = [0] + list(piece_values.values())
  
  # Define positional bonuses for pieces
  positional_bonuses = {
      chess.PAWN: {
          # Center control
          (0, 3): 10, (0, 4): 10, (7, 3): 10, (7, 4): 10,
          # Open files
          (1, 0): 5, (1, 7): 5, (6, 0): 5, (6, 7): 5,
          # Passed pawn bonus
          (0, 0): 10, (0, 7): 10, (7, 0): 10, (7, 7): 10,
      },
      chess.KNIGHT: {
          # Center control
          (0, 3): 10, (0, 4): 10, (7, 3): 10, (7, 4): 10,
          # Open files
          (1, 0): 5, (1, 7): 5, (6, 0): 5, (6, 7): 5,
          # Outpost bonus
          (2, 1): 10, (2, 6): 10, (5, 1): 10, (5, 6): 10,
      },
      chess.BISHOP: {
          # Center control
          (0, 3): 10, (0, 4): 10, (7, 3): 10, (7, 4): 10,
          # Open diagonals
          (0, 0): 5, (0, 7): 5, (7, 0): 5, (7, 7): 5,
      },
      chess.ROOK: {
          # Open files
          (1, 0): 10, (1, 7): 10, (6, 0): 10, (6, 7): 10,
          # Semi-open files
          (2, 0): 5, (2, 7): 5, (5, 0): 5, (5, 7): 5,
      },
      chess.QUEEN: {
          # Center control
          (0, 3): 10, (0, 4): 10, (7, 3): 10, (7, 4): 10,
      },
      chess.KING: {
          # Center control
          (0, 3): 10, (0, 4): 10, (7, 3): 10, (7, 4): 10,
          # End game bonus
          (0, 0): 10, (0, 7): 10, (7, 0): 10, (7, 7): 10,
      }
  }
  
  def evaluate_position(board):
      &quot;&quot;&quot;
      Evaluate the chess position based on the material difference and the positions of the pieces.
      &quot;&quot;&quot;
      # Check for checkmate or stalemate
      if board.is_checkmate():
          return 100000 if board.turn == chess.WHITE else -100000
      if board.is_stalemate():
          return 0
  
      # Calculate the material difference
      material_difference = 0
      for square in chess.SQUARES:
          piece = board.piece_at(square)
          if piece:
              material_difference += piece_values_list[piece.piece_type] * (1 if piece.color == chess.WHITE else -1)
  
      # Calculate positional bonuses
      positional_bonus = 0
      for square in chess.SQUARES:
          piece = board.piece_at(square)
          if piece:
              rank, file = chess.square_rank(square), chess.square_file(square)
              positional_bonus += positional_bonuses[piece.piece_type].get((rank, file), 0) * (0.3 if piece.color == chess.WHITE else -0.3)
  
      # Add a small bonus for pieces that attack more squares
      for square in chess.SQUARES:
          piece = board.piece_at(square)
          if piece:
              material_difference += len(board.attacks(square)) * (1 if piece == chess.KING else 8) * (1 if piece.color == chess.WHITE else -1)
  
      return material_difference + positional_bonus
  
  def minimax(board, depth, alpha, beta, maximizing_player):
      &quot;&quot;&quot;
      Recursively evaluate the chess position using the minimax algorithm with alpha-beta pruning.
      &quot;&quot;&quot;
      # Check for game over or depth limit
      if depth == 0 or board.is_game_over():
          return evaluate_position(board)
  
      # Use a single loop for both maximizing and minimizing players
      best_eval = float('-inf') if maximizing_player else float('inf')
      best_move = None
      for move in board.legal_moves:
          new_board = board.copy()
          new_board.push(move)
          eval = minimax(new_board, depth - 1, alpha, beta, not maximizing_player)
          if maximizing_player:
              if eval &gt; best_eval:
                  best_eval = eval
                  best_move = move
              alpha = max(alpha, eval)
          else:
              if eval &lt; best_eval:
                  best_eval = eval
                  best_move = move
              beta = min(beta, eval)
          if beta &lt;= alpha:
              break
  
      return best_eval
  
  def rank_moves(board):
      &quot;&quot;&quot;
      Rank moves based on capture value, attack value, and check status.
      &quot;&quot;&quot;
      ranked_moves = []
      for move in board.legal_moves:
          new_board = board.copy()
          new_board.push(move)
          # Capture value
          capture_value = 0
          if new_board.is_capture(move):
              capture_value = piece_values_list[new_board.piece_at(move.to_square).piece_type]
          # Attack value
          attack_value = 0
          for square in new_board.attacks(move.to_square):
              if new_board.piece_at(square) is not None:
                  attack_value += piece_values_list[new_board.piece_at(square).piece_type]
          # Check status
          check_value = 0
          if new_board.is_check():
              check_value = 1000
          ranked_moves.append((move, capture_value + attack_value + check_value))
      ranked_moves.sort(key=lambda x: x[1], reverse=True)
      return ranked_moves
  
  def find_best_move(board, depth):
      &quot;&quot;&quot;
      Find the best move for the current player using the minimax algorithm with alpha-beta pruning.
      &quot;&quot;&quot;
      best_move = None
      best_eval = float('-inf')
      # Get the number of legal moves
      num_moves = len(list(board.legal_moves))
      # Initialize progress bar variables
      progress = 0
      bar_length = 20
      print(&quot;Evaluating moves: &quot;, end=&quot;&quot;)
      # Rank moves based on capture, attack, and check
      ranked_moves = rank_moves(board)
      # Evaluate top 10 moves with depth 6, others with depth 4
      for i, (move, _) in enumerate(ranked_moves):
          new_board = board.copy()
          new_board.push(move)
          if i &lt; 3:
              eval = minimax(new_board, depth - 1, float('-inf'), float('inf'), board.turn == chess.BLACK)
          else:
              eval = minimax(new_board, depth - 3, float('-inf'), float('inf'), board.turn == chess.BLACK)
          if eval &gt; best_eval:
              best_eval = eval
              best_move = move
          # Update progress bar
          progress += 1
          filled_length = int(progress / num_moves * bar_length)
          bar = &quot;[&quot; + &quot;#&quot; * filled_length + &quot; &quot; * (bar_length - filled_length) + &quot;]&quot;
          print(f&quot;\rEvaluating moves: {bar} {progress}/{num_moves}&quot;, end=&quot;&quot;)
      print()
      return [best_move, best_eval]
  
  # Example usage
  board = chess.Board()
  
  while not board.is_game_over():
      # Find the best move for White
      start_time = time.time()
      best_move = find_best_move(board, depth=6)
      end_time = time.time()
      print(f&quot;Time taken: {end_time - start_time:.2f} seconds&quot;)
      board.push(best_move[0])
      print(f&quot;White played: {best_move[0]}&quot;)
      print(best_move[1]/100)
      print(board)
      print()
  
      # Black can play a random move for now
      while black_move not in board.legal_moves:
          black_move = board.parse_san(input('Your move: '))
      board.push(black_move)
      print(f&quot;Black played: {black_move}&quot;)
  
      print(board)
      print()
  </code></pre>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-06-06T16:31:58.387Z
Comments.Text: Python is just too slow to produce a production-quality chess engine. There is nothing you can do about this. But it sounds like a fun project, and I'm sure you will learn a lot from it.
Comments.UserDisplayName: TonyK
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-06-29T14:47:56.860Z
Comments.Text: Python is actually adapted for a human strength chess engine. Consider using alpha-beta in negamax way, with quiescence search, move ordering, transposition table and null-move pruning. Refers to chess programming.org.
Comments.UserDisplayName: LittleCoder
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-07-03T21:04:53.110Z
Comments.Text: @TonyK you can get a decent speedup with PyPy, although it'll still be nowhere as fast as C++ or Rust.
Comments.UserDisplayName: qwr
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-07-03T21:07:01.583Z
Comments.Text: You can also post your engine at codereview.stackexchange.com for feedback.
Comments.UserDisplayName: qwr
Tags: <engines><programming>
Title: Help for Building a Chess Engine in Python
ThreadText: # Help for Building a Chess Engine in Python
  
  (Asked by: username_0 on 2024-06-01)
  
  I am building a chess engine in python, as a project for school.
  I am required not to use any engines of course, but I am allowed to use the chess module. The code I tried to develop uses a rough evaluation, minimax, and alpha beta pruning. It is currently very slow with only up to 6 ply, I am not sure how to enhance it and what moves to prune further.
  
  ```
  import chess
  import random
  import math
  import time
  
  timer = 0
  black_move = 0
  
  # Define piece values in a dictionary
  piece_values = {
      chess.PAWN: 100,
      chess.KNIGHT: 320,
      chess.BISHOP: 330,
      chess.ROOK: 500,
      chess.QUEEN: 900,
      chess.KING: 20000
  }
  
  # Pre-calculate the piece values for efficiency
  piece_values_list = [0] + list(piece_values.values())
  
  # Define positional bonuses for pieces
  positional_bonuses = {
      chess.PAWN: {
          # Center control
          (0, 3): 10, (0, 4): 10, (7, 3): 10, (7, 4): 10,
          # Open files
          (1, 0): 5, (1, 7): 5, (6, 0): 5, (6, 7): 5,
          # Passed pawn bonus
          (0, 0): 10, (0, 7): 10, (7, 0): 10, (7, 7): 10,
      },
      chess.KNIGHT: {
          # Center control
          (0, 3): 10, (0, 4): 10, (7, 3): 10, (7, 4): 10,
          # Open files
          (1, 0): 5, (1, 7): 5, (6, 0): 5, (6, 7): 5,
          # Outpost bonus
          (2, 1): 10, (2, 6): 10, (5, 1): 10, (5, 6): 10,
      },
      chess.BISHOP: {
          # Center control
          (0, 3): 10, (0, 4): 10, (7, 3): 10, (7, 4): 10,
          # Open diagonals
          (0, 0): 5, (0, 7): 5, (7, 0): 5, (7, 7): 5,
      },
      chess.ROOK: {
          # Open files
          (1, 0): 10, (1, 7): 10, (6, 0): 10, (6, 7): 10,
          # Semi-open files
          (2, 0): 5, (2, 7): 5, (5, 0): 5, (5, 7): 5,
      },
      chess.QUEEN: {
          # Center control
          (0, 3): 10, (0, 4): 10, (7, 3): 10, (7, 4): 10,
      },
      chess.KING: {
          # Center control
          (0, 3): 10, (0, 4): 10, (7, 3): 10, (7, 4): 10,
          # End game bonus
          (0, 0): 10, (0, 7): 10, (7, 0): 10, (7, 7): 10,
      }
  }
  
  def evaluate_position(board):
      """
      Evaluate the chess position based on the material difference and the positions of the pieces.
      """
      # Check for checkmate or stalemate
      if board.is_checkmate():
          return 100000 if board.turn == chess.WHITE else -100000
      if board.is_stalemate():
          return 0
  
      # Calculate the material difference
      material_difference = 0
      for square in chess.SQUARES:
          piece = board.piece_at(square)
          if piece:
              material_difference += piece_values_list[piece.piece_type] * (1 if piece.color == chess.WHITE else -1)
  
      # Calculate positional bonuses
      positional_bonus = 0
      for square in chess.SQUARES:
          piece = board.piece_at(square)
          if piece:
              rank, file = chess.square_rank(square), chess.square_file(square)
              positional_bonus += positional_bonuses[piece.piece_type].get((rank, file), 0) * (0.3 if piece.color == chess.WHITE else -0.3)
  
      # Add a small bonus for pieces that attack more squares
      for square in chess.SQUARES:
          piece = board.piece_at(square)
          if piece:
              material_difference += len(board.attacks(square)) * (1 if piece == chess.KING else 8) * (1 if piece.color == chess.WHITE else -1)
  
      return material_difference + positional_bonus
  
  def minimax(board, depth, alpha, beta, maximizing_player):
      """
      Recursively evaluate the chess position using the minimax algorithm with alpha-beta pruning.
      """
      # Check for game over or depth limit
      if depth == 0 or board.is_game_over():
          return evaluate_position(board)
  
      # Use a single loop for both maximizing and minimizing players
      best_eval = float('-inf') if maximizing_player else float('inf')
      best_move = None
      for move in board.legal_moves:
          new_board = board.copy()
          new_board.push(move)
          eval = minimax(new_board, depth - 1, alpha, beta, not maximizing_player)
          if maximizing_player:
              if eval > best_eval:
                  best_eval = eval
                  best_move = move
              alpha = max(alpha, eval)
          else:
              if eval < best_eval:
                  best_eval = eval
                  best_move = move
              beta = min(beta, eval)
          if beta <= alpha:
              break
  
      return best_eval
  
  def rank_moves(board):
      """
      Rank moves based on capture value, attack value, and check status.
      """
      ranked_moves = []
      for move in board.legal_moves:
          new_board = board.copy()
          new_board.push(move)
          # Capture value
          capture_value = 0
          if new_board.is_capture(move):
              capture_value = piece_values_list[new_board.piece_at(move.to_square).piece_type]
          # Attack value
          attack_value = 0
          for square in new_board.attacks(move.to_square):
              if new_board.piece_at(square) is not None:
                  attack_value += piece_values_list[new_board.piece_at(square).piece_type]
          # Check status
          check_value = 0
          if new_board.is_check():
              check_value = 1000
          ranked_moves.append((move, capture_value + attack_value + check_value))
      ranked_moves.sort(key=lambda x: x[1], reverse=True)
      return ranked_moves
  
  def find_best_move(board, depth):
      """
      Find the best move for the current player using the minimax algorithm with alpha-beta pruning.
      """
      best_move = None
      best_eval = float('-inf')
      # Get the number of legal moves
      num_moves = len(list(board.legal_moves))
      # Initialize progress bar variables
      progress = 0
      bar_length = 20
      print("Evaluating moves: ", end="")
      # Rank moves based on capture, attack, and check
      ranked_moves = rank_moves(board)
      # Evaluate top 10 moves with depth 6, others with depth 4
      for i, (move, _) in enumerate(ranked_moves):
          new_board = board.copy()
          new_board.push(move)
          if i < 3:
              eval = minimax(new_board, depth - 1, float('-inf'), float('inf'), board.turn == chess.BLACK)
          else:
              eval = minimax(new_board, depth - 3, float('-inf'), float('inf'), board.turn == chess.BLACK)
          if eval > best_eval:
              best_eval = eval
              best_move = move
          # Update progress bar
          progress += 1
          filled_length = int(progress / num_moves * bar_length)
          bar = "[" + "#" * filled_length + " " * (bar_length - filled_length) + "]"
          print(f"\rEvaluating moves: {bar} {progress}/{num_moves}", end="")
      print()
      return [best_move, best_eval]
  
  # Example usage
  board = chess.Board()
  
  while not board.is_game_over():
      # Find the best move for White
      start_time = time.time()
      best_move = find_best_move(board, depth=6)
      end_time = time.time()
      print(f"Time taken: {end_time - start_time:.2f} seconds")
      board.push(best_move[0])
      print(f"White played: {best_move[0]}")
      print(best_move[1]/100)
      print(board)
      print()
  
      # Black can play a random move for now
      while black_move not in board.legal_moves:
          black_move = board.parse_san(input('Your move: '))
      board.push(black_move)
      print(f"Black played: {black_move}")
  
      print(board)
      print()
  
  ```
  
  **Tags:** engines, programming
  
  > **Comments:**
  > **username_1**: Python is just too slow to produce a production-quality chess engine. There is nothing you can do about this. But it sounds like a fun project, and I'm sure you will learn a lot from it.  
  > **username_2**: Python is actually adapted for a human strength chess engine. Consider using alpha-beta in negamax way, with quiescence search, move ordering, transposition table and null-move pruning. Refers to chess programming.org.  
  > **username_3**: @username_1 you can get a decent speedup with PyPy, although it'll still be nowhere as fast as C++ or Rust.  
  > **username_3**: You can also post your engine at codereview.stackexchange.com for feedback.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_4 on 2024-06-03. Score: 0
  
  ## Iterate on the search by increasing search depth.
  
  Also find a way to save the principal variation from your search or minimax.
  
  ```
  # Iterative deepening
  def iterative_deepening(board, max_depth):
      global ply
  
      t1 = time.perf_counter()
  
      for depth in range(1, max_depth + 1):
          ply = 0
  
          eval, pvs = minimax(board, depth, INIT_ALPHA, INIT_BETA, board.turn)
  
          t2 = time.perf_counter()
          elapse_ms = int((t2 - t1) * 1000)
  
          print(f"depth {depth} score cp {int(eval)} time {elapse_ms} pv {' '.join([m.uci() for m in pvs])}")
  
      return pvs[0].uci()
  
  # Example usage
  if __name__ == "__main__":
      fen = '2k5/7Q/1K6/8/8/8/8/8 w - - 0 1'  # mate in 1, Qc7
      fen = 'Q7/8/8/5p2/3r1k2/8/4K3/6q1 b - - 0 1'  # mate in 2, Qd1
  
      fen = chess.STARTING_FEN
      board = chess.Board(fen)
  
      max_depth = 8
      best_move = iterative_deepening(board, max_depth)
      print(f'bestmove {best_move}')
  
  ```
  
  ### Sample output
  
  ```
  depth 1 score cp 56 time 3 pv e2e3
  depth 2 score cp 0 time 25 pv e2e3 e7e6
  depth 3 score cp 85 time 249 pv e2e3 e7e6 d1g4
  depth 4 score cp 8 time 1998 pv e2e3 g8f6 b1c3 b8c6
  depth 5 score cp 29 time 25516 pv g1f3 d7d5 d2d4 d8d6 d1d3
  bestmove g1f3
  
  ```
  
  ## Optimize evaluation
  
  ```
  def evaluate_board(board):
      """
      Evaluate the chess position based on the material difference and the positions of the pieces.
      """
      # Calculate the material difference
      material_difference = 0
  
      # Calculate positional bonuses
      positional_bonus = 0
  
      for square in chess.SQUARES:
          piece = board.piece_at(square)
          if piece:
              material_difference += piece_values_list[piece.piece_type] * (1 if piece.color == chess.WHITE else -1)
  
              rank, file = chess.square_rank(square), chess.square_file(square)
              positional_bonus += positional_bonuses[piece.piece_type].get((rank, file), 0) * (0.3 if piece.color == chess.WHITE else -0.3)
  
              material_difference += len(board.attacks(square)) * (1 if piece == chess.KING else 8) * (1 if piece.color == chess.WHITE else -1)
  
      return material_difference + positional_bonus
  
  ```
  
  ## Testing
  
  Test your engine if it can solve mate in 1 or 2 positions.
  
  ## Add uci protocol
  
  Add uci protocol to allow it to play against other engines.
  
  ## Code profiling
  
  Profile your code to see where the bottlenecks where.
  
  > **Comments:**
  > **username_0**: Thank you so much! I will try to implement these mechanisms as much as possible. May I ask why simply evaluating the material difference is sufficient enough? Also, do I need a specific function to check whether black's move at depth 0 is a fake threat?  
  > **username_4**: Sufficient enough with respect to what? Checkmate and stalemate are usually handled in the search or in your case minimax. Position evaluation are usually called at the leaf for quiet positions. Checkmate, stalemate, repetitions, fifty-move draw rule must be handled in the search, so that it can reject lines / variation that leads to unfavorable positions quickly without calling an expensive static evaluation.  
  
  ---
  
  