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

[mvanthoor]

Hi,

Where do you derive the nps drop from? I don't calculate nps right now; I only calculate how many leaves are found per second.

As the hash makes counting faster, leaves per second will be higher. I don't care too much about NPS; I think leaves/second or time to depth are more important.

I'm just glad I got the same speedup as you mentioned with qperft.

Also, maybe I wasn't completely clear in one of the earlier posts. The drop from 27 to 17 seconds was because of reinstating zobrist key updates, instead of recalculating them from scratch.

To achieve 17 seconds for perft 7 I had to use a 28 GB hash. Now I can achieve 17-18 seconds with only a 2GB hash. With the buckets, even a 32 GB hash is very usable (which has about 1.2M total entries, comparable to your 1M.) Even a 16 MB hash brings improvement (perft 7 drops from 113.2 to 34 secs.) Before the bucket implementation, 16 MB of hash was useless.

[hgm]

Oh, sorry, my mistake. I thought this was what you printed under 'execution speed', (for the same perft leaves/sec would be strictly proportional nodes/sec), and that you actually counted the generated leaves. And I misread the number of digits, thinking that it dropped from 280 Mnps to 114 Mnps, while in fact it said only 28 Mnps in the first case.

OK, so you cannot see how expensive the hash probe is from this. In micro-Max the search speed rises from 1Mnps to 6Mnps when I remove the code for hashing.

Surely you mean 32MB hash for 1.2M entries, not 32GB?

[mvanthoor]

Oh, sorry, my mistake. I thought this was what you printed under 'execution speed', (for the same perft leaves/sec would be strictly proportional nodes/sec), and that you actually counted the generated leaves. And I misread the number of digits, thinking that it dropped from 280 Mnps to 114 Mnps, while in fact it said only 28 Mnps in the first case.

I just print the number of leaves found for each perft depth. So if a depth requires 195 million leaves, and it finds them in 20 seconds, the speed is 9.75 million leaves/sec. The number of nodes traversed is larger. If this is also a good speed indication, I can easily report it.

OK, so you cannot see how expensive the hash probe is from this. In micro-Max the search speed rises from 1Mnps to 6Mnps when I remove the code for hashing.

So I should count all the traversed nodes to compare this.

Surely you mean 32MB hash for 1.2M entries, not 32GB?

Yes. 32MB. Typo.

This evening I'll optimize the hash memory layout. (I'll probably sacrifice the least significant byte from the zobrist key for storing the depth, so the entry size is 16 bits instead of 17. Rust pads an entry to 24 bytes, because it is the first mutliple of 8.)

[hgm]

In Qperft I work the depth into the key, so that the same position at a different depths hashes to a different location. For search you would not want that, because you want to accept any probe that has a depth that is equal or higher. But for perft you can only use equal depth, as unlike search scores, perft counts for higher depth are not better but wrong. This has the disadvantage, however, that I cannot see the depth during replacement, as I don't store it.

Why are your entries so large anyway? Do you also store the redundant key bits (i.e. those that are guaranteed to match, because they were used as table index)?

[mvanthoor]

In Qperft I work the depth into the key, so that the same position at a different depths hashes to a different location. For search you would not want that, because you want to accept any probe that has a depth that is equal or higher. But for perft you can only use equal depth, as unlike search scores, perft counts for higher depth are not better but wrong. This has the disadvantage, however, that I cannot see the depth during replacement, as I don't store it.

I was going to do the same thing, but somewhat differently. As in: first reset the least significant byte of the zobrist key to 0. Then use the result to calculate the index of the hash table, and *then* store the search depth in the first byte.

Why are your entries so large anyway? Do you also store the redundant key bits (i.e. those that are guaranteed to match, because they were used as table index)?

I'm using an unsigned 64-bit int for both the zobrist key and the leaf nodes. I store the entire zobrist key in the entry. Perft 7 already approaches the limits of a 32-bit unsigned int, and I don't know if I can get away with using a 32-bit zobrist key.

As said above: I'm considering "throwing away" part of the zobrist data by first setting the first byte (or maybe more) to 0, then calculate the index, and store the depth and maybe other things in the bytes I reset. (Same sort of technique as is often used for moves; with bits representing different kinds of data.)

[mvanthoor]

I just realized: The other way around, actually.

- Calculate the index from the 7 most significant bytes of the zobrist key.
- Save the 1 "sacrificed" least significant byte and the depth byte in the entry (2 bytes)
- Save the leaf node u64 in the entry (8 bytes).

That would give me a 10 byte entry, instead of 17 bytes. (After finding the bucket at the index, I'd have to compare that last sacrificed byte in the incoming key with the ones in the bucket.)

I'll have to test how Rust will pad if I put 6 entries of 10 bytes in a bucket:

1: (6 entries * 10 bytes) + 4 bytes padding
2: (10 bytes + 6 bytes padding) * 6 = 96 bytes

If Rust pads in the second way, I could only use 4 buckets to stay at or under 64 bytes.