Where to enter/read position into hash table in perft?
Posted: Sat Mar 28, 2020 3:49 pm
Hi
I seem to be somewhat stuck on this concept. I've created a simple hash table:
So basically its a vector with hash entries, backed by a counter and a max-entry limit. If the hashtable hits the number of max entries, it just starts putting entries at index 0 again.
The hash-table is passed to the perft function by reference. Putting entries in it and reading from it works. This is the perft function:
It's just the normal basic perft function (with the exception that it uses a move list pool instead of initializing its own move list on each entry).
When I put a board and depth in it, the result is perfect (tested with all positions in perftsuite.epd).
The one thing I don't understand is: where do I integrate the hash-table?
I've tried inserting the position at several places in the function, and trying to return the number of leaf nodes found in the hash, but nothing seems to work. The function just becomes incredibly slow when searching the hash table and never finds anything.
Also: when searching the hash table, should I just be searching for the Zobrist Key, or on the Zobrist key and depth combination?
I seem to be somewhat stuck on this concept. I've created a simple hash table:
Code: Select all
impl PerftHashEntry {
pub fn new(d: u8, zk: ZobristKey, ln: u64) -> PerftHashEntry {
PerftHashEntry {
depth: d,
zobrist_key: zk,
leaf_nodes: ln,
}
}
}
pub struct PerftHashTable {
hash_table: Vec<PerftHashEntry>,
max_entries: u64,
count: u64,
}
The hash-table is passed to the perft function by reference. Putting entries in it and reading from it works. This is the perft function:
Code: Select all
pub fn perft(
board: &mut Board,
depth: u8,
mlp: &mut MoveListPool,
hash: &mut PerftHashTable,
) -> u64 {
let mut leaf_nodes: u64 = 0;
let index = depth as usize;
if depth == 0 {
return 1;
}
board.gen_all_moves(mlp.get_list_mut(index));
for i in 0..mlp.get_list(index).len() {
let current_move = mlp.get_list(index).get_move(i);
if !make_move(board, current_move) {
continue;
};
leaf_nodes += perft(board, depth - 1, mlp, hash);
unmake_move(board);
}
leaf_nodes
}
When I put a board and depth in it, the result is perfect (tested with all positions in perftsuite.epd).
The one thing I don't understand is: where do I integrate the hash-table?
I've tried inserting the position at several places in the function, and trying to return the number of leaf nodes found in the hash, but nothing seems to work. The function just becomes incredibly slow when searching the hash table and never finds anything.
Also: when searching the hash table, should I just be searching for the Zobrist Key, or on the Zobrist key and depth combination?