On-the fly hash key generation?

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
Evert
Posts: 2920
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

On-the fly hash key generation?

Post by Evert » Tue Jan 12, 2016 9:11 am

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
Posts: 1937
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: On-the fly hash key generation?

Post by mar » Tue Jan 12, 2016 9:35 am

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.

User avatar
hgm
Posts: 23149
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: On-the fly hash key generation?

Post by hgm » Tue Jan 12, 2016 12:31 pm

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

Karlo Bala
Posts: 299
Joined: Wed Mar 22, 2006 9:17 am
Location: Novi Sad, Serbia

Re: On-the fly hash key generation?

Post by Karlo Bala » Tue Jan 12, 2016 2:31 pm

hgm wrote: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...
Best Regards,
Karlo Balla Jr.

AlvaroBegue
Posts: 916
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

Re: On-the fly hash key generation?

Post by AlvaroBegue » Tue Jan 12, 2016 6:36 pm

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;;

User avatar
Evert
Posts: 2920
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: On-the fly hash key generation?

Post by Evert » Tue Jan 12, 2016 7:00 pm

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

Code: Select all

// Assume bb&#91;13&#93; is an array that contains the bitboards
// corresponding to all possible contents of a square, including empty.

// Convert to a denser representation
a&#91;0&#93; = bb&#91;1&#93; ^ bb&#91;3&#93; ^ bb&#91;5&#93; ^ bb&#91;7&#93; ^ bb&#91;9&#93; ^ bb&#91;11&#93;;
a&#91;1&#93; = bb&#91;2&#93; ^ bb&#91;3&#93; ^ bb&#91;6&#93; ^ bb&#91;7&#93; ^ bb&#91;10&#93; ^ bb&#91;11&#93;; 
a&#91;2&#93; = bb&#91;4&#93; ^ bb&#91;5&#93; ^ bb&#91;6&#93; ^ bb&#91;7&#93; ^ bb&#91;12&#93;;
a&#91;3&#93; = bb&#91;8&#93; ^ bb&#91;9&#93; ^ bb&#91;10&#93; ^ bb&#91;11&#93; ^ bb&#91;12&#93;;

// 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.

User avatar
Evert
Posts: 2920
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: On-the fly hash key generation?

Post by Evert » Tue Jan 12, 2016 7:01 pm

mar wrote: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?

User avatar
Evert
Posts: 2920
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: On-the fly hash key generation?

Post by Evert » Tue Jan 12, 2016 7:03 pm

hgm wrote: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
Posts: 1937
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: On-the fly hash key generation?

Post by mar » Tue Jan 12, 2016 7:08 pm

Evert wrote: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.

User avatar
hgm
Posts: 23149
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: On-the fly hash key generation?

Post by hgm » Tue Jan 12, 2016 7:23 pm

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

Code: Select all

// Assume bb&#91;13&#93; is an array that contains the bitboards
// corresponding to all possible contents of a square, including empty.

// Convert to a denser representation
a&#91;0&#93; = bb&#91;1&#93; ^ bb&#91;3&#93; ^ bb&#91;5&#93; ^ bb&#91;7&#93; ^ bb&#91;9&#93; ^ bb&#91;11&#93;;
a&#91;1&#93; = bb&#91;2&#93; ^ bb&#91;3&#93; ^ bb&#91;6&#93; ^ bb&#91;7&#93; ^ bb&#91;10&#93; ^ bb&#91;11&#93;; 
a&#91;2&#93; = bb&#91;4&#93; ^ bb&#91;5&#93; ^ bb&#91;6&#93; ^ bb&#91;7&#93; ^ bb&#91;12&#93;;
a&#91;3&#93; = bb&#91;8&#93; ^ bb&#91;9&#93; ^ bb&#91;10&#93; ^ bb&#91;11&#93; ^ bb&#91;12&#93;;

// 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.)

Post Reply