Where to enter/read position into hash table in perft?

[mvanthoor]

Hi

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,
}

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:

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
}

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?

[fabianVDW]

Posting lost due to moderator stupidity.

Sorry about that, HGM.

[mvanthoor]

Thanks for your reply Most of the things you describe are already implemented. Thanks for the tip with regard to the length of the hash table being a power of 2 to make calculation faster.

Am I correct that I should be trying to read just before

Code: Select all

board.gen_all_moves(mlp.get_list_mut(index));

Then, if I find anything, just return the stored number of leaf nodes and if I don't find anything, do the normal perft routine, and store the position just before passing back the number of leaf nodes as found by the normal perft part?

If so, I had it correct from the beginning and must have made a mistake somewhere. Probably something with regard to initializing / clearing memory again in that case.

edit: I went in search of the elusive "Bruce Moreland pages" because they're often talked about. Found them in the wayback machine. Unfortunately they seem to be unfinished (much more so than I expected), but they do say this about the hash entry:

When you get a result from a search, and you want to store an element in the table, it is important to record how deep the search went, if you plan to use the hash table to avoid doing redundant work. If you searched this position with a 3-ply search, and you come along later planning to do a 10-ply search, you can't assume that the information in this hash element is accurate. So the search depth for this sub-tree is also recorded.

So I had everything right all along with regard to the concept.... except for the fact that I didn't use it as a hash table I stored the positions I found one after the other, starting at the beginning when full, and searched linear. (Sometimes I feel like $%^#@@#$.... forgetting things like this must be because all of the business software programming I do during the day )

[fabianVDW]

Trying to recreate my post from earlier:

You will want to have O(1) when reading from the hashtable, instead of a linear search for each key.
So in Rust, I would do:

Code: Select all

let mut hash_table = vec![HashEntry::default(); HASH_SIZE];

pub fn insert_entry(hash_table: &mut Vec<HashEntry>, entry: HashEntry){
	let existing_entry = hash_table[entry.hash % hash_table.len()];
	if want_to_override(existing_entry,entry){
		hash_table[entry.hash % hash_table.len()] = entry;
	}
}
pub fn query(key: usize, hash_table: &Vec<HashEntry>) -> Option<HashEntry>{
	let entry_at = hash_table[key % hash_table.len()];
	if entry_at.hash == key{
		Some(entry_at)
	}else{
		None
	}
}

for which you will want to fill the function want_to_override with life with that you deem as a useful replacing strategy, e.g. storing the greatest depth. Note that this line

Code: Select all

entry_at.hash == key

is where things can go terribly wrong when two different positions map to the same keys (which can happen with Zobrist), as an invalid HashEntry (for that position) can be returned.
If the length of the hash_table is a power of 2

Code: Select all

key % hash_table.len()

will also collapse into

Code: Select all

key & (HASH_SIZE-1)

,
which should be faster than the modolus calculation.

[fabianVDW]

Am I correct that I should be trying to read just before

Code: Select all

board.gen_all_moves(mlp.get_list_mut(index));

Then, if I find anything, just return the stored number of leaf nodes and if I don't find anything, do the normal perft routine, and store the position just before passing back the number of leaf nodes as found by the normal perft part?

If so, I had it correct from the beginning and must have made a mistake somewhere. Probably something with regard to initializing / clearing memory again in that case.

That's correct, but from your post I can't tell whether you also test if the depth of the hashentry matches. This is also obviously required, as you don't want to return the perft of depth4 from a position for which depth 3 is stored. I am not sure whether people store multiple depth perft's in one hash entry, or just the highest depth. If so, you could modify your hash-entry a bit, which in turn would require more memory for each hashentry.

[mvanthoor]

That's correct, but from your post I can't tell whether you also test if the depth of the hashentry matches. This is also obviously required, as you don't want to return the perft of depth4 from a position for which depth 3 is stored. I am not sure whether people store multiple depth perft's in one hash entry, or just the highest depth. If so, you could modify your hash-entry a bit, which in turn would require more memory for each hashentry.

I do check the depth:

Code: Select all

    pub fn leaf_nodes(&self, depth: u8, zk: ZobristKey) -> Option<u64> {
        let index = (zk % self.max_entries) as usize;
        let correct_key = self.hash_table[index].zobrist_key == zk;
        let correct_depth = self.hash_table[index].depth == depth;
        if correct_key && correct_depth {
            Some(self.hash_table[index].leaf_nodes)
        } else {
            None
        }
    }

With regard to storing positions in the hash-table: for now, I'm only storing positions if an index isn't occupied yet. Shouldn't matter for the results. I'll look at a replacement scheme later.

The hash routine now seems to work, at least partially: perft 6 dropped from 4.2 seconds to about 1.6, and perft 7 dropped from 112 seconds to 41 seconds... but the numbers are off starting from perft 6, sometimes only by one (!) node The miscalculation is always different as well as far as I can see. For example:

Code: Select all

With hash-table: Perft 6: 119060317 (1326 ms)
W/o hash-table: Perft 6: 119060324 (4218 ms) <== this one is correct

I think I'll have to go and check my make_move() function to see if I have any mistakes or omissions in keeping the Zobrist-key updated, because there are multiple different positions having the same zobrist key, at the same depth, or the numbers wouldn't be off.

