Answers.Body: <p>I ended up finding the issue -- the move sorting wasn't working correctly. This meant that at the start of every iteration for iterative deepening, a bad move would be considered first and so set as the best move by default. Then when search time was up, this bad move would be returned as the best move to play.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-07-09T16:09:50.590Z
Answers.LastActivityDate: 2023-07-09T16:09:50.590Z
Answers.UserDisplayName: Olly Britton
Body: <p>I'm writing a simple chess engine in Go and have been running into some issues related to search. I'm currently using iterative deepening and alpha-beta search using the negamax pruning. My issue I think comes from alpha beta search.</p>
  <p>For example, in the following position (engine trying to play black)</p>
  <pre><code>[FEN &quot;&quot;]
  1. e4 a6 2. Bc4 a5 3. Qf3  
  </code></pre>
  <p>many moves lead to Scholar's mate. Putting this position into my engine like so</p>
  <pre><code>isready
  readyok
  position rnbqkbnr/1ppppppp/8/p7/2B1P3/5Q2/PPPP1PPP/RNB1K1NR b KQkq - 1 3
  </code></pre>
  <p>I get</p>
  <pre><code>info starting search at depth 1
  info currmove a5a4 score 0 pv
  info score cp 0 depth 1 nodes 1 pv a5a4
  info currmove b7b6 score 0 pv
  info currmove c7c6 score 0 pv
  info currmove d7d6 score 0 pv
  info currmove e7e6 score 0 pv
  info currmove f7f6 score 0 pv
  info currmove g7g6 score 0 pv
  info currmove h7h6 score 0 pv
  info currmove b7b5 score 0 pv
  info currmove c7c5 score 0 pv
  info currmove d7d5 score 0 pv
  info currmove e7e5 score 0 pv
  info currmove f7f5 score 0 pv
  info currmove g7g5 score 0 pv
  info currmove h7h5 score 0 pv
  info currmove b8a6 score 0 pv
  info currmove b8c6 score 0 pv
  info currmove g8f6 score 0 pv
  info currmove g8h6 score 0 pv
  info currmove a8a6 score 0 pv
  info currmove a8a7 score 0 pv
  info score cp 0 depth 1 nodes 21 pv a5a4
  info starting search at depth 2
  info currmove a5a4 score -1 pv c4f7
  info score cp -1 depth 2 nodes 64 pv a5a4 c4f7
  info currmove b7b6 score -1 pv c4f7
  info currmove c7c6 score -1 pv c4f7
  info currmove d7d6 score -1 pv c4f7
  info currmove e7e6 score -1 pv c4e6
  info currmove f7f6 score -3 pv c4g8
  info currmove g7g6 score -1 pv c4f7
  info currmove h7h6 score -1 pv c4f7
  info currmove b7b5 score -1 pv c4b5
  info currmove c7c5 score -1 pv c4f7
  info currmove d7d5 score -1 pv e4d5
  info currmove e7e5 score -1 pv c4f7
  info currmove f7f5 score -1 pv e4f5
  info currmove g7g5 score -1 pv c4f7
  info currmove h7h5 score -1 pv c4f7
  info currmove b8a6 score -3 pv c4a6
  info currmove b8c6 score -1 pv c4f7
  info currmove g8f6 score -1 pv c4f7
  info currmove g8h6 score -1 pv c4f7
  info currmove a8a6 score -5 pv c4a6
  info currmove a8a7 score -1 pv c4f7
  info score cp -1 depth 2 nodes 605 pv a5a4 c4f7
  info starting search at depth 3
  info currmove a5a4 score -29997 pv c4f7
  info score cp -29997 depth 3 nodes 708 pv a5a4 c4f7
  info currmove b7b6 score -29997 pv c4f7
  info currmove c7c6 score -29997 pv c4f7
  info currmove d7d6 score -1 pv c4f7 e8d7
  info score cp -1 depth 3 nodes 975 pv d7d6 c4f7 e8d7
  info currmove e7e6 score 0 pv b2b3 a5a4
  info score cp 0 depth 3 nodes 1133 pv e7e6 b2b3 a5a4
  info currmove f7f6 score 0 pv a2a3 a5a4
  info currmove g7g6 score 0 pv a2a3 a5a4
  info currmove h7h6 score 0 pv a2a3 a5a4
  info currmove b7b5 score 0 pv c4f1 a5a4
  info currmove c7c5 score 0 pv a2a3 a5a4
  info currmove d7d5 score 0 pv e4d5 d8d5
  info currmove e7e5 score 0 pv b2b3 a5a4
  info currmove f7f5 score 0 pv e4e5 a5a4
  info currmove g7g5 score 0 pv a2a3 a5a4
  info currmove h7h5 score 0 pv a2a3 a5a4
  info currmove b8a6 score 0 pv a2a3 a5a4
  info currmove b8c6 score 0 pv a2a3 a5a4
  info currmove g8f6 score 0 pv e4e5 a5a4
  info currmove g8h6 score 0 pv a2a3 a5a4
  info currmove a8a6 score 0 pv a2a3 a5a4
  info currmove a8a7 score 0 pv a2a3 a5a4
  info score cp 0 depth 3 nodes 2275 pv e7e6 b2b3 a5a4
  bestmove e7e6
  </code></pre>
  <p>Here something strange is going on because at the start of searching at depth 3, it correctly evaluates <code>a5a4</code> as leading to checkmate. However, once it finds a move that avoids instant checkmate, in this case first identifying <code>d7d6</code> and then <code>e7e6</code>, all further moves then have their score capped to the best move found so far. For example, <code>a8a7</code>, which leads to checkmate, is evaluated to have a score of <code>0</code>. As far as I understand, although the <code>alpha</code> value stores the best value that we can guarantee, this shouldn't affect the evaluations of each move.</p>
  <p>Things get stranger with even deeper searches. Here for example is the end of the search at depth 7:</p>
  <pre><code>info starting search at depth 7
  info time 3000 ndes 3729598 nps 1243199 score 0
  info time 4000 ndes 4916163 nps 1229040 score 0
  info currmove a5a4 score -29997 pv c4f7
  info score cp -29997 depth 7 nodes 5572093 pv a5a4 c4f7
  info time 5000 ndes 6105741 nps 1221148 score 0
  info time 6000 ndes 7218855 nps 1203142 score 3
  info currmove b7b6 score -29997 pv c4f7
  info time 7000 ndes 8430976 nps 1204425 score 0
  info time 8000 ndes 9647996 nps 1205999 score -9
  info time 9000 ndes 10866782 nps 1207420 score -1
  info currmove c7c6 score -29995 pv c4e6 a5a4 e6f7
  info score cp -29995 depth 7 nodes 12123230 pv c7c6 c4e6 a5a4 e6f7
  info currmove d7d6 score 0 pv a2a3 a5a4 b2b3 d6d5 c2c3 d5d4
  info score cp 0 depth 7 nodes 12123237 pv d7d6 a2a3 a5a4 b2b3 d6d5 c2c3 d5d4
  info currmove e7e6 score 0 pv a2a3 a5a4 b2b3 e6e5 c2c3 b7b6
  info currmove f7f6 score 0 pv a2a3 a5a4 b2b3 f6f5 c2c3 f5f4
  info currmove g7g6 score 0 pv a2a3 a5a4 b2b3 g6g5 c2c3 g5g4
  info currmove h7h6 score 0 pv a2a3 a5a4 b2b3 h6h5 c2c3 h5h4
  info currmove b7b5 score 0 pv a2a3 a5a4 b2b3 b5b4 c2c3 c7c6
  info currmove c7c5 score 0 pv a2a3 a5a4 b2b3 b7b6 c2c3 b6b5
  info currmove d7d5 score 0 pv a2a3 a5a4 b2b3 d5d4 c2c3 d4d3
  info currmove e7e5 score 0 pv a2a3 a5a4 b2b3 b7b6 c2c3 b6b5
  info time 10000 ndes 12123300 nps 1212330 score 0
  info currmove f7f5 score 0 pv a2a3 a5a4 b2b3 f5f4 c2c3 b7b6
  info currmove g7g5 score 0 pv a2a3 a5a4 b2b3 g5g4 c2c3 g4g3
  info currmove h7h5 score 0 pv a2a3 a5a4 b2b3 h5h4 c2c3 h4h3
  info currmove b8a6 score 0 pv a2a3 a5a4 b2b3 b7b6 c2c3 b6b5
  info currmove b8c6 score 0 pv a2a3 a5a4 b2b3 b7b6 c2c3 b6b5
  info currmove g8f6 score 0 pv a2a3 a5a4 b2b3 b7b6 c2c3 b6b5
  info currmove g8h6 score 0 pv a2a3 a5a4 b2b3 b7b6 c2c3 b6b5
  info currmove a8a6 score 0 pv a2a3 a5a4 b2b3 b7b6 c2c3 b6b5
  info currmove a8a7 score 0 pv a2a3 a5a4 b2b3 b7b6 c2c3 b6b5
  info score cp 0 depth 7 nodes 12123356 pv d7d6 a2a3 a5a4 b2b3 d6d5 c2c3 d5d4
  bestmove d7d6
  </code></pre>
  <p>Now all the outputted principle variations seem to just be in lexiographical order. I can't spot in my code where there might be an issue but am worried that I'm missing something obvious. My code is as follows:</p>
  <pre><code>func (s *AlphaBetaSearch) Root() error {
      var pv pvList      // Holds the principle variation
      var childPV pvList // Holds the principle variation of the position after the first move is made
  
      childPV.new()
  
      for request := range s.requests {
          pos := request.pos // Position we are searching
  
          s.startTime = time.Now()    // Record start time so we know to stop if time is up
          s.nextTime = time.Now()     // Record next time as a counter so we can periodically print information
          s.nodeCount = 0             // Record number of nodes so we can stop after searching a certain number of nodes
          s.options = request.options // Store options in the search struct so we don't have to explicitly pass around.
          s.options.Stop = false      // Make sure we don't stop straight away if we were told to stop previously
  
          // Keep track of the best move found so far. This is outside the loop so that we can return the best move found
          // if we are asked to stop searching at a particular depth.
          bestMove := position.NoMove
  
          // Generate legal moves and annotate them with the evaluation after they've taken place so we can improve
          // move ordering in the search.
          legalMoves := pos.MovesLegalWithEvaluation(position.EvalSimple)
  
          // For loop for iterative deepening
          for depth := uint(1); depth &lt;= s.options.Depth; depth++ {
              // Sort legal moves by the evaluation calculated above
              legalMoves.Sort()
  
              // Best score for a move found so far
              bestScore := position.NoEval
  
              // Alpha and beta
              // Alpha here is the best score we can be guaranteed to achieve
              // Beta here is the best score the opposing player can achieve
              alpha, beta := position.MinEval, position.MaxEval
  
              for _, move := range legalMoves.AsSlice() {
                  // Clear the child PV so it can be used again for this move
                  childPV.clear()
  
                  // Make move, evaluate score of this position, and then undo move.
                  pos.MakeMove(move)
                  score := -s.search(-beta, -alpha, depth-1, 1, &amp;childPV, pos)
                  pos.UndoMove(move)
  
                  s.responses &lt;- fmt.Sprintf(&quot;info currmove %s score %d pv %s&quot;, move.String(), score, childPV.String())
  
                  // Store evaluation of this move so that on the next iteration the move ordering is more effective
                  move.SetEval(position.ScoreFromPerspective(score, pos.SideToMove))
  
                  // If this is the best move we've seen so far...
                  if score &gt; bestScore {
                      // Update bestScore to reflect this
                      bestScore = score
  
                      // Update the principle variation to use this move instead
                      pv.clear()
                      pv.catenate(move, &amp;childPV)
  
                      // Record this as the best move
                      bestMove = move
  
                      // Set alpha to this score
                      alpha = score
  
                      s.responses &lt;- fmt.Sprintf(&quot;info score cp %v depth %v nodes %v pv %s&quot;, bestScore, depth, s.nodeCount, pv.String())
                  }
              }
  
              s.responses &lt;- fmt.Sprintf(&quot;info score cp %v depth %v nodes %v pv %s&quot;, bestScore, depth, s.nodeCount, pv.String())
          }
  
          s.responses &lt;- fmt.Sprintf(&quot;bestmove %s&quot;, bestMove.String())
      }
  
      return nil
  }
  
  func (s *AlphaBetaSearch) search(alpha int16, beta int16, depth uint, ply int, pv *pvList, pos *position.Position) int16 {
      s.nodeCount++
  
      // If we're at depth 0, stop recursing and instead return a static evaluation of this position.
      if depth &lt;= 0 {
          return position.ScoreFromPerspective(position.EvalSimple(pos), pos.SideToMove) // TODO: make more customisable
      }
  
      // Clear the principle variation
      pv.clear()
  
      // Generate all legal moves in this position
      legalMoves := pos.MovesLegal()
  
      // Initialise bestMove and bestScore to hold the best move found so far.
      bestMove, bestScore := position.NoMove, position.NoEval
  
      // TODO: doesn't yet understand draw by threefold repetition
  
      var childPV pvList
  
      for _, move := range legalMoves.AsSlice() {
          childPV.clear()
  
          pos.MakeMove(move)
          score := -s.search(-beta, -alpha, depth-1, ply+1, &amp;childPV, pos)
          pos.UndoMove(move)
  
          // If this is the best score we've found so far...
          if score &gt; bestScore {
              // Update bestScore and bestMove to track this (might not need bestMove)
              bestScore = score
              bestMove = move
              _ = bestMove
  
              // Add this to the principle variation
              pv.catenate(move, &amp;childPV)
  
              // Beta cutoff:
              // The opposing player can guarantee a better position for themselves, so there's no point pursuing this position.
              if score &gt;= beta {
                  return score
              }
  
              // If this is better than the best score we can guarantee so far, then update alpha to reflect this
              if score &gt; alpha {
                  alpha = score
              }
  
          }
  
          // Print info if required
          if time.Since(s.nextTime) &gt;= time.Second {
              diff := time.Since(s.startTime)
              s.responses &lt;- fmt.Sprintf(&quot;info time %v ndes %v nps %v score %d&quot;, diff.Milliseconds(), s.nodeCount, s.nodeCount/int(diff.Seconds()), bestScore)
              s.nextTime = time.Now()
          }
  
          // If required to stop early, return alpha since this is the best we can do.
          if s.options.Stop || time.Since(s.startTime) &gt; s.options.MoveTime {
              return alpha
          }
  
      }
  
      // If we have no moves available, it's either checkmate or stalemate, so return values
      // that reflect this.
      if legalMoves.Len() == 0 {
          if pos.KingInCheck(pos.SideToMove) {
              // Checkmate
              return -30000 + int16(ply) + 1
          }
  
          // Stalemate
          return 0 // TODO: return contempt value instead?
      }
  
      return bestScore
  }
  </code></pre>
  <p>Can anybody spot what might be the mistake here?</p>
  <hr />
  <p>EDIT: Here's the evaluation logic:</p>
  <pre><code>const (
      MaxEval  int16 = 30_000
      MinEval  int16 = -MaxEval
      MateEval int16 = MaxEval + 1
      NoEval   int16 = MinEval - 1
  )
  
  // Evaluator decides the numerical value of a position.
  // An int16 is used so that evaluations can be packed into moves compactly.
  // TODO: Consider refactoring into seperate package
  type Evaluator func(p *Position) int16
  
  var EvaluatorInfo = map[string]Evaluator{
      &quot;simple&quot;: EvalSimple,
  }
  
  // GetEvaluator looks up an evaluator by name.
  func GetEvaluator(name string) Evaluator {
      return EvaluatorInfo[name]
  }
  
  // ScoreFromPerspective takes in a score where negative scores represent good positions for black and positive positions
  // for white, and takes in a side to move, and returns a positive evaluation from their perspective.
  func ScoreFromPerspective(score int16, sideToMove Color) int16 {
      if sideToMove == Black {
          return -score
      }
  
      return score
  }
  
  var simpleEvalTable = map[Piece]int16{
      Pawn:   1,
      Knight: 3,
      Bishop: 4,
      Rook:   5,
      Queen:  9,
      King:   1_000,
  }
  
  // EvalSimple evaluates the position using a simple material count.
  // TODO: This could definitely be sped up by using bitboards instead of the pos.Squares.
  func EvalSimple(pos *Position) int16 {
      overall := int16(0)
  
      for i := 0; i &lt; 64; i++ {
          curr := pos.Squares[i]
  
          switch curr.Color() {
          case White:
              overall += simpleEvalTable[curr.Colorless()]
          case Black:
              overall -= simpleEvalTable[curr.Colorless()]
          }
      }
  
      return overall
  }
  </code></pre>
  <p>and the movement code:</p>
  <pre><code>// MakeMove makes a move on the chess board, or returns an error if it is invalid.
  // Bitboards for occupation and piece locations are updated through the setSquare function.
  func (p *Position) MakeMove(m Move) bool {
      // Need to handle 6 special cases:
      // - White king moving
      // - Black king moving
      // (These two cases can move two pieces at once and disable castling)
  
      // - White rook moving
      // - Black rook moving
      // (These two cases mean some castling privileges may be lost)
  
      // - White pawn moving forward two squares onto an empty square
      // - Black pawn moving forward two squares onto an empty square
      // (These two cases either perform an en passant capture or set the en passant target square)
  
      movingPiece := p.Squares[m.From()]
      var newEnPassantTarget uint8 = NoEnPassant
  
      switch {
      case movingPiece == WhiteKing:
          // Disable any type of castling for the white king as they have moved.
          p.Castling.off(longW | shortW)
  
          // The king has moved two squares and so it is known they have castled.
          // Here we only need to worry about moving the rook, as the king is moved by the general code outside of the switch.
          if abs(int(m.From())-int(m.To())) == 2 {
              // Determine if they have castled long or short.
              if m.To() == SquareG1 { // Short castle
                  p.setSquare(SquareF1, WhiteRook)
                  p.setSquare(SquareH1, Empty)
              } else { // Long castle
                  p.setSquare(SquareD1, WhiteRook)
                  p.setSquare(SquareA1, Empty)
              }
          }
      case movingPiece == BlackKing:
          // Disable any type of castling for the black king as they have moved.
          p.Castling.off(longB | shortB)
  
          // The king has moved two squares and so it is known they have castled.
          // Here we only need to worry about moving the rook, as the king is moved by the general code outside of the switch.
          if abs(int(m.From())-int(m.To())) == 2 {
              // Determine if they have castled long or short.
              if m.To() == SquareG8 { // Short castle
                  p.setSquare(SquareF8, BlackRook)
                  p.setSquare(SquareH8, Empty)
              } else { // Long castle
                  p.setSquare(SquareD8, BlackRook)
                  p.setSquare(SquareA8, Empty)
              }
          }
      case movingPiece == WhiteRook:
          // Disable castling for the king on the side where the rook has moved.
          if m.From() == SquareA1 {
              p.Castling.off(longW)
          } else if m.From() == SquareH1 {
              p.Castling.off(shortW)
          }
      case movingPiece == BlackRook:
          // Disable castling for the king on the side where the rook has moved.
          if m.From() == SquareA8 {
              p.Castling.off(longB)
          } else if m.From() == SquareH8 {
              p.Castling.off(shortB)
          }
      case p.Squares[m.To()] == WhiteRook:
          // Disable castling when a white rook is taken.
          if m.To() == SquareA1 {
              p.Castling.off(longW)
          } else if m.To() == SquareH1 {
              p.Castling.off(shortW)
          }
      case p.Squares[m.To()] == BlackRook:
          // Disable castling when a black rook is taken.
          if m.To() == SquareA8 {
              p.Castling.off(longB)
          } else if m.To() == SquareH8 {
              p.Castling.off(shortB)
          }
      case movingPiece == WhitePawn &amp;&amp; p.Squares[m.To()] == Empty:
          if m.To()-m.From() == 16 {
              // The pawn has moved two full squares onto an empty square.
              // Therefore there is a new en passant target on the rank between its original position and its new position.
              newEnPassantTarget = m.From() + 8
          } else if m.To()-m.From() == 7 || m.To()-m.From() == 9 {
              // The pawn has moved diagonally onto an empty square -- this must be an en passant capture.
              p.setSquare(p.EnPassant-8, Empty)
          }
      case movingPiece == BlackPawn &amp;&amp; p.Squares[m.To()] == Empty:
          if m.From()-m.To() == 16 {
              // The pawn has moved two full squares onto an empty square.
              // Therefore there is a new en passant target on the rank between its original position and its new position.
              newEnPassantTarget = m.To() + 8
          } else if m.From()-m.To() == 7 || m.From()-m.To() == 9 {
              // The pawn has moved diagonally onto an empty square -- this must be an en passant capture.
              p.setSquare(p.EnPassant+8, Empty)
          }
      }
  
      p.EnPassant = newEnPassantTarget
      p.setSquare(m.From(), Empty)
  
      if m.Promotion() == None {
          p.setSquare(m.To(), movingPiece)
      } else {
          p.setSquare(m.To(), m.Promotion().OfColor(p.SideToMove))
      }
  
      p.SideToMove = p.SideToMove.Invert()
  
      if p.KingInCheck(p.SideToMove.Invert()) {
          p.UndoMove(m)
          return false
      }
  
      // If the side to move is now white, we can update the fullmove clock.
      if p.SideToMove == White {
          p.FullMoves += 1
      }
  
      // If there has been no capture and it's not a pawn move, then we need to increment the halfmove clock.
      if movingPiece != WhitePawn &amp;&amp; movingPiece != BlackPawn &amp;&amp; p.Squares[m.To()] != Empty {
          p.HalfmoveClock += 1
      } else {
          p.HalfmoveClock = 0
      }
  
      return true
  }
  </code></pre>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-07-06T14:58:08.927Z
