Body: <p>I am currently developing my own chess engine in rust. It all was working pretty fine, until I added transposition tables. Where my engine was playing the reasonable move e2e4 at a lower depth, with transposition tables, it now plays weak moves at higher depths like h2h4, already thinking it is loosing by 100 centipawns.</p>
  <p>My transposition table uses Zorbist hashing, using a dual keep depth and always replace replacement scheme. I can't think of any reasons for my code being faulty right now, except for maybe the Zorbist number table having unsound random numbers.</p>
  <p>Here is my code for the negamax search:</p>
  <pre><code>pub fn negamax(state: &amp;mut GameState, info: &amp;mut SearchInfo, depth: u32, alpha: Eval, beta: Eval) -&gt; (Eval, Option&lt;Move&gt;) {
      unsafe {
          NODES_SEARCHED += 1;
      }
  
      let alpha_orig = alpha;
  
      let mut alpha = alpha;
      let mut beta = beta;
  
      let tt_probe = info.tt.get(state.zorbist_key);
      match tt_probe {
          Some(entry) =&gt; {
              if entry.depth &gt;= depth {
                  match entry.flag {
                      TTFlag::EXACT =&gt; return (entry.eval, entry.best_move),
                      TTFlag::LOWERBOUND =&gt; {
                          alpha = max(alpha, entry.eval);
                      },
                      TTFlag::UPPERBOUND =&gt; {
                          beta = min(beta, entry.eval);
                      },
                  };
                  if alpha &gt;= beta {
                      return (entry.eval, None);
                  }
              }
          }
          None =&gt; {},
      }
  
      let moves = generate_moves(state);
  
      if moves.is_empty() {
          return (INFINITY * state.get_winner(), None);
      }
  
      if depth == 0 {
          return (quiescence(state, alpha, beta), None);
      }
  
      let moves = order_moves_negamax(moves);
  
      let mut alpha = alpha;
      let mut best_eval = -INFINITY;
      let mut best_move: Option&lt;Move&gt; = None;
  
      for mv in moves {
          unsafe {
              NODES_SEARCHED += 1;
          }
          state.make_move(&amp;mv);
          let (curr_eval, _) = negamax(state, info, depth - 1, -beta, -alpha);
          state.undo_move();
          let curr_eval = curr_eval * -1;
          if curr_eval &gt; best_eval {
              best_eval = curr_eval;
              best_move = Some(mv);
          }
          if curr_eval &gt; alpha {
              alpha = curr_eval;
          }
          if alpha &gt;= beta {
              break;
          }
      }
  
      let flag = if best_eval &lt;= alpha_orig { TTFlag::UPPERBOUND } else if best_eval &gt;= beta { TTFlag::LOWERBOUND } else { TTFlag::EXACT };
      info.tt.store(TTEntry {
          key: state.zorbist_key,
          depth: depth,
          eval: best_eval,
          flag: flag,
          best_move: best_move,
      });
  
      return (best_eval, best_move);
  
  }
  </code></pre>
  <p>And here my code for generating the Zorbist table (using lazy_static!)</p>
  <pre><code>lazy_static! {
      pub static ref ZORBIST_PIECE_LOOKUP: [[Hash; 64]; 12] = {
          let mut rng = rand::thread_rng();
          let mut table = [[0; 64]; 12];
          for i in 0..64 {
              for j in 0..12 {
                  table[j][i] = rng.gen::&lt;Hash&gt;();
              }
          }
          return table;
      };
  }
  </code></pre>
  <p>And last but not least my code for the Transposition table:</p>
  <pre><code>pub struct SearchInfo {
      pub tt: TranspostionTable,
  }
  
  pub struct TranspostionTable {
      size: usize,
      keep_depth: Vec&lt;Option&lt;TTEntry&gt;&gt;,
      always_replace: Vec&lt;Option&lt;TTEntry&gt;&gt;,
  }
  
  #[derive(Debug, Clone, Copy, Eq, PartialEq)]
  pub struct TTEntry {
      pub key: Hash,
      pub depth: u32,
      pub eval: Eval,
      pub flag: TTFlag,
      pub best_move: Option&lt;Move&gt;,   
  }
  
  #[derive(Debug, Clone, Copy, Eq, PartialEq)]
  pub enum TTFlag {
      EXACT,
      UPPERBOUND,
      LOWERBOUND,
  }
  
  impl TranspostionTable {
      pub fn new(size: usize) -&gt; TranspostionTable {
          TranspostionTable {
              size: size,
              keep_depth: vec![None; size],
              always_replace: vec![None; size],
          }
      }
  
      #[inline]
      fn index(&amp;self, zorbist: Hash) -&gt; usize {
          (zorbist % self.size as u64) as usize
      }
  
      pub fn get(&amp;self, zorbist: Hash) -&gt; Option&lt;TTEntry&gt; {
          let i = self.index(zorbist);
          if let Some(entry) = self.keep_depth[i] {
              if entry.key == zorbist {
                  return Some(entry);
              }
          }
  
          if let Some(entry) = self.always_replace[i] {
              if entry.key == zorbist {
                  return Some(entry);
              }
          }
  
          return None;
      }
  
      pub fn store(&amp;mut self, entry: TTEntry) {
          let i = self.index(entry.key);
          if let Some(old) = self.keep_depth[i] {
              if entry.depth &gt;= old.depth {
                  self.keep_depth[i] = Some(entry);
              } else {
                  self.always_replace[i] = Some(entry);
              }
          } else {
              self.keep_depth[i] = Some(entry);
              self.always_replace[i] = Some(entry);
          }
      }
  }
  </code></pre>
  <p>Could you think of anything I am doing wrong here?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-04-18T13:49:33.843Z
