Answers.Body: <p>In the evaluation function, you need to flip the eval if it is black to move</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-10-29T20:18:23.297Z
Answers.LastActivityDate: 2023-10-29T20:18:23.297Z
Answers.UserDisplayName: HWE
Body: <p>I've been working on implementing/improving my engine's search function the past few days, but yesterday I decided my current search implementation was a mess and that it would be much better to rewrite it from scratch, which is what I'm currently doing.</p>
  <p>The issue is, my alpha beta function is returning negative/positive evaluations for the same position for even/odd depths. To try and debug, I wrote a barebones search using the chess programming wiki as reference, but the issue still persists. I don't see where the issue is/could be.</p>
  <p>Here is my current implementation:</p>
  <pre><code>static int quiesce(Board *board, int alpha, int beta, int color) {
      moveList mList = { 0 };
      moveList tacticalMoves = { 0 };
  
      int nMoves    = genLegalMoves(board, &amp;mList);
      int nTactical = genLegalTactical(board, &amp;tacticalMoves);
  
      int standPat = eval(board, nMoves, color);
      if (standPat &gt;= beta)
          return beta;
      if (standPat &gt; alpha)
          alpha = standPat;
  
      for (int i = 0; i &lt; nMoves; i++) {
          if (nTactical == 0) break;
          make(board, mList.moves[i].move);
          int score = -quiesce(board, -beta, -alpha, -color);
          unmake(board, mList.moves[i].move);
  
          if (score &gt;= beta) return beta;
          if (score &gt; alpha) alpha = score;
      }
  
    return alpha;
  }
  
  
  int alphaBeta(Board *board, int alpha, int beta, int depthLeft, int color) {
      if (depthLeft == 0) return quiesce(board, alpha, beta, color);
  
      moveList mList = {0};
      genLegalMoves(board, &amp;mList);
  
      for (int i = 0; i &lt; mList.nMoves; i++) {
          make(board, mList.moves[i].move);
          int score = -alphaBeta(board, -beta, -alpha, depthLeft - 1, -color);
          unmake(board, mList.moves[i].move);
  
          if (score &gt;= beta) return beta;
          if (score &gt; alpha) alpha = score;
      }
  
      return alpha;
  }
  
  void search(Board *board, int depth) {
      moveList mList = { 0 };
      genLegalMoves(board, &amp;mList);
  
      int best;
      int max = -500000;
      for (int i = 0; i &lt; mList.nMoves; i++) {
          int color = (board-&gt;turn == WHITE) ? 1 : -1;
          make(board, mList.moves[i].move);
          int score = -alphaBeta(board, -500000, 500000, depth - 1, -color);
          unmake(board, mList.moves[i].move);
  
          if (score &gt; max) {
              max = score;
              best = mList.moves[i].move;
          }
      }
  
      printf(&quot;score: %d, best move: &quot;, max);
      print_move(best);
      printf(&quot;\n&quot;);
  }
  </code></pre>
  <p>I suspect the issue is the quiescence function, as I don't quite understand how it's supposed to be implemented, but I don't see any glaring differences from the chess programming wiki's pseudocode that would cause this behavior.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-08-07T09:21:24.840Z