Comments.Text: Could you provide the evaluation logic? It almost sounds like the `ScoreFromPerspective` is not adjusting the score properly from black's perspective and is leading it to choose moves that are the worst possible for black, except in mate where the score is calculated elsewhere at the end of the method. Alternatively, is `pos.MakeMove` swapping the `SideToMove` properly?
Comments.UserDisplayName: Nelson O
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-07-06T15:24:15.940Z
Comments.Text: @NelsonO Thanks for the quick reply :) I've updated the post to include the evaluation logic. I'm fairly sure that MakeMove works correctly since I've tested it using perft and all the values match but might have missed something.
Comments.UserDisplayName: Olly Britton
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-07-06T15:50:10.297Z
Comments.Text: From just a brief look, it doesn't seem like the issues are from the evaluation, and I think the SideToMove swapping is fine. However, I'm a bit confused by the part in `MakeMove` where the move is undone if the move was not legal. It doesn't look like your search does anything special in that case, so I think it ends up searching a null move and then undoing an illegal move that had already been undone. So I think the position gets into a bad state partway through the search. Try calling `continue` if the `MakeMove` returns false to skip over the rest of the loop for that illegal move.
Comments.UserDisplayName: Nelson O
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-07-06T16:25:15.730Z
Comments.Text: Thanks for having a look... I think the stuff about legal/illegal moves should be okay since I filter and only evaluate legal moves, but might be a bit wasteful and maybe I should do it when I iterate over each move. Thanks again!
Comments.UserDisplayName: Olly Britton
Tags: <engines>
Title: chess engine: alpha beta pruning starts evaluating moves incorrectly
ThreadText: # chess engine: alpha beta pruning starts evaluating moves incorrectly
  
  (Asked by: username_0 on 2023-07-06)
  
  I'm writing a simple chess engine in Go and have been running into some issues related to search. I'm currently using iterative deepening and alpha-beta search using the negamax pruning. My issue I think comes from alpha beta search.
  
  For example, in the following position (engine trying to play black)
  
  ```
  [FEN ""]
  1. e4 a6 2. Bc4 a5 3. Qf3  
  
  ```
  
  many moves lead to Scholar's mate. Putting this position into my engine like so
  
  ```
  isready
  readyok
  position rnbqkbnr/1ppppppp/8/p7/2B1P3/5Q2/PPPP1PPP/RNB1K1NR b KQkq - 1 3
  
  ```
  
  I get
  
  ```
  info starting search at depth 1
  info currmove a5a4 score 0 pv
  info score cp 0 depth 1 nodes 1 pv a5a4
  info currmove b7b6 score 0 pv
  info currmove c7c6 score 0 pv
  info currmove d7d6 score 0 pv
  info currmove e7e6 score 0 pv
  info currmove f7f6 score 0 pv
  info currmove g7g6 score 0 pv
  info currmove h7h6 score 0 pv
  info currmove b7b5 score 0 pv
  info currmove c7c5 score 0 pv
  info currmove d7d5 score 0 pv
  info currmove e7e5 score 0 pv
  info currmove f7f5 score 0 pv
  info currmove g7g5 score 0 pv
  info currmove h7h5 score 0 pv
  info currmove b8a6 score 0 pv
  info currmove b8c6 score 0 pv
  info currmove g8f6 score 0 pv
  info currmove g8h6 score 0 pv
  info currmove a8a6 score 0 pv
  info currmove a8a7 score 0 pv
  info score cp 0 depth 1 nodes 21 pv a5a4
  info starting search at depth 2
  info currmove a5a4 score -1 pv c4f7
  info score cp -1 depth 2 nodes 64 pv a5a4 c4f7
  info currmove b7b6 score -1 pv c4f7
  info currmove c7c6 score -1 pv c4f7
  info currmove d7d6 score -1 pv c4f7
  info currmove e7e6 score -1 pv c4e6
  info currmove f7f6 score -3 pv c4g8
  info currmove g7g6 score -1 pv c4f7
  info currmove h7h6 score -1 pv c4f7
  info currmove b7b5 score -1 pv c4b5
  info currmove c7c5 score -1 pv c4f7
  info currmove d7d5 score -1 pv e4d5
  info currmove e7e5 score -1 pv c4f7
  info currmove f7f5 score -1 pv e4f5
  info currmove g7g5 score -1 pv c4f7
  info currmove h7h5 score -1 pv c4f7
  info currmove b8a6 score -3 pv c4a6
  info currmove b8c6 score -1 pv c4f7
  info currmove g8f6 score -1 pv c4f7
  info currmove g8h6 score -1 pv c4f7
  info currmove a8a6 score -5 pv c4a6
  info currmove a8a7 score -1 pv c4f7
  info score cp -1 depth 2 nodes 605 pv a5a4 c4f7
  info starting search at depth 3
  info currmove a5a4 score -29997 pv c4f7
  info score cp -29997 depth 3 nodes 708 pv a5a4 c4f7
  info currmove b7b6 score -29997 pv c4f7
  info currmove c7c6 score -29997 pv c4f7
  info currmove d7d6 score -1 pv c4f7 e8d7
  info score cp -1 depth 3 nodes 975 pv d7d6 c4f7 e8d7
  info currmove e7e6 score 0 pv b2b3 a5a4
  info score cp 0 depth 3 nodes 1133 pv e7e6 b2b3 a5a4
  info currmove f7f6 score 0 pv a2a3 a5a4
  info currmove g7g6 score 0 pv a2a3 a5a4
  info currmove h7h6 score 0 pv a2a3 a5a4
  info currmove b7b5 score 0 pv c4f1 a5a4
  info currmove c7c5 score 0 pv a2a3 a5a4
  info currmove d7d5 score 0 pv e4d5 d8d5
  info currmove e7e5 score 0 pv b2b3 a5a4
  info currmove f7f5 score 0 pv e4e5 a5a4
  info currmove g7g5 score 0 pv a2a3 a5a4
  info currmove h7h5 score 0 pv a2a3 a5a4
  info currmove b8a6 score 0 pv a2a3 a5a4
  info currmove b8c6 score 0 pv a2a3 a5a4
  info currmove g8f6 score 0 pv e4e5 a5a4
  info currmove g8h6 score 0 pv a2a3 a5a4
  info currmove a8a6 score 0 pv a2a3 a5a4
  info currmove a8a7 score 0 pv a2a3 a5a4
  info score cp 0 depth 3 nodes 2275 pv e7e6 b2b3 a5a4
  bestmove e7e6
  
  ```
  
  Here something strange is going on because at the start of searching at depth 3, it correctly evaluates `a5a4` as leading to checkmate. However, once it finds a move that avoids instant checkmate, in this case first identifying `d7d6` and then `e7e6`, all further moves then have their score capped to the best move found so far. For example, `a8a7`, which leads to checkmate, is evaluated to have a score of `0`. As far as I understand, although the `alpha` value stores the best value that we can guarantee, this shouldn't affect the evaluations of each move.
  
  Things get stranger with even deeper searches. Here for example is the end of the search at depth 7:
  
  ```
  info starting search at depth 7
  info time 3000 ndes 3729598 nps 1243199 score 0
  info time 4000 ndes 4916163 nps 1229040 score 0
  info currmove a5a4 score -29997 pv c4f7
  info score cp -29997 depth 7 nodes 5572093 pv a5a4 c4f7
  info time 5000 ndes 6105741 nps 1221148 score 0
  info time 6000 ndes 7218855 nps 1203142 score 3
  info currmove b7b6 score -29997 pv c4f7
  info time 7000 ndes 8430976 nps 1204425 score 0
  info time 8000 ndes 9647996 nps 1205999 score -9
  info time 9000 ndes 10866782 nps 1207420 score -1
  info currmove c7c6 score -29995 pv c4e6 a5a4 e6f7
  info score cp -29995 depth 7 nodes 12123230 pv c7c6 c4e6 a5a4 e6f7
  info currmove d7d6 score 0 pv a2a3 a5a4 b2b3 d6d5 c2c3 d5d4
  info score cp 0 depth 7 nodes 12123237 pv d7d6 a2a3 a5a4 b2b3 d6d5 c2c3 d5d4
  info currmove e7e6 score 0 pv a2a3 a5a4 b2b3 e6e5 c2c3 b7b6
  info currmove f7f6 score 0 pv a2a3 a5a4 b2b3 f6f5 c2c3 f5f4
  info currmove g7g6 score 0 pv a2a3 a5a4 b2b3 g6g5 c2c3 g5g4
  info currmove h7h6 score 0 pv a2a3 a5a4 b2b3 h6h5 c2c3 h5h4
  info currmove b7b5 score 0 pv a2a3 a5a4 b2b3 b5b4 c2c3 c7c6
  info currmove c7c5 score 0 pv a2a3 a5a4 b2b3 b7b6 c2c3 b6b5
  info currmove d7d5 score 0 pv a2a3 a5a4 b2b3 d5d4 c2c3 d4d3
  info currmove e7e5 score 0 pv a2a3 a5a4 b2b3 b7b6 c2c3 b6b5
  info time 10000 ndes 12123300 nps 1212330 score 0
  info currmove f7f5 score 0 pv a2a3 a5a4 b2b3 f5f4 c2c3 b7b6
  info currmove g7g5 score 0 pv a2a3 a5a4 b2b3 g5g4 c2c3 g4g3
  info currmove h7h5 score 0 pv a2a3 a5a4 b2b3 h5h4 c2c3 h4h3
  info currmove b8a6 score 0 pv a2a3 a5a4 b2b3 b7b6 c2c3 b6b5
  info currmove b8c6 score 0 pv a2a3 a5a4 b2b3 b7b6 c2c3 b6b5
  info currmove g8f6 score 0 pv a2a3 a5a4 b2b3 b7b6 c2c3 b6b5
  info currmove g8h6 score 0 pv a2a3 a5a4 b2b3 b7b6 c2c3 b6b5
  info currmove a8a6 score 0 pv a2a3 a5a4 b2b3 b7b6 c2c3 b6b5
  info currmove a8a7 score 0 pv a2a3 a5a4 b2b3 b7b6 c2c3 b6b5
  info score cp 0 depth 7 nodes 12123356 pv d7d6 a2a3 a5a4 b2b3 d6d5 c2c3 d5d4
  bestmove d7d6
  
  ```
  
  Now all the outputted principle variations seem to just be in lexiographical order. I can't spot in my code where there might be an issue but am worried that I'm missing something obvious. My code is as follows:
  
  ```
  func (s *AlphaBetaSearch) Root() error {
      var pv pvList      // Holds the principle variation
      var childPV pvList // Holds the principle variation of the position after the first move is made
  
      childPV.new()
  
      for request := range s.requests {
          pos := request.pos // Position we are searching
  
          s.startTime = time.Now()    // Record start time so we know to stop if time is up
          s.nextTime = time.Now()     // Record next time as a counter so we can periodically print information
          s.nodeCount = 0             // Record number of nodes so we can stop after searching a certain number of nodes
          s.options = request.options // Store options in the search struct so we don't have to explicitly pass around.
          s.options.Stop = false      // Make sure we don't stop straight away if we were told to stop previously
  
          // Keep track of the best move found so far. This is outside the loop so that we can return the best move found
          // if we are asked to stop searching at a particular depth.
          bestMove := position.NoMove
  
          // Generate legal moves and annotate them with the evaluation after they've taken place so we can improve
          // move ordering in the search.
          legalMoves := pos.MovesLegalWithEvaluation(position.EvalSimple)
  
          // For loop for iterative deepening
          for depth := uint(1); depth <= s.options.Depth; depth++ {
              // Sort legal moves by the evaluation calculated above
              legalMoves.Sort()
  
              // Best score for a move found so far
              bestScore := position.NoEval
  
              // Alpha and beta
              // Alpha here is the best score we can be guaranteed to achieve
              // Beta here is the best score the opposing player can achieve
              alpha, beta := position.MinEval, position.MaxEval
  
              for _, move := range legalMoves.AsSlice() {
                  // Clear the child PV so it can be used again for this move
                  childPV.clear()
  
                  // Make move, evaluate score of this position, and then undo move.
                  pos.MakeMove(move)
                  score := -s.search(-beta, -alpha, depth-1, 1, &childPV, pos)
                  pos.UndoMove(move)
  
                  s.responses <- fmt.Sprintf("info currmove %s score %d pv %s", move.String(), score, childPV.String())
  
                  // Store evaluation of this move so that on the next iteration the move ordering is more effective
                  move.SetEval(position.ScoreFromPerspective(score, pos.SideToMove))
  
                  // If this is the best move we've seen so far...
                  if score > bestScore {
                      // Update bestScore to reflect this
                      bestScore = score
  
                      // Update the principle variation to use this move instead
                      pv.clear()
                      pv.catenate(move, &childPV)
  
                      // Record this as the best move
                      bestMove = move
  
                      // Set alpha to this score
                      alpha = score
  
                      s.responses <- fmt.Sprintf("info score cp %v depth %v nodes %v pv %s", bestScore, depth, s.nodeCount, pv.String())
                  }
              }
  
              s.responses <- fmt.Sprintf("info score cp %v depth %v nodes %v pv %s", bestScore, depth, s.nodeCount, pv.String())
          }
  
          s.responses <- fmt.Sprintf("bestmove %s", bestMove.String())
      }
  
      return nil
  }
  
  func (s *AlphaBetaSearch) search(alpha int16, beta int16, depth uint, ply int, pv *pvList, pos *position.Position) int16 {
      s.nodeCount++
  
      // If we're at depth 0, stop recursing and instead return a static evaluation of this position.
      if depth <= 0 {
          return position.ScoreFromPerspective(position.EvalSimple(pos), pos.SideToMove) // TODO: make more customisable
      }
  
      // Clear the principle variation
      pv.clear()
  
      // Generate all legal moves in this position
      legalMoves := pos.MovesLegal()
  
      // Initialise bestMove and bestScore to hold the best move found so far.
      bestMove, bestScore := position.NoMove, position.NoEval
  
      // TODO: doesn't yet understand draw by threefold repetition
  
      var childPV pvList
  
      for _, move := range legalMoves.AsSlice() {
          childPV.clear()
  
          pos.MakeMove(move)
          score := -s.search(-beta, -alpha, depth-1, ply+1, &childPV, pos)
          pos.UndoMove(move)
  
          // If this is the best score we've found so far...
          if score > bestScore {
              // Update bestScore and bestMove to track this (might not need bestMove)
              bestScore = score
              bestMove = move
              _ = bestMove
  
              // Add this to the principle variation
              pv.catenate(move, &childPV)
  
              // Beta cutoff:
              // The opposing player can guarantee a better position for themselves, so there's no point pursuing this position.
              if score >= beta {
                  return score
              }
  
              // If this is better than the best score we can guarantee so far, then update alpha to reflect this
              if score > alpha {
                  alpha = score
              }
  
          }
  
          // Print info if required
          if time.Since(s.nextTime) >= time.Second {
              diff := time.Since(s.startTime)
              s.responses <- fmt.Sprintf("info time %v ndes %v nps %v score %d", diff.Milliseconds(), s.nodeCount, s.nodeCount/int(diff.Seconds()), bestScore)
              s.nextTime = time.Now()
          }
  
          // If required to stop early, return alpha since this is the best we can do.
          if s.options.Stop || time.Since(s.startTime) > s.options.MoveTime {
              return alpha
          }
  
      }
  
      // If we have no moves available, it's either checkmate or stalemate, so return values
      // that reflect this.
      if legalMoves.Len() == 0 {
          if pos.KingInCheck(pos.SideToMove) {
              // Checkmate
              return -30000 + int16(ply) + 1
          }
  
          // Stalemate
          return 0 // TODO: return contempt value instead?
      }
  
      return bestScore
  }
  
  ```
  
  Can anybody spot what might be the mistake here?
  
  ---
  
  EDIT: Here's the evaluation logic:
  
  ```
  const (
      MaxEval  int16 = 30_000
      MinEval  int16 = -MaxEval
      MateEval int16 = MaxEval + 1
      NoEval   int16 = MinEval - 1
  )
  
  // Evaluator decides the numerical value of a position.
  // An int16 is used so that evaluations can be packed into moves compactly.
  // TODO: Consider refactoring into seperate package
  type Evaluator func(p *Position) int16
  
  var EvaluatorInfo = map[string]Evaluator{
      "simple": EvalSimple,
  }
  
  // GetEvaluator looks up an evaluator by name.
  func GetEvaluator(name string) Evaluator {
      return EvaluatorInfo[name]
  }
  
  // ScoreFromPerspective takes in a score where negative scores represent good positions for black and positive positions
  // for white, and takes in a side to move, and returns a positive evaluation from their perspective.
  func ScoreFromPerspective(score int16, sideToMove Color) int16 {
      if sideToMove == Black {
          return -score
      }
  
      return score
  }
  
  var simpleEvalTable = map[Piece]int16{
      Pawn:   1,
      Knight: 3,
      Bishop: 4,
      Rook:   5,
      Queen:  9,
      King:   1_000,
  }
  
  // EvalSimple evaluates the position using a simple material count.
  // TODO: This could definitely be sped up by using bitboards instead of the pos.Squares.
  func EvalSimple(pos *Position) int16 {
      overall := int16(0)
  
      for i := 0; i < 64; i++ {
          curr := pos.Squares[i]
  
          switch curr.Color() {
          case White:
              overall += simpleEvalTable[curr.Colorless()]
          case Black:
              overall -= simpleEvalTable[curr.Colorless()]
          }
      }
  
      return overall
  }
  
  ```
  
  and the movement code:
  
  ```
  // MakeMove makes a move on the chess board, or returns an error if it is invalid.
  // Bitboards for occupation and piece locations are updated through the setSquare function.
  func (p *Position) MakeMove(m Move) bool {
      // Need to handle 6 special cases:
      // - White king moving
      // - Black king moving
      // (These two cases can move two pieces at once and disable castling)
  
      // - White rook moving
      // - Black rook moving
      // (These two cases mean some castling privileges may be lost)
  
      // - White pawn moving forward two squares onto an empty square
      // - Black pawn moving forward two squares onto an empty square
      // (These two cases either perform an en passant capture or set the en passant target square)
  
      movingPiece := p.Squares[m.From()]
      var newEnPassantTarget uint8 = NoEnPassant
  
      switch {
      case movingPiece == WhiteKing:
          // Disable any type of castling for the white king as they have moved.
          p.Castling.off(longW | shortW)
  
          // The king has moved two squares and so it is known they have castled.
          // Here we only need to worry about moving the rook, as the king is moved by the general code outside of the switch.
          if abs(int(m.From())-int(m.To())) == 2 {
              // Determine if they have castled long or short.
              if m.To() == SquareG1 { // Short castle
                  p.setSquare(SquareF1, WhiteRook)
                  p.setSquare(SquareH1, Empty)
              } else { // Long castle
                  p.setSquare(SquareD1, WhiteRook)
                  p.setSquare(SquareA1, Empty)
              }
          }
      case movingPiece == BlackKing:
          // Disable any type of castling for the black king as they have moved.
          p.Castling.off(longB | shortB)
  
          // The king has moved two squares and so it is known they have castled.
          // Here we only need to worry about moving the rook, as the king is moved by the general code outside of the switch.
          if abs(int(m.From())-int(m.To())) == 2 {
              // Determine if they have castled long or short.
              if m.To() == SquareG8 { // Short castle
                  p.setSquare(SquareF8, BlackRook)
                  p.setSquare(SquareH8, Empty)
              } else { // Long castle
                  p.setSquare(SquareD8, BlackRook)
                  p.setSquare(SquareA8, Empty)
              }
          }
      case movingPiece == WhiteRook:
          // Disable castling for the king on the side where the rook has moved.
          if m.From() == SquareA1 {
              p.Castling.off(longW)
          } else if m.From() == SquareH1 {
              p.Castling.off(shortW)
          }
      case movingPiece == BlackRook:
          // Disable castling for the king on the side where the rook has moved.
          if m.From() == SquareA8 {
              p.Castling.off(longB)
          } else if m.From() == SquareH8 {
              p.Castling.off(shortB)
          }
      case p.Squares[m.To()] == WhiteRook:
          // Disable castling when a white rook is taken.
          if m.To() == SquareA1 {
              p.Castling.off(longW)
          } else if m.To() == SquareH1 {
              p.Castling.off(shortW)
          }
      case p.Squares[m.To()] == BlackRook:
          // Disable castling when a black rook is taken.
          if m.To() == SquareA8 {
              p.Castling.off(longB)
          } else if m.To() == SquareH8 {
              p.Castling.off(shortB)
          }
      case movingPiece == WhitePawn && p.Squares[m.To()] == Empty:
          if m.To()-m.From() == 16 {
              // The pawn has moved two full squares onto an empty square.
              // Therefore there is a new en passant target on the rank between its original position and its new position.
              newEnPassantTarget = m.From() + 8
          } else if m.To()-m.From() == 7 || m.To()-m.From() == 9 {
              // The pawn has moved diagonally onto an empty square -- this must be an en passant capture.
              p.setSquare(p.EnPassant-8, Empty)
          }
      case movingPiece == BlackPawn && p.Squares[m.To()] == Empty:
          if m.From()-m.To() == 16 {
              // The pawn has moved two full squares onto an empty square.
              // Therefore there is a new en passant target on the rank between its original position and its new position.
              newEnPassantTarget = m.To() + 8
          } else if m.From()-m.To() == 7 || m.From()-m.To() == 9 {
              // The pawn has moved diagonally onto an empty square -- this must be an en passant capture.
              p.setSquare(p.EnPassant+8, Empty)
          }
      }
  
      p.EnPassant = newEnPassantTarget
      p.setSquare(m.From(), Empty)
  
      if m.Promotion() == None {
          p.setSquare(m.To(), movingPiece)
      } else {
          p.setSquare(m.To(), m.Promotion().OfColor(p.SideToMove))
      }
  
      p.SideToMove = p.SideToMove.Invert()
  
      if p.KingInCheck(p.SideToMove.Invert()) {
          p.UndoMove(m)
          return false
      }
  
      // If the side to move is now white, we can update the fullmove clock.
      if p.SideToMove == White {
          p.FullMoves += 1
      }
  
      // If there has been no capture and it's not a pawn move, then we need to increment the halfmove clock.
      if movingPiece != WhitePawn && movingPiece != BlackPawn && p.Squares[m.To()] != Empty {
          p.HalfmoveClock += 1
      } else {
          p.HalfmoveClock = 0
      }
  
      return true
  }
  
  ```
  
  **Tags:** engines
  
  > **Comments:**
  > **username_1**: Could you provide the evaluation logic? It almost sounds like the `ScoreFromPerspective` is not adjusting the score properly from black's perspective and is leading it to choose moves that are the worst possible for black, except in mate where the score is calculated elsewhere at the end of the method. Alternatively, is `pos.MakeMove` swapping the `SideToMove` properly?  
  > **username_0**: @username_1 Thanks for the quick reply :) I've updated the post to include the evaluation logic. I'm fairly sure that MakeMove works correctly since I've tested it using perft and all the values match but might have missed something.  
  > **username_1**: From just a brief look, it doesn't seem like the issues are from the evaluation, and I think the SideToMove swapping is fine. However, I'm a bit confused by the part in `MakeMove` where the move is undone if the move was not legal. It doesn't look like your search does anything special in that case, so I think it ends up searching a null move and then undoing an illegal move that had already been undone. So I think the position gets into a bad state partway through the search. Try calling `continue` if the `MakeMove` returns false to skip over the rest of the loop for that illegal move.  
  > **username_0**: Thanks for having a look... I think the stuff about legal/illegal moves should be okay since I filter and only evaluate legal moves, but might be a bit wasteful and maybe I should do it when I iterate over each move. Thanks again!  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_0 on 2023-07-09. Score: 3
  
  I ended up finding the issue -- the move sorting wasn't working correctly. This meant that at the start of every iteration for iterative deepening, a bad move would be considered first and so set as the best move by default. Then when search time was up, this bad move would be returned as the best move to play.
  
  
  ---
  
  