No Zobrist key

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Henk
Posts: 5514
Joined: Mon May 27, 2013 8:31 am

No Zobrist key

Post by Henk » Mon Sep 26, 2016 9:57 am

My chess engine doesn't use Zobrist key but instead it uses the total bitboard representation of a position. That is 8 x 64 bits.

I wonder if it is important to change that. Would my engine run much faster using Zobrist key ?

D Sceviour
Posts: 401
Joined: Mon Jul 20, 2015 3:06 pm
Contact:

Re: No Zobrist key

Post by D Sceviour » Mon Sep 26, 2016 12:16 pm

Henk wrote:My chess engine doesn't use Zobrist key but instead it uses the total bitboard representation of a position. That is 8 x 64 bits.
How to you define the board with 8? Would it not be 12 x 64, one bitboard for each piece type?

Daniel Anulliero
Posts: 663
Joined: Fri Jan 04, 2013 3:55 pm
Location: Nice

Re: No Zobrist key

Post by Daniel Anulliero » Mon Sep 26, 2016 12:25 pm

D Sceviour wrote:
Henk wrote:My chess engine doesn't use Zobrist key but instead it uses the total bitboard representation of a position. That is 8 x 64 bits.
How to you define the board with 8? Would it not be 12 x 64, one bitboard for each piece type?
Yes seems he just forgot the color of pieces , just a small "newbie" détail lol

Sven
Posts: 3758
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: No Zobrist key

Post by Sven » Mon Sep 26, 2016 12:41 pm

Daniel Anulliero wrote:
D Sceviour wrote:
Henk wrote:My chess engine doesn't use Zobrist key but instead it uses the total bitboard representation of a position. That is 8 x 64 bits.
How to you define the board with 8? Would it not be 12 x 64, one bitboard for each piece type?
Yes seems he just forgot the color of pieces , just a small "newbie" détail lol
Sorry Dennis and Daniel but 8 bitboards are sufficient if you use 6 for the piece types and 2 for the colors. It is also slightly more efficient since all these bitboards fit into one cache line and testing only for the color of a piece on a given square does not require OR-ing of 6 bitboards. Of course it is also a matter of your piece encoding.

Daniel Anulliero
Posts: 663
Joined: Fri Jan 04, 2013 3:55 pm
Location: Nice

Re: No Zobrist key

Post by Daniel Anulliero » Mon Sep 26, 2016 12:52 pm

Sven Schüle wrote:
Daniel Anulliero wrote:
D Sceviour wrote:
Henk wrote:My chess engine doesn't use Zobrist key but instead it uses the total bitboard representation of a position. That is 8 x 64 bits.
How to you define the board with 8? Would it not be 12 x 64, one bitboard for each piece type?
Yes seems he just forgot the color of pieces , just a small "newbie" détail lol
Sorry Dennis and Daniel but 8 bitboards are sufficient if you use 6 for the piece types and 2 for the colors. It is also slightly more efficient since all these bitboards fit into one cache line and testing only for the color of a piece on a given square does not require OR-ing of 6 bitboards. Of course it is also a matter of your piece encoding.
Ah ok sorry, didn't think about that lol seems I'm really à newbie :wink:
But would it be much slower than zobrist in term of access ?

Sven
Posts: 3758
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: No Zobrist key

Post by Sven » Mon Sep 26, 2016 1:11 pm

Daniel Anulliero wrote:
Sven Schüle wrote:
Daniel Anulliero wrote:
D Sceviour wrote:
Henk wrote:My chess engine doesn't use Zobrist key but instead it uses the total bitboard representation of a position. That is 8 x 64 bits.
How to you define the board with 8? Would it not be 12 x 64, one bitboard for each piece type?
Yes seems he just forgot the color of pieces , just a small "newbie" détail lol
Sorry Dennis and Daniel but 8 bitboards are sufficient if you use 6 for the piece types and 2 for the colors. It is also slightly more efficient since all these bitboards fit into one cache line and testing only for the color of a piece on a given square does not require OR-ing of 6 bitboards. Of course it is also a matter of your piece encoding.
Ah ok sorry, didn't think about that lol seems I'm really à newbie :wink:
But would it be much slower than zobrist in term of access ?
I did not understand exactly what Henk does. If he uses 8 x 64 = 512 bits as a hash key for TT access then I don't know how this should be working. So maybe he means that he uses 512 instead of 64 bits to compare two positions, e.g. for repetition detection. That may be ok, if this is slower at all then you won't notice it much, I think, since repetition detection is done once per node and for few positions on average.

ZirconiumX
Posts: 1327
Joined: Sun Jul 17, 2011 9:14 am

Re: No Zobrist key

Post by ZirconiumX » Mon Sep 26, 2016 1:20 pm

As Gerd Isenberg and Fabio Gabbato will tell you: 4 is as dense as possible. You store a single colour bitboard (usually for the side to move, but it depends), and three other bitboards for various combinations of pieces. Then the single piece types can be obtained by ANDing and NOTs and necessary.

Whether this extra computation outweighs the fewer memory accesses is up for debate, though these bitboards can be fairly trivially flipped after each move to implement colour-agnostic move generation.
Some believe in the almighty dollar.

I believe in the almighty printf statement.

Henk
Posts: 5514
Joined: Mon May 27, 2013 8:31 am

Re: No Zobrist key

Post by Henk » Mon Sep 26, 2016 1:24 pm

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]

Sven
Posts: 3758
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: No Zobrist key

Post by Sven » Mon Sep 26, 2016 2:21 pm

Henk wrote:I use this key for hash table.

Code: Select all

 
        public Key&#40;IChessBoardBits board&#41;
        &#123;
            rep = new ulong&#91;SIZE&#93;;
            rep&#91;0&#93; = board.Pawns;
            rep&#91;1&#93; = board.Kings;
            rep&#91;2&#93; = board.Knights;
            rep&#91;3&#93; = board.Bishops;
            rep&#91;4&#93; = board.Rooks;
            rep&#91;5&#93; = board.Queens;
            rep&#91;6&#93; = board.WhitePieces;
            rep&#91;7&#93; = board.Other;
        &#125;

        public bool Equals&#40;Key key&#41;
        &#123;
            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.

Henk
Posts: 5514
Joined: Mon May 27, 2013 8:31 am

Re: No Zobrist key

Post by Henk » Mon Sep 26, 2016 2:50 pm

Properties side to move, castling rights, ep target square are stored in

Code: Select all

rep&#91;7&#93; = board.Other;
If you know a much simpler and still effective formula to compute a hash key then that would be better. For I don't like mystic code. Might be I found it somewhere on internet. Can't remember.

Post Reply