Answers.Body: <p>What you have is a fairly standard programming bug - your user requirements say that X should not happen but X happens.</p>
  <p>The solution is a very standard debugging technique - add a line of code to check for the error condition (your particular silly move) and set a breakpoint on a dummy statement inside the satisfied condition. Run the program in the debugger, feed it the data that produces the error, catch the error condition and then step through to see where you have made your mistake.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-07-29T11:45:32.683Z
Answers.LastActivityDate: 2022-07-29T11:45:32.683Z
Answers.UserDisplayName: Brian Towers
Body: <p>After learning about alpha-beta pruning algorithm for a while, I decided to write a simple chess program. However, when running the program, the computer decides to make a silly move. I don't know where the functions are written wrong.</p>
  <p>What do I have to fix for the program to work properly.</p>
  <p>This is my static evaluation function, where <code>m_turn</code> is the side in turn, and <code>m_xturn</code> is the side that has not yet turned:</p>
  <pre><code>int CChess::Evaluate()
  {
      int score = 0;
      for (int r = 0; r &lt; CHEIGHT; r++)
          for (int c = 0; c &lt; CWIDTH; c++)
              if (m_color[r][c] == m_turn)
                  score += PIECE_VALUE[m_piece[r][c]];
              else if (m_color[r][c] == m_xturn)
                  score -= PIECE_VALUE[m_piece[r][c]];
      return score;
  }
  </code></pre>
  <p>Alpha-beta pruning function:</p>
  <pre><code>int CChess::AlphaBeta(int depth, int alpha, int beta, bool isMaxPlayer)
  {
      if (depth == 0)
          return Evaluate();
      std::vector&lt;CChessMove&gt; move_list = GenMove();
      size_t n = move_list.size();
      if (isMaxPlayer)
      {
          for (size_t i = 0; i &lt; n; i++)
          {
              CChessPiece piece = Move(move_list[i]);
              int value = AlphaBeta(depth - 1, alpha, beta, false);
              UnMove(move_list[i], piece);
              if (value &gt; alpha)
                  alpha = value;
              if (alpha &gt;= beta)
                  break;
          }
          return alpha;
      }
      for (size_t i = 0; i &lt; n; i++)
      {
          CChessPiece piece = Move(move_list[i]);
          int value = AlphaBeta(depth - 1, alpha, beta, true);
          UnMove(move_list[i], piece);
          if (value &lt; beta)
              beta = value;
          if (alpha &gt;= beta)
              break;
      }
      return beta;
  }
  </code></pre>
  <p>The function to find the best move.</p>
  <pre><code>CChessMove CChess::ComputerThinks()
  {
      int best_value = -CCHESS_INFINITY;
      CChessMove best_move = { {-1, -1}, {-1, -1 } };
      std::vector&lt;CChessMove&gt; move_list = GenMove();
      size_t n = move_list.size();
      for (size_t i = 0; i &lt; n; i++)
      {
          CChessPiece piece = Move(move_list[i]);
          int value = AlphaBeta(CCHESS_DEPTH, -CCHESS_INFINITY, CCHESS_INFINITY, false);
          UnMove(move_list[i], piece);
          if (value &gt; best_value)
          {
              best_value = value;
              best_move = move_list[i];
          }
      }
      return best_move;
  }
  </code></pre>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-07-29T09:06:25.470Z
Comments.Text: What do you mean by "a silly move"? It seems like your eval function just counts material, so unless one side is losing material, all positions are evaluated equally. Adding something as simple as piece square tables will get rid of this issue.
Comments.UserDisplayName: emdio
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-08-03T19:15:11.453Z
Comments.Text: does minimax give the same result? alpha beta should never return a different result than minimax
Comments.UserDisplayName: Oscar Smith
Tags: <programming><evaluation>
Title: Alpha-beta pruning with a silly move
ThreadText: # Alpha-beta pruning with a silly move
  
  (Asked by: username_0 on 2022-07-29)
  
  After learning about alpha-beta pruning algorithm for a while, I decided to write a simple chess program. However, when running the program, the computer decides to make a silly move. I don't know where the functions are written wrong.
  
  What do I have to fix for the program to work properly.
  
  This is my static evaluation function, where `m_turn` is the side in turn, and `m_xturn` is the side that has not yet turned:
  
  ```
  int CChess::Evaluate()
  {
      int score = 0;
      for (int r = 0; r < CHEIGHT; r++)
          for (int c = 0; c < CWIDTH; c++)
              if (m_color[r][c] == m_turn)
                  score += PIECE_VALUE[m_piece[r][c]];
              else if (m_color[r][c] == m_xturn)
                  score -= PIECE_VALUE[m_piece[r][c]];
      return score;
  }
  
  ```
  
  Alpha-beta pruning function:
  
  ```
  int CChess::AlphaBeta(int depth, int alpha, int beta, bool isMaxPlayer)
  {
      if (depth == 0)
          return Evaluate();
      std::vector<CChessMove> move_list = GenMove();
      size_t n = move_list.size();
      if (isMaxPlayer)
      {
          for (size_t i = 0; i < n; i++)
          {
              CChessPiece piece = Move(move_list[i]);
              int value = AlphaBeta(depth - 1, alpha, beta, false);
              UnMove(move_list[i], piece);
              if (value > alpha)
                  alpha = value;
              if (alpha >= beta)
                  break;
          }
          return alpha;
      }
      for (size_t i = 0; i < n; i++)
      {
          CChessPiece piece = Move(move_list[i]);
          int value = AlphaBeta(depth - 1, alpha, beta, true);
          UnMove(move_list[i], piece);
          if (value < beta)
              beta = value;
          if (alpha >= beta)
              break;
      }
      return beta;
  }
  
  ```
  
  The function to find the best move.
  
  ```
  CChessMove CChess::ComputerThinks()
  {
      int best_value = -CCHESS_INFINITY;
      CChessMove best_move = { {-1, -1}, {-1, -1 } };
      std::vector<CChessMove> move_list = GenMove();
      size_t n = move_list.size();
      for (size_t i = 0; i < n; i++)
      {
          CChessPiece piece = Move(move_list[i]);
          int value = AlphaBeta(CCHESS_DEPTH, -CCHESS_INFINITY, CCHESS_INFINITY, false);
          UnMove(move_list[i], piece);
          if (value > best_value)
          {
              best_value = value;
              best_move = move_list[i];
          }
      }
      return best_move;
  }
  
  ```
  
  **Tags:** programming, evaluation
  
  > **Comments:**
  > **username_1**: What do you mean by "a silly move"? It seems like your eval function just counts material, so unless one side is losing material, all positions are evaluated equally. Adding something as simple as piece square tables will get rid of this issue.  
  > **username_2**: does minimax give the same result? alpha beta should never return a different result than minimax  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_3 on 2022-07-29. Score: 3
  
  What you have is a fairly standard programming bug - your user requirements say that X should not happen but X happens.
  
  The solution is a very standard debugging technique - add a line of code to check for the error condition (your particular silly move) and set a breakpoint on a dummy statement inside the satisfied condition. Run the program in the debugger, feed it the data that produces the error, catch the error condition and then step through to see where you have made your mistake.
  
  
  ---
  
  