Zobrist alternative?

Discussion of chess software programming and technical issues.

Moderator: Ras

diep
Posts: 1822
Joined: Thu Mar 09, 2006 11:54 pm
Location: The Netherlands

Re: Zobrist alternative?

Post by diep »

Don wrote:
diep wrote:
Daniel Shawul wrote:Hi Vincent
We can't use a look up table for sq and piece since we are trying to avoid that. Rotation of a magic number was a substitute for that in this case. This will probably be not a good cryptographic hash but for zobrist might work since xor changes the hash key based on adjacent bits. The problem is that there are too many squares 1200 so we need a many majic numbers. But the rotation reduces tables size by 64 times. This is mentioned somewhere in this thread to reduce tables size, but can it be used to completely avoid it? I will see what can be used from RanRot for this purpose.
Thanks
Hi, just try it.
You missed the point. We have already discussed using two small tables and have concluded that adding them together might work just fine. Then it was suggested that might find a way to completely avoid any table lookups and wondered if there was a fast way to do that. Not because we don't think we should, but because we wondered if we could.

I'm rotating the sq random number by a small prime lookuped for piece and vice versa. Maybe you missed this detail.

And then we add up this after 2 rotations.

So effectively we're having a bitresult of a multiplication in a field.

HGM wanted to avoid 5MB lookup to generate his Zobrist key and this definitely does with such tiny lookup tables of just a few kilobyte :)

HGM wanted to avoid lookup of a double array, not single array.

double array is [piece][sq]
this is however single lookups of just [piece] and [sq]
We CAN use looking up piece and sq in a table,
we just can't afford a table sized sq * piece, that's all :)

Bottomline is that what i posted here is factors faster than the multiplication you proposed.

As the lookups probably can get prefetched what i posted is under 2 clocks and will keep just 3 execution units busy for 1 cycle :)

So throughput latency is 1 cycle, not counting the prefetch of the L1.

What you posted is maybe 5 cycles throughput or so?
The original question was a caching question to not get outside of the L1. Focus upon that. Changing the discussion is not what wise men would do.

Using multiplication then and smaller tables isn't very clever, as todays cpu's have magnificent caches, so the multiplication will just slow it down too much as it's 5 times slower or so than using small lookup tables.
diep
Posts: 1822
Joined: Thu Mar 09, 2006 11:54 pm
Location: The Netherlands

Re: Zobrist alternative?

Post by diep »

Daniel Shawul wrote:"we changed the discussion"
As i hardly have time to check the forum,
changing the discussion is not very clever.

Finding a fast hashfunction using small tables IS however an interesting
topic in itself.

Multiplication is too slow simply.

It's interesting though to test for chess whether addition works
as a stand alone manner.

it would require a table
HashKey lookupPIECE[2][6]; // not speed optimized
HashKey lookupSQUARE[2][64];

Getting 'rid' of the side to move seems not so clever for now.

However in Diep i'm using 128 bits, so i could just flip the 2 random numbers as my hashkey has a .hi and a .lo each of 64 bits and i
can flip those.

And get away with it. Yet i realize in my MakeMove i have a generic makemove. So nowadays i didn't write it out for black and white, as a big problem for Diep is the L1i missrate of around a 1.34% going up to 1.6%
which is a lot.

The L1d really is a far smaller issue and at 0.6% from which 0.5% goes to the hashtable it's a non issue really as the max we can optimize for there is 0.1%. That's not an issue.

So the hashfunction i would not favour for now as reducing codesize is more important than table size.

In my experiments with a sieve, it turned out that when the random lookups are within L1d and the 'streaming' within the L2+L3 that things still is really fast.

Streaming for a primebase that keeps within L2+L3 really is not a problem there. Prefetching helps that.

that's here the case as well: codesize and time to execute the code is of crucial interest. So forget doing any multiplications.
diep
Posts: 1822
Joined: Thu Mar 09, 2006 11:54 pm
Location: The Netherlands

Re: Zobrist alternative?

Post by diep »

The problem i foresee with addition is basically this:

suppose we have a position with a knight on f3 and a king on g2.
Versus the position with a knight on g2 and a king on f3

Now we do this:

Code: Select all

Zobrist = sq[f3] + piece[knight] | sq[g2] + piece[king]
versus

Code: Select all

         Zobrist = sq[f3] + piece[king] | sq[g2] + piece[knight]
 
In (modified to) MANY cases that generates the same Zobrist key.
I don't feel this is a safe key generation function.

So just addition won't work. We need to shift/rotate as well.

Vincent
diep
Posts: 1822
Joined: Thu Mar 09, 2006 11:54 pm
Location: The Netherlands

Re: Zobrist alternative?

Post by diep »

i think most importantly :

Code: Select all

Zobrist = (sq[f3] + piece[knight]) | (sq[g2] + piece[king])

or

(a+b) | (c+d) 
versus

Code: Select all

