On-the fly hash key generation?

[Evert]

I've always generated keys for my hash tables at the beginning of the program. This requires an array with 2*piece_types*board_size elements. Not too bad, but it does grow if you include more piece types or move to larger boards and it's yet another thing competing for cache storage space.

So I'm wondering, has anyone tried to generate hash keys on the fly? This requires some calculation, but it doesn't require any storage space. If the calculation can be done fast enough, the reduced cache pressure may make it worthwhile. Or not? Any thoughts?

[mar]

That's interesting and I think it might be doable.
I would probably go for something like (feature_index ^ magic1)*magic2 (assuming 64-bit keys).
If it's not enough I'd try to add other ops, rotations are always nice
I'm pretty sure that it's possible to come up with something both fast and giving usable keys (some experimenting should probably do).

I've seen in practice that generating zobrist keys doesn't really require statistically good PRNGs.

[hgm]

HaChu does that. It multiplies a piece key with a square key.

[Karlo Bala]

HaChu does that. It multiplies a piece key with a square key.

Interesting approach. I wonder whether it is possible to use similar technique for hashing sliding piece attacks? For example, file/rank occupancy X square key. Unlike in the magic attack generation, here we could use hash tables of an arbitrary size. I suppose something similar already exists...

[AlvaroBegue]

You could probably skip the Zobrist key altogether and compute a hash of a bitboard representation fairly fast.

Code: Select all

// Assume bb[13] is an array that contains the bitboards
// corresponding to all possible contents of a square, including empty.

// Convert to a denser representation
a[0] = bb[1] ^ bb[3] ^ bb[5] ^ bb[7] ^ bb[9] ^ bb[11];
a[1] = bb[2] ^ bb[3] ^ bb[6] ^ bb[7] ^ bb[10] ^ bb[11]; 
a[2] = bb[4] ^ bb[5] ^ bb[6] ^ bb[7] ^ bb[12];
a[3] = bb[8] ^ bb[9] ^ bb[10] ^ bb[11] ^ bb[12];

// Compute a string-style hash of the denser representation
hash = 0;
for &#40;int i = 0; i < 4; ++i&#41;
    hash = rotate&#40;(&#40;hash + a&#91;i&#93;) ^ MAGIC_1&#41; * MAGIC_2, 32&#41;;

[Evert]

You could probably skip the Zobrist key altogether and compute a hash of a bitboard representation fairly fast.

Code: Select all

// Assume bb[13] is an array that contains the bitboards
// corresponding to all possible contents of a square, including empty.

// Convert to a denser representation
a[0] = bb[1] ^ bb[3] ^ bb[5] ^ bb[7] ^ bb[9] ^ bb[11];
a[1] = bb[2] ^ bb[3] ^ bb[6] ^ bb[7] ^ bb[10] ^ bb[11]; 
a[2] = bb[4] ^ bb[5] ^ bb[6] ^ bb[7] ^ bb[12];
a[3] = bb[8] ^ bb[9] ^ bb[10] ^ bb[11] ^ bb[12];

// Compute a string-style hash of the denser representation
hash = 0;
for &#40;int i = 0; i < 4; ++i&#41;
    hash = rotate&#40;(&#40;hash + a&#91;i&#93;) ^ MAGIC_1&#41; * MAGIC_2, 32&#41;;

Maybe, but that's quite a bit of code. I'm not sure that'll be faster, even with reducing cache pressure (remember, I'm not saying I measured that as a bottle-neck, but I wonder if there's a viable alternative to even test that).

Anyway, the use-case is not for a bitboard engine with 6 piece types, but for a mailbox engine with some 24 piece types.

[Evert]

That's interesting and I think it might be doable.
I would probably go for something like (feature_index ^ magic1)*magic2 (assuming 64-bit keys).
If it's not enough I'd try to add other ops, rotations are always nice
I'm pretty sure that it's possible to come up with something both fast and giving usable keys (some experimenting should probably do).

I've seen in practice that generating zobrist keys doesn't really require statistically good PRNGs.

That's what I was thinking.

I guess what I should do is come up with a generator and then test it both ways: grabbing the key from a table and on-the-fly calculation. Am I correct in thinking that magic1 and magic2 should be prime?

[Evert]

HaChu does that. It multiplies a piece key with a square key.

That's close-ish to what I was thinking, but I see it still gets those from tables, right? Of course the tables can be much smaller, so it may not be worth it to go for full calculation...

[mar]

I guess what I should do is come up with a generator and then test it both ways: grabbing the key from a table and on-the-fly calculation. Am I correct in thinking that magic1 and magic2 should be prime?

Yes, I always use primes for multiplicative keys.

[hgm]

You could probably skip the Zobrist key altogether and compute a hash of a bitboard representation fairly fast.

Code: Select all

// Assume bb[13] is an array that contains the bitboards
// corresponding to all possible contents of a square, including empty.

// Convert to a denser representation
a[0] = bb[1] ^ bb[3] ^ bb[5] ^ bb[7] ^ bb[9] ^ bb[11];
a[1] = bb[2] ^ bb[3] ^ bb[6] ^ bb[7] ^ bb[10] ^ bb[11]; 
a[2] = bb[4] ^ bb[5] ^ bb[6] ^ bb[7] ^ bb[12];
a[3] = bb[8] ^ bb[9] ^ bb[10] ^ bb[11] ^ bb[12];

// Compute a string-style hash of the denser representation
hash = 0;
for &#40;int i = 0; i < 4; ++i&#41;
    hash = rotate&#40;(&#40;hash + a&#91;i&#93;) ^ MAGIC_1&#41; * MAGIC_2, 32&#41;;

For calculating a key from scratch it could be competitive, but compared to incremental update of the hash key this is excruciatingly slow. Even just making the denser representation takes 13 memory loads and 19 XOR operations. The normal key update would just have 3 of each.

In HaChu I bias the piece and square keys to having more 1s in the LSB by initializing them to ~(random()*random()). This should make 75% of the keys end in 1. If you then multiply the piece and square key, 56% of them will end in a 1 bit.

HaChu was designed to handle >100 piece types on a board of 625 squares. Having a piece-square table of 62,500 8-byte Zobrist keys would be very expensive (1MB). Now I just have 100 4-bit sub-keys and 625 8-bit sub-keys, which is just 5,4KB, fitting comfortably in L1. I guess I could squeeze it further by having the 8-byte values overlap bytewise, then it would just be 1KB.

Aleks Peshkov seems to have tried a scheme for normal Chess where you had just 12 hash keys, one for each piece type, and then rotated those by the square number:

Zobrist(piece, square) = key[piece] << square | key[piece] >> 63-square;

For castling-rights keys or e.p. keys I usually just multiply the applicable variable by some randomly typed number. In micro-Max I add (stm + 128)*epSquare to the key, where stm = 0 or 16. (I guess I never bothered to work the castling rights into the key.)