Zobrist alternative?

Discussion of chess software programming and technical issues.

Moderator: Ras

Daniel Shawul
Posts: 4186
Joined: Tue Mar 14, 2006 11:34 am
Location: Ethiopia

Re: Zobrist alternative?

Post by Daniel Shawul »

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.
Did you read the code I posted?? I used XOR not OR. XOR and add work fine as far as I can see. You on the other hand used an OR and complained about hash collisions...
Daniel Shawul
Posts: 4186
Joined: Tue Mar 14, 2006 11:34 am
Location: Ethiopia

Re: Zobrist alternative?

Post by Daniel Shawul »

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...
You are trolling now ... Multiplication works fine but only questioned the quality of the keys as the low order bits contain too many zeros. So does the higher bits as I have shown with 10 million trials. I thought that was interesting and suggested "addition" to cure just that. Whats the problem now ?
Please stop trolling or go away.
diep
Posts: 1822
Joined: Thu Mar 09, 2006 11:54 pm
Location: The Netherlands

Re: Zobrist alternative?

Post by diep »

Daniel Shawul wrote:
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.
Did you read the code I posted?? I used XOR not OR. XOR and add work fine as far as I can see. You on the other hand used an OR and complained about hash collisions...
You responded to me:

"I didn't. HGM did use separate tables for piece and sq saving significantly on table size and used multiplication as well. But I suggested addition, try and beat that Smile As Don explained, we are now trying to avoid table look ups all in all, as the matter is settled..."

So you say only "addition" no nothing about XOR.

Don quotes the same thing also only 'addition'.
No nothing about XOR or any other instruction other than addition.

Just 'addition' is what you and Don mentionned in a reply to me.
Please read carefully what you write.
Daniel Shawul
Posts: 4186
Joined: Tue Mar 14, 2006 11:34 am
Location: Ethiopia

Re: Zobrist alternative?

Post by Daniel Shawul »

ust 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
Again I used addition for speed.
diep
Posts: 1822
Joined: Thu Mar 09, 2006 11:54 pm
Location: The Netherlands

Re: Zobrist alternative?

Post by diep »

Daniel Shawul wrote:
ust 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
Again I used addition for speed.
You were laughing towards me. Even you posted a 'smile'.
As for a few minutes you thought you could beat the combination of
rotation with addition with just addition.

Don acked you in that.
Also explicitly mentions only addition.

That's 2 of you.

Fact is what i posted is about a 5x faster than what you showed up with.

p.s. it's good habit to remove the 'you are so dumb' you initially posted.
Daniel Shawul
Posts: 4186
Joined: Tue Mar 14, 2006 11:34 am
Location: Ethiopia

Re: Zobrist alternative?

Post by Daniel Shawul »

The XOR of piece_on_square hash keys is implied as zobrist hashing is being used. You can even reverse the roles and use XOR and ADD for combining piece_and_square and assembling the final hash keys. You should know I use an ADD to hash holdings for crazy house. Because there you can't xor since that will nullify the key when two pieces of the same color are in holding. Your "method" is still going to use zobrist hashing in the end so it will have XOR in the end.
diep
Posts: 1822
Joined: Thu Mar 09, 2006 11:54 pm
Location: The Netherlands

Re: Zobrist alternative?

Post by diep »

Daniel Shawul wrote:The XOR of piece_on_square hash keys is implied as zobrist hashing is being used. You can even reverse the roles and use XOR and ADD for combining piece_and_square and assembling the final hash keys. You should know I use an ADD to hash holdings for crazy house. Because there you can't xor since that will nullify the key when two pieces of the same color are in holding. Your "method" is still going to use zobrist hashing in the end so it will have XOR in the end.
For the resulting key sure we XOR all the 'random numbers'.
We were busy designing a function to quickly generate those 'random numbers' to keep within L1 cache using a game on a pretty big board with a huge amount of pieces.

The fastest proposal i've seen so far is doing 2 rotations and an addition as i posted.
diep
Posts: 1822
Joined: Thu Mar 09, 2006 11:54 pm
Location: The Netherlands

Re: Zobrist alternative?

Post by diep »

Daniel Shawul wrote:
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...
You are trolling now ... Multiplication works fine but only questioned the quality of the keys as the low order bits contain too many zeros. So does the higher bits as I have shown with 10 million trials. I thought that was interesting and suggested "addition" to cure just that. Whats the problem now ?
Please stop trolling or go away.
It was me who suggest that a combination using multiplication would work, yet would be too slow.

Throughput latency, we aren't even looking to total latency, of multiplication is 3.75 clocks at intel cpu's.

Therefore the proposal to use what RanRot is using to generate random numbers, namely a combination of 2 rotations with 1 addition, that's a lot faster than doing a multiplication.

Accusing me of trolling is not a good habit.
User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 4:27 pm

Re: Zobrist alternative?

Post by Don »

diep wrote: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
We xor for the normal zobrist function but addition for computing a key to use for a color/piece/square combination. At least that is what someone in an early post recommends and claims is strong. I cannot vouch for that but it could very well be good.

For the sake of this discussion let's use the terminology "piece" to represent the piece exactly including the color of the piece. In other words "white pawn" is distinct from "black pawn."

So let's say we are doing this for chess. To compute incremental zobrist for a simple knight move (using xor for incremental updates but addition for computing the key to work with) we have this:

Assume Nf1-g3 - no capture:

signature = signature ^ (ptab[wn] + sqtab[f1]); // downdate
signature = signature ^ (ptab[wn] + sqtab[f3]); // update

ptab[] is a table of random numbers for each piece and sqtab[] is a table of random numbers for each square. For chess, dimensions might be ptab[12] and sqtab[64].

Don
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.
Daniel Shawul
Posts: 4186
Joined: Tue Mar 14, 2006 11:34 am
Location: Ethiopia

Re: Zobrist alternative?

Post by Daniel Shawul »

It was me who suggest that a combination using multiplication would work, yet would be too slow.
No. You haven't even started posting by that time (fact!). I suggested addition over multiplication after doing some bit frequency tests. Go ahead check the post on the first page. Actually addition has two fold advantages as that also keeps the uniform distribution.
Throughput latency, we aren't even looking to total latency, of multiplication is 3.75 clocks at intel cpu's.

Therefore the proposal to use what RanRot is using to generate random numbers, namely a combination of 2 rotations with 1 addition, that's a lot faster than doing a multiplication.

Accusing me of trolling is not a good habit.