Zobrist = (sq[f3] + piece[king]) |  sq[g2] + piece[knight])

or

(a+d) | (c+b)
Even if you manage to get unique numbers, you'll get massive chaining.

Let's look just to the last 2 bits and write it down for first few cases
then let computer calculate it:

Code: Select all

a       b     c    d     x1   x2   collission?
00     00   00   00   00   00   YES
01     00   00   00   01   01   YES
.....
Massive amounts of collissions, i don't even need to start writing further.
Daniel Shawul
Posts: 4186
Joined: Tue Mar 14, 2006 11:34 am
Location: Ethiopia

Re: Zobrist alternative?

Post by Daniel Shawul »

No vincent. I refer to you the very first posts I made in the first page. I literally begged for attention since I thought addition is a fast and also preserving the uniform distribution which avoids hash table clustering...

Code: Select all

key(piece,square) = key1[piece] + key2[square];
Then normal zobrist

Code: Select all

key(p1,sq1) ^ key(p2,sq2) ^ key(p3,sq3) ...
Here is my "golden" post specially for you ;)
From the available operations, those that sustain uniform distribution of bits are : add , sub , xor. The rest i.e mul, div,and,or all change the distribution in some way. So a hash table constructed with the latter operators will show some clustering unlike those that maintain uniform distribution. Why not mix the first group of operators (say add and xor ) to get a key like this : key = key1[piece] + key2[square] and then use xor to form the final key for the position. I am not sure if add and xor are "dependent" somehow so this may not work. For example, if I just used an add for all operations, then a position like : Bishop at d4 Pawn at c3 will be equivalent to Bishop at c3 and Pawn at d4... An xor for the final hash key will solve this problem, but I am not sure. Anyway I just wanted to clearly describe what the problem is ..
diep
Posts: 1822
Joined: Thu Mar 09, 2006 11:54 pm
Location: The Netherlands

Re: Zobrist alternative?

Post by diep »

Daniel Shawul wrote:No vincent. I refer to you the very first posts I made in the first page. I literally begged for attention since I thought addition is a fast and also preserving the uniform distribution which avoids hash table clustering...

Code: Select all

key(piece,square) = key1[piece] + key2[square];
Then normal zobrist

Code: Select all

key(p1,sq1) ^ key(p2,sq2) ^ key(p3,sq3) ...
XOR of random numbers is strong.

Generating those random numbers using addition
is generating too many collisions simply.

It will cause your zobrist key to have the effective strength of something much smaller. More like square root of it, so a 64 bits key will be having
effective strength of 32 bits.

Addition and OR is too similar to each other. You need some rotation/shifting as well and NOT multiplication as that's too slow simply.

Your golden post is a beginnersstatement basically as you want to combine add with or.

Stronger is combining + with rotating.
Last edited by diep on Sat Jun 16, 2012 4:12 pm, edited 1 time in total.
Daniel Shawul
Posts: 4186
Joined: Tue Mar 14, 2006 11:34 am
Location: Ethiopia

Re: Zobrist alternative?

Post by Daniel Shawul »

diep wrote:
Daniel Shawul wrote:"we changed the discussion"
As i hardly have time to check the forum,
changing the discussion is not very clever.
You basically quoted something I didn't say (straw man) and then argued with yourself. The discussion is not changed more like refined since we already thought the part with reduced table sizes was over. We are not responsible for keeping you up to date ..
diep
Posts: 1822
Joined: Thu Mar 09, 2006 11:54 pm
Location: The Netherlands

Re: Zobrist alternative?

Post by diep »

Daniel Shawul wrote:
diep wrote:
Daniel Shawul wrote:"we changed the discussion"
As i hardly have time to check the forum,
changing the discussion is not very clever.
You basically quoted something I didn't say (straw man) and then argued with yourself. The discussion is not changed more like refined since we already thought the part with reduced table sizes was over. We are not responsible for keeping you up to date ..
Just an addition won't work.

You didn't solve the problem at all.
Instead as usual you focussed upon a slow multiplication :)

Furthermore you didn't move on as well, as reducing table size was not the original question. Speed is :)
diep
Posts: 1822
Joined: Thu Mar 09, 2006 11:54 pm
Location: The Netherlands

Re: Zobrist alternative?

Post by diep »

i conclude all of you guys simply did NOT show up with anything workable that's fast.

Only something with a slow multiplication, which you initially rejected as being not safe.

So until then i designed something that's 5x faster than what you showed up with.
diep
Posts: 1822
Joined: Thu Mar 09, 2006 11:54 pm
Location: The Netherlands

Re: Zobrist alternative?

Post by diep »

You missed the point. We have already discussed using two small tables and have concluded that adding them together might work just fine.
Don,
Just an addition doesn't work.
In fact if you read well you'll see that Shawul didn't believe initially a multiplication would work...
Last edited by diep on Sat Jun 16, 2012 4:22 pm, edited 1 time in total.