Could it actually be that I have a random number generator seed that generates the same random number twice, so for example... white pawn on e3 ends up with the same random number as black knight on c6... ? I'll seed the random number generator from entropy first before I try jacking around with the make_move() function.

edit: I seeded the Zobrist random number generator from entropy (different seed at every run). The numbers at perft 6 and higher are always off. I'll switch from SmallRNG to a different random number generator, and if that doesn't work, I'll go and check make_move().

(unmake_move() doesn't maintain Zobrist keys. make_move() just stores the board state including the Zobrist-key in a vector. unmake_move() just pops the state off the vector and restores it after unmaking the move. I've checked; the Zobrist keys before make_move() and after unmake_move() are always the same.)

[fabianVDW]

That really sounds like a make move error to me, zobrist collision with that amount of nodes is unlikely to occur that often

edit: For debugging purposes, you can try to make zobrist keys static, or start from a fixed seed. This makes it easier to find the error, just perft_div until you found the illegal moves. you might need to save the cache though, as the error also partially seems to be coming from there

[mvanthoor]

That really sounds like a make move error to me, zobrist collision with that amount of nodes is unlikely to occur that often

edit: For debugging purposes, you can try to make zobrist keys static, or start from a fixed seed. This makes it easier to find the error, just perft_div until you found the illegal moves. you might need to save the cache though, as the error also partially seems to be coming from there

I have removed all zobrist permutations from make_move, and removed hash usage from perft. It sped up perft by almost 2 million found leaf nodes per second; I've ran the entire perft suite from perftsuite.epd. The result is correct for all positions.

I'm now going to try and just rebuild the zobrist-key from scratch at the very end of make_move (I know this will slow down make_move a lot, but it allows me to see if I forgot anything anywhere), using the build_zobrist_key() function that I have in the board struct:

Code: Select all

    pub fn build_zobrist_key(&mut self) {
	self.zobrist_key = 0;
        for (piece, (bb_w, bb_b)) in self.bb_w.iter().zip(self.bb_b.iter()).enumerate() {
            let mut white = *bb_w;
            let mut black = *bb_b;

            while white > 0 {
                let square = next(&mut white);
                self.zobrist_key ^= self.zobrist_randoms.piece(WHITE, piece, square);
            }

            while black > 0 {
                let square = next(&mut black);
                self.zobrist_key ^= self.zobrist_randoms.piece(BLACK, piece, square);
            }
        }

        self.zobrist_key ^= self.zobrist_randoms.castling(self.castling);
        self.zobrist_key ^= self.zobrist_randoms.side(self.active_color as usize);
        self.zobrist_key ^= self.zobrist_randoms.en_passant(self.en_passant);
    }
    

I'm almost convinced that this function (and the ones in the "zobrist" module) are correct. I already did a perft(1), and had the zobrist creation process printed for each move. It seems to be correct. The only thing I can still imagine is that not all of the random numbers are unique.

The zobrist module has...
2 sides, 6 pieces, 64 squares for the pieces (three-dimensional array)
16 randoms for castling (4 bits; 0-15)
two randoms for sides
two randoms for en-passant (set and not set)

[mvanthoor]

Found the problem in the en-passant zobrist function:

Code: Select all

    pub fn en_passant(&self, en_passant: Option<u8>) -> u64 {
        // let x = if en_passant.is_some() { EP_YES } else { EP_NO };
        // self.rnd_en_passant[x]
        if let Some(ep) = en_passant {
            self.rnd_en_passant[ep as usize]
        } else {
            self.rnd_en_passant[ALL_SQUARES]
        }
    }

I've watched many of BlueFever Software's video's on VICE with regard to the concepts of writing a chess engine. That series is a great piece of work, but it does seem to contain a bug in generating the hash keys. It generates a key if the EP-square is set, and no key if it isn't set. I did something similar: generating one key if set, generating the other if not set. See the commented out code. above.

This seems to be problematic, because if you do it that way, different positions can get the same hash key, apparently.

As I wrote above, I stripped all hash key updates from make_move(), and used the build_zobrist_key() in the Board struct, which I use to initialize the key when the board is created. It still didn't work when using the hash-table.

Then I replaced the en_passant zobrist code, mainly because I've always felt like "this can't be right...." (You don't have a single castling key per color either; for "can castle" or "can't castle" per color). Instead of generating only two keys (for set and not set), I created 65 EP keys; 64 for the squares (I don't care about wasting the memory space for 48 unused keys, which is 384 bytes) and one key for "not set". When creating the Zobrist keys, I now return the key for the exact EP square if set, and the key for "not set" if no EP-square is set.

Without changing anything else, the perft function with hash started working correctly.

make_move() became 50% slower (17 mln leaves/sec vs 30 mln leaves/sec) when I stripped the zobrist updates from it and started using build_zobrist_keys() to generate the keys from scratch. Even with that handicap, the hash now speeds up the perft function to 70-100 million moves/sec depending on the position. I wonder if it'll actually reach 200 million positions/sec after I reinstate the zobrist updates in make_move().

(The other change I made is that I now overwrite a hash entry if, for a certain Zobrist Key, leaf nodes have been found at a greater depth. I'll see what happens when I just bluntly overwrite an existing entry.)

[Terje]

There are bugs in VICE, but zobrist keys are not one of them. VICE has a separate en passant key for each square (even squares that can never be an en passant square).

You don't need a separate key for "no en passant" as "no key" can represent that. VICE does this.