Answers.Body: <p>Be also careful with the first call with negamax you negate the alpha and beta. There is no negative value for INT_MIN, often -INT_MIN becomes INT_MIN, so wrong values are passed and thus resulting in returning different things.
  Thus use -INT_MAX or INT_MIN+1, as initial lower bound.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-06-14T08:41:48.653Z
Answers.LastActivityDate: 2024-06-14T08:41:48.653Z
Answers.UserDisplayName: Jimmy Venema
Answers.Body: <p>I believe i found the issue <code>alpha = max(alpha, value)</code> should be <code>alpha = max(alpha, best_value)</code>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-24T21:43:07.320Z
Answers.Text: Hi, thanks for your answer but this had no effect on it, same output
Answers.UserDisplayName: user24551772
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-24T13:25:17.853Z
Answers.LastActivityDate: 2024-04-24T13:42:16.983Z
Answers.LastEditDate: 2024-04-24T13:42:16.983Z
Answers.UserDisplayName: Sheyteo
Body: <p>I've made a decently simple chess engine so far and I'm running into a problem related to the chess engine thinking it found mate and playing those moves despite it not having a forced mate.</p>
  <p>This occurs in the fen: <code>1R6/Pn6/K6p/7P/8/4NNp1/6P1/7k w - - 0 1</code>, at <code>depth: 7</code>. There is a checkmate that can be seen at this depth, but only one. (Knight Promotion, a7a8N). However, my engine finds multiple moves that &quot;mate&quot; in this depth even though they don't.</p>
  <p>As far as I understand, alpha-beta pruning does not affect the result compared to not using it so it shouldn't think that all these moves are mate. The weird thing here is that the entire thing can be fixed by commenting two lines of code that do the alpha-beta pruning, however, this makes the code insanely slow to make a move (10+ minutes) and I need to have alpha-beta pruning to make the engine reasonable.</p>
  <p>Here is the code for the engine, along with some print statements I used to debug:</p>
  <pre><code>import time
  
  from .move_gen import move_gen, get_pins_and_checks
  from .evaluate import evaluate
  from .board import Board
  from .move import Move
  from .constants import MATE_SCORE
  
  
  class Engine:
      def search(self, board: Board) -&gt; Move | None:
          start = time.time()
          self.tt = {}
  
          eval = self.negamax(board, 7, float(&quot;-inf&quot;), float(&quot;inf&quot;))
  
          # format eval
          eval = eval if board.white_move else -eval  # switch from perspective of engine to perspective of white
          eval_output = f&quot;+{eval}&quot; if eval &gt;= 0 else str(eval)  # add positive and negative signs + convert to string
  
          print(f&quot;Time: {round(time.time() - start, 3)}s - Eval: {eval_output}&quot;)
  
          return self.tt.get(board.zobrist, {&quot;move&quot;: None})[&quot;move&quot;]
  
      def move_value(self, move: Move) -&gt; int:
          if move.prom:
              return 1
          elif move.capture:
              return 1
          return 2
  
      def negamax(self, board: Board, depth: int, alpha: float, beta: float, ply: int = 0) -&gt; float:
          # get and sort moves
          moves = move_gen(board)
          moves = sorted(moves, key=lambda x: self.move_value(x))
  
          if len(moves) == 0:
              # determine if in check
              king = &quot;K&quot; if board.white_move else &quot;k&quot;
              king_pos = board.board.index(king)
              in_check, _, _ = get_pins_and_checks(board.board, board.white_move, king_pos)
  
              # if in check with no moves -&gt; checkmate -&gt; return super low score
              if in_check:
                  return -MATE_SCORE + ply
              # not in check with no moves -&gt; stalemate -&gt; draw
              else:
                  if ply == 1:
                      print(&quot;Best Response: No Moves - Best Value: Stalemate -&gt; 0&quot;)
                  return 0
  
          if depth == 0:
              return evaluate(board)
  
          best_value = float(&quot;-inf&quot;)
          best_move = None
  
          for move in moves:
              if ply == 0:
                  print(f&quot;----- Move {move} -----&quot;)
  
              board.make(move)
              value = -self.negamax(board, depth - 1, -beta, -alpha, ply + 1)
              board.unmake(move)
  
              if value &gt;= best_value:
                  best_value = value
                  best_move = move
  
              alpha = max(alpha, value)
  
              if alpha &gt;= beta:
                  break
  
          if ply == 1:
              print(f&quot;Best Response: {best_move} - Best Value: {best_value}&quot;)
  
          # store in transposition table
          self.tt[board.zobrist] = {&quot;depth&quot;: depth, &quot;value&quot;: best_value, &quot;move&quot;: best_move}
  
          return best_value
  </code></pre>
  <p>When I run this code I get the following output:</p>
  <pre><code>----- Move b8b7 -----
  Best Response: No Moves - Best Value: Stalemate -&gt; 0
  ----- Move a7a8B -----
  Best Response: b7a5 - Best Value: -1332
  ----- Move a7a8N -----
  Best Response: b7d6 - Best Value: -99993
  ----- Move a7a8R -----
  Best Response: b7c5 - Best Value: -99993
  ----- Move a7a8Q -----
  Best Response: b7c5 - Best Value: -99993
  ----- Move a6b7 -----
  Best Response: No Moves - Best Value: Stalemate -&gt; 0
  ----- Move b8c8 -----
  Best Response: b7c5 - Best Value: -99993
  ----- Move b8d8 -----
  Best Response: b7d8 - Best Value: -99993
  ----- Move b8e8 -----
  Best Response: b7c5 - Best Value: -99993
  ----- Move b8f8 -----
  Best Response: b7c5 - Best Value: -99993
  ----- Move b8g8 -----
  Best Response: b7c5 - Best Value: -99993
  ----- Move b8h8 -----
  Best Response: b7c5 - Best Value: -99993
  ----- Move b8a8 -----
  Best Response: b7c5 - Best Value: -99993
  ----- Move a6b6 -----
  Best Response: b7c5 - Best Value: -99993
  ----- Move a6b5 -----
  Best Response: b7c5 - Best Value: -99993
  ----- Move e3f5 -----
  Best Response: h1g2 - Best Value: -99993
  ----- Move e3d5 -----
  Best Response: h1g2 - Best Value: -1966
  ----- Move e3f1 -----
  Best Response: h1g2 - Best Value: -1716
  ----- Move e3d1 -----
  Best Response: h1g2 - Best Value: -1880
  ----- Move e3g4 -----
  Best Response: h1g2 - Best Value: -99993
  ----- Move e3c4 -----
  Best Response: h1g2 - Best Value: -1929
  ----- Move e3c2 -----
  Best Response: h1g2 - Best Value: -1930
  ----- Move f3g5 -----
  Best Response: h6g5 - Best Value: -1873
  ----- Move f3e5 -----
  Best Response: b7c5 - Best Value: -99993
  ----- Move f3g1 -----
  Best Response: h1g1 - Best Value: -1810
  ----- Move f3e1 -----
  Best Response: b7c5 - Best Value: -99993
  ----- Move f3h4 -----
  Best Response: b7c5 - Best Value: -99993
  ----- Move f3h2 -----
  Best Response: g3h2 - Best Value: -99993
  ----- Move f3d4 -----
  Best Response: b7c5 - Best Value: -99993
  ----- Move f3d2 -----
  Best Response: b7c5 - Best Value: -99993
  Time: 16.259s - Eval: +99993
  </code></pre>
  <p>As seen by the output, the engine finds the mate at the move it should, but it also finds many other moves that the opponent has a best value of still a checkmate(as seen by -99993, because -100000 is MATE_SCORE).</p>
  <p>The lines that removing fixes it are, but as mentioned earlier make it way too slow:</p>
  <pre><code>if alpha &gt;= beta:
     break
  </code></pre>
  <p>I've simplified the code as much as I can, which is why there is a transposition table that the cutoffs are not being used.</p>
  <p>So in conclusion, the engine finds a bunch of moves that lead to a forced checkmate, even though it should only find one. Removing alpha-beta pruning fixes that, but makes it way too slow.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-05-28T19:11:59.373Z