Comments.Text: You might be better asking this is Stack Overflow - certainly as a programming question you will get a more programming orientated audience there.
Comments.UserDisplayName: Ian Bush
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-08-07T10:06:25.100Z
Comments.Text: @IanBush Yea, I figured as much. I saw some engine questions here and thought this was the place to ask. Do I delete my question? Or do I leave it up
Comments.UserDisplayName: pavel_fyodorovich
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-08-07T10:07:20.667Z
Comments.Text: I have not looked at the code, but is it possible that it is from white's perspective or black's perspective on even/odd?
Comments.UserDisplayName: chesskobra
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-08-07T10:10:20.320Z
Comments.Text: @chesskobra White is odd, black even; position favors black
Comments.UserDisplayName: pavel_fyodorovich
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-08-09T05:52:02.457Z
Comments.Text: maybe wrong implementation of negamax?
Comments.UserDisplayName: qwr
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-08-13T21:11:39.397Z
Comments.Text: The bug might be in your `eval()` function, which you haven't shown us. You should probably add it to your question. (If it's too long and complicated to post in full, consider replacing it with some very simple dummy evaluator — and make sure to test whether the bug still occurs when using the simplified evaluator!)
Comments.UserDisplayName: Ilmari Karonen
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-08-14T12:32:14.173Z
Comments.Text: This `search(Board *board, int depth)` is not optimal, you are iterating on the moves. you should iterate on the depth.
Comments.UserDisplayName: ferdy
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-11-02T03:04:32.937Z
Comments.Text: Personally, I find it a lot simpler to just store board metadata directly with the actual board, for example things like ep square, color, and castling rights, which makes things a lot simpler in my opinion. Also, as @ferdy said, the search thing is not optimal because you don't get any pruning benefits from having alpha/beta values from the previous initial move branches, as you only search every initial move with the window [-500000, 500000]. What I do in my engine is just have alphaBeta and search be the same and return the best move instead of alpha at the end if it's the initial call.
Comments.UserDisplayName: Hank's back rank
Tags: <engines><programming>
Title: My engine's alpha-beta search returns negative score eval. on odd depths and positive on even. Dont understand what is causing this bug
ThreadText: # My engine's alpha-beta search returns negative score eval. on odd depths and positive on even. Dont understand what is causing this bug
  
  (Asked by: username_0 on 2022-08-07)
  
  I've been working on implementing/improving my engine's search function the past few days, but yesterday I decided my current search implementation was a mess and that it would be much better to rewrite it from scratch, which is what I'm currently doing.
  The issue is, my alpha beta function is returning negative/positive evaluations for the same position for even/odd depths. To try and debug, I wrote a barebones search using the chess programming wiki as reference, but the issue still persists. I don't see where the issue is/could be.
  Here is my current implementation:
  static int quiesce(Board *board, int alpha, int beta, int color) {
      moveList mList = { 0 };
      moveList tacticalMoves = { 0 };
  
      int nMoves    = genLegalMoves(board, &mList);
      int nTactical = genLegalTactical(board, &tacticalMoves);
  
      int standPat = eval(board, nMoves, color);
      if (standPat >= beta)
          return beta;
      if (standPat > alpha)
          alpha = standPat;
  
      for (int i = 0; i < nMoves; i++) {
          if (nTactical == 0) break;
          make(board, mList.moves[i].move);
          int score = -quiesce(board, -beta, -alpha, -color);
          unmake(board, mList.moves[i].move);
  
          if (score >= beta) return beta;
          if (score > alpha) alpha = score;
      }
  
    return alpha;
  }
  
  
  int alphaBeta(Board *board, int alpha, int beta, int depthLeft, int color) {
      if (depthLeft == 0) return quiesce(board, alpha, beta, color);
  
      moveList mList = {0};
      genLegalMoves(board, &mList);
  
      for (int i = 0; i < mList.nMoves; i++) {
          make(board, mList.moves[i].move);
          int score = -alphaBeta(board, -beta, -alpha, depthLeft - 1, -color);
          unmake(board, mList.moves[i].move);
  
          if (score >= beta) return beta;
          if (score > alpha) alpha = score;
      }
  
      return alpha;
  }
  
  void search(Board *board, int depth) {
      moveList mList = { 0 };
      genLegalMoves(board, &mList);
  
      int best;
      int max = -500000;
      for (int i = 0; i < mList.nMoves; i++) {
          int color = (board->turn == WHITE) ? 1 : -1;
          make(board, mList.moves[i].move);
          int score = -alphaBeta(board, -500000, 500000, depth - 1, -color);
          unmake(board, mList.moves[i].move);
  
          if (score > max) {
              max = score;
              best = mList.moves[i].move;
          }
      }
  
      printf("score: %d, best move: ", max);
      print_move(best);
      printf("\n");
  }
  
  I suspect the issue is the quiescence function, as I don't quite understand how it's supposed to be implemented, but I don't see any glaring differences from the chess programming wiki's pseudocode that would cause this behavior.
  
  **Tags:** engines, programming
  
  > **Comments:**
  > **username_1**: You might be better asking this is Stack Overflow - certainly as a programming question you will get a more programming orientated audience there.  
  > **username_0**: @IanBush Yea, I figured as much. I saw some engine questions here and thought this was the place to ask. Do I delete my question? Or do I leave it up  
  > **username_2**: I have not looked at the code, but is it possible that it is from white's perspective or black's perspective on even/odd?  
  > **username_0**: @username_2 White is odd, black even; position favors black  
  > **username_3**: maybe wrong implementation of negamax?  
  > **username_4**: The bug might be in your `eval()` function, which you haven't shown us. You should probably add it to your question. (If it's too long and complicated to post in full, consider replacing it with some very simple dummy evaluator — and make sure to test whether the bug still occurs when using the simplified evaluator!)  
  > **username_5**: This `search(Board *board, int depth)` is not optimal, you are iterating on the moves. you should iterate on the depth.  
  > **username_6**: Personally, I find it a lot simpler to just store board metadata directly with the actual board, for example things like ep square, color, and castling rights, which makes things a lot simpler in my opinion. Also, as @username_5 said, the search thing is not optimal because you don't get any pruning benefits from having alpha/beta values from the previous initial move branches, as you only search every initial move with the window [-500000, 500000]. What I do in my engine is just have alphaBeta and search be the same and return the best move instead of alpha at the end if it's the initial call.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_7 on 2023-10-29. Score: 2
  
  In the evaluation function, you need to flip the eval if it is black to move
  
  
  ---
  
  