I was wondering if someone tried this:
http://www.scribd.com/doc/16300302/Alqr ... of-hashing
I would say my results are inconsistent.
Alqrainys Hash Function
Moderators: hgm, Rebel, chrisw
-
- Posts: 454
- Joined: Sat Apr 04, 2009 6:44 pm
- Location: Bulgaria
-
- Posts: 1922
- Joined: Thu Mar 09, 2006 12:51 am
- Location: Earth
Re: Alqrainys Hash Function
100% useless. Not just for chess, for anything.
-
- Posts: 12540
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Re: Alqrainys Hash Function
The functions he compares "Alqrainy's Hash Function" to are literally pathetic.xcomponent wrote:I was wondering if someone tried this:
http://www.scribd.com/doc/16300302/Alqr ... of-hashing
I would say my results are inconsistent.
For chess, you want to use Zobrist hashing because it is incremental. But if you want to try something else, you should use a hash function that is:
1. Good
2. Fast.
All the functions in his paper are fast. None of them are good.
Hash function discussions:
http://burtleburtle.net/bob/hash/index.html
http://www.eternallyconfuzzled.com/tuts ... table.aspx
http://www.eternallyconfuzzled.com/tuts ... shing.aspx
http://www.azillionmonkeys.com/qed/hash.html
http://www.partow.net/programming/hashfunctions/
http://murmurhash.googlepages.com/
Important:
You do *not* want a cryptographic hash for chess, unless it is one of the fast 64 bit varieties like UMAC (and even then, Zobrist is better).
While cryptographic hashes will have superior collision rates, the cost of calculation is very high.
-
- Posts: 454
- Joined: Sat Apr 04, 2009 6:44 pm
- Location: Bulgaria
Re: Alqrainys Hash Function
This was not about me or do i need to use Zobrist hashing, Dann.
I was just curious if someone tried this particular one. That's all.
Zach's opinion just confirmed my initial doubts. Thanks for your replys.
I was just curious if someone tried this particular one. That's all.
Zach's opinion just confirmed my initial doubts. Thanks for your replys.
-
- Posts: 27792
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Alqrainys Hash Function
The standard Zobrist scheme is very much based on the occupation numbers of squares being 0 or 1 (by XORing the keys). Putting a second piece on the same square makes the square undistinguishable from empty.
This is easily remedied by adding the keys, rater than XORing them. My engines have always used such an additive key, and I never discovered any adverse effects. Of course for Chess you don't really need this, but for Crazyhouse you already need it in the holdings (where you can have two pieces of the same type).
You of course lose the property that the code for restoring the old value is the same as for the update, (you now would have to subtract in stead of add), but this is of no practical importance s the copy-modify method for managing the hash key is twice as fast as the update-undo. (You don't need to undo and the update makes the copy for free, as it is done in the registers, and it does not matter wheter you store it back in the same or a different memory location before you enter the recursion.)
This is easily remedied by adding the keys, rater than XORing them. My engines have always used such an additive key, and I never discovered any adverse effects. Of course for Chess you don't really need this, but for Crazyhouse you already need it in the holdings (where you can have two pieces of the same type).
You of course lose the property that the code for restoring the old value is the same as for the update, (you now would have to subtract in stead of add), but this is of no practical importance s the copy-modify method for managing the hash key is twice as fast as the update-undo. (You don't need to undo and the update makes the copy for free, as it is done in the registers, and it does not matter wheter you store it back in the same or a different memory location before you enter the recursion.)
-
- Posts: 1922
- Joined: Thu Mar 09, 2006 12:51 am
- Location: Earth
Re: Alqrainys Hash Function
For crazyhouse, instead of hashing pieces individually, you could hash by piece count. So when you get a new holding you update by zobrist[piece][oldcount] ^ zobrist[piece][newcount].
Also, the "paper" didn't have anything to do with the actual hashkey generation, but rather how you index the hashtable given a generation. There's the obvious key%size method, and then the Alqrainy's method, which basically just rotates the keys through the index space by 3/7. I'm amazed that anyone would think that would make a difference.
Also, the "paper" didn't have anything to do with the actual hashkey generation, but rather how you index the hashtable given a generation. There's the obvious key%size method, and then the Alqrainy's method, which basically just rotates the keys through the index space by 3/7. I'm amazed that anyone would think that would make a difference.
-
- Posts: 27792
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Alqrainys Hash Function
You could, but it is much simpler to just add zobrist[piece][HOLDINGS].Zach Wegner wrote:For crazyhouse, instead of hashing pieces individually, you could hash by piece count. So when you get a new holding you update by zobrist[piece][oldcount] ^ zobrist[piece][newcount].
-
- Posts: 454
- Joined: Sat Apr 04, 2009 6:44 pm
- Location: Bulgaria
Re: Alqrainys Hash Function
Exactly. Nobody is talking about Replacing the Zobrist hashing at all. It is all about the "hash function" (indexing method) itself!Zach Wegner wrote: Also, the "paper" didn't have anything to do with the actual hashkey generation, but rather how you index the hashtable given a generation. There's the obvious key%size method, and then the Alqrainy's method, which basically just rotates the keys through the index space by 3/7. I'm amazed that anyone would think that would make a difference.
I.E. Instead of "by division", to use something like:
#define HINDEX ((key + (tt_numentry * 3) / 7) % tt_numentry)
And I think Zach is absolutely right, at least from the tests I've made just of curiosity.