Comments.Text: Maybe try if alpha >= beta: return beta? Probably won't help though.
Comments.UserDisplayName: Hank's back rank
Tags: <python>
Title: Fix Alpha-Beta Pruning in Chess Negamax Algorithm
ThreadText: # Fix Alpha-Beta Pruning in Chess Negamax Algorithm
  
  (Asked by: username_0 on 2024-04-22)
  
  I've made a decently simple chess engine so far and I'm running into a problem related to the chess engine thinking it found mate and playing those moves despite it not having a forced mate.
  This occurs in the fen: 1R6/Pn6/K6p/7P/8/4NNp1/6P1/7k w - - 0 1, at depth: 7. There is a checkmate that can be seen at this depth, but only one. (Knight Promotion, a7a8N). However, my engine finds multiple moves that "mate" in this depth even though they don't.
  As far as I understand, alpha-beta pruning does not affect the result compared to not using it so it shouldn't think that all these moves are mate. The weird thing here is that the entire thing can be fixed by commenting two lines of code that do the alpha-beta pruning, however, this makes the code insanely slow to make a move (10+ minutes) and I need to have alpha-beta pruning to make the engine reasonable.
  Here is the code for the engine, along with some print statements I used to debug:
  import time
  
  from .move_gen import move_gen, get_pins_and_checks
  from .evaluate import evaluate
  from .board import Board
  from .move import Move
  from .constants import MATE_SCORE
  
  
  class Engine:
      def search(self, board: Board) -> Move | None:
          start = time.time()
          self.tt = {}
  
          eval = self.negamax(board, 7, float("-inf"), float("inf"))
  
          # format eval
          eval = eval if board.white_move else -eval  # switch from perspective of engine to perspective of white
          eval_output = f"+{eval}" if eval >= 0 else str(eval)  # add positive and negative signs + convert to string
  
          print(f"Time: {round(time.time() - start, 3)}s - Eval: {eval_output}")
  
          return self.tt.get(board.zobrist, {"move": None})["move"]
  
      def move_value(self, move: Move) -> int:
          if move.prom:
              return 1
          elif move.capture:
              return 1
          return 2
  
      def negamax(self, board: Board, depth: int, alpha: float, beta: float, ply: int = 0) -> float:
          # get and sort moves
          moves = move_gen(board)
          moves = sorted(moves, key=lambda x: self.move_value(x))
  
          if len(moves) == 0:
              # determine if in check
              king = "K" if board.white_move else "k"
              king_pos = board.board.index(king)
              in_check, _, _ = get_pins_and_checks(board.board, board.white_move, king_pos)
  
              # if in check with no moves -> checkmate -> return super low score
              if in_check:
                  return -MATE_SCORE + ply
              # not in check with no moves -> stalemate -> draw
              else:
                  if ply == 1:
                      print("Best Response: No Moves - Best Value: Stalemate -> 0")
                  return 0
  
          if depth == 0:
              return evaluate(board)
  
          best_value = float("-inf")
          best_move = None
  
          for move in moves:
              if ply == 0:
                  print(f"----- Move {move} -----")
  
              board.make(move)
              value = -self.negamax(board, depth - 1, -beta, -alpha, ply + 1)
              board.unmake(move)
  
              if value >= best_value:
                  best_value = value
                  best_move = move
  
              alpha = max(alpha, value)
  
              if alpha >= beta:
                  break
  
          if ply == 1:
              print(f"Best Response: {best_move} - Best Value: {best_value}")
  
          # store in transposition table
          self.tt[board.zobrist] = {"depth": depth, "value": best_value, "move": best_move}
  
          return best_value
  
  When I run this code I get the following output:
  ----- Move b8b7 -----
  Best Response: No Moves - Best Value: Stalemate -> 0
  ----- Move a7a8B -----
  Best Response: b7a5 - Best Value: -1332
  ----- Move a7a8N -----
  Best Response: b7d6 - Best Value: -99993
  ----- Move a7a8R -----
  Best Response: b7c5 - Best Value: -99993
  ----- Move a7a8Q -----
  Best Response: b7c5 - Best Value: -99993
  ----- Move a6b7 -----
  Best Response: No Moves - Best Value: Stalemate -> 0
  ----- Move b8c8 -----
  Best Response: b7c5 - Best Value: -99993
  ----- Move b8d8 -----
  Best Response: b7d8 - Best Value: -99993
  ----- Move b8e8 -----
  Best Response: b7c5 - Best Value: -99993
  ----- Move b8f8 -----
  Best Response: b7c5 - Best Value: -99993
  ----- Move b8g8 -----
  Best Response: b7c5 - Best Value: -99993
  ----- Move b8h8 -----
  Best Response: b7c5 - Best Value: -99993
  ----- Move b8a8 -----
  Best Response: b7c5 - Best Value: -99993
  ----- Move a6b6 -----
  Best Response: b7c5 - Best Value: -99993
  ----- Move a6b5 -----
  Best Response: b7c5 - Best Value: -99993
  ----- Move e3f5 -----
  Best Response: h1g2 - Best Value: -99993
  ----- Move e3d5 -----
  Best Response: h1g2 - Best Value: -1966
  ----- Move e3f1 -----
  Best Response: h1g2 - Best Value: -1716
  ----- Move e3d1 -----
  Best Response: h1g2 - Best Value: -1880
  ----- Move e3g4 -----
  Best Response: h1g2 - Best Value: -99993
  ----- Move e3c4 -----
  Best Response: h1g2 - Best Value: -1929
  ----- Move e3c2 -----
  Best Response: h1g2 - Best Value: -1930
  ----- Move f3g5 -----
  Best Response: h6g5 - Best Value: -1873
  ----- Move f3e5 -----
  Best Response: b7c5 - Best Value: -99993
  ----- Move f3g1 -----
  Best Response: h1g1 - Best Value: -1810
  ----- Move f3e1 -----
  Best Response: b7c5 - Best Value: -99993
  ----- Move f3h4 -----
  Best Response: b7c5 - Best Value: -99993
  ----- Move f3h2 -----
  Best Response: g3h2 - Best Value: -99993
  ----- Move f3d4 -----
  Best Response: b7c5 - Best Value: -99993
  ----- Move f3d2 -----
  Best Response: b7c5 - Best Value: -99993
  Time: 16.259s - Eval: +99993
  
  As seen by the output, the engine finds the mate at the move it should, but it also finds many other moves that the opponent has a best value of still a checkmate(as seen by -99993, because -100000 is MATE_SCORE).
  The lines that removing fixes it are, but as mentioned earlier make it way too slow:
  if alpha >= beta:
     break
  
  I've simplified the code as much as I can, which is why there is a transposition table that the cutoffs are not being used.
  So in conclusion, the engine finds a bunch of moves that lead to a forced checkmate, even though it should only find one. Removing alpha-beta pruning fixes that, but makes it way too slow.
  
  **Tags:** python
  
  > **Comments:**
  > **username_1**: Maybe try if alpha >= beta: return beta? Probably won't help though.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2024-06-14. Score: 0
  
  Be also careful with the first call with negamax you negate the alpha and beta. There is no negative value for INT\_MIN, often -INT\_MIN becomes INT\_MIN, so wrong values are passed and thus resulting in returning different things.
  Thus use -INT\_MAX or INT\_MIN+1, as initial lower bound.
  
  
  ---
  
  ### Answer by username_3 on 2024-04-24. Score: 0
  
  I believe i found the issue `alpha = max(alpha, value)` should be `alpha = max(alpha, best_value)`.
  
  > **Comments:**
  > **username_0**: Hi, thanks for your answer but this had no effect on it, same output  
  
  ---
  
  