Comments.Text: I believe that your recursive calls to negamax (and possibly quiesence) are wrong. You should be negating the result of negamax and quiesence at each recursive call. This negation is what allows it to work like minimax without needing to keep track of whether the player is trying to minimize or maximize. However, it's important for the evaluation function to return a score relative to the side to move (i.e. a position favorable to black should be evaluated with a positive score when it is black's turn to move).
Comments.UserDisplayName: Nelson O
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-04-18T13:50:58.460Z
Comments.Text: See: https://www.chessprogramming.org/Alpha-Beta#Negamax_Framework and https://www.chessprogramming.org/Quiescence_Search#Pseudo_Code
Comments.UserDisplayName: Nelson O
Tags: <engines><programming><transpositions>
Title: Transposition table produces diffrent and wrong search results
ThreadText: # Transposition table produces diffrent and wrong search results
  
  (Asked by: username_0 on 2023-02-24)
  
  I am currently developing my own chess engine in rust. It all was working pretty fine, until I added transposition tables. Where my engine was playing the reasonable move e2e4 at a lower depth, with transposition tables, it now plays weak moves at higher depths like h2h4, already thinking it is loosing by 100 centipawns.
  
  My transposition table uses Zorbist hashing, using a dual keep depth and always replace replacement scheme. I can't think of any reasons for my code being faulty right now, except for maybe the Zorbist number table having unsound random numbers.
  
  Here is my code for the negamax search:
  
  ```
  pub fn negamax(state: &mut GameState, info: &mut SearchInfo, depth: u32, alpha: Eval, beta: Eval) -> (Eval, Option<Move>) {
      unsafe {
          NODES_SEARCHED += 1;
      }
  
      let alpha_orig = alpha;
  
      let mut alpha = alpha;
      let mut beta = beta;
  
      let tt_probe = info.tt.get(state.zorbist_key);
      match tt_probe {
          Some(entry) => {
              if entry.depth >= depth {
                  match entry.flag {
                      TTFlag::EXACT => return (entry.eval, entry.best_move),
                      TTFlag::LOWERBOUND => {
                          alpha = max(alpha, entry.eval);
                      },
                      TTFlag::UPPERBOUND => {
                          beta = min(beta, entry.eval);
                      },
                  };
                  if alpha >= beta {
                      return (entry.eval, None);
                  }
              }
          }
          None => {},
      }
  
      let moves = generate_moves(state);
  
      if moves.is_empty() {
          return (INFINITY * state.get_winner(), None);
      }
  
      if depth == 0 {
          return (quiescence(state, alpha, beta), None);
      }
  
      let moves = order_moves_negamax(moves);
  
      let mut alpha = alpha;
      let mut best_eval = -INFINITY;
      let mut best_move: Option<Move> = None;
  
      for mv in moves {
          unsafe {
              NODES_SEARCHED += 1;
          }
          state.make_move(&mv);
          let (curr_eval, _) = negamax(state, info, depth - 1, -beta, -alpha);
          state.undo_move();
          let curr_eval = curr_eval * -1;
          if curr_eval > best_eval {
              best_eval = curr_eval;
              best_move = Some(mv);
          }
          if curr_eval > alpha {
              alpha = curr_eval;
          }
          if alpha >= beta {
              break;
          }
      }
  
      let flag = if best_eval <= alpha_orig { TTFlag::UPPERBOUND } else if best_eval >= beta { TTFlag::LOWERBOUND } else { TTFlag::EXACT };
      info.tt.store(TTEntry {
          key: state.zorbist_key,
          depth: depth,
          eval: best_eval,
          flag: flag,
          best_move: best_move,
      });
  
      return (best_eval, best_move);
  
  }
  
  ```
  
  And here my code for generating the Zorbist table (using lazy\_static!)
  
  ```
  lazy_static! {
      pub static ref ZORBIST_PIECE_LOOKUP: [[Hash; 64]; 12] = {
          let mut rng = rand::thread_rng();
          let mut table = [[0; 64]; 12];
          for i in 0..64 {
              for j in 0..12 {
                  table[j][i] = rng.gen::<Hash>();
              }
          }
          return table;
      };
  }
  
  ```
  
  And last but not least my code for the Transposition table:
  
  ```
  pub struct SearchInfo {
      pub tt: TranspostionTable,
  }
  
  pub struct TranspostionTable {
      size: usize,
      keep_depth: Vec<Option<TTEntry>>,
      always_replace: Vec<Option<TTEntry>>,
  }
  
  #[derive(Debug, Clone, Copy, Eq, PartialEq)]
  pub struct TTEntry {
      pub key: Hash,
      pub depth: u32,
      pub eval: Eval,
      pub flag: TTFlag,
      pub best_move: Option<Move>,   
  }
  
  #[derive(Debug, Clone, Copy, Eq, PartialEq)]
  pub enum TTFlag {
      EXACT,
      UPPERBOUND,
      LOWERBOUND,
  }
  
  impl TranspostionTable {
      pub fn new(size: usize) -> TranspostionTable {
          TranspostionTable {
              size: size,
              keep_depth: vec![None; size],
              always_replace: vec![None; size],
          }
      }
  
      #[inline]
      fn index(&self, zorbist: Hash) -> usize {
          (zorbist % self.size as u64) as usize
      }
  
      pub fn get(&self, zorbist: Hash) -> Option<TTEntry> {
          let i = self.index(zorbist);
          if let Some(entry) = self.keep_depth[i] {
              if entry.key == zorbist {
                  return Some(entry);
              }
          }
  
          if let Some(entry) = self.always_replace[i] {
              if entry.key == zorbist {
                  return Some(entry);
              }
          }
  
          return None;
      }
  
      pub fn store(&mut self, entry: TTEntry) {
          let i = self.index(entry.key);
          if let Some(old) = self.keep_depth[i] {
              if entry.depth >= old.depth {
                  self.keep_depth[i] = Some(entry);
              } else {
                  self.always_replace[i] = Some(entry);
              }
          } else {
              self.keep_depth[i] = Some(entry);
              self.always_replace[i] = Some(entry);
          }
      }
  }
  
  ```
  
  Could you think of anything I am doing wrong here?
  
  **Tags:** engines, programming, transpositions
  
  > **Comments:**
  > **username_1**: I believe that your recursive calls to negamax (and possibly quiesence) are wrong. You should be negating the result of negamax and quiesence at each recursive call. This negation is what allows it to work like minimax without needing to keep track of whether the player is trying to minimize or maximize. However, it's important for the evaluation function to return a score relative to the side to move (i.e. a position favorable to black should be evaluated with a positive score when it is black's turn to move).  
  > **username_1**: See: https://www.chessprogramming.org/Alpha-Beta#Negamax_Framework and https://www.chessprogramming.org/Quiescence_Search#Pseudo_Code  
  
  ---
  
  ## 0 answers
  
  