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...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.
Zobrist alternative?
Moderator: Ras
-
- Posts: 4186
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Zobrist alternative?
-
- Posts: 4186
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Zobrist alternative?
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 ?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...
Please stop trolling or go away.
-
- Posts: 1822
- Joined: Thu Mar 09, 2006 11:54 pm
- Location: The Netherlands
Re: Zobrist alternative?
You responded to me:Daniel Shawul wrote: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...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.
"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.
-
- Posts: 4186
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Zobrist alternative?
Again I used addition for speed.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
-
- Posts: 1822
- Joined: Thu Mar 09, 2006 11:54 pm
- Location: The Netherlands
Re: Zobrist alternative?
You were laughing towards me. Even you posted a 'smile'.Daniel Shawul wrote:Again I used addition for speed.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
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.
-
- Posts: 4186
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Zobrist alternative?
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.
-
- Posts: 1822
- Joined: Thu Mar 09, 2006 11:54 pm
- Location: The Netherlands
Re: Zobrist alternative?
For the resulting key sure we XOR all the 'random numbers'.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.
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.
-
- Posts: 1822
- Joined: Thu Mar 09, 2006 11:54 pm
- Location: The Netherlands
Re: Zobrist alternative?
It was me who suggest that a combination using multiplication would work, yet would be too slow.Daniel Shawul wrote: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 ?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...
Please stop trolling or go away.
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.
-
- Posts: 5106
- Joined: Tue Apr 29, 2008 4:27 pm
Re: Zobrist alternative?
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.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:
versusCode: Select all
Zobrist = sq[f3] + piece[knight] | sq[g2] + piece[king]
In (modified to) MANY cases that generates the same Zobrist key.Code: Select all
Zobrist = sq[f3] + piece[king] | sq[g2] + piece[knight]
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
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.
-
- Posts: 4186
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Zobrist alternative?
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.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.