No Zobrist key

[AndrewGrant]

I've just realised that I've over looked castle rights / so square for my hashes. What's the process to add them in? A 64 length array of zorbist keys for ep, and 16length array of zorbist keys for castle rights?

[Daniel Anulliero]

I've just realised that I've over looked castle rights / so square for my hashes. What's the process to add them in? A 64 length array of zorbist keys for ep, and 16length array of zorbist keys for castle rights?

Yes Andrew (but in reality , 16 keys are sufficent for en passant moves) and 2 keys for the side to move too , but I think we are a little bit off topic of Mr Henk....

[Sven]

I've just realised that I've over looked castle rights / so square for my hashes. What's the process to add them in? A 64 length array of zorbist keys for ep, and 16length array of zorbist keys for castle rights?

16 zobrist keys for castling rights is ok. For ep target square 8 zobrist keys for the different files would be sufficient since the moving side is already part of the hash key (or it should be) and file + moving side uniquely identifies the ep target square (always on 6th resp. 3rd rank). However, you also need a 9th state for "no ep target square".

[Evert]

16 zobrist keys for castling rights is ok.

In fact, only 4 of those need to be linearly independent, of course (it is sufficient to xor in the applicable castling right key(s) if the move gives up castling rights).

For ep target square 8 zobrist keys for the different files would be sufficient since the moving side is already part of the hash key (or it should be) and file + moving side uniquely identifies the ep target square (always on 6th resp. 3rd rank). However, you also need a 9th state for "no ep target square".

Yes, but that can be taken to be 0.

[Sven]

For ep target square 8 zobrist keys for the different files would be sufficient since the moving side is already part of the hash key (or it should be) and file + moving side uniquely identifies the ep target square (always on 6th resp. 3rd rank). However, you also need a 9th state for "no ep target square".

Yes, but that can be taken to be 0.

Right, I just looked into my own code and saw that I use an array of 8 keys

[flok]

What about generating the zobrist keys?
I used to just get data from /dev/urandom as that's supposed to be very much random but for testing it is easier to have the same randoms each times so I took a different path: now I have a 64-bit starting value and then for each zobrist-key I calculate the md5 of it, throw away the upper 64 bit, use the lower 64 bit and use that as a value for the next md5 calculation. Yes, this is not cryptographically strong but it should be randomly enough, isn't it?

[Evert]

What about generating the zobrist keys?
I used to just get data from /dev/urandom as that's supposed to be very much random but for testing it is easier to have the same randoms each times so I took a different path: now I have a 64-bit starting value and then for each zobrist-key I calculate the md5 of it, throw away the upper 64 bit, use the lower 64 bit and use that as a value for the next md5 calculation. Yes, this is not cryptographically strong but it should be randomly enough, isn't it?

Why so complicated? Just pull the numbers you need from a pseudo-random number generator and call it a day.
Or even just use the fruit/polyglot ones if you're really lazy.

[flok]

What about generating the zobrist keys?
I used to just get data from /dev/urandom as that's supposed to be very much random but for testing it is easier to have the same randoms each times so I took a different path: now I have a 64-bit starting value and then for each zobrist-key I calculate the md5 of it, throw away the upper 64 bit, use the lower 64 bit and use that as a value for the next md5 calculation. Yes, this is not cryptographically strong but it should be randomly enough, isn't it?

Why so complicated? Just pull the numbers you need from a pseudo-random number generator and call it a day.
Or even just use the fruit/polyglot ones if you're really lazy.

Complicated? For me that's just the easiest way! I mean I don't have to make sure that the PRNG works ok and does what I expect. And regarding using other people's code: I try not to, then I won't have any licensing issues. So far I copied 1 line of code.

[Daniel Anulliero]

Mersenne twister is a good generator and they had 1000 64 bits numbers on the page (I can't find now)
I saved these numbers and put in my engine
Better to have the same code at each exécution

[Henk]

I use this key for hash table.

Code: Select all

 
        public Key(IChessBoardBits board)
        {
            rep = new ulong[SIZE];
            rep[0] = board.Pawns;
            rep[1] = board.Kings;
            rep[2] = board.Knights;
            rep[3] = board.Bishops;
            rep[4] = board.Rooks;
            rep[5] = board.Queens;
            rep[6] = board.WhitePieces;
            rep[7] = board.Other;
        }

        public bool Equals(Key key)
        {
            for &#40;int i = 0; i < SIZE; i++)
            &#123;
                if &#40;rep&#91;i&#93; != key&#91;i&#93;) return false;
            &#125;
            return true;
        &#125;

        

        public override int GetHashCode&#40;)
        &#123;
            int hash, i;
            for &#40;hash = i = 0; i < SIZE; ++i&#41;
            &#123;
                for &#40;int j = 0; j < 4; j++)
                &#123;
                    hash += &#40;int&#41;&#40;rep&#91;i&#93; >> &#40;j * 8&#41;);
                    hash += &#40;hash << 10&#41;;
                    hash ^= &#40;hash >> 6&#41;;
                &#125;
            &#125;
            hash += &#40;hash << 3&#41;;
            hash ^= &#40;hash >> 11&#41;;
            hash += &#40;hash << 15&#41;;
          
          
            return hash;
         &#125;

And I wonder if it does make my engine slow and if Zobrist key would be much better. But hash table is not used in qSearch.

[Don't ask how GetHashCode works for it's abracadabra to me now]

That's 32 memory accesses to rep (hopefully most from cache) plus 152 shifts (j * 8 is like j << 3), 80 "+=" and 40 "^=" operations, plus some loop control stuff. A lot of calculation, even if almost everything is done in registers, and it will certainly burn many CPU cycles. "Beware of nested loops" ...

Btw, where are the other properties of the position like side to move, castling rights, ep target square, that need to have an influence on the hash key?

I would ask some different questions first before asking about the performance: does this hash function distribute well over the whole index range (so your hash table will reach 100% "used" entries after some moves), and what is your collision rate?

Speed-wise it is clear that this way is slow since you always have to calculate the hash key from scratch while the Zobrist method allows to do that incrementally based on very few XORs. But if there are massive functional drawbacks then the speed argument would not matter any longer, of course ...

The distribution properties of the hash function could be analyzed by running a simulation where you allocate a table of N entries (N = your typical number of hash table entries) with 1 bit per entry (or, to save programming effort, one byte representing a bool), initialize the table to 0, generate many "realistic random positions" (more than N), calculate your hash function for each position, take its index bits as indicated by N, and set table[index] to 1. Then count how often you store a "1" where you already had a "1" before, and how many entries remain at "0" in the end.

Code: Select all

        public override int GetHashCode()
        {
            int hash = 0;
            for &#40;int i = 0; i < SIZE-1; i++)
            &#123;
                hash += &#40;int&#41;&#40;rep&#91;i&#93; % 13&#41;;
                hash = &#40;hash << 4&#41;;
               
            &#125;
            hash += &#40;int&#41;&#40;rep&#91;SIZE-1&#93; % 13&#41;;


            return hash;
        &#125;

Maybe this is better. At least I understand it. Collecting 8 times four bits because hash code must be 32 bits. Largest prime for four bits is 13.