2

I am struggeling to get the transposition table aspect of my search algorithm right. These are the table functions:

pub fn lookup(&self, hash: ZHash, depth: u32) -> Option<&TranspositionEntry> {
        let entry = &self.entries[hash.0 as usize % T];
        if entry.zhash == hash && entry.depth >= depth{
            Some(entry)
        } else {
            None
        }
    }
pub fn add_entry(&mut self, hash: ZHash,  eval: i32, depth: u32) {
        let entry = &mut self.entries[hash.0 as usize % T];
        if entry.zhash.0 == 0 {
            entry.zhash = hash;
            entry.eval = eval;
            entry.depth = depth;
            self.occupancy += 1;
        } else if entry.zhash == hash && entry.depth < depth {
            entry.depth = depth;
            entry.eval = eval;
        }
    }

And this is my minimax-alpha-beta implementation:

fn minimax_alpha_beta(
        &mut self,
        board_state: &ChessBoardState,
        ply_remaining: u32,
        ply_from_root: u32,
        mut alpha: i32,
        mut beta: i32
    ) -> i32 {
        if let Some(te) = self.transposition_table.lookup(board_state.zhash, ply_remaining) {
            return te.eval;
        }

        if ply_remaining == 0 {
            let eval = Self::eval(board_state);
            self.transposition_table.add_entry(board_state.zhash, eval, ply_remaining);
            return eval;
        }

        let mut moves = board_state.generate_legal_moves_for_current_player();

        // No moves, either draw or checkmate
        if moves.len() == 0 {
            let score = self.calc_draw_or_mate_score(ply_remaining);
            self.transposition_table
                .add_entry(board_state.zhash, score, ply_remaining);
            return score;
        }

        // Check for drawing moves
        if self.is_draw(board_state, ply_from_root) {
            self.transposition_table.add_entry(board_state.zhash, 0, ply_remaining);
            return 0;
        }

        // Sort moves by expected value
        moves.sort_by(|a, b| b.get_type().cmp(&a.get_type()));

        if board_state.side == PieceColor::White {
            let mut value = i32::MIN;

            for mv in &moves {
                let new_board = board_state.exec_move(*mv);

                value = max(
                    value,
                    self.minimax_alpha_beta(&new_board, ply_remaining - 1, ply_from_root + 1, alpha, beta),
                );
                alpha = max(alpha, value);
                if value >= beta {
                    break;
                }
            }
            self.transposition_table.add_entry(board_state.zhash, value, ply_remaining);
            value
        } else {
            let mut value = i32::MAX;
            for mv in &moves {
                let new_board = board_state.exec_move(*mv);
                value = min(
                    value,
                    self.minimax_alpha_beta(&new_board, ply_remaining - 1, ply_from_root + 1, alpha, beta),
                );

                beta = min(beta, value);
                if value <= alpha {
                    break;
                }
            }
            self.transposition_table.add_entry(board_state.zhash, value, ply_remaining);
            value
        }
    }
}

I am thoroughly confused when to use the ply_from_root vs ply_remaining when storing/searching the transposition table and also if it makes sense to try and update the transposition table after it has looped over the possible moves. Can someone englighten me here?

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.